iOS/Pods/Realm/include/index_set.hpp

   1 ////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Copyright 2015 Realm Inc.
   4 //
   5 // Licensed under the Apache License, Version 2.0 (the "License");
   6 // you may not use this file except in compliance with the License.
   7 // You may obtain a copy of the License at
   8 //
   9 // http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing, software
  12 // distributed under the License is distributed on an "AS IS" BASIS,
  13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 // See the License for the specific language governing permissions and
  15 // limitations under the License.
  16 //
  17 ////////////////////////////////////////////////////////////////////////////
  18
  19 #ifndef REALM_INDEX_SET_HPP
  20 #define REALM_INDEX_SET_HPP
  21
  22 #include <cstddef>
  23 #include <initializer_list>
  24 #include <iterator>
  25 #include <type_traits>
  26 #include <utility>
  27 #include <vector>
  28
  29 namespace realm {
  30 namespace _impl {
  31 template<typename OuterIterator>
  32 class MutableChunkedRangeVectorIterator;
  33
  34 // An iterator for ChunkedRangeVector, templated on the vector iterator/const_iterator
  35 template<typename OuterIterator>
  36 class ChunkedRangeVectorIterator {
  37 public:
  38     using iterator_category = std::bidirectional_iterator_tag;
  39     using value_type = typename std::remove_reference<decltype(*OuterIterator()->data.begin())>::type;
  40     using difference_type = ptrdiff_t;
  41     using pointer = const value_type*;
  42     using reference = const value_type&;
  43
  44     ChunkedRangeVectorIterator(OuterIterator outer, OuterIterator end, value_type* inner)
  45     : m_outer(outer), m_end(end), m_inner(inner) { }
  46
  47     reference operator*() const noexcept { return *m_inner; }
  48     pointer operator->() const noexcept { return m_inner; }
  49
  50     template<typename Other> bool operator==(Other const& it) const noexcept;
  51     template<typename Other> bool operator!=(Other const& it) const noexcept;
  52
  53     ChunkedRangeVectorIterator& operator++() noexcept;
  54     ChunkedRangeVectorIterator operator++(int) noexcept;
  55
  56     ChunkedRangeVectorIterator& operator--() noexcept;
  57     ChunkedRangeVectorIterator operator--(int) noexcept;
  58
  59     // Advance directly to the next outer block
  60     void next_chunk() noexcept;
  61
  62     OuterIterator outer() const noexcept { return m_outer; }
  63     size_t offset() const noexcept { return m_inner - &m_outer->data[0]; }
  64
  65 private:
  66     OuterIterator m_outer;
  67     OuterIterator m_end;
  68     value_type* m_inner;
  69     friend struct ChunkedRangeVector;
  70     friend class MutableChunkedRangeVectorIterator<OuterIterator>;
  71 };
  72
  73 // A mutable iterator that adds some invariant-preserving mutation methods
  74 template<typename OuterIterator>
  75 class MutableChunkedRangeVectorIterator : public ChunkedRangeVectorIterator<OuterIterator> {
  76 public:
  77     using ChunkedRangeVectorIterator<OuterIterator>::ChunkedRangeVectorIterator;
  78
  79     // Set this iterator to the given range and update the parent if needed
  80     void set(size_t begin, size_t end);
  81     // Adjust the begin and end of this iterator by the given amounts and
  82     // update the parent if needed
  83     void adjust(ptrdiff_t front, ptrdiff_t back);
  84     // Shift this iterator by the given amount and update the parent if needed
  85     void shift(ptrdiff_t distance);
  86 };
  87
  88 // A vector which stores ranges in chunks with a maximum size
  89 struct ChunkedRangeVector {
  90     struct Chunk {
  91         std::vector<std::pair<size_t, size_t>> data;
  92         size_t begin;
  93         size_t end;
  94         size_t count;
  95     };
  96     std::vector<Chunk> m_data;
  97
  98     using value_type = std::pair<size_t, size_t>;
  99     using iterator = MutableChunkedRangeVectorIterator<typename decltype(m_data)::iterator>;
 100     using const_iterator = ChunkedRangeVectorIterator<typename decltype(m_data)::const_iterator>;
 101
 102 #ifdef REALM_DEBUG
 103     static const size_t max_size = 4;
 104 #else
 105     static const size_t max_size = 4096 / sizeof(std::pair<size_t, size_t>);
 106 #endif
 107
 108     iterator begin() noexcept { return empty() ? end() : iterator(m_data.begin(), m_data.end(), &m_data[0].data[0]); }
 109     iterator end() noexcept { return iterator(m_data.end(), m_data.end(), nullptr); }
 110     const_iterator begin() const noexcept { return cbegin(); }
 111     const_iterator end() const noexcept { return cend(); }
 112     const_iterator cbegin() const noexcept { return empty() ? cend() : const_iterator(m_data.cbegin(), m_data.end(), &m_data[0].data[0]); }
 113     const_iterator cend() const noexcept { return const_iterator(m_data.end(), m_data.end(), nullptr); }
 114
 115     bool empty() const noexcept { return m_data.empty(); }
 116
 117     iterator insert(iterator pos, value_type value);
 118     iterator erase(iterator pos) noexcept;
 119     void push_back(value_type value);
 120     iterator ensure_space(iterator pos);
 121
 122     void verify() const noexcept;
 123 };
 124 } // namespace _impl
 125
 126 class IndexSet : private _impl::ChunkedRangeVector {
 127 public:
 128     static const size_t npos = -1;
 129
 130     using ChunkedRangeVector::value_type;
 131     using ChunkedRangeVector::iterator;
 132     using ChunkedRangeVector::const_iterator;
 133     using ChunkedRangeVector::begin;
 134     using ChunkedRangeVector::end;
 135     using ChunkedRangeVector::empty;
 136     using ChunkedRangeVector::verify;
 137
 138     IndexSet() = default;
 139     IndexSet(std::initializer_list<size_t>);
 140
 141     // Check if the index set contains the given index
 142     bool contains(size_t index) const noexcept;
 143
 144     // Counts the number of indices in the set in the given range
 145     size_t count(size_t start_index=0, size_t end_index=-1) const noexcept;
 146
 147     // Add an index to the set, doing nothing if it's already present
 148     void add(size_t index);
 149     void add(IndexSet const& is);
 150
 151     // Add an index which has had all of the ranges in the set before it removed
 152     // Returns the unshifted index
 153     size_t add_shifted(size_t index);
 154     // Add indexes which have had the ranges in `shifted_by` added and the ranges
 155     // in the current set removed
 156     void add_shifted_by(IndexSet const& shifted_by, IndexSet const& values);
 157
 158     // Remove all indexes from the set and then add a single range starting from
 159     // zero with the given length
 160     void set(size_t len);
 161
 162     // Insert an index at the given position, shifting existing indexes at or
 163     // after that point back by one
 164     void insert_at(size_t index, size_t count=1);
 165     void insert_at(IndexSet const&);
 166
 167     // Shift indexes at or after the given point back by one
 168     void shift_for_insert_at(size_t index, size_t count=1);
 169     void shift_for_insert_at(IndexSet const&);
 170
 171     // Delete an index at the given position, shifting indexes after that point
 172     // forward by one
 173     void erase_at(size_t index);
 174     void erase_at(IndexSet const&);
 175
 176     // If the given index is in the set remove it and return npos; otherwise unshift() it
 177     size_t erase_or_unshift(size_t index);
 178
 179     // Remove the indexes at the given index from the set, without shifting
 180     void remove(size_t index, size_t count=1);
 181     void remove(IndexSet const&);
 182
 183     // Shift an index by inserting each of the indexes in this set
 184     size_t shift(size_t index) const noexcept;
 185     // Shift an index by deleting each of the indexes in this set
 186     size_t unshift(size_t index) const noexcept;
 187
 188     // Remove all indexes from the set
 189     void clear() noexcept;
 190
 191     // An iterator over the individual indices in the set rather than the ranges
 192     class IndexIterator : public std::iterator<std::forward_iterator_tag, size_t> {
 193     public:
 194         IndexIterator(IndexSet::const_iterator it) : m_iterator(it) { }
 195         size_t operator*() const noexcept { return m_iterator->first + m_offset; }
 196         bool operator==(IndexIterator const& it) const noexcept { return m_iterator == it.m_iterator; }
 197         bool operator!=(IndexIterator const& it) const noexcept { return m_iterator != it.m_iterator; }
 198
 199         IndexIterator& operator++() noexcept
 200         {
 201             ++m_offset;
 202             if (m_iterator->first + m_offset == m_iterator->second) {
 203                 ++m_iterator;
 204                 m_offset = 0;
 205             }
 206             return *this;
 207         }
 208
 209         IndexIterator operator++(int) noexcept
 210         {
 211             auto value = *this;
 212             ++*this;
 213             return value;
 214         }
 215
 216     private:
 217         IndexSet::const_iterator m_iterator;
 218         size_t m_offset = 0;
 219     };
 220
 221     class IndexIteratableAdaptor {
 222     public:
 223         using value_type = size_t;
 224         using iterator = IndexIterator;
 225         using const_iterator = iterator;
 226
 227         const_iterator begin() const noexcept { return m_index_set.begin(); }
 228         const_iterator end() const noexcept { return m_index_set.end(); }
 229
 230         IndexIteratableAdaptor(IndexSet const& is) : m_index_set(is) { }
 231     private:
 232         IndexSet const& m_index_set;
 233     };
 234
 235     IndexIteratableAdaptor as_indexes() const noexcept { return *this; }
 236
 237 private:
 238     // Find the range which contains the index, or the first one after it if
 239     // none do
 240     iterator find(size_t index) noexcept;
 241     iterator find(size_t index, iterator it) noexcept;
 242     // Insert the index before the given position, combining existing ranges as
 243     // applicable
 244     // returns inserted position
 245     iterator do_add(iterator pos, size_t index);
 246     void do_erase(iterator it, size_t index);
 247     iterator do_remove(iterator it, size_t index, size_t count);
 248
 249     void shift_until_end_by(iterator begin, ptrdiff_t shift);
 250 };
 251
 252 namespace util {
 253 // This was added in C++14 but is missing from libstdc++ 4.9
 254 template<typename Iterator>
 255 std::reverse_iterator<Iterator> make_reverse_iterator(Iterator it) noexcept
 256 {
 257     return std::reverse_iterator<Iterator>(it);
 258 }
 259 } // namespace util
 260
 261
 262 namespace _impl {
 263 template<typename T>
 264 template<typename OtherIterator>
 265 inline bool ChunkedRangeVectorIterator<T>::operator==(OtherIterator const& it) const noexcept
 266 {
 267     return m_outer == it.outer() && m_inner == it.operator->();
 268 }
 269
 270 template<typename T>
 271 template<typename OtherIterator>
 272 inline bool ChunkedRangeVectorIterator<T>::operator!=(OtherIterator const& it) const noexcept
 273 {
 274     return !(*this == it);
 275 }
 276
 277 template<typename T>
 278 inline ChunkedRangeVectorIterator<T>& ChunkedRangeVectorIterator<T>::operator++() noexcept
 279 {
 280     ++m_inner;
 281     if (offset() == m_outer->data.size())
 282         next_chunk();
 283     return *this;
 284 }
 285
 286 template<typename T>
 287 inline ChunkedRangeVectorIterator<T> ChunkedRangeVectorIterator<T>::operator++(int) noexcept
 288 {
 289     auto value = *this;
 290     ++*this;
 291     return value;
 292 }
 293
 294 template<typename T>
 295 inline ChunkedRangeVectorIterator<T>& ChunkedRangeVectorIterator<T>::operator--() noexcept
 296 {
 297     if (!m_inner || m_inner == &m_outer->data.front()) {
 298         --m_outer;
 299         m_inner = &m_outer->data.back();
 300     }
 301     else {
 302         --m_inner;
 303     }
 304     return *this;
 305 }
 306
 307 template<typename T>
 308 inline ChunkedRangeVectorIterator<T> ChunkedRangeVectorIterator<T>::operator--(int) noexcept
 309 {
 310     auto value = *this;
 311     --*this;
 312     return value;
 313 }
 314
 315 template<typename T>
 316 inline void ChunkedRangeVectorIterator<T>::next_chunk() noexcept
 317 {
 318     ++m_outer;
 319     m_inner = m_outer != m_end ? &m_outer->data[0] : nullptr;
 320 }
 321 } // namespace _impl
 322
 323 } // namespace realm
 324
 325 #endif // REALM_INDEX_SET_HPP