typedef std::multimap<std::string, FGPositioned*> NamedPositionedIndex;
typedef std::pair<NamedPositionedIndex::const_iterator, NamedPositionedIndex::const_iterator> NamedIndexRange;
+using std::lower_bound;
+using std::upper_bound;
+
/**
* Order positioned elements by type, then pointer address. This allows us to
* use range searches (lower_ and upper_bound) to grab items of a particular
}
};
+class LowerLimitOfType
+{
+public:
+ bool operator()(const FGPositioned* a, const FGPositioned::Type b) const
+ {
+ return a->type() < b;
+ }
+
+ bool operator()(const FGPositioned::Type a, const FGPositioned* b) const
+ {
+ return a < b->type();
+ }
+
+ // The operator below is required by VS2005 in debug mode
+ bool operator()(const FGPositioned* a, const FGPositioned* b) const
+ {
+ return a->type() < b->type();
+ }
+};
+
+
typedef std::set<FGPositioned*, OrderByType> BucketEntry;
typedef std::map<long int, BucketEntry> SpatialPositionedIndex;
return;
}
+ if (aFilter->hasTypeRange()) {
+ // avoid many calls to the filter hook
+ l = lower_bound(it->second.begin(), it->second.end(), aFilter->minType(), LowerLimitOfType());
+ u = upper_bound(l, it->second.end(), aFilter->maxType(), LowerLimitOfType());
+ }
+
for ( ; l != u; ++l) {
if ((*aFilter)(*l)) {
aResult.push_back(*l);
} // of i-iteration
}
-/*
-class LowerLimitOfType
-{
-public:
- bool operator()(const FGPositioned* a, const FGPositioned::Type b) const
- {
- return a->type() < b;
- }
-
- bool operator()(const FGPositioned::Type a, const FGPositioned* b) const
- {
- return a < b->type();
- }
-};
-
-
-static void
-spatialFindTyped(const SGGeod& aPos, double aRange, FGPositioned::Type aLower, FGPositioned::Type aUpper, FGPositioned::List& aResult)
-{
- SGBucket buck(aPos);
- double lat = aPos.getLatitudeDeg(),
- lon = aPos.getLongitudeDeg();
-
- int bx = (int)( aRange*SG_NM_TO_METER / buck.get_width_m() / 2);
- int by = (int)( aRange*SG_NM_TO_METER / buck.get_height_m() / 2 );
-
- // loop over bucket range
- for ( int i=-bx; i<=bx; i++) {
- for ( int j=-by; j<=by; j++) {
- buck = sgBucketOffset(lon, lat, i, j);
-
- SpatialPositionedIndex::const_iterator it;
- it = global_spatialIndex.find(buck.gen_index());
- if (it == global_spatialIndex.end()) {
- continue;
- }
-
- BucketEntry::const_iterator l = std::lower_bound(it->second.begin(), it->second.end(), aLower, LowerLimitOfType());
- BucketEntry::const_iterator u = std::upper_bound(l, it->second.end(), aUpper, LowerLimitOfType());
-
- for ( ; l != u; ++l) {
- aResult.push_back(*l);
- }
-
- } // of j-iteration
- } // of i-iteration
-}
-*/
-
/**
*/
class RangePredictate
// sequential iterators, not random-access ones
NamedPositionedIndex::const_iterator check = range.first;
if (++check == range.second) {
- // excellent, only one match in the range - all we care about is the type
- if (aFilter && !aFilter->pass(range.first->second)) {
- return NULL; // type check failed
- }
-
- return range.first->second;
+ // excellent, only one match in the range
+ FGPositioned* r = range.first->second;
+ if (aFilter) {
+ if (aFilter->hasTypeRange() && !aFilter->passType(r->type())) {
+ return NULL;
+ }
+
+ if (!aFilter->pass(r)) {
+ return NULL;
+ }
+ } // of have a filter
+
+ return r;
} // of short-circuit logic for single-element range
// multiple matches, we need to actually check the distance to each one
SGVec3d cartOrigin(SGVec3d::fromGeod(aOrigin));
for (; it != range.second; ++it) {
- if (aFilter && !aFilter->pass(range.first->second)) {
- continue;
+ FGPositioned* r = it->second;
+ if (aFilter) {
+ if (aFilter->hasTypeRange() && !aFilter->passType(r->type())) {
+ continue;
+ }
+
+ if (!aFilter->pass(r)) {
+ continue;
+ }
}
// find distance
- double d2 = distSqr(cartOrigin, it->second->cart());
+ double d2 = distSqr(cartOrigin, r->cart());
if (d2 < minDist) {
minDist = d2;
- result = it->second;
+ result = r;
}
}
///////////////////////////////////////////////////////////////////////////////
+bool
+FGPositioned::Filter::hasTypeRange() const
+{
+ assert(minType() <= maxType());
+ return (minType() != INVALID) && (maxType() != INVALID);
+}
+
+bool
+FGPositioned::Filter::passType(Type aTy) const
+{
+ assert(hasTypeRange());
+ return (minType() <= aTy) && (maxType() >= aTy);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
FGPositioned::FGPositioned(Type ty, const std::string& aIdent, const SGGeod& aPos, bool aIndexed) :
mType(ty),
mPosition(aPos),
SGReferenced::get(this); // hold an owning ref, for the moment
if (aIndexed) {
- assert(ty != TAXIWAY);
+ assert(ty != TAXIWAY && ty != PAVEMENT);
addToIndices(this);
}
}
switch (aTy) {
case RUNWAY: return "runway";
case TAXIWAY: return "taxiway";
+ case PAVEMENT: return "pavement";
case PARK_STAND: return "parking stand";
case FIX: return "fix";
case VOR: return "VOR";
return spatialGetClosest(aPos, aN, aCutoffNm, aFilter);
}
+/*
FGPositionedRef
FGPositioned::findNextWithPartialId(FGPositionedRef aCur, const std::string& aId, Filter* aFilter)
{
continue;
}
- if (aFilter && !aFilter->pass(candidate)) {
- continue;
+ if (aFilter) {
+ if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
+ continue;
+ }
+
+ if(!aFilter->pass(candidate)) {
+ continue;
+ }
}
if (!aCur) {
}
return NULL; // fell out, no match in range
+}*/
+
+FGPositionedRef
+FGPositioned::findNextWithPartialId(FGPositionedRef aCur, const std::string& aId, Filter* aFilter)
+{
+ // It is essential to bound our search, to avoid iterating all the way to the end of the database.
+ // Do this by generating a second ID with the final character incremented by 1.
+ // e.g., if the partial ID is "KI", we wish to search "KIxxx" but not "KJ".
+ std::string upperBoundId = aId;
+ upperBoundId[upperBoundId.size()-1]++;
+ NamedPositionedIndex::const_iterator upperBound = global_namedIndex.lower_bound(upperBoundId);
+
+ NamedIndexRange range = global_namedIndex.equal_range(aId);
+ while (range.first != upperBound) {
+ for (; range.first != range.second; ++range.first) {
+ FGPositionedRef candidate = range.first->second;
+ if (aCur == candidate) {
+ aCur = NULL; // found our start point, next match will pass
+ continue;
+ }
+
+ if (aFilter) {
+ if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
+ continue;
+ }
+
+ if (!aFilter->pass(candidate)) {
+ continue;
+ }
+ }
+
+ if (!aCur) {
+ return candidate;
+ }
+ }
+
+ // Unable to match the filter with this range - try the next range.
+ range = global_namedIndex.equal_range(range.second->first);
+ }
+
+ return NULL; // Reached the end of the valid sequence with no match.
}
+