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