[MOAB-dev] r3060 - MOAB/trunk
kraftche at cae.wisc.edu
kraftche at cae.wisc.edu
Mon Jul 27 13:05:43 CDT 2009
Author: kraftche
Date: 2009-07-27 13:05:42 -0500 (Mon, 27 Jul 2009)
New Revision: 3060
Modified:
MOAB/trunk/MBRange.cpp
MOAB/trunk/MBRange.hpp
MOAB/trunk/MBTest.cpp
Log:
o Add more efficent range-based erase implementation for MBRange
o Fix exsiting single-value MBRange::erase such that all iterators
pointing into a location in an MBRange previous to an erased
value remain valid after the erase.
o Add unit tests for the above.
Modified: MOAB/trunk/MBRange.cpp
===================================================================
--- MOAB/trunk/MBRange.cpp 2009-07-27 15:29:51 UTC (rev 3059)
+++ MOAB/trunk/MBRange.cpp 2009-07-27 18:05:42 UTC (rev 3060)
@@ -424,14 +424,71 @@
// split the range
else
{
- PairNode* new_node = alloc_pair(iter.mNode, iter.mNode->mPrev, kter->first, iter.mValue-1);
+ PairNode* new_node = alloc_pair(iter.mNode->mNext, iter.mNode, iter.mValue+1, kter->second);
new_node->mPrev->mNext = new_node->mNext->mPrev = new_node;
- iter.mNode->first = iter.mValue+1;
+ iter.mNode->second = iter.mValue - 1;
return new_iter;
}
}
+
+ //! remove a range of items from the list
+MBRange::iterator MBRange::erase( iterator iter1, iterator iter2)
+{
+ iterator result;
+
+ if (iter1.mNode == iter2.mNode) {
+ if (iter2.mValue <= iter1.mValue) {
+ // empty range OK, otherwise invalid input
+ return iter2;
+ }
+
+ // If both iterators reference the same pair node, then
+ // we're either removing values from the front of the
+ // node or splitting the node. We can never be removing
+ // the last value in the node in this case because iter2
+ // points *after* the last entry to be removed.
+
+ PairNode* node = iter1.mNode;
+ if (iter1.mValue == node->first) {
+ node->first = iter2.mValue;
+ result = iter2;
+ }
+ else {
+ PairNode* new_node = alloc_pair( node->mNext, node, iter2.mValue, node->second );
+ new_node->mNext->mPrev = new_node;
+ new_node->mPrev->mNext = new_node;
+ node->second = iter1.mValue - 1;
+ result = iterator( new_node, new_node->first );
+ }
+ }
+ else {
+ if (iter1.mNode == &mHead)
+ return iter1;
+ PairNode* dn = iter1.mNode;
+ if (iter1.mValue > dn->first) {
+ dn->second = iter1.mValue-1;
+ dn = dn->mNext;
+ }
+ if (iter2.mNode != &mHead)
+ iter2.mNode->first = iter2.mValue;
+ while (dn != iter2.mNode) {
+ PairNode* dead = dn;
+ dn = dn->mNext;
+
+ dead->mPrev->mNext = dead->mNext;
+ dead->mNext->mPrev = dead->mPrev;
+ dead->mPrev = dead->mNext = 0;
+ delete dead;
+ }
+
+ result = iter2;
+ }
+
+ return result;
+}
+
void MBRange::delete_pair_node( PairNode* node )
{
if (node != &mHead) { // pop_front() and pop_back() rely on this check
Modified: MOAB/trunk/MBRange.hpp
===================================================================
--- MOAB/trunk/MBRange.hpp 2009-07-27 15:29:51 UTC (rev 3059)
+++ MOAB/trunk/MBRange.hpp 2009-07-27 18:05:42 UTC (rev 3060)
@@ -759,14 +759,6 @@
return (mHead.mNext == &mHead);
}
- //! remove a range of items from the list
-inline MBRange::iterator MBRange::erase( iterator iter1, iterator iter2)
-{
- while( iter1 != iter2 )
- erase( iter1++ );
- return iter1;
-}
-
//! erases a value from this container
inline MBRange::iterator MBRange::erase(MBEntityHandle val)
{
Modified: MOAB/trunk/MBTest.cpp
===================================================================
--- MOAB/trunk/MBTest.cpp 2009-07-27 15:29:51 UTC (rev 3059)
+++ MOAB/trunk/MBTest.cpp 2009-07-27 18:05:42 UTC (rev 3060)
@@ -62,6 +62,16 @@
<< __LINE__ << std::endl; \
return A; } } while(false)
+
+#define CHECK_EQUAL( A, B ) do { if ((A) != (B)) { \
+ std::cerr << "Equality Test failed at " __FILE__ ":" << __LINE__ << std::endl; \
+ std::cerr << " Expected: " << (A) << std::endl; \
+ std::cerr << " Actual: " << (B) << std::endl; \
+ return MB_FAILURE; } } while(false)
+#define CHECK( A ) do { if (!(A)) { \
+ std::cerr << "Test failed at " __FILE__ ":" << __LINE__ << std::endl; \
+ return MB_FAILURE; } } while(false)
+
/*!
@test
Vertex Coordinates
@@ -5209,6 +5219,171 @@
return result;
}
+MBErrorCode mb_range_erase_test(MBInterface *)
+{
+ MBRange range;
+ MBRange::iterator result;
+
+ // test erase from first node
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin(), range.begin()+2 );
+ CHECK_EQUAL( 7u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 13u, range.size() );
+ CHECK_EQUAL( 7u, *result );
+
+ // test erase first node
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin(), range.begin()+6 );
+ CHECK_EQUAL( 12u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 9u, range.size() );
+ CHECK_EQUAL( 12u, *result );
+
+ // test erase from back of first node
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin()+2, range.begin()+6 );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 11u, range.size() );
+ CHECK_EQUAL( 12u, *result );
+
+ // test erase from middle of first node
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin()+2, range.begin()+5 );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 12u, range.size() );
+ CHECK_EQUAL( 10u, *result );
+
+ // test erase spanning two nodes
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin()+3, range.begin()+7 );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 11u, range.size() );
+ CHECK_EQUAL( 13u, *result );
+
+ // test erase of first node and part of second
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin(), range.begin()+7 );
+ CHECK_EQUAL( 13u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 8u, range.size() );
+ CHECK_EQUAL( 13u, *result );
+
+ // test erase spanning three nodes
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ range.insert( 100, 101 );
+ result = range.erase( range.begin()+3, range.begin()+16 );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 101u, range.back() );
+ CHECK_EQUAL( 4u, range.size() );
+ CHECK_EQUAL( 101u, *result );
+
+ // test erase from start of second node
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin()+6, range.begin()+8 );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 13u, range.size() );
+ CHECK_EQUAL( 14u, *result );
+
+ // test erase from back of last node
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin()+13, range.end() );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 18u, range.back() );
+ CHECK_EQUAL( 13u, range.size() );
+ CHECK( result == range.end() );
+
+ // test erase part of first node through end
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin()+4, range.end() );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 8u, range.back() );
+ CHECK_EQUAL( 4u, range.size() );
+ CHECK( result == range.end() );
+
+ // test erase of single node
+ range.clear();
+ range.insert( 5, 10 );
+ result = range.erase( range.begin(), range.end() );
+ CHECK_EQUAL( 0u, range.size() );
+ CHECK( result == range.end() );
+
+ // test erase of multi-node range
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ range.insert( 100, 101 );
+ result = range.erase( range.begin(), range.end() );
+ CHECK_EQUAL( 0u, range.size() );
+ CHECK( result == range.end() );
+
+ // test erase nothing
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ result = range.erase( range.begin()+3, range.begin()+3 );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 15u, range.size() );
+ CHECK_EQUAL( 8u, *result );
+
+ // test iterators before erase remain valid
+ MBRange::iterator a, b, c;
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ a = range.begin();
+ b = range.begin() + 6;
+ c = range.begin() + 8;
+ result = range.erase( range.begin() + 9, range.end() );
+ CHECK( a == range.begin() );
+ CHECK( b == range.begin() + 6 );
+ CHECK( c == range.begin() + 8 );
+ CHECK( result == range.end() );
+
+ // test iterators before erase remain valid, single value case
+ range.clear();
+ range.insert( 5, 10 );
+ range.insert( 12, 20 );
+ a = range.begin();
+ b = range.begin() + 6;
+ c = range.begin() + 8;
+ result = range.erase( range.begin() + 9 );
+ CHECK_EQUAL( 5u, range.front() );
+ CHECK_EQUAL( 20u, range.back() );
+ CHECK_EQUAL( 14u, range.size() );
+ CHECK( a == range.begin() );
+ CHECK( b == range.begin() + 6 );
+ CHECK( c == range.begin() + 8 );
+ CHECK_EQUAL( 16u, *result );
+
+ return MB_SUCCESS;
+}
+
MBErrorCode mb_topo_util_test(MBInterface *gMB)
{
MeshTopoUtil mtu(gMB);
@@ -6514,6 +6689,7 @@
RUN_TEST( mb_canon_number_test );
RUN_TEST( mb_poly_test );
RUN_TEST( mb_range_test );
+ RUN_TEST( mb_range_erase_test );
RUN_TEST( mb_topo_util_test );
RUN_TEST( mb_split_test );
RUN_TEST( mb_range_seq_intersect_test );
More information about the moab-dev
mailing list