X-Git-Url: https://git.mxchange.org/?a=blobdiff_plain;f=src%2FNavaids%2Fpositioned.cxx;h=b01418a17367a1814dea1b8cbd5427f80192d2e7;hb=c6045147544badd6daefdcab9d4de1ed6936533b;hp=e09f0da2c5c63800769885d415b2ccd65308a27d;hpb=812485d623f5a58f722f40d14bcd23430c2ac6f9;p=flightgear.git diff --git a/src/Navaids/positioned.cxx b/src/Navaids/positioned.cxx index e09f0da2c..b01418a17 100644 --- a/src/Navaids/positioned.cxx +++ b/src/Navaids/positioned.cxx @@ -24,9 +24,13 @@ #include #include -#include +#include // for sort +#include // for char-traits toupper + +#include #include +#include #include "positioned.hxx" @@ -71,8 +75,10 @@ static void 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); @@ -83,14 +89,16 @@ removeFromIndices(FGPositioned* 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); @@ -98,7 +106,7 @@ removeFromIndices(FGPositioned* 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()); @@ -109,8 +117,13 @@ spatialFilterInBucket(const SGBucket& aBucket, const FGPositioned::Filter& aFilt 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; + } + for ( ; l != u; ++l) { - if (aFilter(*l)) { + if ((*aFilter)(*l)) { aResult.push_back(*l); } } @@ -118,7 +131,7 @@ spatialFilterInBucket(const SGBucket& aBucket, const FGPositioned::Filter& aFilt 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(), @@ -135,6 +148,7 @@ spatialFind(const SGGeod& aPos, double aRange, } // of i-iteration } +/* class LowerLimitOfType { public: @@ -149,6 +163,7 @@ public: } }; + static void spatialFindTyped(const SGGeod& aPos, double aRange, FGPositioned::Type aLower, FGPositioned::Type aUpper, FGPositioned::List& aResult) { @@ -180,6 +195,7 @@ spatialFindTyped(const SGGeod& aPos, double aRange, FGPositioned::Type aLower, F } // of j-iteration } // of i-iteration } +*/ /** */ @@ -187,20 +203,19 @@ 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 @@ -216,19 +231,18 @@ class DistanceOrdering { 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 @@ -238,8 +252,7 @@ sortByDistance(const SGGeod& aPos, FGPositioned::List& aResult) } 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) { @@ -251,8 +264,7 @@ namedFindClosestTyped(const std::string& aIdent, const SGGeod& aOrigin, 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)) { + if (aFilter && !aFilter->pass(range.first->second)) { return NULL; // type check failed } @@ -263,19 +275,17 @@ namedFindClosestTyped(const std::string& aIdent, const SGGeod& aOrigin, 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)) { + if (aFilter && !aFilter->pass(range.first->second)) { continue; } // find distance - double d, az1, az2; - SGGeodesy::inverse(aOrigin, it->second->geod(), az2, az2, d); - if (d < minDist) { - minDist = d; + double d2 = distSqr(cartOrigin, it->second->cart()); + if (d2 < minDist) { + minDist = d2; result = it->second; } } @@ -284,7 +294,7 @@ namedFindClosestTyped(const std::string& aIdent, const SGGeod& aOrigin, } 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 @@ -320,36 +330,120 @@ spatialGetClosest(const SGGeod& aPos, unsigned int aN, double aCutoffNm, const F 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; } -/////////////////////////////////////////////////////////////////////////////// +////////////////////////////////////////////////////////////////////////////// -FGPositioned::FGPositioned(Type ty, const std::string& aIdent, double aLat, double aLon, double aElev) : - mType(ty), - mPosition(SGGeod::fromDegFt(aLon, aLat, aElev)), - mIdent(aIdent) +class OrderByName { - addToIndices(this); - SGReferenced::get(this); // hold an owning ref, for the moment +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 &ct = std::use_facet >(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 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; iname().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(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); + addToIndices(this); + } } FGPositioned::~FGPositioned() { + //std::cout << "destroying:" << mIdent << "/" << nameForType(mType) << std::endl; removeFromIndices(this); } @@ -359,12 +453,24 @@ FGPositioned::bucket() const 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 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"; @@ -372,6 +478,8 @@ const char* FGPositioned::nameForType(Type aTy) case HELIPORT: return "heliport"; case SEAPORT: return "seaport"; case WAYPOINT: return "waypoint"; + case DME: return "dme"; + case TACAN: return "tacan"; default: return "unknown"; } @@ -381,28 +489,13 @@ const char* FGPositioned::nameForType(Type aTy) // search / query functions FGPositionedRef -FGPositioned::findClosestWithIdent(const std::string& aIdent, double aLat, double aLon) +FGPositioned::findClosestWithIdent(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter) { - 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) -{ - 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); @@ -411,20 +504,60 @@ FGPositioned::findWithinRange(const SGGeod& aPos, double aRangeNm, const Filter& } 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 && !aFilter->pass(candidate)) { + continue; + } + + if (!aCur) { + return candidate; + } + } + + return NULL; // fell out, no match in range +} +