Changeset 3297

Timestamp:

11/06/09 13:58:45 (2 weeks ago)

Author:

kraftche

Message:

Speed up range-based get_adjacencies:

Initial time: 11.92 s
After MBCore changes: 9.42 s
After MBRange changes: 9.32 s

MBCore: more intellegent merges/intersect of range-based data
MBRange: insert single handle with hint

Location:

MOAB/trunk

Files:

• MBCore.cpp (modified) (2 diffs)
• MBRange.cpp (modified) (3 diffs)
• MBRange.hpp (modified) (2 diffs)

MOAB/trunk/MBCore.cpp

@@ -1217 +1217 @@
   MBRange temp_range;
   std::vector<MBEntityHandle> temp_vec;
+  std::vector<MBEntityHandle>::const_iterator adj_it;
   MBErrorCode result = MB_SUCCESS, tmp_result;
 
@@ -1235 +1236 @@
     if (MB_SUCCESS != tmp_result) result = tmp_result;
     
+    std::sort( temp_vec.begin(), temp_vec.end() );
+    
       // if we're on the first iteration and we didn't come in with entities,
       // just get the first results and move on
     if (adj_entities.empty() && from_it == from_entities.begin()) {
-      std::copy(temp_vec.begin(), temp_vec.end(), mb_range_inserter(adj_entities));
+      std::copy(temp_vec.rbegin(), temp_vec.rend(), mb_range_inserter(adj_entities));
       continue;
     }
 
       // operate on the vectors
+    MBRange::iterator hint = adj_entities.begin();
     if (operation_type == MBInterface::INTERSECT) {
-        // only have to sort if we're doing intersection
-      std::sort(temp_vec.begin(), temp_vec.end());
-      std::set_intersection(adj_entities.begin(), adj_entities.end(), 
-                            temp_vec.begin(), temp_vec.end(),
-                            mb_range_inserter(temp_range));
-      adj_entities.swap(temp_range);
+      adj_it = temp_vec.begin();
+      while (hint != adj_entities.end()) {
+        while (adj_it != temp_vec.end() && *adj_it < *hint)
+          ++adj_it;
+        if (adj_it == temp_vec.end()) {
+          adj_entities.erase( hint, adj_entities.end() );
+          break;
+        }
+        
+        if (*adj_it == *hint)
+          ++hint;
+        else
+          hint = adj_entities.erase(hint);
+      }
+      
+        // If doing INTERSECT and the current results are the empty set,
+        // then the final result must also be the empty set.  
+      if (adj_entities.empty())
+        return MB_SUCCESS;
     }
     else if (operation_type == MBInterface::UNION) {
-      std::copy(temp_vec.begin(), temp_vec.end(), mb_range_inserter(adj_entities));
+      for (adj_it = temp_vec.begin(); adj_it != temp_vec.end(); ++adj_it)
+        hint = adj_entities.insert( hint, *adj_it );
     }
   }

MOAB/trunk/MBRange.cpp

@@ -232 +232 @@
 */
 
-MBRange::iterator MBRange::insert(MBEntityHandle val)
+MBRange::iterator MBRange::insert( MBRange::iterator hint, MBEntityHandle val )
 {
 
@@ -247 +247 @@
   // find the location in the list where we can safely insert
   // new items and keep it ordered
-  PairNode* jter = mHead.mNext;
+  PairNode* hter = hint.mNode;
+  PairNode* jter = hter->first <= val ? hter : mHead.mNext;
   for( ; (jter != &mHead) && (jter->second < val); jter=jter->mNext);
   PairNode* iter = jter;
@@ -300 +301 @@
 }
 
-
-/*!
-  inserts a range of values
-*/
-MBRange::iterator MBRange::insert(MBEntityHandle val1, MBEntityHandle val2)
-{
-
-  if(val1 == 0 || val1 > val2)
-    return end();
-
-  return insert( begin(), val1, val2 );
-}
-
 MBRange::iterator MBRange::insert( MBRange::iterator prev,
                                    MBEntityHandle val1, 
                                    MBEntityHandle val2 )
 {
-  assert( val1 <= val2 && val1 );
+  if(val1 == 0 || val1 > val2)
+    return end();
 
   // Empty 

MOAB/trunk/MBRange.hpp

@@ -242 +242 @@
   inline bool empty() const;
 
+  iterator insert( iterator hint, MBEntityHandle val );
+
   //! insert an item into the list and return the iterator for the inserted item
-  iterator insert(MBEntityHandle val);
+  iterator insert(MBEntityHandle val)
+    { return insert( begin(), val ); }
   
   //! insert a range of items into this list and return the iterator for the first
   //! inserted item
-  iterator insert(MBEntityHandle val1, MBEntityHandle val2);
+  iterator insert( iterator hint, MBEntityHandle first, MBEntityHandle last );
+  
+  //! insert a range of items into this list and return the iterator for the first
+  //! inserted item
+  iterator insert(MBEntityHandle val1, MBEntityHandle val2)
+    { return insert( begin(), val1, val2 ); }
   
     //! remove an item from this list and return an iterator to the next item
@@ -339 +347 @@
 
   int index(MBEntityHandle handle) const;
-  
-  MBRange::iterator insert( MBRange::iterator prev,
-                            MBEntityHandle first,
-                            MBEntityHandle last );
   
 protected: