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_identIndex;
  86 static NamedPositionedIndex global_nameIndex;
  87 static SpatialPositionedIndex global_spatialIndex;
  88
  89 SpatialPositionedIndex::iterator
  90 bucketEntryForPositioned(FGPositioned* aPos)
  91 {
  92   int bucketIndex = aPos->bucket().gen_index();
  93   SpatialPositionedIndex::iterator it = global_spatialIndex.find(bucketIndex);
  94   if (it != global_spatialIndex.end()) {
  95     return it;
  96   }
  97
  98   // create a new BucketEntry
  99   return global_spatialIndex.insert(it, std::make_pair(bucketIndex, BucketEntry()));
 100 }
 101
 102 static void
 103 addToIndices(FGPositioned* aPos)
 104 {
 105   assert(aPos);
 106   if (!aPos->ident().empty()) {
 107     global_identIndex.insert(global_identIndex.begin(),
 108       std::make_pair(aPos->ident(), aPos));
 109   }
 110
 111   if (!aPos->name().empty()) {
 112     global_nameIndex.insert(global_nameIndex.begin(),
 113                              std::make_pair(aPos->name(), aPos));
 114   }
 115
 116
 117   SpatialPositionedIndex::iterator it = bucketEntryForPositioned(aPos);
 118   it->second.insert(aPos);
 119 }
 120
 121 static void
 122 removeFromIndices(FGPositioned* aPos)
 123 {
 124   assert(aPos);
 125
 126   if (!aPos->ident().empty()) {
 127     NamedPositionedIndex::iterator it = global_identIndex.find(aPos->ident());
 128     while (it != global_identIndex.end() && (it->first == aPos->ident())) {
 129       if (it->second == aPos) {
 130         global_identIndex.erase(it);
 131         break;
 132       }
 133
 134       ++it;
 135     } // of multimap walk
 136   }
 137
 138   if (!aPos->name().empty()) {
 139     NamedPositionedIndex::iterator it = global_nameIndex.find(aPos->name());
 140     while (it != global_nameIndex.end() && (it->first == aPos->name())) {
 141       if (it->second == aPos) {
 142         global_nameIndex.erase(it);
 143         break;
 144       }
 145
 146       ++it;
 147     } // of multimap walk
 148   }
 149
 150   SpatialPositionedIndex::iterator sit = bucketEntryForPositioned(aPos);
 151   sit->second.erase(aPos);
 152 }
 153
 154 static void
 155 spatialFilterInBucket(const SGBucket& aBucket, FGPositioned::Filter* aFilter, FGPositioned::List& aResult)
 156 {
 157   SpatialPositionedIndex::const_iterator it;
 158   it = global_spatialIndex.find(aBucket.gen_index());
 159   if (it == global_spatialIndex.end()) {
 160     return;
 161   }
 162
 163   BucketEntry::const_iterator l = it->second.begin();
 164   BucketEntry::const_iterator u = it->second.end();
 165
 166   if (!aFilter) { // pass everything
 167     aResult.insert(aResult.end(), l, u);
 168     return;
 169   }
 170
 171   if (aFilter->hasTypeRange()) {
 172     // avoid many calls to the filter hook
 173     l = lower_bound(it->second.begin(), it->second.end(), aFilter->minType(), LowerLimitOfType());
 174     u = upper_bound(l, it->second.end(), aFilter->maxType(), LowerLimitOfType());
 175   }
 176
 177   for ( ; l != u; ++l) {
 178     if ((*aFilter)(*l)) {
 179       aResult.push_back(*l);
 180     }
 181   }
 182 }
 183
 184 static void
 185 spatialFind(const SGGeod& aPos, double aRange,
 186   FGPositioned::Filter* aFilter, FGPositioned::List& aResult)
 187 {
 188   SGBucket buck(aPos);
 189   double lat = aPos.getLatitudeDeg(),
 190     lon = aPos.getLongitudeDeg();
 191
 192   int bx = (int)( aRange*SG_NM_TO_METER / buck.get_width_m() / 2);
 193   int by = (int)( aRange*SG_NM_TO_METER / buck.get_height_m() / 2 );
 194
 195   // loop over bucket range
 196   for ( int i=-bx; i<=bx; i++) {
 197     for ( int j=-by; j<=by; j++) {
 198       spatialFilterInBucket(sgBucketOffset(lon, lat, i, j), aFilter, aResult);
 199     } // of j-iteration
 200   } // of i-iteration
 201 }
 202
 203 /**
 204  */
 205 class RangePredictate
 206 {
 207 public:
 208   RangePredictate(const SGGeod& aOrigin, double aRange) :
 209     mOrigin(SGVec3d::fromGeod(aOrigin)),
 210     mRangeSqr(aRange * aRange)
 211   { ; }
 212
 213   bool operator()(const FGPositionedRef& aPos)
 214   {
 215     double dSqr = distSqr(aPos->cart(), mOrigin);
 216     return (dSqr > mRangeSqr);
 217   }
 218
 219 private:
 220   SGVec3d mOrigin;
 221   double mRangeSqr;
 222 };
 223
 224 static void
 225 filterListByRange(const SGGeod& aPos, double aRange, FGPositioned::List& aResult)
 226 {
 227   RangePredictate pred(aPos, aRange * SG_NM_TO_METER);
 228   FGPositioned::List::iterator newEnd;
 229   newEnd = std::remove_if(aResult.begin(), aResult.end(), pred);
 230   aResult.erase(newEnd, aResult.end());
 231 }
 232
 233 class DistanceOrdering
 234 {
 235 public:
 236   DistanceOrdering(const SGGeod& aPos) :
 237     mPos(SGVec3d::fromGeod(aPos))
 238   { }
 239
 240   bool operator()(const FGPositionedRef& a, const FGPositionedRef& b) const
 241   {
 242     double dA = distSqr(a->cart(), mPos),
 243       dB = distSqr(b->cart(), mPos);
 244     return dA < dB;
 245   }
 246
 247 private:
 248   SGVec3d mPos;
 249 };
 250
 251 static void
 252 sortByDistance(const SGGeod& aPos, FGPositioned::List& aResult)
 253 {
 254   std::sort(aResult.begin(), aResult.end(), DistanceOrdering(aPos));
 255 }
 256
 257 static FGPositionedRef
 258 namedFindClosest(const NamedPositionedIndex& aIndex, const std::string& aName,
 259                  const SGGeod& aOrigin, FGPositioned::Filter* aFilter)
 260 {
 261   NamedIndexRange range = aIndex.equal_range(aName);
 262   if (range.first == range.second) {
 263     return NULL;
 264   }
 265
 266 // common case, only one result. looks a bit ugly because these are
 267 // sequential iterators, not random-access ones
 268   NamedPositionedIndex::const_iterator check = range.first;
 269   if (++check == range.second) {
 270     // excellent, only one match in the range
 271     FGPositioned* r = range.first->second;
 272     if (aFilter) {
 273       if (aFilter->hasTypeRange() && !aFilter->passType(r->type())) {
 274         return NULL;
 275       }
 276
 277       if (!aFilter->pass(r)) {
 278         return NULL;
 279       }
 280     } // of have a filter
 281
 282     return r;
 283   } // of short-circuit logic for single-element range
 284
 285 // multiple matches, we need to actually check the distance to each one
 286   double minDist = HUGE_VAL;
 287   FGPositionedRef result;
 288   NamedPositionedIndex::const_iterator it = range.first;
 289   SGVec3d cartOrigin(SGVec3d::fromGeod(aOrigin));
 290
 291   for (; it != range.second; ++it) {
 292     FGPositioned* r = it->second;
 293     if (aFilter) {
 294       if (aFilter->hasTypeRange() && !aFilter->passType(r->type())) {
 295         continue;
 296       }
 297
 298       if (!aFilter->pass(r)) {
 299         continue;
 300       }
 301     }
 302
 303   // find distance
 304     double d2 = distSqr(cartOrigin, r->cart());
 305     if (d2 < minDist) {
 306       minDist = d2;
 307       result = r;
 308     }
 309   }
 310
 311   return result;
 312 }
 313
 314 static FGPositioned::List
 315 spatialGetClosest(const SGGeod& aPos, unsigned int aN, double aCutoffNm, FGPositioned::Filter* aFilter)
 316 {
 317   FGPositioned::List result;
 318   int radius = 1; // start at 1, radius 0 is handled explicitly
 319   SGBucket buck;
 320   double lat = aPos.getLatitudeDeg(),
 321     lon = aPos.getLongitudeDeg();
 322   // final cutoff is in metres, and scaled to account for testing the corners
 323   // of the 'box' instead of the centre of each edge
 324   double cutoffM = aCutoffNm * SG_NM_TO_METER * 1.5;
 325
 326   // base case, simplifes loop to do it seperately here
 327   spatialFilterInBucket(sgBucketOffset(lon, lat, 0, 0), aFilter, result);
 328
 329   for (;result.size() < aN; ++radius) {
 330     // cutoff check
 331     double az1, az2, d1, d2;
 332     SGGeodesy::inverse(aPos, sgBucketOffset(lon, lat, -radius, -radius).get_center(), az1, az2, d1);
 333     SGGeodesy::inverse(aPos, sgBucketOffset(lon, lat, radius, radius).get_center(), az1, az2, d2);
 334
 335     if ((d1 > cutoffM) && (d2 > cutoffM)) {
 336       //std::cerr << "spatialGetClosest terminating due to range cutoff" << std::endl;
 337       break;
 338     }
 339
 340     FGPositioned::List hits;
 341     for ( int i=-radius; i<=radius; i++) {
 342       spatialFilterInBucket(sgBucketOffset(lon, lat, i, -radius), aFilter, hits);
 343       spatialFilterInBucket(sgBucketOffset(lon, lat, -radius, i), aFilter, hits);
 344       spatialFilterInBucket(sgBucketOffset(lon, lat, i, radius), aFilter, hits);
 345       spatialFilterInBucket(sgBucketOffset(lon, lat, radius, i), aFilter, hits);
 346     }
 347
 348     result.insert(result.end(), hits.begin(), hits.end()); // append
 349   } // of outer loop
 350
 351   sortByDistance(aPos, result);
 352   if (result.size() > aN) {
 353     result.resize(aN); // truncate at requested number of matches
 354   }
 355
 356   return result;
 357 }
 358
 359 //////////////////////////////////////////////////////////////////////////////
 360
 361 class OrderByName
 362 {
 363 public:
 364   bool operator()(FGPositioned* a, FGPositioned* b) const
 365   {
 366     return a->name() < b->name();
 367   }
 368 };
 369
 370 /**
 371  * A special purpose helper (imported by FGAirport::searchNamesAndIdents) to
 372  * implement the AirportList dialog. It's unfortunate that it needs to reside
 373  * here, but for now it's least ugly solution.
 374  */
 375 char** searchAirportNamesAndIdents(const std::string& aFilter)
 376 {
 377   const std::ctype<char> &ct = std::use_facet<std::ctype<char> >(std::locale());
 378   std::string filter(aFilter);
 379   bool hasFilter = !filter.empty();
 380   if (hasFilter) {
 381     ct.toupper((char *)filter.data(), (char *)filter.data() + filter.size());
 382   }
 383
 384   NamedPositionedIndex::const_iterator it = global_identIndex.begin();
 385   NamedPositionedIndex::const_iterator end = global_identIndex.end();
 386
 387   // note this is a vector of raw pointers, not smart pointers, because it
 388   // may get very large and smart-pointer-atomicity-locking then becomes a
 389   // bottleneck for this case.
 390   std::vector<FGPositioned*> matches;
 391   std::string upper;
 392
 393   for (; it != end; ++it) {
 394     FGPositioned::Type ty = it->second->type();
 395     if ((ty < FGPositioned::AIRPORT) || (ty > FGPositioned::SEAPORT)) {
 396       continue;
 397     }
 398
 399     if (hasFilter && (it->second->ident().find(aFilter) == std::string::npos)) {
 400       upper = it->second->name(); // string copy, sadly
 401       ct.toupper((char *)upper.data(), (char *)upper.data() + upper.size());
 402       if (upper.find(aFilter) == std::string::npos) {
 403         continue;
 404       }
 405     }
 406
 407     matches.push_back(it->second);
 408   }
 409
 410   // sort alphabetically on name
 411   std::sort(matches.begin(), matches.end(), OrderByName());
 412
 413   // convert results to format comptible with puaList
 414   unsigned int numMatches = matches.size();
 415   char** result = new char*[numMatches + 1];
 416   result[numMatches] = NULL; // end-of-list marker
 417
 418   // nasty code to avoid excessive string copying and allocations.
 419   // We format results as follows (note whitespace!):
 420   //   ' name-of-airport-chars   (ident)'
 421   // so the total length is:
 422   //    1 + strlen(name) + 4 + 4 (for the ident) + 1 + 1 (for the null)
 423   // which gives a grand total of 11 + the length of the name.
 424   // note the ident is sometimes only three letters for non-ICAO small strips
 425   for (unsigned int i=0; i<numMatches; ++i) {
 426     int nameLength = matches[i]->name().size();
 427     int icaoLength = matches[i]->ident().size();
 428     char* entry = new char[nameLength + 11];
 429     char* dst = entry;
 430     *dst++ = ' ';
 431     memcpy(dst, matches[i]->name().c_str(), nameLength);
 432     dst += nameLength;
 433     *dst++ = ' ';
 434     *dst++ = ' ';
 435     *dst++ = ' ';
 436     *dst++ = '(';
 437     memcpy(dst, matches[i]->ident().c_str(), icaoLength);
 438     dst += icaoLength;
 439     *dst++ = ')';
 440     *dst++ = 0;
 441     result[i] = entry;
 442   }
 443
 444   return result;
 445 }
 446
 447 ///////////////////////////////////////////////////////////////////////////////
 448
 449 bool
 450 FGPositioned::Filter::hasTypeRange() const
 451 {
 452   assert(minType() <= maxType());
 453   return (minType() != INVALID) && (maxType() != INVALID);
 454 }
 455
 456 bool
 457 FGPositioned::Filter::passType(Type aTy) const
 458 {
 459   assert(hasTypeRange());
 460   return (minType() <= aTy) && (maxType() >= aTy);
 461 }
 462
 463 static FGPositioned::List
 464 findAllSortedByRange(const NamedPositionedIndex& aIndex,
 465                              const std::string& aName, const SGGeod& aPos, FGPositioned::Filter* aFilter)
 466 {
 467   FGPositioned::List result;
 468   NamedIndexRange range = aIndex.equal_range(aName);
 469   for (; range.first != range.second; ++range.first) {
 470     FGPositioned* candidate = range.first->second;
 471     if (aFilter) {
 472       if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 473         continue;
 474       }
 475
 476       if (!aFilter->pass(candidate)) {
 477         continue;
 478       }
 479     }
 480
 481     result.push_back(range.first->second);
 482   }
 483
 484   sortByDistance(aPos, result);
 485   return result;
 486 }
 487
 488 static FGPositionedRef
 489 findWithPartial(const NamedPositionedIndex& aIndex, const std::string& aName,
 490                     FGPositioned::Filter* aFilter, int aOffset, bool& aNext)
 491 {
 492   // see comment in findNextWithPartialId concerning upperBoundId
 493   std::string upperBoundId = aName;
 494   upperBoundId[upperBoundId.size()-1]++;
 495   NamedPositionedIndex::const_iterator upperBound = aIndex.lower_bound(upperBoundId);
 496
 497   NamedIndexRange range = aIndex.equal_range(aName);
 498   FGPositionedRef result;
 499
 500   while (range.first != upperBound) {
 501     for (; range.first != range.second; ++range.first) {
 502       FGPositionedRef candidate = range.first->second;
 503       if (aFilter) {
 504         if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 505           continue;
 506         }
 507
 508         if (!aFilter->pass(candidate)) {
 509           continue;
 510         }
 511       }
 512
 513       if (result) {
 514         aNext = true;
 515         return result;
 516       } else if (aOffset == 0) {
 517         // okay, found our result. we need to go around once more to set aNext
 518         result = candidate;
 519       } else {
 520         --aOffset; // seen one more valid result, decrement the count
 521       }
 522     }
 523
 524     // Unable to match the filter with this range - try the next range.
 525     range = aIndex.equal_range(range.second->first);
 526   }
 527
 528   // if we fell out, we reached the end of the valid range. We might have a
 529   // valid result, but we definitiely don't have a next result.
 530   aNext = false;
 531   return result;
 532 }
 533
 534 ///////////////////////////////////////////////////////////////////////////////
 535
 536 FGPositioned::FGPositioned(Type ty, const std::string& aIdent, const SGGeod& aPos, bool aIndexed) :
 537   mType(ty),
 538   mPosition(aPos),
 539   mIdent(aIdent)
 540 {
 541   SGReferenced::get(this); // hold an owning ref, for the moment
 542
 543   if (aIndexed) {
 544     assert(ty != TAXIWAY && ty != PAVEMENT);
 545     addToIndices(this);
 546   }
 547 }
 548
 549 FGPositioned::~FGPositioned()
 550 {
 551   //std::cout << "destroying:" << mIdent << "/" << nameForType(mType) << std::endl;
 552   removeFromIndices(this);
 553 }
 554
 555 FGPositioned*
 556 FGPositioned::createUserWaypoint(const std::string& aIdent, const SGGeod& aPos)
 557 {
 558   return new FGPositioned(WAYPOINT, aIdent, aPos, true);
 559 }
 560
 561 SGBucket
 562 FGPositioned::bucket() const
 563 {
 564   return SGBucket(mPosition);
 565 }
 566
 567 SGVec3d
 568 FGPositioned::cart() const
 569 {
 570   return SGVec3d::fromGeod(mPosition);
 571 }
 572
 573 FGPositioned::Type FGPositioned::typeFromName(const std::string& aName)
 574 {
 575   if (aName.empty() || (aName == "")) {
 576     return INVALID;
 577   }
 578
 579   typedef struct {
 580     const char* _name;
 581     Type _ty;
 582   } NameTypeEntry;
 583
 584   const NameTypeEntry names[] = {
 585     {"airport", AIRPORT},
 586     {"vor", VOR},
 587     {"ndb", NDB},
 588     {"wpt", WAYPOINT},
 589     {"fix", FIX},
 590     {"tacan", TACAN},
 591     {"dme", DME},
 592   // aliases
 593     {"waypoint", WAYPOINT},
 594     {"apt", AIRPORT},
 595     {"any", INVALID},
 596     {"all", INVALID},
 597
 598     {NULL, INVALID}
 599   };
 600
 601   std::string lowerName(boost::to_lower_copy(aName));
 602
 603   for (const NameTypeEntry* n = names; (n->_name != NULL); ++n) {
 604     if (::strcmp(n->_name, lowerName.c_str()) == 0) {
 605       return n->_ty;
 606     }
 607   }
 608
 609   SG_LOG(SG_GENERAL, SG_WARN, "FGPositioned::typeFromName: couldn't match:" << aName);
 610   return INVALID;
 611 }
 612
 613 const char* FGPositioned::nameForType(Type aTy)
 614 {
 615  switch (aTy) {
 616  case RUNWAY: return "runway";
 617  case TAXIWAY: return "taxiway";
 618  case PAVEMENT: return "pavement";
 619  case PARK_STAND: return "parking stand";
 620  case FIX: return "fix";
 621  case VOR: return "VOR";
 622  case NDB: return "NDB";
 623  case ILS: return "ILS";
 624  case LOC: return "localiser";
 625  case GS: return "glideslope";
 626  case OM: return "outer-marker";
 627  case MM: return "middle-marker";
 628  case IM: return "inner-marker";
 629  case AIRPORT: return "airport";
 630  case HELIPORT: return "heliport";
 631  case SEAPORT: return "seaport";
 632  case WAYPOINT: return "waypoint";
 633  case DME: return "dme";
 634  case TACAN: return "tacan";
 635  default:
 636   return "unknown";
 637  }
 638 }
 639
 640 ///////////////////////////////////////////////////////////////////////////////
 641 // search / query functions
 642
 643 FGPositionedRef
 644 FGPositioned::findClosestWithIdent(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter)
 645 {
 646   return namedFindClosest(global_identIndex, aIdent, aPos, aFilter);
 647 }
 648
 649 FGPositioned::List
 650 FGPositioned::findWithinRange(const SGGeod& aPos, double aRangeNm, Filter* aFilter)
 651 {
 652   List result;
 653   spatialFind(aPos, aRangeNm, aFilter, result);
 654   filterListByRange(aPos, aRangeNm, result);
 655   return result;
 656 }
 657
 658 FGPositioned::List
 659 FGPositioned::findAllWithIdentSortedByRange(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter)
 660 {
 661   return findAllSortedByRange(global_identIndex, aIdent, aPos, aFilter);
 662 }
 663
 664 FGPositioned::List
 665 FGPositioned::findAllWithNameSortedByRange(const std::string& aName, const SGGeod& aPos, Filter* aFilter)
 666 {
 667   return findAllSortedByRange(global_nameIndex, aName, aPos, aFilter);
 668 }
 669
 670 FGPositionedRef
 671 FGPositioned::findClosest(const SGGeod& aPos, double aCutoffNm, Filter* aFilter)
 672 {
 673    FGPositioned::List l(spatialGetClosest(aPos, 1, aCutoffNm, aFilter));
 674    if (l.empty()) {
 675       return NULL;
 676    }
 677
 678    assert(l.size() == 1);
 679    return l.front();
 680 }
 681
 682 FGPositioned::List
 683 FGPositioned::findClosestN(const SGGeod& aPos, unsigned int aN, double aCutoffNm, Filter* aFilter)
 684 {
 685   return spatialGetClosest(aPos, aN, aCutoffNm, aFilter);
 686 }
 687
 688 FGPositionedRef
 689 FGPositioned::findNextWithPartialId(FGPositionedRef aCur, const std::string& aId, Filter* aFilter)
 690 {
 691   // It is essential to bound our search, to avoid iterating all the way to the end of the database.
 692   // Do this by generating a second ID with the final character incremented by 1.
 693   // e.g., if the partial ID is "KI", we wish to search "KIxxx" but not "KJ".
 694   std::string upperBoundId = aId;
 695   upperBoundId[upperBoundId.size()-1]++;
 696   NamedPositionedIndex::const_iterator upperBound = global_identIndex.lower_bound(upperBoundId);
 697
 698   NamedIndexRange range = global_identIndex.equal_range(aId);
 699   while (range.first != upperBound) {
 700     for (; range.first != range.second; ++range.first) {
 701       FGPositionedRef candidate = range.first->second;
 702       if (aCur == candidate) {
 703         aCur = NULL; // found our start point, next match will pass
 704         continue;
 705       }
 706
 707       if (aFilter) {
 708         if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 709           continue;
 710         }
 711
 712         if (!aFilter->pass(candidate)) {
 713           continue;
 714         }
 715       }
 716
 717       if (!aCur) {
 718         return candidate;
 719       }
 720     }
 721
 722     // Unable to match the filter with this range - try the next range.
 723     range = global_identIndex.equal_range(range.second->first);
 724   }
 725
 726   return NULL; // Reached the end of the valid sequence with no match.
 727 }
 728
 729 FGPositionedRef
 730 FGPositioned::findWithPartialId(const std::string& aId, Filter* aFilter, int aOffset, bool& aNext)
 731 {
 732   return findWithPartial(global_identIndex, aId, aFilter, aOffset, aNext);
 733 }
 734
 735
 736 FGPositionedRef
 737 FGPositioned::findWithPartialName(const std::string& aName, Filter* aFilter, int aOffset, bool& aNext)
 738 {
 739   return findWithPartial(global_nameIndex, aName, aFilter, aOffset, aNext);
 740 }
 741
 742 /**
 743  * Wrapper filter which proxies to an inner filter, but also ensures the
 744  * ident starts with supplied partial ident.
 745  */
 746 class PartialIdentFilter : public FGPositioned::Filter
 747 {
 748 public:
 749   PartialIdentFilter(const std::string& ident, FGPositioned::Filter* filter) :
 750     _inner(filter)
 751   {
 752     _ident = boost::to_upper_copy(ident);
 753   }
 754
 755   virtual bool pass(FGPositioned* aPos) const
 756   {
 757     if (!_inner->pass(aPos)) {
 758       return false;
 759     }
 760
 761     return (::strncmp(aPos->ident().c_str(), _ident.c_str(), _ident.size()) == 0);
 762   }
 763
 764   virtual FGPositioned::Type minType() const
 765   { return _inner->minType(); }
 766
 767   virtual FGPositioned::Type maxType() const
 768   { return _inner->maxType(); }
 769
 770 private:
 771   std::string _ident;
 772   FGPositioned::Filter* _inner;
 773 };
 774
 775 static FGPositionedRef
 776 findClosestWithPartial(const SGGeod& aPos, FGPositioned::Filter* aFilter, int aOffset, bool& aNext)
 777 {
 778   // why aOffset +2 ? at offset=3, we want the fourth search result, but also
 779   // to know if the fifth result exists (to set aNext flag for iterative APIs)
 780   FGPositioned::List matches =
 781     spatialGetClosest(aPos, aOffset + 2, 1000.0, aFilter);
 782
 783   if ((int) matches.size() <= aOffset) {
 784     SG_LOG(SG_GENERAL, SG_INFO, "findClosestWithPartial, couldn't match enough with prefix");
 785     aNext = false;
 786     return NULL; // couldn't find a match within the cutoff distance
 787   }
 788
 789   aNext = ((int) matches.size() >= (aOffset + 2));
 790   return matches[aOffset];
 791
 792 }
 793
 794 FGPositionedRef
 795 FGPositioned::findClosestWithPartialId(const SGGeod& aPos, const std::string& aId, Filter* aFilter, int aOffset, bool& aNext)
 796 {
 797   PartialIdentFilter pf(aId, aFilter);
 798   return findClosestWithPartial(aPos, &pf, aOffset, aNext);
 799 }
 800
 801 /**
 802  * Wrapper filter which proxies to an inner filter, but also ensures the
 803  * name starts with supplied partial name.
 804  */
 805 class PartialNameFilter : public FGPositioned::Filter
 806 {
 807 public:
 808   PartialNameFilter(const std::string& nm, FGPositioned::Filter* filter) :
 809   _inner(filter)
 810   {
 811     _name = nm;
 812   }
 813
 814   virtual bool pass(FGPositioned* aPos) const
 815   {
 816     if (!_inner->pass(aPos)) {
 817       return false;
 818     }
 819
 820     return (::strncasecmp(aPos->name().c_str(), _name.c_str(), _name.size()) == 0);
 821   }
 822
 823   virtual FGPositioned::Type minType() const
 824   { return _inner->minType(); }
 825
 826   virtual FGPositioned::Type maxType() const
 827   { return _inner->maxType(); }
 828
 829 private:
 830   std::string _name;
 831   FGPositioned::Filter* _inner;
 832 };
 833
 834 FGPositionedRef
 835 FGPositioned::findClosestWithPartialName(const SGGeod& aPos, const std::string& aName, Filter* aFilter, int aOffset, bool& aNext)
 836 {
 837   PartialNameFilter pf(aName, aFilter);
 838   return findClosestWithPartial(aPos, &pf, aOffset, aNext);
 839 }
 840