Convert SwPageDescs to a o3tl::sorted_vector

Originally I planned to use a boost::container::flat_map, but there
seem to be no way to directly access the indexed vector.

And since this already needs the "first item is default" special
handling, o3tl::sorted_vector is used with the offset.

Change-Id: Idfb79af8ddfd5f5e2e6ca312b46d30e3ddc166d9
(cherry picked from commit 014cb3c9598f10bd316a7df8aa1e66ddb20b9b5e)

2 files changed, 61 insertions, 60 deletions

diff --git a/sw/inc/pagedesc.hxx b/sw/inc/pagedesc.hxx
index 1b6da4ac30d7..3c23fbe2560c 100644
--- a/sw/inc/pagedesc.hxx
+++ b/sw/inc/pagedesc.hxx
@@ -26,6 +26,7 @@
 #include <frmfmt.hxx>
 #include <editeng/numitem.hxx>
 #include <editeng/borderline.hxx>
+#include <o3tl/sorted_vector.hxx>
 #include "poolfmt.hxx"
 
 class SfxPoolItem;
@@ -344,25 +345,43 @@ public:
     operator SwPageDesc() const; // #i7983#
 };
 
-typedef std::vector<SwPageDesc*> SwPageDescsBase;
+struct CompareSwPageDescs
+{
+    bool operator()(OUString const& lhs, SwPageDesc* const& rhs) const;
+    bool operator()(SwPageDesc* const& lhs, OUString const& rhs) const;
+    bool operator()(SwPageDesc* const& lhs, SwPageDesc* const& rhs) const;
+};
+
+typedef o3tl::sorted_vector<SwPageDesc*, CompareSwPageDescs> SwPageDescsBase;
 
 #define RES_POOLPAGE_SIZE (RES_POOLPAGE_END - RES_POOLPAGE_BEGIN)
 
-// Mimics o3tl::sorted_vector interface
-class SwPageDescs : private SwPageDescsBase
+//! A list of SwPageDesc pointers sorted by name.
+/*!
+ * The list of SwPageDesc is implemented as a sorted vector. This results in
+ * fast index access O(1) and fast searches O(log n).
+ *
+ * It currently uses special case version of sorted vector, which keeps the
+ * first item out of the sorted vector, as the first item is
+ *   * non-deletable
+ *   * the default item
+ *
+ * There is some internal friend handling for the name and pool id, so these
+ * can be changed on the object and will correctly be reflected in the list.
+ *
+ * @see SwDoc::DelPageDescP
+ * @see SwPageDesc
+ */
+class SwPageDescs : public SwPageDescsBase
 {
     // to update the poolpages array on PoolFmtId change
     friend void SwPageDesc::SetPoolFmtId( sal_uInt16 nId );
 
-public:
-    typedef SwPageDescsBase::const_iterator const_iterator;
-    typedef SwPageDescsBase::size_type size_type;
-    typedef SwPageDescsBase::value_type value_type;
-
 private:
     // fast index for pool page resources
     value_type poolpages[RES_POOLPAGE_SIZE];
 
+    // updates the poolpages array and the SwPageDesc list member
     void _erase( const value_type& x );
     bool IsIdInPoolRange( sal_uInt16 nId, bool allowDefault ) const;
 
@@ -375,33 +394,16 @@ public:
 
     void DeleteAndDestroyAll();
 
-    using SwPageDescsBase::clear;
-    using SwPageDescsBase::empty;
-    using SwPageDescsBase::size;
-
     std::pair<const_iterator,bool> insert( const value_type& x );
     size_type erase( const value_type& x );
     void erase( size_type index );
     void erase( const_iterator const& position );
 
-    const value_type& front() const { return SwPageDescsBase::front(); }
-    const value_type& back() const { return SwPageDescsBase::back(); }
-    const value_type& operator[]( size_t index ) const
-        { return SwPageDescsBase::operator[]( index ); }
-
     const_iterator find( const OUString &name ) const;
     const_iterator find( const value_type& x ) const;
 
-    const_iterator begin() const { return SwPageDescsBase::begin(); }
-    const_iterator end() const { return SwPageDescsBase::end(); }
-
     bool Contains( const value_type& x ) const;
     value_type GetPoolPageDesc( sal_uInt16 nId ) const;
-
-private:
-    typedef SwPageDescsBase::iterator iterator;
-    iterator begin_nonconst() { return SwPageDescsBase::begin(); }
-    iterator end_nonconst() { return SwPageDescsBase::end(); }
 };
 
 SwPageDesc* GetPageDescByName_Impl(SwDoc& rDoc, const OUString& rName);
diff --git a/sw/source/core/layout/pagedesc.cxx b/sw/source/core/layout/pagedesc.cxx
index d1af6afb4a0d..255236e47e91 100644
--- a/sw/source/core/layout/pagedesc.cxx
+++ b/sw/source/core/layout/pagedesc.cxx
@@ -554,7 +554,7 @@ SwPageDescExt::operator SwPageDesc() const
     return aResult;
 }
 
