include/o3tl/sorted_vector.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  */
   9
  10 #ifndef INCLUDED_O3TL_SORTED_VECTOR_HXX
  11 #define INCLUDED_O3TL_SORTED_VECTOR_HXX
  12
  13 #include <vector>
  14 #include <functional>
  15 #include <algorithm>
  16
  17 namespace o3tl
  18 {
  19
  20 // forward declared because it's default tempate arg for sorted_vector
  21 template<class Value, class Compare>
  22 struct find_unique;
  23
  24 /** Represents a sorted vector of values.
  25
  26     @tpl Value class of item to be stored in container
  27     @tpl Compare comparison method
  28     @tpl Find   look up index of a Value in the array
  29 */
  30 template<typename Value, typename Compare = std::less<Value>,
  31      template<typename, typename> class Find = find_unique >
  32 class sorted_vector
  33     : private std::vector<Value>
  34 {
  35 private:
  36     typedef Find<Value, Compare> Find_t;
  37     typedef typename std::vector<Value> base_t;
  38     typedef typename std::vector<Value>::iterator  iterator;
  39 public:
  40     typedef typename std::vector<Value>::const_iterator const_iterator;
  41     typedef typename std::vector<Value>::size_type size_type;
  42
  43     using base_t::clear;
  44     using base_t::empty;
  45     using base_t::size;
  46
  47     // MODIFIERS
  48
  49     std::pair<const_iterator,bool> insert( const Value& x )
  50     {
  51         std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
  52         if (!ret.second)
  53         {
  54             const_iterator const it = base_t::insert(
  55                             begin_nonconst() + (ret.first - begin()), x);
  56             return std::make_pair(it, true);
  57         }
  58         return std::make_pair(ret.first, false);
  59     }
  60
  61     size_type erase( const Value& x )
  62     {
  63         std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
  64         if (ret.second)
  65         {
  66             base_t::erase(begin_nonconst() + (ret.first - begin()));
  67             return 1;
  68         }
  69         return 0;
  70     }
  71
  72     void erase( size_t index )
  73     {
  74         base_t::erase( begin_nonconst() + index );
  75     }
  76
  77     // like C++ 2011: erase with const_iterator (doesn't change sort order)
  78     void erase(const_iterator const& position)
  79     {   // C++98 has vector::erase(iterator), so call that
  80         base_t::erase(begin_nonconst() + (position - begin()));
  81     }
  82
  83     void erase(const_iterator const& first, const_iterator const& last)
  84     {
  85         base_t::erase(begin_nonconst() + (first - begin()),
  86                       begin_nonconst() + (last  - begin()));
  87     }
  88
  89     // ACCESSORS
  90
  91     // Only return a const iterator, so that the vector cannot be directly updated.
  92     const_iterator begin() const
  93     {
  94         return base_t::begin();
  95     }
  96
  97     // Only return a const iterator, so that the vector cannot be directly updated.
  98     const_iterator end() const
  99     {
 100         return base_t::end();
 101     }
 102
 103     const Value& front() const
 104     {
 105         return base_t::front();
 106     }
 107
 108     const Value& back() const
 109     {
 110         return base_t::back();
 111     }
 112
 113     const Value& operator[]( size_t index ) const
 114     {
 115         return base_t::operator[]( index );
 116     }
 117
 118     // OPERATIONS
 119
 120     const_iterator lower_bound( const Value& x ) const
 121     {
 122         return std::lower_bound( base_t::begin(), base_t::end(), x, Compare() );
 123     }
 124
 125     const_iterator upper_bound( const Value& x ) const
 126     {
 127         return std::upper_bound( base_t::begin(), base_t::end(), x, Compare() );
 128     }
 129
 130     /* Searches the container for an element with a value of x
 131      * and returns an iterator to it if found, otherwise it returns an
 132      * iterator to sorted_vector::end (the element past the end of the container).
 133      *
 134      * Only return a const iterator, so that the vector cannot be directly updated.
 135      */
 136     const_iterator find( const Value& x ) const
 137     {
 138         std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
 139         return (ret.second) ? ret.first : end();
 140     }
 141
 142     void insert(sorted_vector<Value,Compare,Find> const& rOther)
 143     {
 144        // optimisation for the rather common case that we are overwriting this with the contents
 145        // of another sorted vector
 146        if ( empty() )
 147        {
 148            base_t::insert(begin_nonconst(), rOther.begin(), rOther.end());
 149        }
 150        else
 151            for( const_iterator it = rOther.begin(); it != rOther.end(); ++it )
 152                insert( *it );
 153     }
 154
 155     /* Clear() elements in the vector, and free them one by one. */
 156     void DeleteAndDestroyAll()
 157     {
 158         for( const_iterator it = begin(); it != end(); ++it )
 159             delete *it;
 160         clear();
 161     }
 162
 163     // fdo#58793: some existing code in Writer (SwpHintsArray)
 164     // routinely modifies the members of the vector in a way that
 165     // violates the sort order, and then re-sorts the array.
 166     // This is a kludge to enable that code to work.
 167     // If you are calling this function, you are Doing It Wrong!
 168     void Resort()
 169     {
 170         std::stable_sort(begin_nonconst(), end_nonconst(), Compare());
 171     }
 172
 173 private:
 174
 175     typename base_t::iterator begin_nonconst() { return base_t::begin(); }
 176     typename base_t::iterator end_nonconst()   { return base_t::end(); }
 177
 178 };
 179
 180
 181 /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
 182     Very useful for the cases where we put pointers to objects inside a sorted_vector.
 183 */
 184 template <class T> struct less_ptr_to : public std::binary_function <T*,T*,bool>
 185 {
 186     bool operator() ( T* const& lhs, T* const& rhs ) const
 187     {
 188         return (*lhs) < (*rhs);
 189     }
 190 };
 191
 192 /** the elements are totally ordered by Compare,
 193     for no 2 elements !Compare(a,b) && !Compare(b,a) is true
 194   */
 195 template<class Value, class Compare>
 196 struct find_unique
 197 {
 198     typedef typename sorted_vector<Value, Compare,
 199             o3tl::find_unique> ::const_iterator const_iterator;
 200     std::pair<const_iterator, bool> operator()(
 201             const_iterator first, const_iterator last,
 202             Value const& v)
 203     {
 204         const_iterator const it = std::lower_bound(first, last, v, Compare());
 205         return std::make_pair(it, (it != last && !Compare()(v, *it)));
 206     }
 207 };
 208
 209 /** the elements are partially ordered by Compare,
 210     2 elements are allowed if they are not the same element (pointer equal)
 211   */
 212 template<class Value, class Compare>
 213 struct find_partialorder_ptrequals
 214 {
 215     typedef typename sorted_vector<Value, Compare,
 216             o3tl::find_partialorder_ptrequals>::const_iterator const_iterator;
 217     std::pair<const_iterator, bool> operator()(
 218             const_iterator first, const_iterator last,
 219             Value const& v)
 220     {
 221         std::pair<const_iterator, const_iterator> const its =
 222             std::equal_range(first, last, v, Compare());
 223         for (const_iterator it = its.first; it != its.second; ++it)
 224         {
 225             if (v == *it)
 226             {
 227                 return std::make_pair(it, true);
 228             }
 229         }
 230         return std::make_pair(its.first, false);
 231     }
 232 };
 233
 234 }   // namespace o3tl
 235 #endif
 236
 237 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */