Changeset 2019 for GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h

Timestamp:

01/23/07 00:11:50 (17 years ago)

Author:

bittner

Message:

merge

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h (modified) (7 diffs)

GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h

@@ -5 +5 @@
 #include <vector>
 #include "common.h"
+#include <math.h>
+using namespace std;
 
 namespace GtpVisibilityPreprocessor {
@@ -171 +173 @@
 
 public:
-
-        Pvs(): mSamples(0), mEntries(), mLastSorted(0) {}
+  
+        Pvs(): mSamples(0), mEntries(), mLastSorted(0), mQueriesSinceSort(0) {}
 
         /** creates pvs and initializes it with the given entries. 
@@ -312 +314 @@
           // the last part should not be more than log of the sorted part. this
           // way we can achieve logarithmic behaviour for insertion and find
-          const int dirtySize = (int)mEntries.size() - mLastSorted;
-          return dirtySize > 500;
-          //              4*(int)(log((double)mEntries.size()) / log(2.0));
+          const int n = mEntries.size();
+          const int dirtySize = n - mLastSorted;
+
+#define LOG2E 1.442695040f
+          
+          const float logN = log((float)max(1, n))/LOG2E;
+          const float logS = log((float)max(1, mLastSorted))/LOG2E;
+          const float logD = log((float)max(1, dirtySize))/LOG2E;
+          
+          if (8*(n + 2*dirtySize*logD) <
+                  mQueriesSinceSort*((mLastSorted*logS + dirtySize*dirtySize/2)/n - logN)) {
+                //              cout<<"Q="<<mQueriesSinceSort<<" N="<<n<<" D="<<dirtySize<<endl;
+                return true;
+          }
+          return false;
         }
 
@@ -342 +356 @@
   
         /// Last sorted entry in the pvs (important for find and merge)
-        int mLastSorted;  
+        int mLastSorted;
+
+  int mQueriesSinceSort;
 };
 
@@ -367 +383 @@
         sort(it, newEnd);
         //sort(mEntries.begin(), mEntries.end());
-
+        
         // now merge sorted ranges
         ObjectPvs newPvs;
         Merge(newPvs, 
-                  mEntries.begin(), it, 
-                  it, newEnd, 
-                  mSamples, 0);
+                  mEntries.begin(),
+                  it, 
+                  it,
+                  newEnd, 
+                  mSamples,
+                  0);
         
         mEntries = newPvs.mEntries;
         mLastSorted = (int)mEntries.size();
+        mQueriesSinceSort = 0;
 }
 
@@ -382 +402 @@
 void Pvs<T, S>::SimpleSort()
 {
-  sort(mEntries.begin(), mEntries.end());
+  //  sort(mEntries.begin(), mEntries.end());
+  std::vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
+  
+  sort(it, mEntries.end());
+  inplace_merge(mEntries.begin(), it, mEntries.end());
+  
   mLastSorted = (int)mEntries.size();
+  mQueriesSinceSort = 0;
 }
 
@@ -610 +636 @@
 {
   PvsEntry<T, S> dummy(sample, PvsData());
+  mQueriesSinceSort++;
   
   // only check clean part