Sorted vector special case: default first element

A lot of code using vectors in LO relies on the fact, that the
first entry in the vector contains the default value.

Therefore this adds a boolean to the constructor, which leaves
the first entry unsorted in the vector and special cases find
and insert.

Additionally lower_bound, upper_bound and Resort will skip
the first element.

Change-Id: I9603f47be4fb56d991f42066ce9f5ad0ab6ffdf8
(cherry picked from commit 3f1c34cd231bcb7067ccb0d4e64d5ab5cdab4879)

2 files changed, 161 insertions, 11 deletions

diff --git a/include/o3tl/sorted_vector.hxx b/include/o3tl/sorted_vector.hxx
index 776fd5605e6f..7fd23234e550 100644
--- a/include/o3tl/sorted_vector.hxx
+++ b/include/o3tl/sorted_vector.hxx
@@ -23,9 +23,21 @@ 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
+    The vector has a special "first default" mode, enabled by the
+    constructor boolean FirstDefault.
+
+    This keeps the first item always unsorted. Many LO lists store
+    their defaults in the first item and index access expect it at
+    at position 0.
+
+    The alternative of "marking a special item as default" in the
+    vector was dropped, as new iterators would have been needed in
+    case one would keep index and iterator distance interchangeable
+    and still represent the default item at index 0.
+
+    @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<typename Value, typename Compare = std::less<Value>,
      template<typename, typename> class Find = find_unique >
@@ -36,19 +48,48 @@ private:
     typedef Find<Value, Compare> Find_t;
     typedef typename std::vector<Value> base_t;
     typedef typename std::vector<Value>::iterator  iterator;
+    int mOffset;
+
 public:
     typedef typename std::vector<Value>::const_iterator const_iterator;
     typedef typename std::vector<Value>::size_type size_type;
+    typedef typename std::vector<Value>::value_type value_type;
+    typedef std::pair<const_iterator, bool> find_insert_type;
 
+private:
+    find_insert_type _find( const Value& x ) const
+    {
+        if (mOffset && empty())
+            return find_insert_type(end(), false);
+        find_insert_type const ret(Find_t()(begin() + mOffset, end(), x));
+
+        // We haven't found the item, but have a default, so check the offset item
+        if (!ret.second && mOffset) {
+            find_insert_type const check(Find_t()(begin(), begin() + mOffset, x));
+            // Just return on success; we otherwise need the insert point from ret
+            if (check.second)
+                return check;
+        }
+        return ret;
+    }
+
+public:
     using base_t::clear;
     using base_t::empty;
     using base_t::size;
 
+    sorted_vector( bool FirstDefault=false )
+    {
+       mOffset = FirstDefault ? 1 : 0;
+    }
+
+    int GetOffset() const { return mOffset; }
+
     // MODIFIERS
 