-SwPageDescs::SwPageDescs()
+SwPageDescs::SwPageDescs() : SwPageDescsBase( true )
 {
     memset(poolpages, 0, sizeof(value_type) * RES_POOLPAGE_SIZE);
 }
@@ -566,10 +566,8 @@ SwPageDescs::~SwPageDescs()
 
 void SwPageDescs::DeleteAndDestroyAll()
 {
-    for( const_iterator it = begin(); it != end(); ++it )
-        delete *it;
     memset(poolpages, 0, sizeof(value_type) * RES_POOLPAGE_SIZE);
-    clear();
+    SwPageDescsBase::DeleteAndDestroyAll();
 }
 
 std::pair<SwPageDescs::const_iterator,bool> SwPageDescs::insert( const value_type& x )
@@ -578,9 +576,8 @@ std::pair<SwPageDescs::const_iterator,bool> SwPageDescs::insert( const value_typ
     SAL_WARN_IF(nId != USHRT_MAX && NULL != GetPoolPageDesc( nId ),
                 "sw", "Inserting already assigned pool ID item!");
 
-    const_iterator const ret = find( x );
-    if (ret == end()) {
-        SwPageDescsBase::push_back( x );
+    std::pair<SwPageDescs::const_iterator,bool> ret = SwPageDescsBase::insert( x );
+    if (ret.second) {
         if (x->list != 0) {
             SAL_WARN("sw", "Inserting already assigned item!");
             SAL_WARN_IF(x->list != this, "sw",
@@ -589,9 +586,8 @@ std::pair<SwPageDescs::const_iterator,bool> SwPageDescs::insert( const value_typ
         x->list = this;
         if (nId != USHRT_MAX)
             poolpages[ nId - RES_POOLPAGE_BEGIN ] = x;
-        return std::make_pair(end() - 1 , true);
     }
-    return std::make_pair(ret, false);
+    return ret;
 }
 
 void SwPageDescs::_erase( const value_type& x )
@@ -607,57 +603,60 @@ void SwPageDescs::_erase( const value_type& x )
 
 SwPageDescs::size_type SwPageDescs::erase( const value_type& x )
 {
-    const_iterator const ret = find( x );
-    if (ret != end()) {
-        SwPageDescsBase::erase( begin_nonconst() + (ret - begin()) );
+    size_type ret = SwPageDescsBase::erase( x );
+    if (ret)
         _erase( x );
-        return 1;
-    }
-    return 0;
+    return ret;
 }
 
 void SwPageDescs::erase( size_type index )
 {
-    erase( begin_nonconst() + index );
+    erase( begin() + index );
 }
 
 void SwPageDescs::erase( const_iterator const& position )
 {
     _erase( *position );
-    SwPageDescsBase::erase( begin_nonconst() + (position - begin()) );
+    SwPageDescsBase::erase( position );
 }
 
-struct spd_oustring_compare : public std::unary_function<SwPageDesc*, bool>
+bool CompareSwPageDescs::operator()(OUString const& lhs, SwPageDesc* const& rhs) const
 {
-    spd_oustring_compare(const OUString &_baseline) : baseline(_baseline) {}
-    bool operator() (SwPageDesc* const &arg)
-        { return (baseline.compareTo( arg->GetName() ) == 0); }
-    const OUString baseline;
-};
+    return (lhs.compareTo( rhs->GetName() ) < 0);
+}
 
-struct spd_item_compare : public std::unary_function<SwPageDesc*, bool>
+bool CompareSwPageDescs::operator()(SwPageDesc* const& lhs, OUString const& rhs) const
 {
-    spd_item_compare(const SwPageDesc* _baseline) : baseline(_baseline) {}
-    bool operator() (SwPageDesc* const &arg)
-        { return (baseline->GetName().compareTo( arg->GetName() ) == 0); }
-    const SwPageDesc* baseline;
-};
+    return (lhs->GetName().compareTo( rhs ) < 0);
+}
+
+bool CompareSwPageDescs::operator()(SwPageDesc* const& lhs, SwPageDesc* const& rhs) const
+{
+    return (lhs->GetName().compareTo( rhs->GetName() ) < 0);
+}
 
 SwPageDescs::const_iterator SwPageDescs::find( const OUString &name ) const
 {
-    const_iterator const it = std::find_if(
-        begin(), end(), spd_oustring_compare( name ) );
+    if (empty())
+        return end();
+
+    const_iterator it = end();
+    if (size() > 1) {
+        it = std::lower_bound( begin() + 1, end(), name, CompareSwPageDescs() );
+        if (it != end() && CompareSwPageDescs()(name, *it))
+            it = end();
+    }
+    if (it == end() && !name.compareTo( (*this)[0]->GetName() ))
+        it = begin();
     return it;
 }
 
 SwPageDescs::const_iterator SwPageDescs::find( const value_type& x ) const
 {
-    const_iterator const it = std::find_if(
-        begin(), end(), spd_item_compare( x ) );
-    return it;
+    return find( x->GetName() );
 }
 
-bool SwPageDescs::Contains( const SwPageDescs::value_type& x ) const
+bool SwPageDescs::Contains( const value_type& x ) const
 {
     return (x->list == this);
 }