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