#include <map>
#include <set>
-#include <algorithm>
+#include <algorithm> // for sort
+#include <locale> // for char-traits toupper
#include <iostream>
#include <simgear/math/sg_geodesy.hxx>
+#include <simgear/timing/timestamp.hxx>
#include "positioned.hxx"
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;
}
}
return result;
}
+//////////////////////////////////////////////////////////////////////////////
+
+class OrderByName
+{
+public:
+ bool operator()(FGPositioned* a, FGPositioned* b) const
+ {
+ return a->name() < b->name();
+ }
+};
+
+/**
+ * A special purpose helper (imported by FGAirport::searchNamesAndIdents) to
+ * implement the AirportList dialog. It's unfortunate that it needs to reside
+ * here, but for now it's least ugly solution.
+ */
+char** searchAirportNamesAndIdents(const std::string& aFilter)
+{
+ const std::ctype<char> &ct = std::use_facet<std::ctype<char> >(std::locale());
+ std::string filter(aFilter);
+ bool hasFilter = !filter.empty();
+ if (hasFilter) {
+ ct.toupper((char *)filter.data(), (char *)filter.data() + filter.size());
+ }
+
+ NamedPositionedIndex::const_iterator it = global_namedIndex.begin();
+ NamedPositionedIndex::const_iterator end = global_namedIndex.end();
+
+ // note this is a vector of raw pointers, not smart pointers, because it
+ // may get very large and smart-pointer-atomicity-locking then becomes a
+ // bottleneck for this case.
+ std::vector<FGPositioned*> matches;
+ std::string upper;
+
+ for (; it != end; ++it) {
+ FGPositioned::Type ty = it->second->type();
+ if ((ty < FGPositioned::AIRPORT) || (ty > FGPositioned::SEAPORT)) {
+ continue;
+ }
+
+ if (hasFilter && (it->second->ident().find(aFilter) == std::string::npos)) {
+ upper = it->second->name(); // string copy, sadly
+ ct.toupper((char *)upper.data(), (char *)upper.data() + upper.size());
+ if (upper.find(aFilter) == std::string::npos) {
+ continue;
+ }
+ }
+
+ matches.push_back(it->second);
+ }
+
+ // sort alphabetically on name
+ std::sort(matches.begin(), matches.end(), OrderByName());
+
+ // convert results to format comptible with puaList
+ unsigned int numMatches = matches.size();
+ char** result = new char*[numMatches + 1];
+ result[numMatches] = NULL; // end-of-list marker
+
+ // nasty code to avoid excessive string copying and allocations.
+ // We format results as follows (note whitespace!):
+ // ' name-of-airport-chars (ident)'
+ // so the total length is:
+ // 1 + strlen(name) + 4 + 4 (for the ident) + 1 + 1 (for the null)
+ // which gives a grand total of 11 + the length of the name.
+ // note the ident is sometimes only three letters for non-ICAO small strips
+ for (unsigned int i=0; i<numMatches; ++i) {
+ int nameLength = matches[i]->name().size();
+ int icaoLength = matches[i]->ident().size();
+ char* entry = new char[nameLength + 11];
+ char* dst = entry;
+ *dst++ = ' ';
+ memcpy(dst, matches[i]->name().c_str(), nameLength);
+ dst += nameLength;
+ *dst++ = ' ';
+ *dst++ = ' ';
+ *dst++ = ' ';
+ *dst++ = '(';
+ memcpy(dst, matches[i]->ident().c_str(), icaoLength);
+ dst += icaoLength;
+ *dst++ = ')';
+ *dst++ = 0;
+ result[i] = entry;
+ }
+
+ return result;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+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) :
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.
}
+
projects / flightgear.git / blobdiff