gcc warning fixes

[flightgear.git] / src / Navaids / positioned.cxx

diff --git a/src/Navaids/positioned.cxx b/src/Navaids/positioned.cxx
index bc08c4ed16953d98696fd6b7568682d38ad2ac2a..48f284648a7678a7c0ef1203d318ecf592827d23 100644 (file)
--- a/src/Navaids/positioned.cxx
+++ b/src/Navaids/positioned.cxx
@@ -30,11 +30,10 @@
 #include <boost/algorithm/string/case_conv.hpp>
 #include <boost/algorithm/string/predicate.hpp>
 
-#include <simgear/math/sg_geodesy.hxx>
 #include <simgear/timing/timestamp.hxx>
 #include <simgear/debug/logstream.hxx>
 #include <simgear/structure/exception.hxx>
-#include <simgear/math/SGBox.hxx>
+#include <simgear/math/SGGeometry.hxx>
 
 #include "positioned.hxx"
 
@@ -55,27 +54,6 @@ namespace Octree
 const double LEAF_SIZE = SG_NM_TO_METER * 8.0;
 const double LEAF_SIZE_SQR = LEAF_SIZE * LEAF_SIZE;
 
-typedef SGBox<double> SGBoxd;
-
-template<typename T1, typename T2>
-inline bool
-intersects(const SGVec3<T1>& v, const SGBox<T2>& box)
-{
-  if (v[0] < box.getMin()[0])
-    return false;
-  if (box.getMax()[0] < v[0])
-    return false;
-  if (v[1] < box.getMin()[1])
-    return false;
-  if (box.getMax()[1] < v[1])
-    return false;
-  if (v[2] < box.getMin()[2])
-    return false;
-  if (box.getMax()[2] < v[2])
-    return false;
-  return true;
-}
-
 /**
  * Decorate an object with a double value, and use that value to order 
  * items, for the purpoises of the STL algorithms
@@ -156,28 +134,11 @@ public:
 
     double distSqrToNearest(const SGVec3d& aPos) const
     {
-        return distSqr(aPos, getClosestPoint(aPos));
+        return distSqr(aPos, _box.getClosestPoint(aPos));
     }
     
     virtual void insert(FGPositioned* aP) = 0;
     
-    SGVec3d getClosestPoint(const SGVec3d& aPos) const
-    {
-      SGVec3d r;
-      
-      for (unsigned int i=0;i<3; ++i) {
-        if (aPos[i] < _box.getMin()[i]) {
-          r[i] = _box.getMin()[i];
-        } else if (aPos[i] > _box.getMax()[i]) {
-          r[i] = _box.getMax()[i];
-        } else {
-          r[i] = aPos[i];
-        }
-      } // of axis iteration
-      
-      return r;
-    }
-    
     virtual void visit(const SGVec3d& aPos, double aCutoff, 
       FGPositioned::Filter* aFilter, 
       FindNearestResults& aResults, FindNearestPQueue&) = 0;
@@ -210,7 +171,9 @@ public:
       FGPositioned::Filter* aFilter, 
       FindNearestResults& aResults, FindNearestPQueue&)
     {
-        std::vector<Ordered<FGPositioned*> > results;
+        int previousResultsSize = aResults.size();
+        int addedCount = 0;
+        
         for (unsigned int i=0; i<_members.size(); ++i) {
             FGPositioned* p = _members[i];
             double d2 = distSqr(aPos, p->cart());
@@ -228,8 +191,21 @@ public:
               }
             } // of have a filter
 
+            ++addedCount;
             aResults.push_back(OrderedPositioned(p, d2));
         }
+        
+        if (addedCount == 0) {
+          return;
+        }
+        
+      // keep aResults sorted
+        // sort the new items, usually just one or two items
+        std::sort(aResults.begin() + previousResultsSize, aResults.end());
+        
+        // merge the two sorted ranges together - in linear time
+        std::inplace_merge(aResults.begin(), 
+          aResults.begin() + previousResultsSize, aResults.end());
       }
 private:
     FGPositioned::List _members;
@@ -321,9 +297,14 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
     pq.push(Ordered<Node*>(global_spatialOctree, 0));
     double cut = aCutoffM * aCutoffM;
     
-    while (aResults.size() < aN) {
-        if (pq.empty()) {
+    while (!pq.empty()) {
+        if (!results.empty()) {
+          // terminate the search if we have sufficent results, and we are
+          // sure no node still on the queue contains a closer match
+          double furthestResultOrder = results.back().order();
+          if ((results.size() >= aN) && (furthestResultOrder < pq.top().order())) {
             break;
+          }
         }
         
         Node* nd = pq.top().get();
@@ -332,12 +313,9 @@ void findNearestN(const SGVec3d& aPos, unsigned int aN, double aCutoffM, FGPosit
         nd->visit(aPos, cut, aFilter, results, pq);
     } // of queue iteration
     
-  // sort by distance
-    std::sort(results.begin(), results.end());
     // depending on leaf population, we may have (slighty) more results
     // than requested
     unsigned int numResults = std::min((unsigned int) results.size(), aN);
-
   // copy results out
     aResults.resize(numResults);
     for (unsigned int r=0; r<numResults; ++r) {
@@ -360,10 +338,7 @@ void findAllWithinRange(const SGVec3d& aPos, double aRangeM, FGPositioned::Filte
         nd->visit(aPos, rng, aFilter, results, pq);
     } // of queue iteration
     
-  // sort by distance
-    std::sort(results.begin(), results.end());
     unsigned int numResults = results.size();
-
   // copy results out
     aResults.resize(numResults);
     for (unsigned int r=0; r<numResults; ++r) {
@@ -575,13 +550,14 @@ char** searchAirportNamesAndIdents(const std::string& aFilter)
   // We format results as follows (note whitespace!):
   //   ' name-of-airport-chars   (ident)'
   // so the total length is:
-  //    1 + strlen(name) + 4 + 4 (for the ident) + 1 + 1 (for the null)
-  // which gives a grand total of 11 + the length of the name.
-  // note the ident is sometimes only three letters for non-ICAO small strips
+  //    1 + strlen(name) + 4 + strlen(icao) + 1 + 1 (for the null)
+  // which gives a grand total of 7 + name-length + icao-length.
+  // note the ident can be three letters (non-ICAO local strip), four
+  // (default ICAO) or more (extended format ICAO)
   for (unsigned int i=0; i<numMatches; ++i) {
     int nameLength = matches[i]->name().size();
     int icaoLength = matches[i]->ident().size();
-    char* entry = new char[nameLength + 11];
+    char* entry = new char[7 + nameLength + icaoLength];
     char* dst = entry;
     *dst++ = ' ';
     memcpy(dst, matches[i]->name().c_str(), nameLength);
@@ -690,8 +666,8 @@ findWithPartial(const NamedPositionedIndex& aIndex, const std::string& aName,
 ///////////////////////////////////////////////////////////////////////////////
 
 FGPositioned::FGPositioned(Type ty, const std::string& aIdent, const SGGeod& aPos, bool aIndexed) :
-  mType(ty),
   mPosition(aPos),
+  mType(ty),
   mIdent(aIdent)
 {  
   SGReferenced::get(this); // hold an owning ref, for the moment
@@ -714,12 +690,6 @@ FGPositioned::createUserWaypoint(const std::string& aIdent, const SGGeod& aPos)
   return new FGPositioned(WAYPOINT, aIdent, aPos, true);
 }
 
-SGBucket
-FGPositioned::bucket() const
-{
-  return SGBucket(mPosition);
-}
-
 SGVec3d
 FGPositioned::cart() const
 {