sorted_vector: add an additional template parameter:

The Find parameter allows to implement sorted_vector that uses the
obvious std::less-like semantics, and also allows for a different
semantics where the array is sorted like std::less but duplicate values
(according to std::less) are allowed except if they're actually the same
object (pointer equality).

Change-Id: Id54871c336ddbc2d0a2272bcc81c56914943b449

1 files changed, 114 insertions, 0 deletions

diff --git a/o3tl/qa/test-sorted_vector.cxx b/o3tl/qa/test-sorted_vector.cxx
index 5641ad2cd177..1b321c91a2a4 100644
--- a/o3tl/qa/test-sorted_vector.cxx
+++ b/o3tl/qa/test-sorted_vector.cxx
@@ -133,6 +133,118 @@ public:
         CPPUNIT_ASSERT( aVec.lower_bound(p4) == aVec.end() );
     }
 
+    void testBasics_FindPtr()
+    {
+        o3tl::sorted_vector<SwContent*, o3tl::less_ptr_to<SwContent>,
+            o3tl::find_partialorder_ptrequals<SwContent*,
+                o3tl::less_ptr_to<SwContent> > > aVec;
+        SwContent *p1 = new SwContent(1);
+        SwContent *p2 = new SwContent(2);
+        SwContent *p2_2 = new SwContent(2);
+        SwContent *p2_3 = new SwContent(2);
+        SwContent *p2_4 = new SwContent(2);
+        SwContent *p3 = new SwContent(3);
+        SwContent *p4 = new SwContent(4);
+
+        CPPUNIT_ASSERT( aVec.insert(p3).second );
+        CPPUNIT_ASSERT( aVec.insert(p1).second );
+        CPPUNIT_ASSERT( !aVec.insert(p3).second );
+
+        CPPUNIT_ASSERT( aVec.size() == 2 );
+
+        CPPUNIT_ASSERT( aVec[0] == p1 );
+        CPPUNIT_ASSERT( aVec[1] == p3 );
+
+        CPPUNIT_ASSERT( aVec.insert(p2_2).second );
+        CPPUNIT_ASSERT( aVec.insert(p2_3).second );
+        CPPUNIT_ASSERT( !aVec.insert(p2_2).second );
+        CPPUNIT_ASSERT( aVec.insert(p2_4).second );
+        CPPUNIT_ASSERT( aVec.size() == 5 );
+
+        CPPUNIT_ASSERT( *aVec.begin() == p1 );
+        CPPUNIT_ASSERT( *(aVec.end()-1) == p3 );
+
+        CPPUNIT_ASSERT( aVec.front() == p1 );
+        CPPUNIT_ASSERT( aVec.back() == p3 );
+
+        CPPUNIT_ASSERT( aVec.find(p1) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p1) - aVec.begin() == 0 );
+        CPPUNIT_ASSERT( aVec.find(p3) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p3) - aVec.begin() == 4 );
+        CPPUNIT_ASSERT( aVec.find(p2) == aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p4) == aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p2_2) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p2_2) - aVec.begin() >= 1 );
+        CPPUNIT_ASSERT( aVec.find(p2_2) - aVec.begin() <  4 );
+        CPPUNIT_ASSERT( aVec.find(p2_3) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p2_3) - aVec.begin() >= 1 );
+        CPPUNIT_ASSERT( aVec.find(p2_3) - aVec.begin() <  4 );
+        CPPUNIT_ASSERT( aVec.find(p2_4) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p2_4) - aVec.begin() >= 1 );
+        CPPUNIT_ASSERT( aVec.find(p2_4) - aVec.begin() <  4 );
+
+        CPPUNIT_ASSERT( aVec.erase(p1) == 1 );
+        CPPUNIT_ASSERT( aVec.size() == 4 );
+        CPPUNIT_ASSERT( aVec.erase(p2) == 0 );
+        CPPUNIT_ASSERT( aVec.erase(p2_3) == 1 );
+        CPPUNIT_ASSERT( aVec.size() == 3 );
+
+        aVec.DeleteAndDestroyAll();
+    }
+
+    void testErase_FindPtr()
+    {
+        o3tl::sorted_vector<SwContent*, o3tl::less_ptr_to<SwContent>,
+            o3tl::find_partialorder_ptrequals<SwContent*,
+                o3tl::less_ptr_to<SwContent> > > aVec;
+        SwContent *p1 = new SwContent(1);
+        SwContent *p1_2 = new SwContent(1);
+        SwContent *p1_3 = new SwContent(1);
+        SwContent *p2 = new SwContent(2);
+        SwContent *p3 = new SwContent(3);
+        SwContent *p4 = new SwContent(4);
+
+        aVec.insert(p1);
+        aVec.insert(p2);
+        aVec.insert(p3);
+
+        CPPUNIT_ASSERT( aVec.erase(p1) == 1 );
+        CPPUNIT_ASSERT( aVec.size() == 2 );
+
+        aVec.erase(1);
+        CPPUNIT_ASSERT( aVec.size() == 1 );
+
+        CPPUNIT_ASSERT( aVec.erase(p4) == 0 );
+
+        aVec.clear();
+        CPPUNIT_ASSERT( aVec.size() == 0 );
+
+        aVec.insert(p1);
+        aVec.insert(p2);
+        aVec.insert(p3);
+        aVec.insert(p1_2);
+        CPPUNIT_ASSERT( aVec.size() == 4 );
+        aVec.insert(p1_3);
+        CPPUNIT_ASSERT( aVec.size() == 5 );
+        CPPUNIT_ASSERT( aVec.erase(p1) == 1 );
+        CPPUNIT_ASSERT( aVec.find(p1) == aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p1_2) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p1_3) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.erase(p1_3) == 1 );
+        CPPUNIT_ASSERT( aVec.find(p1) == aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p1_2) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p1_3) == aVec.end() );
+        CPPUNIT_ASSERT( aVec.erase(p1_3) == 0 );
+        CPPUNIT_ASSERT( aVec.find(p1) == aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p1_2) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p1_3) == aVec.end() );
+
+        aVec.DeleteAndDestroyAll();
+        CPPUNIT_ASSERT( aVec.size() == 0 );
+    }
+
+
+
     // Change the following lines only, if you add, remove or rename
     // member functions of the current class,
     // because these macros are need by auto register mechanism.
@@ -142,6 +254,8 @@ public:
     CPPUNIT_TEST(testErase);
     CPPUNIT_TEST(testInsertRange);
     CPPUNIT_TEST(testLowerBound);
+    CPPUNIT_TEST(testBasics_FindPtr);
+    CPPUNIT_TEST(testErase_FindPtr);
     CPPUNIT_TEST_SUITE_END();
 };