-    std::pair<const_iterator,bool> insert( const Value& x )
+    find_insert_type insert( const Value& x )
     {
-        std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
+        find_insert_type const ret = _find( x );
         if (!ret.second)
         {
             const_iterator const it = base_t::insert(
@@ -60,7 +101,7 @@ public:
 
     size_type erase( const Value& x )
     {
-        std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
+        find_insert_type const ret = _find( x );
         if (ret.second)
         {
             base_t::erase(begin_nonconst() + (ret.first - begin()));
@@ -69,7 +110,7 @@ public:
         return 0;
     }
 
-    void erase( size_t index )
+    void erase( size_type index )
     {
         base_t::erase( begin_nonconst() + index );
     }
@@ -119,14 +160,15 @@ public:
 
     const_iterator lower_bound( const Value& x ) const
     {
-        return std::lower_bound( base_t::begin(), base_t::end(), x, Compare() );
+        return std::lower_bound( base_t::begin() + mOffset, base_t::end(), x, Compare() );
     }
 
     const_iterator upper_bound( const Value& x ) const
     {
-        return std::upper_bound( base_t::begin(), base_t::end(), x, Compare() );
+        return std::upper_bound( base_t::begin() + mOffset, base_t::end(), x, Compare() );
     }
 
+public:
     /* Searches the container for an element with a value of x
      * and returns an iterator to it if found, otherwise it returns an
      * iterator to sorted_vector::end (the element past the end of the container).
@@ -135,7 +177,7 @@ public:
      */
     const_iterator find( const Value& x ) const
     {
-        std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
+        find_insert_type const ret = _find( x );
         return (ret.second) ? ret.first : end();
     }
 
@@ -167,7 +209,7 @@ public:
     // If you are calling this function, you are Doing It Wrong!
     void Resort()
     {
-        std::stable_sort(begin_nonconst(), end_nonconst(), Compare());
+        std::stable_sort(begin_nonconst() + mOffset, end_nonconst(), Compare());
     }
 
 private:
diff --git a/o3tl/qa/test-sorted_vector.cxx b/o3tl/qa/test-sorted_vector.cxx
index ee2e818a555e..7b4dacaac5f3 100644
--- a/o3tl/qa/test-sorted_vector.cxx
+++ b/o3tl/qa/test-sorted_vector.cxx
@@ -30,6 +30,25 @@ public:
     }
 };
 
+class SwContentComplex
+{
+public:
+    int x;
+    int y;
+    SwContentComplex(int x_, int y_) : x(x_), y(y_) {}
+};
+
+struct CompareSwContentComplexs {
+    bool operator()(SwContentComplex* const& lhs, SwContentComplex* const& rhs) const
+    {
+        if (lhs->x < rhs->x)
+            return true;
+        if (lhs->x > rhs->x)
+            return false;
+        return (lhs->y < rhs->y);
+    }
+};
+
 class sorted_vector_test : public CppUnit::TestFixture
 {
 public:
@@ -244,7 +263,94 @@ public:
         delete p4;
     }
 
+    void testBasicsDefault()
+    {
+        o3tl::sorted_vector<SwContent*, o3tl::less_ptr_to<SwContent> > aVec( true );
+        SwContent *p1 = new SwContent(1);
+        SwContent *p2 = new SwContent(2);
+        SwContent *p3 = new SwContent(3);
+        SwContent *p4 = new SwContent(4);
+        SwContent *p5 = new SwContent(5);
+
+        CPPUNIT_ASSERT( aVec.insert(p3).second );
+        CPPUNIT_ASSERT( aVec.insert(p1).second );
+        CPPUNIT_ASSERT( !aVec.insert(p3).second );
+        CPPUNIT_ASSERT( aVec.insert(p5).second );
+
+        CPPUNIT_ASSERT( aVec.size() == 3 );
+
+        CPPUNIT_ASSERT( aVec[0] == p3 );
+        CPPUNIT_ASSERT( aVec[1] == p1 );
+        CPPUNIT_ASSERT( aVec[2] == p5 );
+
+        CPPUNIT_ASSERT( aVec.insert(p2).second );
+
+        CPPUNIT_ASSERT( aVec.size() == 4 );
 
+        CPPUNIT_ASSERT( aVec[0] == p3 );
+        CPPUNIT_ASSERT( aVec[1] == p1 );
+        CPPUNIT_ASSERT( aVec[2] == p2 );
+        CPPUNIT_ASSERT( aVec[3] == p5 );
+
+        CPPUNIT_ASSERT( *aVec.begin() == p3 );
+        CPPUNIT_ASSERT( *(aVec.end()-1) == p5 );
+
+        CPPUNIT_ASSERT( aVec.front() == p3 );
+        CPPUNIT_ASSERT( aVec.back() == p5 );
+
+        CPPUNIT_ASSERT( aVec.find(p3) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p3) == aVec.begin() );
+        CPPUNIT_ASSERT( aVec.find(p3) - aVec.begin() == 0 );
+        CPPUNIT_ASSERT( aVec.find(p5) != aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p5) - aVec.begin() == 3 );
+        CPPUNIT_ASSERT( aVec.find(p4) == aVec.end() );
+
+        CPPUNIT_ASSERT( aVec.erase(p3) == 1 );
+        CPPUNIT_ASSERT( aVec.find(p1) == aVec.begin() );
+        CPPUNIT_ASSERT( aVec.size() == 3 );
+        CPPUNIT_ASSERT( aVec.erase(p3) == 0 );
+
+        aVec.DeleteAndDestroyAll();
+        delete p4;
+    }
+
+    void testComplexDefault()
+    {
+        o3tl::sorted_vector<SwContentComplex*, CompareSwContentComplexs,
+                            o3tl::find_partialorder_ptrequals> aVec( true );
+        SwContentComplex *p1 = new SwContentComplex(10, 1);
+        SwContentComplex *p2 = new SwContentComplex(2, 1);
+        SwContentComplex *p3 = new SwContentComplex(5, 0);
+        SwContentComplex *p4 = new SwContentComplex(5, 2);
+        SwContentComplex *p5 = new SwContentComplex(2, 2);
+        SwContentComplex *p6 = new SwContentComplex(2, 1);
+
+        CPPUNIT_ASSERT( aVec.insert(p1).second );
+        CPPUNIT_ASSERT( aVec.insert(p2).second );
+        CPPUNIT_ASSERT( !aVec.insert(p1).second );
+        CPPUNIT_ASSERT( aVec.insert(p3).second );
+        CPPUNIT_ASSERT( aVec.insert(p4).second );
+        CPPUNIT_ASSERT( !aVec.insert(p3).second );
+        CPPUNIT_ASSERT( aVec.insert(p5).second );
+        CPPUNIT_ASSERT( aVec.insert(p6).second );
+
+        CPPUNIT_ASSERT( aVec.size() == 6 );
+
+        CPPUNIT_ASSERT( aVec[0] == p1 );
+        if (p2 < p6) {
+            CPPUNIT_ASSERT( aVec[1] == p6 );
+            CPPUNIT_ASSERT( aVec[2] == p2 );
+        }
+        else {
+            CPPUNIT_ASSERT( aVec[1] == p2 );
+            CPPUNIT_ASSERT( aVec[2] == p6 );
+        }
+        CPPUNIT_ASSERT( aVec[3] == p5 );
+        CPPUNIT_ASSERT( aVec[4] == p3 );
+        CPPUNIT_ASSERT( aVec[5] == p4 );
+
+        aVec.DeleteAndDestroyAll();
+    }
 
     // Change the following lines only, if you add, remove or rename
     // member functions of the current class,
@@ -257,6 +363,8 @@ public:
     CPPUNIT_TEST(testLowerBound);
     CPPUNIT_TEST(testBasics_FindPtr);
     CPPUNIT_TEST(testErase_FindPtr);
+    CPPUNIT_TEST(testBasicsDefault);
+    CPPUNIT_TEST(testComplexDefault);
     CPPUNIT_TEST_SUITE_END();
 };