[MOAB-dev] r3297 - MOAB/trunk

[kraftche at cae.wisc.edu]

Author: kraftche
Date: 2009-11-06 13:58:45 -0600 (Fri, 06 Nov 2009)
New Revision: 3297

Modified:
   MOAB/trunk/MBCore.cpp
   MOAB/trunk/MBRange.cpp
   MOAB/trunk/MBRange.hpp
Log:
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


Modified: MOAB/trunk/MBCore.cpp
===================================================================
--- MOAB/trunk/MBCore.cpp	2009-11-06 18:37:19 UTC (rev 3296)
+++ MOAB/trunk/MBCore.cpp	2009-11-06 19:58:45 UTC (rev 3297)
@@ -1216,6 +1216,7 @@
 
   MBRange temp_range;
   std::vector<MBEntityHandle> temp_vec;
+  std::vector<MBEntityHandle>::const_iterator adj_it;
   MBErrorCode result = MB_SUCCESS, tmp_result;
 
   for (MBRange::const_iterator from_it = from_entities.begin(); 
@@ -1234,24 +1235,41 @@
     
     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 );
     }
   }
 

Modified: MOAB/trunk/MBRange.cpp
===================================================================
--- MOAB/trunk/MBRange.cpp	2009-11-06 18:37:19 UTC (rev 3296)
+++ MOAB/trunk/MBRange.cpp	2009-11-06 19:58:45 UTC (rev 3297)
@@ -231,7 +231,7 @@
   inserts a single value into this range
 */
 
-MBRange::iterator MBRange::insert(MBEntityHandle val)
+MBRange::iterator MBRange::insert( MBRange::iterator hint, MBEntityHandle val )
 {
 
   // if this is empty, just add it and return an iterator to it
@@ -246,7 +246,8 @@
   
   // 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;
   jter = jter->mPrev;
@@ -299,24 +300,12 @@
 
 }
 
-
-/*!
-  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 
   if (mHead.mNext == &mHead)

Modified: MOAB/trunk/MBRange.hpp
===================================================================
--- MOAB/trunk/MBRange.hpp	2009-11-06 18:37:19 UTC (rev 3296)
+++ MOAB/trunk/MBRange.hpp	2009-11-06 19:58:45 UTC (rev 3297)
@@ -241,13 +241,21 @@
   //! always use "if(!Ranges::empty())" instead of "if(Ranges::size())"
   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
   iterator erase(iterator iter);
 
@@ -339,10 +347,6 @@
 
   int index(MBEntityHandle handle) const;
   
-  MBRange::iterator insert( MBRange::iterator prev,
-                            MBEntityHandle first,
-                            MBEntityHandle last );
-  
 protected:
 
   //! the head of the list that contains pairs that represent the ranges