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