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 "positioned.hxx"
  26
  27 #include <map>
  28 #include <set>
  29 #include <algorithm> // for sort
  30 #include <queue>
  31
  32 #include <boost/algorithm/string/case_conv.hpp>
  33 #include <boost/algorithm/string/predicate.hpp>
  34
  35 #include <simgear/timing/timestamp.hxx>
  36 #include <simgear/debug/logstream.hxx>
  37 #include <simgear/structure/exception.hxx>
  38 #include <simgear/math/SGGeometry.hxx>
  39
  40
  41
  42 typedef std::multimap<std::string, FGPositioned*> NamedPositionedIndex;
  43 typedef std::pair<NamedPositionedIndex::const_iterator, NamedPositionedIndex::const_iterator> NamedIndexRange;
  44
  45 using std::lower_bound;
  46 using std::upper_bound;
  47
  48 static NamedPositionedIndex global_identIndex;
  49 static NamedPositionedIndex global_nameIndex;
  50
  51 //////////////////////////////////////////////////////////////////////////////
  52
  53 namespace Octree
  54 {
  55
  56 const double LEAF_SIZE = SG_NM_TO_METER * 8.0;
  57 const double LEAF_SIZE_SQR = LEAF_SIZE * LEAF_SIZE;
  58
  59 /**
  60  * Decorate an object with a double value, and use that value to order
  61  * items, for the purpoises of the STL algorithms
  62  */
  63 template <class T>
  64 class Ordered
  65 {
  66 public:
  67     Ordered(const T& v, double x) :
  68         _order(x),
  69         _inner(v)
  70     {
  71     }
  72
  73     Ordered(const Ordered<T>& a) :
  74         _order(a._order),
  75         _inner(a._inner)
  76     {
  77     }
  78
  79     Ordered<T>& operator=(const Ordered<T>& a)
  80     {
  81         _order = a._order;
  82         _inner = a._inner;
  83         return *this;
  84     }
  85
  86     bool operator<(const Ordered<T>& other) const
  87     {
  88         return _order < other._order;
  89     }
  90
  91     bool operator>(const Ordered<T>& other) const
  92     {
  93         return _order > other._order;
  94     }
  95
  96     const T& get() const
  97         { return _inner; }
  98
  99     double order() const
 100         { return _order; }
 101
 102 private:
 103     double _order;
 104     T _inner;
 105 };
 106
 107 class Node;
 108 typedef Ordered<Node*> OrderedNode;
 109 typedef std::greater<OrderedNode> FNPQCompare;
 110
 111 /**
 112  * the priority queue is fundamental to our search algorithm. When searching,
 113  * we know the front of the queue is the nearest unexpanded node (to the search
 114  * location). The default STL pqueue returns the 'largest' item from top(), so
 115  * to get the smallest, we need to replace the default Compare functor (less<>)
 116  * with greater<>.
 117  */
 118 typedef std::priority_queue<OrderedNode, std::vector<OrderedNode>, FNPQCompare> FindNearestPQueue;
 119
 120 typedef Ordered<FGPositioned*> OrderedPositioned;
 121 typedef std::vector<OrderedPositioned> FindNearestResults;
 122
 123 Node* global_spatialOctree = NULL;
 124
 125 /**
 126  * Octree node base class, tracks its bounding box and provides various
 127  * queries relating to it
 128  */
 129 class Node
 130 {
 131 public:
 132     bool contains(const SGVec3d& aPos) const
 133     {
 134         return intersects(aPos, _box);
 135     }
 136
 137     double distSqrToNearest(const SGVec3d& aPos) const
 138     {
 139         return distSqr(aPos, _box.getClosestPoint(aPos));
 140     }
 141
 142     virtual void insert(FGPositioned* aP) = 0;
 143
 144     virtual void visit(const SGVec3d& aPos, double aCutoff,
 145       FGPositioned::Filter* aFilter,
 146       FindNearestResults& aResults, FindNearestPQueue&) = 0;
 147 protected:
 148     Node(const SGBoxd &aBox) :
 149         _box(aBox)
 150     {
 151     }
 152
 153     const SGBoxd _box;
 154 };
 155
 156 class Leaf : public Node
 157 {
 158 public:
 159     Leaf(const SGBoxd& aBox) :
 160         Node(aBox)
 161     {
 162     }
 163
 164     const FGPositioned::List& members() const
 165     { return _members; }
 166
 167     virtual void insert(FGPositioned* aP)
 168     {
 169         _members.push_back(aP);
 170     }
 171
 172     virtual void visit(const SGVec3d& aPos, double aCutoff,
 173       FGPositioned::Filter* aFilter,
 174       FindNearestResults& aResults, FindNearestPQueue&)
 175     {
 176         int previousResultsSize = aResults.size();
 177         int addedCount = 0;
 178
 179         for (unsigned int i=0; i<_members.size(); ++i) {
 180             FGPositioned* p = _members[i];
 181             double d2 = distSqr(aPos, p->cart());
 182             if (d2 > aCutoff) {
 183                 continue;
 184             }
 185
 186             if (aFilter) {
 187               if (aFilter->hasTypeRange() && !aFilter->passType(p->type())) {
 188                 continue;
 189               }
 190
 191               if (!aFilter->pass(p)) {
 192                 continue;
 193               }
 194             } // of have a filter
 195
 196             ++addedCount;
 197             aResults.push_back(OrderedPositioned(p, d2));
 198         }
 199
 200         if (addedCount == 0) {
 201           return;
 202         }
 203
 204       // keep aResults sorted
 205         // sort the new items, usually just one or two items
 206         std::sort(aResults.begin() + previousResultsSize, aResults.end());
 207
 208         // merge the two sorted ranges together - in linear time
 209         std::inplace_merge(aResults.begin(),
 210           aResults.begin() + previousResultsSize, aResults.end());
 211       }
 212 private:
 213     FGPositioned::List _members;
 214 };
 215
 216 class Branch : public Node
 217 {
 218 public:
 219     Branch(const SGBoxd& aBox) :
 220         Node(aBox)
 221     {
 222         memset(children, 0, sizeof(Node*) * 8);
 223     }
 224
 225     virtual void insert(FGPositioned* aP)
 226     {
 227         SGVec3d cart(aP->cart());
 228         assert(contains(cart));
 229         int childIndex = 0;
 230
 231         SGVec3d center(_box.getCenter());
 232     // tests must match indices in SGbox::getCorner
 233         if (cart.x() < center.x()) {
 234             childIndex += 1;
 235         }
 236
 237         if (cart.y() < center.y()) {
 238             childIndex += 2;
 239         }
 240
 241         if (cart.z() < center.z()) {
 242             childIndex += 4;
 243         }
 244
 245         Node* child = children[childIndex];
 246         if (!child) { // lazy building of children
 247             SGBoxd cb(boxForChild(childIndex));
 248             double d2 = dot(cb.getSize(), cb.getSize());
 249             if (d2 < LEAF_SIZE_SQR) {
 250                 child = new Leaf(cb);
 251             } else {
 252                 child = new Branch(cb);
 253             }
 254
 255             children[childIndex] = child;
 256         }
 257
 258         child->insert(aP);
 259     }
 260
 261     virtual void visit(const SGVec3d& aPos, double aCutoff,
 262       FGPositioned::Filter*,
 263       FindNearestResults&, FindNearestPQueue& aQ)
 264     {
 265         for (unsigned int i=0; i<8; ++i) {
 266             if (!children[i]) {
 267                 continue;
 268             }
 269
 270             double d2 = children[i]->distSqrToNearest(aPos);
 271             if (d2 > aCutoff) {
 272                 continue; // exceeded cutoff
 273             }
 274
 275             aQ.push(Ordered<Node*>(children[i], d2));
 276         } // of child iteration
 277     }
 278
 279
 280 private:
 281     /**
 282      * Return the box for a child touching the specified corner
 283      */
 284     SGBoxd boxForChild(unsigned int aCorner) const
 285     {
 286         SGBoxd r(_box.getCenter());
 287         r.expandBy(_box.getCorner(aCorner));
 288         return r;
 289     }
 290
 291     Node* children[8];
 292 };
 293
 294 void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults)
 295 {
 296     aResults.clear();
 297     FindNearestPQueue pq;
 298     FindNearestResults results;
 299     pq.push(Ordered<Node*>(global_spatialOctree, 0));
 300     double cut = aCutoffM * aCutoffM;
 301
 302     while (!pq.empty()) {
 303         if (!results.empty()) {
 304           // terminate the search if we have sufficent results, and we are
 305           // sure no node still on the queue contains a closer match
 306           double furthestResultOrder = results.back().order();
 307           if ((results.size() >= aN) && (furthestResultOrder < pq.top().order())) {
 308             break;
 309           }
 310         }
 311
 312         Node* nd = pq.top().get();
 313         pq.pop();
 314
 315         nd->visit(aPos, cut, aFilter, results, pq);
 316     } // of queue iteration
 317
 318     // depending on leaf population, we may have (slighty) more results
 319     // than requested
 320     unsigned int numResults = std::min((unsigned int) results.size(), aN);
 321   // copy results out
 322     aResults.resize(numResults);
 323     for (unsigned int r=0; r<numResults; ++r) {
 324       aResults[r] = results[r].get();
 325     }
 326 }
 327
 328 void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filter* aFilter, FGPositioned::List& aResults)
 329 {
 330     aResults.clear();
 331     FindNearestPQueue pq;
 332     FindNearestResults results;
 333     pq.push(Ordered<Node*>(global_spatialOctree, 0));
 334     double rng = aRangeM * aRangeM;
 335
 336     while (!pq.empty()) {
 337         Node* nd = pq.top().get();
 338         pq.pop();
 339
 340         nd->visit(aPos, rng, aFilter, results, pq);
 341     } // of queue iteration
 342
 343     unsigned int numResults = results.size();
 344   // copy results out
 345     aResults.resize(numResults);
 346     for (unsigned int r=0; r<numResults; ++r) {
 347       aResults[r] = results[r].get();
 348     }
 349 }
 350
 351 } // of namespace Octree
 352
 353 //////////////////////////////////////////////////////////////////////////////
 354
 355 static void
 356 addToIndices(FGPositioned* aPos)
 357 {
 358   assert(aPos);
 359   if (!aPos->ident().empty()) {
 360     global_identIndex.insert(global_identIndex.begin(),
 361       std::make_pair(aPos->ident(), aPos));
 362   }
 363
 364   if (!aPos->name().empty()) {
 365     global_nameIndex.insert(global_nameIndex.begin(),
 366                              std::make_pair(aPos->name(), aPos));
 367   }
 368
 369   if (!Octree::global_spatialOctree) {
 370     double RADIUS_EARTH_M = 7000 * 1000.0; // 7000km is plenty
 371     SGVec3d earthExtent(RADIUS_EARTH_M, RADIUS_EARTH_M, RADIUS_EARTH_M);
 372     Octree::global_spatialOctree = new Octree::Branch(SGBox<double>(-earthExtent, earthExtent));
 373   }
 374   Octree::global_spatialOctree->insert(aPos);
 375 }
 376
 377 static void
 378 removeFromIndices(FGPositioned* aPos)
 379 {
 380   assert(aPos);
 381
 382   if (!aPos->ident().empty()) {
 383     NamedPositionedIndex::iterator it = global_identIndex.find(aPos->ident());
 384     while (it != global_identIndex.end() && (it->first == aPos->ident())) {
 385       if (it->second == aPos) {
 386         global_identIndex.erase(it);
 387         break;
 388       }
 389
 390       ++it;
 391     } // of multimap walk
 392   }
 393
 394   if (!aPos->name().empty()) {
 395     NamedPositionedIndex::iterator it = global_nameIndex.find(aPos->name());
 396     while (it != global_nameIndex.end() && (it->first == aPos->name())) {
 397       if (it->second == aPos) {
 398         global_nameIndex.erase(it);
 399         break;
 400       }
 401
 402       ++it;
 403     } // of multimap walk
 404   }
 405 }
 406
 407 //////////////////////////////////////////////////////////////////////////////
 408
 409 class OrderByName
 410 {
 411 public:
 412   bool operator()(FGPositioned* a, FGPositioned* b) const
 413   {
 414     return a->name() < b->name();
 415   }
 416 };
 417
 418 /**
 419  * A special purpose helper (imported by FGAirport::searchNamesAndIdents) to
 420  * implement the AirportList dialog. It's unfortunate that it needs to reside
 421  * here, but for now it's least ugly solution.
 422  */
 423 char** searchAirportNamesAndIdents(const std::string& aFilter)
 424 {
 425   const std::ctype<char> &ct = std::use_facet<std::ctype<char> >(std::locale());
 426   std::string filter(aFilter);
 427   bool hasFilter = !filter.empty();
 428   if (hasFilter) {
 429     ct.toupper((char *)filter.data(), (char *)filter.data() + filter.size());
 430   }
 431
 432   NamedPositionedIndex::const_iterator it = global_identIndex.begin();
 433   NamedPositionedIndex::const_iterator end = global_identIndex.end();
 434
 435   // note this is a vector of raw pointers, not smart pointers, because it
 436   // may get very large and smart-pointer-atomicity-locking then becomes a
 437   // bottleneck for this case.
 438   std::vector<FGPositioned*> matches;
 439   std::string upper;
 440
 441   for (; it != end; ++it) {
 442     FGPositioned::Type ty = it->second->type();
 443     if ((ty < FGPositioned::AIRPORT) || (ty > FGPositioned::SEAPORT)) {
 444       continue;
 445     }
 446
 447     if (hasFilter && (it->second->ident().find(aFilter) == std::string::npos)) {
 448       upper = it->second->name(); // string copy, sadly
 449       ct.toupper((char *)upper.data(), (char *)upper.data() + upper.size());
 450       if (upper.find(aFilter) == std::string::npos) {
 451         continue;
 452       }
 453     }
 454
 455     matches.push_back(it->second);
 456   }
 457
 458   // sort alphabetically on name
 459   std::sort(matches.begin(), matches.end(), OrderByName());
 460
 461   // convert results to format comptible with puaList
 462   unsigned int numMatches = matches.size();
 463   char** result = new char*[numMatches + 1];
 464   result[numMatches] = NULL; // end-of-list marker
 465
 466   // nasty code to avoid excessive string copying and allocations.
 467   // We format results as follows (note whitespace!):
 468   //   ' name-of-airport-chars   (ident)'
 469   // so the total length is:
 470   //    1 + strlen(name) + 4 + strlen(icao) + 1 + 1 (for the null)
 471   // which gives a grand total of 7 + name-length + icao-length.
 472   // note the ident can be three letters (non-ICAO local strip), four
 473   // (default ICAO) or more (extended format ICAO)
 474   for (unsigned int i=0; i<numMatches; ++i) {
 475     int nameLength = matches[i]->name().size();
 476     int icaoLength = matches[i]->ident().size();
 477     char* entry = new char[7 + nameLength + icaoLength];
 478     char* dst = entry;
 479     *dst++ = ' ';
 480     memcpy(dst, matches[i]->name().c_str(), nameLength);
 481     dst += nameLength;
 482     *dst++ = ' ';
 483     *dst++ = ' ';
 484     *dst++ = ' ';
 485     *dst++ = '(';
 486     memcpy(dst, matches[i]->ident().c_str(), icaoLength);
 487     dst += icaoLength;
 488     *dst++ = ')';
 489     *dst++ = 0;
 490     result[i] = entry;
 491   }
 492
 493   return result;
 494 }
 495
 496 ///////////////////////////////////////////////////////////////////////////////
 497
 498 bool
 499 FGPositioned::Filter::hasTypeRange() const
 500 {
 501   assert(minType() <= maxType());
 502   return (minType() != INVALID) && (maxType() != INVALID);
 503 }
 504
 505 bool
 506 FGPositioned::Filter::passType(Type aTy) const
 507 {
 508   assert(hasTypeRange());
 509   return (minType() <= aTy) && (maxType() >= aTy);
 510 }
 511
 512 static FGPositioned::List
 513 findAll(const NamedPositionedIndex& aIndex,
 514                              const std::string& aName, FGPositioned::Filter* aFilter)
 515 {
 516   FGPositioned::List result;
 517   if (aName.empty()) {
 518     return result;
 519   }
 520
 521   std::string upperBoundId = aName;
 522   upperBoundId[upperBoundId.size()-1]++;
 523   NamedPositionedIndex::const_iterator upperBound = aIndex.lower_bound(upperBoundId);
 524   NamedPositionedIndex::const_iterator it = aIndex.lower_bound(aName);
 525
 526   for (; it != upperBound; ++it) {
 527     FGPositionedRef candidate = it->second;
 528     if (aFilter) {
 529       if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 530         continue;
 531       }
 532
 533       if (!aFilter->pass(candidate)) {
 534         continue;
 535       }
 536     }
 537
 538     result.push_back(candidate);
 539   }
 540
 541   return result;
 542 }
 543
 544 ///////////////////////////////////////////////////////////////////////////////
 545
 546 FGPositioned::FGPositioned(Type ty, const std::string& aIdent, const SGGeod& aPos) :
 547   mPosition(aPos),
 548   mType(ty),
 549   mIdent(aIdent)
 550 {
 551 }
 552
 553 void FGPositioned::init(bool aIndexed)
 554 {
 555   SGReferenced::get(this); // hold an owning ref, for the moment
 556   mCart = SGVec3d::fromGeod(mPosition);
 557
 558   if (aIndexed) {
 559     assert(mType != TAXIWAY && mType != PAVEMENT);
 560     addToIndices(this);
 561   }
 562 }
 563
 564 FGPositioned::~FGPositioned()
 565 {
 566   //std::cout << "destroying:" << mIdent << "/" << nameForType(mType) << std::endl;
 567   removeFromIndices(this);
 568 }
 569
 570 FGPositioned*
 571 FGPositioned::createUserWaypoint(const std::string& aIdent, const SGGeod& aPos)
 572 {
 573   FGPositioned* wpt = new FGPositioned(WAYPOINT, aIdent, aPos);
 574   wpt->init(true);
 575   return wpt;
 576 }
 577
 578 const SGVec3d&
 579 FGPositioned::cart() const
 580 {
 581   return mCart;
 582 }
 583
 584 FGPositioned::Type FGPositioned::typeFromName(const std::string& aName)
 585 {
 586   if (aName.empty() || (aName == "")) {
 587     return INVALID;
 588   }
 589
 590   typedef struct {
 591     const char* _name;
 592     Type _ty;
 593   } NameTypeEntry;
 594
 595   const NameTypeEntry names[] = {
 596     {"airport", AIRPORT},
 597     {"vor", VOR},
 598     {"ndb", NDB},
 599     {"wpt", WAYPOINT},
 600     {"fix", FIX},
 601     {"tacan", TACAN},
 602     {"dme", DME},
 603   // aliases
 604     {"waypoint", WAYPOINT},
 605     {"apt", AIRPORT},
 606     {"arpt", AIRPORT},
 607     {"any", INVALID},
 608     {"all", INVALID},
 609
 610     {NULL, INVALID}
 611   };
 612
 613   std::string lowerName(boost::to_lower_copy(aName));
 614
 615   for (const NameTypeEntry* n = names; (n->_name != NULL); ++n) {
 616     if (::strcmp(n->_name, lowerName.c_str()) == 0) {
 617       return n->_ty;
 618     }
 619   }
 620
 621   SG_LOG(SG_GENERAL, SG_WARN, "FGPositioned::typeFromName: couldn't match:" << aName);
 622   return INVALID;
 623 }
 624
 625 const char* FGPositioned::nameForType(Type aTy)
 626 {
 627  switch (aTy) {
 628  case RUNWAY: return "runway";
 629  case TAXIWAY: return "taxiway";
 630  case PAVEMENT: return "pavement";
 631  case PARK_STAND: return "parking stand";
 632  case FIX: return "fix";
 633  case VOR: return "VOR";
 634  case NDB: return "NDB";
 635  case ILS: return "ILS";
 636  case LOC: return "localiser";
 637  case GS: return "glideslope";
 638  case OM: return "outer-marker";
 639  case MM: return "middle-marker";
 640  case IM: return "inner-marker";
 641  case AIRPORT: return "airport";
 642  case HELIPORT: return "heliport";
 643  case SEAPORT: return "seaport";
 644  case WAYPOINT: return "waypoint";
 645  case DME: return "dme";
 646  case TACAN: return "tacan";
 647  default:
 648   return "unknown";
 649  }
 650 }
 651
 652 ///////////////////////////////////////////////////////////////////////////////
 653 // search / query functions
 654
 655 FGPositionedRef
 656 FGPositioned::findClosestWithIdent(const std::string& aIdent, const SGGeod& aPos, Filter* aFilter)
 657 {
 658   FGPositioned::List r(findAll(global_identIndex, aIdent, aFilter));
 659   if (r.empty()) {
 660     return FGPositionedRef();
 661   }
 662
 663   sortByRange(r, aPos);
 664   return r.front();
 665 }
 666
 667 FGPositioned::List
 668 FGPositioned::findWithinRange(const SGGeod& aPos, double aRangeNm, Filter* aFilter)
 669 {
 670   List result;
 671   Octree::findAllWithinRange(SGVec3d::fromGeod(aPos),
 672     aRangeNm * SG_NM_TO_METER, aFilter, result);
 673   return result;
 674 }
 675
 676 FGPositioned::List
 677 FGPositioned::findAllWithIdent(const std::string& aIdent, Filter* aFilter)
 678 {
 679   return findAll(global_identIndex, aIdent, aFilter);
 680 }
 681
 682 FGPositioned::List
 683 FGPositioned::findAllWithName(const std::string& aName, Filter* aFilter)
 684 {
 685   return findAll(global_nameIndex, aName, aFilter);
 686 }
 687
 688 FGPositionedRef
 689 FGPositioned::findClosest(const SGGeod& aPos, double aCutoffNm, Filter* aFilter)
 690 {
 691    List l(findClosestN(aPos, 1, aCutoffNm, aFilter));
 692    if (l.empty()) {
 693       return NULL;
 694    }
 695
 696    assert(l.size() == 1);
 697    return l.front();
 698 }
 699
 700 FGPositioned::List
 701 FGPositioned::findClosestN(const SGGeod& aPos, unsigned int aN, double aCutoffNm, Filter* aFilter)
 702 {
 703   List result;
 704   Octree::findNearestN(SGVec3d::fromGeod(aPos), aN, aCutoffNm * SG_NM_TO_METER, aFilter, result);
 705   return result;
 706 }
 707
 708 FGPositionedRef
 709 FGPositioned::findNextWithPartialId(FGPositionedRef aCur, const std::string& aId, Filter* aFilter)
 710 {
 711   if (aId.empty()) {
 712     return NULL;
 713   }
 714
 715   std::string id(boost::to_upper_copy(aId));
 716
 717   // It is essential to bound our search, to avoid iterating all the way to the end of the database.
 718   // Do this by generating a second ID with the final character incremented by 1.
 719   // e.g., if the partial ID is "KI", we wish to search "KIxxx" but not "KJ".
 720   std::string upperBoundId = id;
 721   upperBoundId[upperBoundId.size()-1]++;
 722   NamedPositionedIndex::const_iterator upperBound = global_identIndex.lower_bound(upperBoundId);
 723
 724   NamedIndexRange range = global_identIndex.equal_range(id);
 725   while (range.first != upperBound) {
 726     for (; range.first != range.second; ++range.first) {
 727       FGPositionedRef candidate = range.first->second;
 728       if (aCur == candidate) {
 729         aCur = NULL; // found our start point, next match will pass
 730         continue;
 731       }
 732
 733       if (aFilter) {
 734         if (aFilter->hasTypeRange() && !aFilter->passType(candidate->type())) {
 735           continue;
 736         }
 737
 738         if (!aFilter->pass(candidate)) {
 739           continue;
 740         }
 741       }
 742
 743       if (!aCur) {
 744         return candidate;
 745       }
 746     }
 747
 748     // Unable to match the filter with this range - try the next range.
 749     range = global_identIndex.equal_range(range.second->first);
 750   }
 751
 752   return NULL; // Reached the end of the valid sequence with no match.
 753 }
 754
 755 void
 756 FGPositioned::sortByRange(List& aResult, const SGGeod& aPos)
 757 {
 758   SGVec3d cartPos(SGVec3d::fromGeod(aPos));
 759 // computer ordering values
 760   Octree::FindNearestResults r;
 761   List::iterator it = aResult.begin(), lend = aResult.end();
 762   for (; it != lend; ++it) {
 763     double d2 = distSqr((*it)->cart(), cartPos);
 764     r.push_back(Octree::OrderedPositioned(*it, d2));
 765   }
 766
 767 // sort
 768   std::sort(r.begin(), r.end());
 769
 770 // convert to a plain list
 771   unsigned int count = aResult.size();
 772   for (unsigned int i=0; i<count; ++i) {
 773     aResult[i] = r[i].get();
 774   }
 775 }