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