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 <algorithm>
  15 #include <functional>
  16 #include <memory>
  17 #include <type_traits>
  18
  19 namespace o3tl
  20 {
  21
  22 // forward declared because it's default template arg for sorted_vector
  23 template<class Value, class Compare>
  24 struct find_unique;
  25
  26 /** Represents a sorted vector of values.
  27
  28     @tpl Value class of item to be stored in container
  29     @tpl Compare comparison method
  30     @tpl Find   look up index of a Value in the array
  31 */
  32 template<
  33      typename Value,
  34      typename Compare = std::less<Value>,
  35      template<typename, typename> class Find = find_unique,
  36      bool = std::is_copy_constructible<Value>::value >
  37 class sorted_vector
  38 {
  39 private:
  40     typedef Find<Value, Compare> Find_t;
  41     typedef typename std::vector<Value> vector_t;
  42     typedef typename std::vector<Value>::iterator  iterator;
  43 public:
  44     typedef typename std::vector<Value>::const_iterator const_iterator;
  45     typedef typename std::vector<Value>::const_reverse_iterator const_reverse_iterator;
  46     typedef typename std::vector<Value>::difference_type difference_type;
  47     typedef typename std::vector<Value>::size_type size_type;
  48     typedef Value value_type;
  49
  50     constexpr sorted_vector( std::initializer_list<Value> init )
  51         : m_vector(init)
  52     {
  53         std::sort(m_vector.begin(), m_vector.end(), Compare());
  54     }
  55     sorted_vector() = default;
  56     sorted_vector(sorted_vector const&) = default;
  57     sorted_vector(sorted_vector&&) = default;
  58
  59     sorted_vector& operator=(sorted_vector const&) = default;
  60     sorted_vector& operator=(sorted_vector&&) = default;
  61
  62     // MODIFIERS
  63
  64     std::pair<const_iterator,bool> insert( Value&& x )
  65     {
  66         std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
  67         if (!ret.second)
  68         {
  69             const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), std::move(x));
  70             return std::make_pair(it, true);
  71         }
  72         return std::make_pair(ret.first, false);
  73     }
  74
  75     std::pair<const_iterator,bool> insert( const Value& x )
  76     {
  77         std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
  78         if (!ret.second)
  79         {
  80             const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), x);
  81             return std::make_pair(it, true);
  82         }
  83         return std::make_pair(ret.first, false);
  84     }
  85
  86     size_type erase( const Value& x )
  87     {
  88         std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
  89         if (ret.second)
  90         {
  91             m_vector.erase(m_vector.begin() + (ret.first - m_vector.begin()));
  92             return 1;
  93         }
  94         return 0;
  95     }
  96
  97     void erase( size_t index )
  98     {
  99         m_vector.erase(m_vector.begin() + index);
 100     }
 101
 102     // like C++ 2011: erase with const_iterator (doesn't change sort order)
 103     const_iterator erase(const_iterator const& position)
 104     {   // C++98 has vector::erase(iterator), so call that
 105         return m_vector.erase(m_vector.begin() + (position - m_vector.begin()));
 106     }
 107
 108     void erase(const_iterator const& first, const_iterator const& last)
 109     {
 110         m_vector.erase(m_vector.begin() + (first - m_vector.begin()),
 111                        m_vector.begin() + (last - m_vector.begin()));
 112     }
 113
 114     /**
 115      * make erase return the removed element, otherwise there is no useful way of extracting a std::unique_ptr
 116      * from this.
 117      */
 118     Value erase_extract( size_t index )
 119     {
 120         Value val = std::move(m_vector[index]);
 121         m_vector.erase(m_vector.begin() + index);
 122         return val;
 123     }
 124
 125     void clear()
 126     {
 127         m_vector.clear();
 128     }
 129
 130     void swap(sorted_vector & other)
 131     {
 132         m_vector.swap(other.m_vector);
 133     }
 134
 135     void reserve(size_type amount)
 136     {
 137         m_vector.reserve(amount);
 138     }
 139
 140     // ACCESSORS
 141
 142     size_type size() const
 143     {
 144         return m_vector.size();
 145     }
 146
 147     bool empty() const
 148     {
 149         return m_vector.empty();
 150     }
 151
 152     // Only return a const iterator, so that the vector cannot be directly updated.
 153     const_iterator begin() const
 154     {
 155         return m_vector.begin();
 156     }
 157
 158     // Only return a const iterator, so that the vector cannot be directly updated.
 159     const_iterator end() const
 160     {
 161         return m_vector.end();
 162     }
 163
 164     // Only return a const iterator, so that the vector cannot be directly updated.
 165     const_reverse_iterator rbegin() const
 166     {
 167         return m_vector.rbegin();
 168     }
 169
 170     // Only return a const iterator, so that the vector cannot be directly updated.
 171     const_reverse_iterator rend() const
 172     {
 173         return m_vector.rend();
 174     }
 175
 176     const Value& front() const
 177     {
 178         return m_vector.front();
 179     }
 180
 181     const Value& back() const
 182     {
 183         return m_vector.back();
 184     }
 185
 186     const Value& operator[]( size_t index ) const
 187     {
 188         return m_vector.operator[]( index );
 189     }
 190
 191     // OPERATIONS
 192
 193     const_iterator lower_bound( const Value& x ) const
 194     {
 195         return std::lower_bound( m_vector.begin(), m_vector.end(), x, Compare() );
 196     }
 197
 198     const_iterator upper_bound( const Value& x ) const
 199     {
 200         return std::upper_bound( m_vector.begin(), m_vector.end(), x, Compare() );
 201     }
 202
 203     /* Searches the container for an element with a value of x
 204      * and returns an iterator to it if found, otherwise it returns an
 205      * iterator to sorted_vector::end (the element past the end of the container).
 206      *
 207      * Only return a const iterator, so that the vector cannot be directly updated.
 208      */
 209     const_iterator find( const Value& x ) const
 210     {
 211         std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
 212         return (ret.second) ? ret.first : m_vector.end();
 213     }
 214
 215     size_type count(const Value& v) const
 216     {
 217         return find(v) != end() ? 1 : 0;
 218     }
 219
 220     bool operator==(const sorted_vector & other) const
 221     {
 222         return m_vector == other.m_vector;
 223     }
 224
 225     bool operator!=(const sorted_vector & other) const
 226     {
 227         return m_vector != other.m_vector;
 228     }
 229
 230     void insert(sorted_vector<Value,Compare,Find> const& rOther)
 231     {
 232        // optimization for the rather common case that we are overwriting this with the contents
 233        // of another sorted vector
 234        if ( empty() )
 235        {
 236            m_vector.insert(m_vector.begin(), rOther.m_vector.begin(), rOther.m_vector.end());
 237        }
 238        else
 239        {
 240            for (const_iterator it = rOther.m_vector.begin(); it != rOther.m_vector.end(); ++it)
 241            {
 242                insert(*it);
 243            }
 244        }
 245     }
 246
 247     /* Clear() elements in the vector, and free them one by one. */
 248     void DeleteAndDestroyAll()
 249     {
 250         for (const_iterator it = m_vector.begin(); it != m_vector.end(); ++it)
 251         {
 252             delete *it;
 253         }
 254
 255         clear();
 256     }
 257
 258     // fdo#58793: some existing code in Writer (SwpHintsArray)
 259     // routinely modifies the members of the vector in a way that
 260     // violates the sort order, and then re-sorts the array.
 261     // This is a kludge to enable that code to work.
 262     // If you are calling this function, you are Doing It Wrong!
 263     void Resort()
 264     {
 265         std::stable_sort(m_vector.begin(), m_vector.end(), Compare());
 266     }
 267
 268 private:
 269
 270     vector_t m_vector;
 271 };
 272
 273 /* Specialise the template for cases like Value = std::unique_ptr<T>, where
 274    MSVC2017 needs some help
 275 */
 276 template<
 277      typename Value,
 278      typename Compare,
 279      template<typename, typename> class Find >
 280 class sorted_vector<Value,Compare,Find,false> : public sorted_vector<Value, Compare, Find, true>
 281 {
 282 public:
 283     using sorted_vector<Value, Compare, Find, true>::sorted_vector;
 284     typedef sorted_vector<Value, Compare, Find, true> super_sorted_vector;
 285
 286     sorted_vector(sorted_vector const&) = delete;
 287     sorted_vector& operator=(sorted_vector const&) = delete;
 288
 289     sorted_vector() = default;
 290     sorted_vector(sorted_vector&&) = default;
 291     sorted_vector& operator=(sorted_vector&&) = default;
 292
 293     /**
 294      * implement find for sorted_vectors containing std::unique_ptr
 295      */
 296     typename super_sorted_vector::const_iterator find( typename Value::element_type const * x ) const
 297     {
 298         Value tmp(const_cast<typename Value::element_type*>(x));
 299         auto ret = super_sorted_vector::find(tmp);
 300         tmp.release();
 301         return ret;
 302     }
 303     /**
 304      * implement upper_bound for sorted_vectors containing std::unique_ptr
 305      */
 306     typename super_sorted_vector::const_iterator upper_bound( typename Value::element_type const * x ) const
 307     {
 308         Value tmp(const_cast<typename Value::element_type*>(x));
 309         auto ret = super_sorted_vector::upper_bound(tmp);
 310         tmp.release();
 311         return ret;
 312     }
 313     /**
 314      * implement lower_bound for sorted_vectors containing std::unique_ptr
 315      */
 316     typename super_sorted_vector::const_iterator lower_bound( typename Value::element_type const * x ) const
 317     {
 318         Value tmp(const_cast<typename Value::element_type*>(x));
 319         auto ret = super_sorted_vector::lower_bound(tmp);
 320         tmp.release();
 321         return ret;
 322     }
 323 };
 324
 325
 326 /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
 327     Very useful for the cases where we put pointers to objects inside a sorted_vector.
 328 */
 329 template <class T> struct less_ptr_to
 330 {
 331     bool operator() ( T* const& lhs, T* const& rhs ) const
 332     {
 333         return (*lhs) < (*rhs);
 334     }
 335 };
 336
 337 template <class T> struct less_uniqueptr_to
 338 {
 339     bool operator() ( std::unique_ptr<T> const& lhs, std::unique_ptr<T> const& rhs ) const
 340     {
 341         return (*lhs) < (*rhs);
 342     }
 343 };
 344
 345 /** the elements are totally ordered by Compare,
 346     for no 2 elements !Compare(a,b) && !Compare(b,a) is true
 347   */
 348 template<class Value, class Compare>
 349 struct find_unique
 350 {
 351     typedef typename sorted_vector<Value, Compare,
 352             o3tl::find_unique> ::const_iterator const_iterator;
 353     std::pair<const_iterator, bool> operator()(
 354             const_iterator first, const_iterator last,
 355             Value const& v)
 356     {
 357         const_iterator const it = std::lower_bound(first, last, v, Compare());
 358         return std::make_pair(it, (it != last && !Compare()(v, *it)));
 359     }
 360 };
 361
 362 /** the elements are partially ordered by Compare,
 363     2 elements are allowed if they are not the same element (pointer equal)
 364   */
 365 template<class Value, class Compare>
 366 struct find_partialorder_ptrequals
 367 {
 368     typedef typename sorted_vector<Value, Compare,
 369             o3tl::find_partialorder_ptrequals>::const_iterator const_iterator;
 370     std::pair<const_iterator, bool> operator()(
 371             const_iterator first, const_iterator last,
 372             Value const& v)
 373     {
 374         std::pair<const_iterator, const_iterator> const its =
 375             std::equal_range(first, last, v, Compare());
 376         for (const_iterator it = its.first; it != its.second; ++it)
 377         {
 378             if (v == *it)
 379             {
 380                 return std::make_pair(it, true);
 381             }
 382         }
 383         return std::make_pair(its.first, false);
 384     }
 385 };
 386
 387 }   // namespace o3tl
 388 #endif
 389
 390 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */