src/Navaids/positioned.cxx

   1 // positioned.cxx - base class for objects which are positioned
   2 //
   3 // Copyright (C) 2008 James Turner
   4 //
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License as
   7 // published by the Free Software Foundation; either version 2 of the
   8 // License, or (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful, but
  11 // WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 // General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  18 //
  19 // $Id$
  20
  21 #ifdef HAVE_CONFIG_H
  22 #  include "config.h"
  23 #endif
  24
  25 #include <map>
  26 #include <set>
  27 #include <algorithm> // for sort
  28 #include <locale> // for char-traits toupper
  29
  30 #include <iostream>
  31
  32 #include <boost/algorithm/string/case_conv.hpp>
  33
  34 #include <simgear/math/sg_geodesy.hxx>
  35 #include <simgear/timing/timestamp.hxx>
  36 #include <simgear/debug/logstream.hxx>
  37
  38 #include "positioned.hxx"
  39
  40 typedef std::multimap<std::string, FGPositioned*> NamedPositionedIndex;
  41 typedef std::pair<NamedPositionedIndex::const_iterator, NamedPositionedIndex::const_iterator> NamedIndexRange;
  42
  43 using std::lower_bound;
  44 using std::upper_bound;
  45
  46 /**
  47  * Order positioned elements by type, then pointer address. This allows us to
  48  * use range searches (lower_ and upper_bound) to grab items of a particular
  49  * type out of bucket efficently.
  50  */
  51 class OrderByType
  52 {
  53 public:
  54   bool operator()(const FGPositioned* a, const FGPositioned* b) const
  55   {
  56     if (a->type() == b->type()) return a < b;
  57     return a->type() < b->type();
  58   }
  59 };
  60
  61 class LowerLimitOfType
  62 {
  63 public:
  64   bool operator()(const FGPositioned* a, const FGPositioned::Type b) const
  65   {
  66     return a->type() < b;
  67   }
  68
  69   bool operator()(const FGPositioned::Type a, const FGPositioned* b) const
  70   {
  71     return a < b->type();
  72   }
  73
  74   // The operator below is required by VS2005 in debug mode
  75   bool operator()(const FGPositioned* a, const FGPositioned* b) const
  76   {
  77     return a->type() < b->type();
  78   }
  79 };
  80
  81
  82 typedef std::set<FGPositioned*, OrderByType> BucketEntry;
  83 typedef std::map<long int, BucketEntry> SpatialPositionedIndex;
  84
  85 static NamedPositionedIndex global_namedIndex;
  86 static SpatialPositionedIndex global_spatialIndex;
  87
  88 SpatialPositionedIndex::iterator
  89 bucketEntryForPositioned(FGPositioned* aPos)
  90 {
  91   int bucketIndex = aPos->bucket().gen_index();
  92   SpatialPositionedIndex::iterator it = global_spatialIndex.find(bucketIndex);
  93   if (it != global_spatialIndex.end()) {
  94     return it;
  95   }
  96
  97   // create a new BucketEntry
  98   return global_spatialIndex.insert(it, std::make_pair(bucketIndex, BucketEntry()));
  99 }
 100
 101 static void
 102 addToIndices(FGPositioned* aPos)
 103 {
 104   assert(aPos);
 105   if (!aPos->ident().empty()) {
 106     global_namedIndex.insert(global_namedIndex.begin(),
 107       std::make_pair(aPos->ident(), aPos));
 108   }
 109
 110   SpatialPositionedIndex::iterator it = bucketEntryForPositioned(aPos);
 111   it->second.insert(aPos);
 112 }
 113
 114 static void
 115 removeFromIndices(FGPositioned* aPos)
 116 {
 117   assert(aPos);
 118
 119   if (!aPos->ident().empty()) {
 120     NamedPositionedIndex::iterator it = global_namedIndex.find(aPos->ident());
 121     while (it != global_namedIndex.end() && (it->first == aPos->ident())) {
 122       if (it->second == aPos) {
 123         global_namedIndex.erase(it);
 124         break;
 125       }
 126
 127       ++it;
 128     } // of multimap walk
 129   }
 130
 131   SpatialPositionedIndex::iterator sit = bucketEntryForPositioned(aPos);
 132   sit->second.erase(aPos);
 133 }
 134
 135 static void
 136 spatialFilterInBucket(const SGBucket& aBucket, FGPositioned::Filter* aFilter, FGPositioned::List& aResult)
 137 {
 138   SpatialPositionedIndex::const_iterator it;
 139   it = global_spatialIndex.find(aBucket.gen_index());
 140   if (it == global_spatialIndex.end()) {
 141     return;
 142   }
 143
 144   BucketEntry::const_iterator l = it->second.begin();
 145   BucketEntry::const_iterator u = it->second.end();
 146
 147   if (!aFilter) { // pass everything
 148     aResult.insert(aResult.end(), l, u);
 149     return;
 150   }
 151
 152   if (aFilter->hasTypeRange()) {
 153     // avoid many calls to the filter hook
 154     l = lower_bound(it->second.begin(), it->second.end(), aFilter->minType(), LowerLimitOfType());
 155     u = upper_bound(l, it->second.end(), aFilter->maxType(), LowerLimitOfType());
 156   }
 157
 158   for ( ; l != u; ++l) {
 159     if ((*aFilter)(*l)) {
 160       aResult.push_back(*l);
 161     }
 162   }
 163 }
 164
 165 static void
 166 spatialFind(const SGGeod& aPos, double aRange,
 167   FGPositioned::Filter* aFilter, FGPositioned::List& aResult)
 168 {
 169   SGBucket buck(aPos);
 170   double lat = aPos.getLatitudeDeg(),
 171     lon = aPos.getLongitudeDeg();
 172
 173   int bx = (int)( aRange*SG_NM_TO_METER / buck.get_width_m() / 2);
 174   int by = (int)( aRange*SG_NM_TO_METER / buck.get_height_m() / 2 );
 175
 176   // loop over bucket range
 177   for ( int i=-bx; i<=bx; i++) {
 178     for ( int j=-by; j<=by; j++) {
 179       spatialFilterInBucket(sgBucketOffset(lon, lat, i, j), aFilter, aResult);
 180     } // of j-iteration
 181   } // of i-iteration
 182 }
 183
 184 /**
 185  */
 186 class RangePredictate
 187 {
 188 public:
 189   RangePredictate(const SGGeod& aOrigin, double aRange) :
 190     mOrigin(SGVec3d::fromGeod(aOrigin)),
 191     mRangeSqr(aRange * aRange)
 192   { ; }
 193
 194   bool operator()(const FGPositionedRef& aPos)
 195   {
 196     double dSqr = distSqr(aPos->cart(), mOrigin);
 197     return (dSqr > mRangeSqr);
 198   }
 199
 200 private:
 201   SGVec3d mOrigin;
 202   double mRangeSqr;
 203 };
 204
 205 static void
 206 filterListByRange(const SGGeod& aPos, double aRange, FGPositioned::List& aResult)
 207 {
 208   RangePredictate pred(aPos, aRange * SG_NM_TO_METER);
 209   FGPositioned::List::iterator newEnd;
 210   newEnd = std::remove_if(aResult.begin(), aResult.end(), pred);
 211   aResult.erase(newEnd, aResult.end());
 212 }
 213
 214 class DistanceOrdering
 215 {
 216 public:
 217   DistanceOrdering(const SGGeod& aPos) :
 218     mPos(SGVec3d::fromGeod(aPos))
 219   { }
 220
 221   bool operator()(const FGPositionedRef& a, const FGPositionedRef& b) const
 222   {
 223     double dA = distSqr(a->cart(), mPos),
 224       dB = distSqr(b->cart(), mPos);
 225     return dA < dB;
 226   }
 227
 228 private:
 229   SGVec3d mPos;
 230 };
 231
 232 static void
 233 sortByDistance(const SGGeod& aPos, FGPositioned::List& aResult)
 234 {
 235   std::sort(aResult.begin(), aResult.end(), DistanceOrdering(aPos));
 236 }
 237
 238 static FGPositionedRef
 239 namedFindClosest(const std::string& aIdent, const SGGeod& aOrigin, FGPositioned::Filter* aFilter)
 240 {
 241   NamedIndexRange range = global_namedIndex.equal_range(aIdent);
 242   if (range.first == range.second) {
 243     return NULL;
 244   }
 245
 246 // common case, only one result. looks a bit ugly because these are
 247 // sequential iterators, not random-access ones
 248   NamedPositionedIndex::const_iterator check = range.first;
 249   if (++check == range.second) {
 250     // excellent, only one match in the range
 251     FGPositioned* r = range.first->second;
 252     if (aFilter) {
 253       if (aFilter->hasTypeRange() && !aFilter->passType(r->type())) {
 254         return NULL;
 255       }
 256
 257       if (!aFilter->pass(r)) {
 258         return NULL;
 259       }
 260     } // of have a filter
 261
 262     return r;
 263   } // of short-circuit logic for single-element range
 264
 265 // multiple matches, we need to actually check the distance to each one
 266   double minDist = HUGE_VAL;
 267   FGPositionedRef result;
 268   NamedPositionedIndex::const_iterator it = range.first;
 269   SGVec3d cartOrigin(SGVec3d::fromGeod(aOrigin));
 270
 271   for (; it != range.second; ++it) {
 272     FGPositioned* r = it->second;
 273     if (aFilter) {
 274       if (aFilter->hasTypeRange() && !aFilter->passType(r->type())) {
 275         continue;
 276       }
 277
 278       if (!aFilter->pass(r)) {
 279         continue;
 280       }
 281     }
 282
 283   // find distance
 284     double d2 = distSqr(cartOrigin, r->cart());
 285     if (d2 < minDist) {
 286       minDist = d2;
 287       result = r;
 288     }
 289   }
 290
 291   return result;
 292 }
 293
 294 static FGPositioned::List
 295 spatialGetClosest(const SGGeod& aPos, unsigned int aN, double aCutoffNm, FGPositioned::Filter* aFilter)
 296 {
 297   FGPositioned::List result;
 298   int radius = 1; // start at 1, radius 0 is handled explicitly
 299   SGBucket buck;
 300   double lat = aPos.getLatitudeDeg(),
 301     lon = aPos.getLongitudeDeg();
 302   // final cutoff is in metres, and scaled to account for testing the corners
 303   // of the 'box' instead of the centre of each edge
 304   double cutoffM = aCutoffNm * SG_NM_TO_METER * 1.5;
 305
 306   // base case, simplifes loop to do it seperately here
 307   spatialFilterInBucket(sgBucketOffset(lon, lat, 0, 0), aFilter, result);
 308
 309   for (;result.size() < aN; ++radius) {
 310     // cutoff check
 311     double az1, az2, d1, d2;
 312     SGGeodesy::inverse(aPos, sgBucketOffset(lon, lat, -radius, -radius).get_center(), az1, az2, d1);
 313     SGGeodesy::inverse(aPos, sgBucketOffset(lon, lat, radius, radius).get_center(), az1, az2, d2);
 314
 315     if ((d1 > cutoffM) && (d2 > cutoffM)) {
 316       //std::cerr << "spatialGetClosest terminating due to range cutoff" << std::endl;
 317       break;
 318     }
 319
 320     FGPositioned::List hits;
 321     for ( int i=-radius; i<=radius; i++) {
 322       spatialFilterInBucket(sgBucketOffset(lon, lat, i, -radius), aFilter, hits);
 323       spatialFilterInBucket(sgBucketOffset(lon, lat, -radius, i), aFilter, hits);
 324       spatialFilterInBucket(sgBucketOffset(lon, lat, i, radius), aFilter, hits);
 325       spatialFilterInBucket(sgBucketOffset(lon, lat, radius, i), aFilter, hits);
 326     }
 327
 328     result.insert(result.end(), hits.begin(), hits.end()); // append
 329   } // of outer loop
 330
 331   sortByDistance(aPos, result);
 332   if (result.size() > aN) {
 333     result.resize(aN); // truncate at requested number of matches
 334   }
 335
 336   return result;
 337 }
 338
 339 //////////////////////////////////////////////////////////////////////////////
 340
 341 class OrderByName
 342 {
 343 public:
 344   bool operator()(FGPositioned* a, FGPositioned* b) const
 345   {
 346     return a->name() < b->name();
 347   }
 348 };
 349
 350 /**
 351  * A special purpose helper (imported by FGAirport::searchNamesAndIdents) to
 352  * implement the AirportList dialog. It's unfortunate that it needs to reside
 353  * here, but for now it's least ugly solution.
 354  */
 355 char** searchAirportNamesAndIdents(const std::string& aFilter)
 356 {
 357   const std::ctype<char> &ct = std::use_facet<std::ctype<char> >(std::locale());
 358   std::string filter(aFilter);
 359   bool hasFilter = !filter.empty();
 360   if (hasFilter) {
 361     ct.toupper((char *)filter.data(), (char *)filter.data() + filter.size());
 362   }
 363
 364   NamedPositionedIndex::const_iterator it = global_namedIndex.begin();
 365   NamedPositionedIndex::const_iterator end = global_namedIndex.end();
 366
 367   // note this is a vector of raw pointers, not smart pointers, because it
 368   // may get very large and smart-pointer-atomicity-locking then becomes a
 369   // bottleneck for this case.
 370   std::vector<FGPositioned*> matches;
 371   std::string upper;
 372
 373   for (; it != end; ++it) {
 374     FGPositioned::Type ty = it->second->type();
 375     if ((ty < FGPositioned::AIRPORT) || (ty > FGPositioned::SEAPORT)) {
 376       continue;
 377     }
 378
 379     if (hasFilter && (it->second->ident().find(aFilter) == std::string::npos)) {
 380       upper = it->second->name(); // string copy, sadly
 381       ct.toupper((char *)upper.data(), (char *)upper.data() + upper.size());
 382       if (upper.find(aFilter) == std::string::npos) {
 383         continue;
 384       }
 385     }
 386
 387     matches.push_back(it->second);
 388   }
 389
 390   // sort alphabetically on name
 391   std::sort(matches.begin(), matches.end(), OrderByName());
 392
 393   // convert results to format comptible with puaList
 394   unsigned int numMatches = matches.size();
 395   char** result = new char*[numMatches + 1];
 396   result[numMatches] = NULL; // end-of-list marker
 397
 398   // nasty code to avoid excessive string copying and allocations.
 399   // We format results as follows (note whitespace!):
 400   //   ' name-of-airport-chars   (ident)'
 401   // so the total length is:
 402   //    1 + strlen(name) + 4 + 4 (for the ident) + 1 + 1 (for the null)
 403   // which gives a grand total of 11 + the length of the name.
 404   // note the ident is sometimes only three letters for non-ICAO small strips
 405   for (unsigned int i=0; i<numMatches; ++i) {
 406     int nameLength = matches[i]->name().size();
 407     int icaoLength = matches[i]->ident().size();
 408     char* entry = new char[nameLength + 11];
 409     char* dst = entry;
 410     *dst++ = ' ';
 411     memcpy(dst, matches[i]->name().c_str(), nameLength);
 412     dst += nameLength;
 413     *dst++ = ' ';
 414     *dst++ = ' ';
 415     *dst++ = ' ';
 416     *dst++ = '(';
 417     memcpy(dst, matches[i]->ident().c_str(), icaoLength);
 418     dst += icaoLength;
 419     *dst++ = ')';
 420     *dst++ = 0;
 421     result[i] = entry;
 422   }
 423
 424   return result;
 425 }
 426
 427 ///////////////////////////////////////////////////////////////////////////////
 428
 429 bool
 430 FGPositioned::Filter::hasTypeRange() const
 431 {
 432   assert(minType() <= maxType());
 433   return (minType() != INVALID) && (maxType() != INVALID);
 434 }
 435
 436 bool
 437 FGPositioned::Filter::passType(Type aTy) const
 438 {
 439   assert(hasTypeRange());
 440   return (minType() <= aTy) && (maxType() >= aTy);
 441 }
 442
 443 ///////////////////////////////////////////////////////////////////////////////
 444
 445 FGPositioned::FGPositioned(Type ty, const std::string& aIdent, const SGGeod& aPos, bool aIndexed) :
 446   mType(ty),
 447   mPosition(aPos),
 448   mIdent(aIdent)
 449 {
 450   SGReferenced::get(this); // hold an owning ref, for the moment
 451
 452   if (aIndexed) {
 453     assert(ty != TAXIWAY && ty != PAVEMENT);
 454     addToIndices(this);
 455   }
 456 }
 457
 458 FGPositioned::~FGPositioned()
 459 {
 460   //std::cout << "destroying:" << mIdent << "/" << nameForType(mType) << std::endl;
 461   removeFromIndices(this);
 462 }
 463
 464 FGPositioned*
 465 FGPositioned::createUserWaypoint(const std::string& aIdent, const SGGeod& aPos)
 466 {
 467   return new FGPositioned(WAYPOINT, aIdent, aPos, true);
 468 }
 469
 470 SGBucket
 471 FGPositioned::bucket() const
 472 {
 473   return SGBucket(mPosition);
 474 }
 475
 476 SGVec3d
 477 FGPositioned::cart() const
 478 {
 479   return SGVec3d::fromGeod(mPosition);
 480 }
 481
 482 FGPositioned::Type FGPositioned::typeFromName(const std::string& aName)
 483 {
 484   if (aName.empty() || (aName == "")) {
 485     return INVALID;
 486   }
 487
 488   typedef struct {
 489     const char* _name;
 490     Type _ty;
 491   } NameTypeEntry;
 492
 493   const NameTypeEntry names[] = {
 494     {"airport", AIRPORT},
 495     {"vor", VOR},
 496     {"ndb", NDB},
 497     {"wpt", WAYPOINT},
 498     {"fix", FIX},
 499     {"tacan", TACAN},
 500     {"dme", DME},
 501   // aliases
 502     {"waypoint", WAYPOINT},
 503     {"apt", AIRPORT},
 504
 505     {NULL, INVALID}
 506   };
 507
 508   std::string lowerName(boost::to_lower_copy(aName));
 509
 510   for (const NameTypeEntry* n = names; (n->_name != NULL); ++n) {
 511     if (::strcmp(n->_name, lowerName.c_str()) == 0) {
 512       return n->_ty;
 513     }
 514   }
 515
 516   SG_LOG(SG_GENERAL, SG_WARN, "FGPositioned::typeFromName: couldn't match:" << aName);
 517   return INVALID;
 518 }
 519
 520 const char* FGPositioned::nameForType(Type aTy)
 521 {
 522  switch (aTy) {
 523  case RUNWAY: return "runway";
 524  case TAXIWAY: return "taxiway";
 525  case PAVEMENT: return "pavement";
 526  case PARK_STAND: return "parking stand";
 527  case FIX: return "fix";
 528  case VOR: return "VOR";
 529  case NDB: return "NDB";
 530  case ILS: return "ILS";
 531  case LOC: return "localiser";
 532  case GS: return "glideslope";
 533  case OM: return "outer-marker";
 534  case MM: return "middle-marker";
 535  case IM: return "inner-marker";
 536  case AIRPORT: return "airport";
 537  case HELIPORT: return "heliport";
 538  case SEAPORT: return "seaport";
 539  case WAYPOINT: return "waypoint";
 540  case DME: return "dme";
 541  case TACAN: return "tacan";
 542  default:
 543   return "unknown";
 544  }
 545 }
 546
 547 ///////////////////////////////////////////////////////////////////////////////
 548 // search / query functions
 549
 550 FGPositionedRef
 551 FGPositioned::findClosestWithIdent(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter)
 552 {
 553   return namedFindClosest(aIdent, aPos, aFilter);
 554 }
 555
 556 FGPositioned::List
 557 FGPositioned::findWithinRange(const SGGeod& aPos, double aRangeNm, Filter* aFilter)
 558 {
 559   List result;
 560   spatialFind(aPos, aRangeNm, aFilter, result);
 561   filterListByRange(aPos, aRangeNm, result);
 562   return result;
 563 }
 564
 565 FGPositioned::List
 566 FGPositioned::findAllWithIdentSortedByRange(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter)
 567 {
 568   List result;
 569   NamedIndexRange range = global_namedIndex.equal_range(aIdent);
 570   for (; range.first != range.second; ++range.first) {
 571     FGPositioned* candidate = range.first->second;
 572     if (aFilter) {
 573       if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 574         continue;
 575       }
 576
 577       if (!aFilter->pass(candidate)) {
 578         continue;
 579       }
 580     }
 581
 582     result.push_back(range.first->second);
 583   }
 584
 585   sortByDistance(aPos, result);
 586   return result;
 587 }
 588
 589 FGPositionedRef
 590 FGPositioned::findClosest(const SGGeod& aPos, double aCutoffNm, Filter* aFilter)
 591 {
 592    FGPositioned::List l(spatialGetClosest(aPos, 1, aCutoffNm, aFilter));
 593    if (l.empty()) {
 594       return NULL;
 595    }
 596
 597    assert(l.size() == 1);
 598    return l.front();
 599 }
 600
 601 FGPositioned::List
 602 FGPositioned::findClosestN(const SGGeod& aPos, unsigned int aN, double aCutoffNm, Filter* aFilter)
 603 {
 604   return spatialGetClosest(aPos, aN, aCutoffNm, aFilter);
 605 }
 606
 607 FGPositionedRef
 608 FGPositioned::findNextWithPartialId(FGPositionedRef aCur, const std::string& aId, Filter* aFilter)
 609 {
 610   // It is essential to bound our search, to avoid iterating all the way to the end of the database.
 611   // Do this by generating a second ID with the final character incremented by 1.
 612   // e.g., if the partial ID is "KI", we wish to search "KIxxx" but not "KJ".
 613   std::string upperBoundId = aId;
 614   upperBoundId[upperBoundId.size()-1]++;
 615   NamedPositionedIndex::const_iterator upperBound = global_namedIndex.lower_bound(upperBoundId);
 616
 617   NamedIndexRange range = global_namedIndex.equal_range(aId);
 618   while (range.first != upperBound) {
 619     for (; range.first != range.second; ++range.first) {
 620       FGPositionedRef candidate = range.first->second;
 621       if (aCur == candidate) {
 622         aCur = NULL; // found our start point, next match will pass
 623         continue;
 624       }
 625
 626       if (aFilter) {
 627         if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 628           continue;
 629         }
 630
 631         if (!aFilter->pass(candidate)) {
 632           continue;
 633         }
 634       }
 635
 636       if (!aCur) {
 637         return candidate;
 638       }
 639     }
 640
 641     // Unable to match the filter with this range - try the next range.
 642     range = global_namedIndex.equal_range(range.second->first);
 643   }
 644
 645   return NULL; // Reached the end of the valid sequence with no match.
 646 }
 647
 648 FGPositionedRef
 649 FGPositioned::findWithPartialId(const std::string& aId, Filter* aFilter, int aOffset, bool& aNext)
 650 {
 651   // see comment in findNextWithPartialId concerning upperBoundId
 652   std::string upperBoundId = aId;
 653   upperBoundId[upperBoundId.size()-1]++;
 654   NamedPositionedIndex::const_iterator upperBound = global_namedIndex.lower_bound(upperBoundId);
 655
 656   NamedIndexRange range = global_namedIndex.equal_range(aId);
 657   FGPositionedRef result;
 658
 659   while (range.first != upperBound) {
 660     for (; range.first != range.second; ++range.first) {
 661       FGPositionedRef candidate = range.first->second;
 662       if (aFilter) {
 663         if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 664           continue;
 665         }
 666
 667         if (!aFilter->pass(candidate)) {
 668           continue;
 669         }
 670       }
 671
 672       if (result) {
 673         aNext = true;
 674         return result;
 675       } else if (aOffset == 0) {
 676         // okay, found our result. we need to go around once more to set aNext
 677         result = candidate;
 678       } else {
 679         --aOffset; // seen one more valid result, decrement the count
 680       }
 681     }
 682
 683     // Unable to match the filter with this range - try the next range.
 684     range = global_namedIndex.equal_range(range.second->first);
 685   }
 686
 687   // if we fell out, we reached the end of the valid range. We might have a
 688   // valid result, but we definitiely don't have a next result.
 689   aNext = false;
 690   return result;
 691 }
 692
 693 /**
 694  * Wrapper filter which proxies to an inner filter, but also ensures the
 695  * ident starts with supplied partial ident.
 696  */
 697 class PartialIdentFilter : public FGPositioned::Filter
 698 {
 699 public:
 700   PartialIdentFilter(const std::string& ident, FGPositioned::Filter* filter) :
 701     _ident(ident),
 702     _inner(filter)
 703   { ; }
 704
 705   virtual bool pass(FGPositioned* aPos) const
 706   {
 707     if (!_inner->pass(aPos)) {
 708       return false;
 709     }
 710
 711     return (::strncmp(aPos->ident().c_str(), _ident.c_str(), _ident.size()) == 0);
 712   }
 713
 714   virtual FGPositioned::Type minType() const
 715   { return _inner->minType(); }
 716
 717   virtual FGPositioned::Type maxType() const
 718   { return _inner->maxType(); }
 719
 720 private:
 721   std::string _ident;
 722   FGPositioned::Filter* _inner;
 723 };
 724
 725 FGPositionedRef
 726 FGPositioned::findClosestWithPartialId(const SGGeod& aPos, const std::string& aId, Filter* aFilter, int aOffset, bool& aNext)
 727 {
 728   PartialIdentFilter pf(aId, aFilter);
 729   // why aOffset +2 ? at offset=3, we want the fourth search result, but also
 730   // to know if the fifth result exists (to set aNext flag for iterative APIs)
 731   List matches = spatialGetClosest(aPos, aOffset + 2, 1000.0, &pf);
 732
 733   if ((int) matches.size() <= aOffset) {
 734     SG_LOG(SG_GENERAL, SG_INFO, "FGPositioned::findClosestWithPartialId, couldn't match enough with prefix:" << aId);
 735     aNext = false;
 736     return NULL; // couldn't find a match within the cutoff distance
 737   }
 738
 739   aNext = ((int) matches.size() >= (aOffset + 2));
 740   return matches[aOffset];
 741 }
 742