Create a template container class for sorted vector

We use this kind of container a lot, so creating a single
implementation makes sense.

Change-Id: I67ead58becd7d2a287812145c11d93ab1c593c0f

4 files changed, 218 insertions, 0 deletions

diff --git a/o3tl/CppunitTest_o3tl_tests.mk b/o3tl/CppunitTest_o3tl_tests.mk
index 464a5e7539f5..29e1ff8a6a1f 100644
--- a/o3tl/CppunitTest_o3tl_tests.mk
+++ b/o3tl/CppunitTest_o3tl_tests.mk
@@ -41,6 +41,7 @@ $(eval $(call gb_CppunitTest_add_exception_objects,o3tl_tests,\
 	o3tl/qa/test-heap_ptr \
 	o3tl/qa/test-range \
 	o3tl/qa/test-vector_pool \
+	o3tl/qa/test-sorted_vector \
 ))
 
 # vim: set noet sw=4:
diff --git a/o3tl/Package_inc.mk b/o3tl/Package_inc.mk
index 088c289660f7..b4a6575b1088 100644
--- a/o3tl/Package_inc.mk
+++ b/o3tl/Package_inc.mk
@@ -33,5 +33,6 @@ $(eval $(call gb_Package_add_file,o3tl_inc,inc/o3tl/heap_ptr.hxx,o3tl/heap_ptr.h
 $(eval $(call gb_Package_add_file,o3tl_inc,inc/o3tl/lazy_update.hxx,o3tl/lazy_update.hxx))
 $(eval $(call gb_Package_add_file,o3tl_inc,inc/o3tl/range.hxx,o3tl/range.hxx))
 $(eval $(call gb_Package_add_file,o3tl_inc,inc/o3tl/vector_pool.hxx,o3tl/vector_pool.hxx))
+$(eval $(call gb_Package_add_file,o3tl_inc,inc/o3tl/sorted_vector.hxx,o3tl/sorted_vector.hxx))
 
 # vim: set noet sw=4:
diff --git a/o3tl/inc/o3tl/sorted_vector.hxx b/o3tl/inc/o3tl/sorted_vector.hxx
new file mode 100644
index 000000000000..79ede037fdd8
--- /dev/null
+++ b/o3tl/inc/o3tl/sorted_vector.hxx
@@ -0,0 +1,136 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#ifndef INCLUDED_O3TL_SORTED_VECTOR_HXX
+#define INCLUDED_O3TL_SORTED_VECTOR_HXX
+
+#include <vector>
+#include <functional>
+#include <algorithm>
+
+namespace o3tl
+{
+
+/** Helper template */
+template <class Value, class Compare>
+class sorted_vector_compare : public Compare
+{
+public:
+    bool operator()(const Value& lhs, const Value& rhs) const
+    {
+        return Compare::operator()(lhs, rhs);
+    }
+};
+
+/** Represents a sorted vector of values.
+
+    @tpl Value class of item to be stored in container
+    @tpl Compare comparison method
+*/
+template <class Value, class Compare = std::less<Value> >
+class sorted_vector : public std::vector<Value>, private sorted_vector_compare<Value, Compare>
+{
+public:
+    typedef typename std::vector<Value>::iterator  iterator;
+    typedef typename std::vector<Value>::const_iterator  const_iterator;
+    typedef typename std::vector<Value>::size_type  size_type;
+    typedef sorted_vector_compare<Value, Compare> MyCompare;
+
+    using std::vector<Value>::begin;
+    using std::vector<Value>::end;
+    using std::vector<Value>::clear;
+    using std::vector<Value>::insert;
+    using std::vector<Value>::erase;
+
+    // MODIFIERS
+
+    std::pair<iterator,bool> insert( const Value& x )
+    {
+        const MyCompare& me = *this;
+        iterator it = std::lower_bound( begin(), end(), x, me );
+        if( it == end() || less_than(x, *it) )
+        {
+            it = insert( it, x );
+            return std::make_pair( it, true );
+        }
+        return std::make_pair( it, false );
+    }
+
+    size_type erase( const Value& x )
+    {
+        iterator it = find(x);
+        if( it != end() )
+        {
+            erase( it );
+            return 1;
+        }
+        return 0;
+    }
+
+    // OPERATIONS
+
+    /* 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).
+     */
+    const_iterator find( const Value& x ) const
+    {
+        const MyCompare& me = *this;
+        const_iterator it = std::lower_bound( begin(), end(), x, me );
+        if( it == end() || less_than(x, *it) )
+        {
+            return end();
+        }
+        return it;
+    }
+    iterator find( const Value& x )
+    {
+        const MyCompare& me = *this;
+        iterator it = std::lower_bound( begin(), end(), x, me );
+        if( it == end() || less_than(x, *it) )
+        {
+            return end();
+        }
+        return it;
+    }
+
+    /* Clear() elements in the vector, and free them one by one. */
+    void DeleteAndDestroyAll()
+    {
+        for( const_iterator it = begin(); it != end(); ++it )
+            delete *it;
+        clear();
+    }
+
+private:
+    /** just makes the code easier to read */
+    bool less_than(const Value& lhs, const Value& rhs) const
+    {
+        const MyCompare& me = *this;
+        return me.operator()(lhs, rhs);
+    }
+};
+
+
+/** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
+    Very useful for the cases where we put pointers to objects inside a sorted_vector.
+*/
+template <class T> struct less_ptr_to : public std::binary_function <T*,T*,bool>
+{
+    bool operator() ( T* const& lhs, T* const& rhs ) const
+    {
+        return (*lhs) < (*rhs);
+    }
+};
+
+
+}   // namespace o3tl
+#endif
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/o3tl/qa/test-sorted_vector.cxx b/o3tl/qa/test-sorted_vector.cxx
new file mode 100644
index 000000000000..11732bd5f875
--- /dev/null
+++ b/o3tl/qa/test-sorted_vector.cxx
@@ -0,0 +1,80 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include "cppunit/TestAssert.h"
+#include "cppunit/TestFixture.h"
+#include "cppunit/extensions/HelperMacros.h"
+
+#include <o3tl/sorted_vector.hxx>
+
+using namespace ::o3tl;
+
+
+// helper class
+class SwContent
+{
+public:
+    int x;
+
+    SwContent(int x_) : x(x_) {}
+
+    bool operator<( const SwContent &rCmp) const
+    {
+        return x < rCmp.x;
+    }
+};
+
+class sorted_vector_test : public CppUnit::TestFixture
+{
+public:
+    void testBasics()
+    {
+        o3tl::sorted_vector<SwContent*, o3tl::less_ptr_to<SwContent> > aVec;
+        SwContent *p1 = new SwContent(1);
+        SwContent *p2 = 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.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() == 1 );
+        CPPUNIT_ASSERT( aVec.find(p2) == aVec.end() );
+        CPPUNIT_ASSERT( aVec.find(p4) == aVec.end() );
+
+        CPPUNIT_ASSERT( aVec.erase(p1) == 1 );
+        CPPUNIT_ASSERT( aVec.size() == 1 );
+        CPPUNIT_ASSERT( aVec.erase(p2) == 0 );
+
+        aVec.DeleteAndDestroyAll();
+    }
+
+
+    // 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.
+
+    CPPUNIT_TEST_SUITE(sorted_vector_test);
+    CPPUNIT_TEST(testBasics);
+    CPPUNIT_TEST_SUITE_END();
+};
+
+// -----------------------------------------------------------------------------
+CPPUNIT_TEST_SUITE_REGISTRATION(sorted_vector_test);
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */