diff options
author | Jan-Marek Glogowski <glogow@fbihome.de> | 2014-05-12 10:20:00 +0200 |
---|---|---|
committer | Jan-Marek Glogowski <glogow@fbihome.de> | 2014-09-30 09:56:31 +0200 |
commit | d2180aacc58112a6b41bb8ff93b382a735dc5aa4 (patch) | |
tree | 7ae647d04f6044f4f22a1c2194dad9585a3f2b2a | |
parent | ec3e220fe215b21df16294daf88426b23f3ab7b3 (diff) |
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)
-rw-r--r-- | include/o3tl/sorted_vector.hxx | 64 | ||||
-rw-r--r-- | o3tl/qa/test-sorted_vector.cxx | 108 |
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(); }; |