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