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

2 files changed, 174 insertions, 26 deletions

diff --git a/o3tl/inc/o3tl/sorted_vector.hxx b/o3tl/inc/o3tl/sorted_vector.hxx
index 0fe46cf7bd02..4d442dd590ae 100644
--- a/o3tl/inc/o3tl/sorted_vector.hxx
+++ b/o3tl/inc/o3tl/sorted_vector.hxx
@@ -17,12 +17,18 @@
 namespace o3tl
 {
 
+// forward declared because it's default tempate arg for sorted_vector
+template<class Value, class Compare>
+struct find_unique;
+
 /** Represents a sorted vector of values.
 
     @tpl Value class of item to be stored in container
     @tpl Compare comparison method
+    @tpl Find   look up index of a Value in the array
 */
-template <class Value, class Compare = std::less<Value> >
+template<class Value, class Compare = std::less<Value>,
+         class Find = find_unique<Value, Compare> >
 class sorted_vector
     : private std::vector<Value>
 {
@@ -41,21 +47,22 @@ public:
 
     std::pair<const_iterator,bool> insert( const Value& x )
     {
-        iterator it = lower_bound_nonconst( x );
-        if (it == base_t::end() || less_than(x, *it))
+        std::pair<const_iterator, bool> const ret(Find()(begin(), end(), x));
+        if (!ret.second)
         {
-            it = base_t::insert( it, x );
-            return std::make_pair( it, true );
+            const_iterator const it = base_t::insert(
+                            begin_nonconst() + (ret.first - begin()), x);
+            return std::make_pair(it, true);
         }
-        return std::make_pair( it, false );
+        return std::make_pair(ret.first, false);
     }
 
     size_type erase( const Value& x )
     {
-        iterator it = lower_bound_nonconst( x );
-        if (it != base_t::end() && !less_than(x, *it))
+        std::pair<const_iterator, bool> const ret(Find()(begin(), end(), x));
+        if (ret.second)
         {
-            base_t::erase(it);
+            base_t::erase(begin_nonconst() + (ret.first - begin()));
             return 1;
         }
         return 0;
@@ -122,15 +129,11 @@ public:
      */
     const_iterator find( const Value& x ) const
     {
-        const_iterator it = lower_bound( x );
-        if (it == base_t::end() || less_than(x, *it))
-        {
-            return base_t::end();
-        }
-        return it;
+        std::pair<const_iterator, bool> const ret(Find()(begin(), end(), x));
+        return (ret.second) ? ret.first : end();
     }
 
-    void insert( sorted_vector<Value,Compare> &rOther )
+    void insert( sorted_vector<Value,Compare,Find> &rOther )
     {
        // optimisation for the rather common case that we are overwriting this with the contents
        // of another sorted vector
@@ -153,16 +156,6 @@ public:
     }
 
 private:
-    /** just makes the code easier to read */
-    bool less_than(const Value& lhs, const Value& rhs) const
-    {
-        return Compare().operator()(lhs, rhs);
-    }
-
-    iterator lower_bound_nonconst( const Value& x )
-    {
-        return std::lower_bound( base_t::begin(), base_t::end(), x, Compare() );
-    }
 
     typename base_t::iterator begin_nonconst() { return base_t::begin(); }
     typename base_t::iterator end_nonconst()   { return base_t::end(); }
@@ -181,6 +174,47 @@ template <class T> struct less_ptr_to : public std::binary_function <T*,T*,bool>
     }
 };
 
+/** the elements are totally ordered by Compare,
+    for no 2 elements !Compare(a,b) && !Compare(b,a) is true
+  */
+template<class Value, class Compare>
+struct find_unique
+{
+    typedef typename sorted_vector<Value, Compare, find_unique>
+                ::const_iterator const_iterator;
+    std::pair<const_iterator, bool> operator()(
+            const_iterator first, const_iterator last,
+            Value const& v)
+    {
+        const_iterator const it = std::lower_bound(first, last, v, Compare());
+        return std::make_pair(it, (it != last && !Compare()(v, *it)));
+    }
+};
+
+/** the elments are partially ordered by Compare,
+    2 elements are allowed if they are not the same element (pointer equal)
+  */
+template<class Value, class Compare>
+struct find_partialorder_ptrequals
+{
+    typedef typename sorted_vector<Value, Compare, find_partialorder_ptrequals>
+                ::const_iterator const_iterator;
+    std::pair<const_iterator, bool> operator()(
+            const_iterator first, const_iterator last,
+            Value const& v)
+    {
+        std::pair<const_iterator, const_iterator> const its =
+            std::equal_range(first, last, v, Compare());
+        for (const_iterator it = its.first; it != its.second; ++it)
+        {
+            if (v == *it)
+            {
+                return std::make_pair(it, true);
+            }
+        }
+        return std::make_pair(its.first, false);
+    }
+};
 
 }   // namespace o3tl
 #endif
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();
 };