#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;
addToIndices(FGPositioned* aPos)
{
assert(aPos);
- global_namedIndex.insert(global_namedIndex.begin(),
- std::make_pair(aPos->ident(), aPos));
+ if (!aPos->ident().empty()) {
+ global_namedIndex.insert(global_namedIndex.begin(),
+ std::make_pair(aPos->ident(), aPos));
+ }
SpatialPositionedIndex::iterator it = bucketEntryForPositioned(aPos);
it->second.insert(aPos);
{
assert(aPos);
- NamedPositionedIndex::iterator it = global_namedIndex.find(aPos->ident());
- while (it != global_namedIndex.end() && (it->first == aPos->ident())) {
- if (it->second == aPos) {
- global_namedIndex.erase(it);
- break;
- }
-
- ++it;
+ if (!aPos->ident().empty()) {
+ NamedPositionedIndex::iterator it = global_namedIndex.find(aPos->ident());
+ while (it != global_namedIndex.end() && (it->first == aPos->ident())) {
+ if (it->second == aPos) {
+ global_namedIndex.erase(it);
+ break;
+ }
+
+ ++it;
+ } // of multimap walk
}
SpatialPositionedIndex::iterator sit = bucketEntryForPositioned(aPos);
}
static void
-spatialFilterInBucket(const SGBucket& aBucket, const FGPositioned::Filter& aFilter, FGPositioned::List& aResult)
+spatialFilterInBucket(const SGBucket& aBucket, FGPositioned::Filter* aFilter, FGPositioned::List& aResult)
{
SpatialPositionedIndex::const_iterator it;
it = global_spatialIndex.find(aBucket.gen_index());
BucketEntry::const_iterator l = it->second.begin();
BucketEntry::const_iterator u = it->second.end();
+ if (!aFilter) { // pass everything
+ aResult.insert(aResult.end(), l, u);
+ 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)) {
+ if ((*aFilter)(*l)) {
aResult.push_back(*l);
}
}
static void
spatialFind(const SGGeod& aPos, double aRange,
- const FGPositioned::Filter& aFilter, FGPositioned::List& aResult)
+ FGPositioned::Filter* aFilter, FGPositioned::List& aResult)
{
SGBucket buck(aPos);
double lat = aPos.getLatitudeDeg(),
} // 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
{
public:
RangePredictate(const SGGeod& aOrigin, double aRange) :
- mOrigin(aOrigin),
- mRange(aRange)
+ mOrigin(SGVec3d::fromGeod(aOrigin)),
+ mRangeSqr(aRange * aRange)
{ ; }
bool operator()(const FGPositionedRef& aPos)
{
- double d, az1, az2;
- SGGeodesy::inverse(aPos->geod(), mOrigin, az1, az2, d);
- return (d > mRange);
+ double dSqr = distSqr(aPos->cart(), mOrigin);
+ return (dSqr > mRangeSqr);
}
private:
- SGGeod mOrigin;
- double mRange;
+ SGVec3d mOrigin;
+ double mRangeSqr;
};
static void
{
public:
DistanceOrdering(const SGGeod& aPos) :
- mPos(aPos)
+ mPos(SGVec3d::fromGeod(aPos))
{ }
bool operator()(const FGPositionedRef& a, const FGPositionedRef& b) const
{
- double dA, dB, az1, az2;
- SGGeodesy::inverse(mPos, a->geod(), az1, az2, dA);
- SGGeodesy::inverse(mPos, b->geod(), az1, az2, dB);
+ double dA = distSqr(a->cart(), mPos),
+ dB = distSqr(b->cart(), mPos);
return dA < dB;
}
private:
- SGGeod mPos;
+ SGVec3d mPos;
};
static void
}
static FGPositionedRef
-namedFindClosestTyped(const std::string& aIdent, const SGGeod& aOrigin,
- FGPositioned::Type aLower, FGPositioned::Type aUpper)
+namedFindClosest(const std::string& aIdent, const SGGeod& aOrigin, FGPositioned::Filter* aFilter)
{
NamedIndexRange range = global_namedIndex.equal_range(aIdent);
if (range.first == range.second) {
// 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
- FGPositioned::Type ty = range.first->second->type();
- if ((ty < aLower) || (ty > aUpper)) {
- 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
double minDist = HUGE_VAL;
FGPositionedRef result;
NamedPositionedIndex::const_iterator it = range.first;
-
+ SGVec3d cartOrigin(SGVec3d::fromGeod(aOrigin));
+
for (; it != range.second; ++it) {
- // filter by type
- FGPositioned::Type ty = it->second->type();
- if ((ty < aLower) || (ty > aUpper)) {
- continue;
+ FGPositioned* r = it->second;
+ if (aFilter) {
+ if (aFilter->hasTypeRange() && !aFilter->passType(r->type())) {
+ continue;
+ }
+
+ if (!aFilter->pass(r)) {
+ continue;
+ }
}
// find distance
- double d, az1, az2;
- SGGeodesy::inverse(aOrigin, it->second->geod(), az2, az2, d);
- if (d < minDist) {
- minDist = d;
- result = it->second;
+ double d2 = distSqr(cartOrigin, r->cart());
+ if (d2 < minDist) {
+ minDist = d2;
+ result = r;
}
}
}
static FGPositioned::List
-spatialGetClosest(const SGGeod& aPos, unsigned int aN, double aCutoffNm, const FGPositioned::Filter& aFilter)
+spatialGetClosest(const SGGeod& aPos, unsigned int aN, double aCutoffNm, FGPositioned::Filter* aFilter)
{
FGPositioned::List result;
int radius = 1; // start at 1, radius 0 is handled explicitly
result.insert(result.end(), hits.begin(), hits.end()); // append
} // of outer loop
+ sortByDistance(aPos, result);
if (result.size() > aN) {
result.resize(aN); // truncate at requested number of matches
}
- sortByDistance(aPos, result);
+ 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;
}
///////////////////////////////////////////////////////////////////////////////
-FGPositioned::FGPositioned() :
- mType(INVALID)
+bool
+FGPositioned::Filter::hasTypeRange() const
{
+ assert(minType() <= maxType());
+ return (minType() != INVALID) && (maxType() != INVALID);
}
-FGPositioned::FGPositioned(Type ty, const std::string& aIdent, double aLat, double aLon, double aElev) :
- mType(ty),
- mPosition(SGGeod::fromDegFt(aLon, aLat, aElev)),
- mIdent(aIdent)
+bool
+FGPositioned::Filter::passType(Type aTy) const
{
- addToIndices(this);
- SGReferenced::get(this); // hold an owning ref, for the moment
+ assert(hasTypeRange());
+ return (minType() <= aTy) && (maxType() >= aTy);
}
-FGPositioned::FGPositioned(Type ty, const std::string& aIdent, const SGGeod& aPos) :
+///////////////////////////////////////////////////////////////////////////////
+
+FGPositioned::FGPositioned(Type ty, const std::string& aIdent, const SGGeod& aPos, bool aIndexed) :
mType(ty),
mPosition(aPos),
mIdent(aIdent)
-{
- addToIndices(this);
+{
SGReferenced::get(this); // hold an owning ref, for the moment
+
+ if (aIndexed) {
+ assert(ty != TAXIWAY && ty != PAVEMENT);
+ addToIndices(this);
+ }
}
FGPositioned::~FGPositioned()
{
+ //std::cout << "destroying:" << mIdent << "/" << nameForType(mType) << std::endl;
removeFromIndices(this);
}
return SGBucket(mPosition);
}
+SGVec3d
+FGPositioned::cart() const
+{
+ return SGVec3d::fromGeod(mPosition);
+}
+
const char* FGPositioned::nameForType(Type aTy)
{
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";
case NDB: return "NDB";
+ case ILS: return "ILS";
+ case LOC: return "localiser";
+ case GS: return "glideslope";
case OM: return "outer-marker";
case MM: return "middle-marker";
case IM: return "inner-marker";
case HELIPORT: return "heliport";
case SEAPORT: return "seaport";
case WAYPOINT: return "waypoint";
+ case DME: return "dme";
+ case TACAN: return "tacan";
default:
return "unknown";
}
// search / query functions
FGPositionedRef
-FGPositioned::findClosestWithIdent(const std::string& aIdent, double aLat, double aLon)
-{
- return findClosestWithIdent(aIdent, SGGeod::fromDeg(aLon, aLat));
-}
-
-FGPositionedRef
-FGPositioned::findClosestWithIdent(const std::string& aIdent, const SGGeod& aPos)
-{
- return namedFindClosestTyped(aIdent, aPos, INVALID, LAST_TYPE);
-}
-
-FGPositioned::List
-FGPositioned::findWithinRangeByType(const SGGeod& aPos, double aRangeNm, Type aTy)
+FGPositioned::findClosestWithIdent(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter)
{
- List result;
- spatialFindTyped(aPos, aRangeNm, aTy, aTy, result);
- filterListByRange(aPos, aRangeNm, result);
- return result;
+ return namedFindClosest(aIdent, aPos, aFilter);
}
FGPositioned::List
-FGPositioned::findWithinRange(const SGGeod& aPos, double aRangeNm, const Filter& aFilter)
+FGPositioned::findWithinRange(const SGGeod& aPos, double aRangeNm, Filter* aFilter)
{
List result;
spatialFind(aPos, aRangeNm, aFilter, result);
}
FGPositioned::List
-FGPositioned::findAllWithIdent(const std::string& aIdent)
+FGPositioned::findAllWithIdentSortedByRange(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter)
{
List result;
NamedIndexRange range = global_namedIndex.equal_range(aIdent);
for (; range.first != range.second; ++range.first) {
+ if (aFilter && !aFilter->pass(range.first->second)) {
+ continue;
+ }
+
result.push_back(range.first->second);
}
+ sortByDistance(aPos, result);
return result;
}
+FGPositionedRef
+FGPositioned::findClosest(const SGGeod& aPos, double aCutoffNm, Filter* aFilter)
+{
+ FGPositioned::List l(spatialGetClosest(aPos, 1, aCutoffNm, aFilter));
+ if (l.empty()) {
+ return NULL;
+ }
+
+ assert(l.size() == 1);
+ return l.front();
+}
+
FGPositioned::List
-FGPositioned::findClosestN(const SGGeod& aPos, unsigned int aN, double aCutoffNm, const Filter& aFilter)
+FGPositioned::findClosestN(const SGGeod& aPos, unsigned int aN, double aCutoffNm, Filter* aFilter)
{
return spatialGetClosest(aPos, aN, aCutoffNm, aFilter);
}
+/*
+FGPositionedRef
+FGPositioned::findNextWithPartialId(FGPositionedRef aCur, const std::string& aId, Filter* aFilter)
+{
+ NamedIndexRange range = global_namedIndex.equal_range(aId);
+ 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;
+ }
+ }
+
+ 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