#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();
+ }
+};
+
+
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::Type ty = range.first->second->type();
+ if (aFilter) {
+ if (aFilter->hasTypeRange() && !aFilter->passType(ty)) {
+ continue;
+ }
+
+ if (!aFilter->pass(range.first->second)) {
+ continue;
+ }
}
// find distance
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) :
continue;
}
- if (aFilter && !aFilter->pass(candidate)) {
- continue;
+ if (aFilter) {
+ if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
+ continue;
+ }
+
+ if(!aFilter->pass(candidate)) {
+ continue;
+ }
}
if (!aCur) {