added iOS source code
[wl-app.git] / iOS / Pods / Realm / Realm / ObjectStore / src / index_set.cpp
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 #include "index_set.hpp"
20
21 #include <realm/util/assert.hpp>
22
23 #include <algorithm>
24
25 using namespace realm;
26 using namespace realm::_impl;
27
28 const size_t IndexSet::npos;
29
30 template<typename T>
31 void MutableChunkedRangeVectorIterator<T>::set(size_t front, size_t back)
32 {
33     this->m_outer->count -= this->m_inner->second - this->m_inner->first;
34     if (this->offset() == 0) {
35         this->m_outer->begin = front;
36     }
37     if (this->m_inner == &this->m_outer->data.back()) {
38         this->m_outer->end = back;
39     }
40     this->m_outer->count += back - front;
41     this->m_inner->first = front;
42     this->m_inner->second = back;
43 }
44
45 template<typename T>
46 void MutableChunkedRangeVectorIterator<T>::adjust(ptrdiff_t front, ptrdiff_t back)
47 {
48     if (this->offset() == 0) {
49         this->m_outer->begin += front;
50     }
51     if (this->m_inner == &this->m_outer->data.back()) {
52         this->m_outer->end += back;
53     }
54     this->m_outer->count += -front + back;
55     this->m_inner->first += front;
56     this->m_inner->second += back;
57 }
58
59 template<typename T>
60 void MutableChunkedRangeVectorIterator<T>::shift(ptrdiff_t distance)
61 {
62     if (this->offset() == 0) {
63         this->m_outer->begin += distance;
64     }
65     if (this->m_inner == &this->m_outer->data.back()) {
66         this->m_outer->end += distance;
67     }
68     this->m_inner->first += distance;
69     this->m_inner->second += distance;
70 }
71
72 void ChunkedRangeVector::push_back(value_type value)
73 {
74     if (!empty() && m_data.back().data.size() < max_size) {
75         auto& range = m_data.back();
76         REALM_ASSERT(range.end <= value.first);
77
78         range.data.push_back(value);
79         range.count += value.second - value.first;
80         range.end = value.second;
81     }
82     else {
83         m_data.push_back({{value}, value.first, value.second, value.second - value.first});
84     }
85     verify();
86 }
87
88 ChunkedRangeVector::iterator ChunkedRangeVector::insert(iterator pos, value_type value)
89 {
90     if (pos.m_outer == m_data.end()) {
91         push_back(std::move(value));
92         return std::prev(end());
93     }
94
95     pos = ensure_space(pos);
96     auto& chunk = *pos.m_outer;
97     pos.m_inner = &*chunk.data.insert(pos.m_outer->data.begin() + pos.offset(), value);
98     chunk.count += value.second - value.first;
99     chunk.begin = std::min(chunk.begin, value.first);
100     chunk.end = std::max(chunk.end, value.second);
101
102     verify();
103     return pos;
104 }
105
106 ChunkedRangeVector::iterator ChunkedRangeVector::ensure_space(iterator pos)
107 {
108     if (pos.m_outer->data.size() + 1 <= max_size)
109         return pos;
110
111     auto offset = pos.offset();
112
113     // Split the chunk in half to make space for the new insertion
114     auto new_pos = m_data.insert(pos.m_outer + 1, Chunk{});
115     auto prev = new_pos - 1;
116     auto to_move = max_size / 2;
117     new_pos->data.reserve(to_move);
118     new_pos->data.assign(prev->data.end() - to_move, prev->data.end());
119     prev->data.resize(prev->data.size() - to_move);
120
121     size_t moved_count = 0;
122     for (auto range : new_pos->data)
123         moved_count += range.second - range.first;
124
125     prev->end = prev->data.back().second;
126     prev->count -= moved_count;
127     new_pos->begin = new_pos->data.front().first;
128     new_pos->end = new_pos->data.back().second;
129     new_pos->count = moved_count;
130
131     if (offset >= to_move) {
132         pos.m_outer = new_pos;
133         offset -= to_move;
134     }
135     else {
136         pos.m_outer = prev;
137     }
138     pos.m_end = m_data.end();
139     pos.m_inner = &pos.m_outer->data[offset];
140     verify();
141     return pos;
142 }
143
144 ChunkedRangeVector::iterator ChunkedRangeVector::erase(iterator pos) noexcept
145 {
146     auto offset = pos.offset();
147     auto& chunk = *pos.m_outer;
148     chunk.count -= pos->second - pos->first;
149     chunk.data.erase(chunk.data.begin() + offset);
150
151     if (chunk.data.size() == 0) {
152         pos.m_outer = m_data.erase(pos.m_outer);
153         pos.m_end = m_data.end();
154         pos.m_inner = pos.m_outer == m_data.end() ? nullptr : &pos.m_outer->data.front();
155         verify();
156         return pos;
157     }
158
159     chunk.begin = chunk.data.front().first;
160     chunk.end = chunk.data.back().second;
161     if (offset < chunk.data.size())
162         pos.m_inner = &chunk.data[offset];
163     else {
164         ++pos.m_outer;
165         pos.m_inner = pos.m_outer == pos.m_end ? nullptr : &pos.m_outer->data.front();
166     }
167
168     verify();
169     return pos;
170 }
171
172 void ChunkedRangeVector::verify() const noexcept
173 {
174 #ifdef REALM_DEBUG
175     size_t prev_end = -1;
176     for (auto range : *this) {
177         REALM_ASSERT(range.first < range.second);
178         REALM_ASSERT(prev_end == size_t(-1) || range.first > prev_end);
179         prev_end = range.second;
180     }
181
182     for (auto& chunk : m_data) {
183         REALM_ASSERT(!chunk.data.empty());
184         REALM_ASSERT(chunk.data.front().first == chunk.begin);
185         REALM_ASSERT(chunk.data.back().second == chunk.end);
186         REALM_ASSERT(chunk.count <= chunk.end - chunk.begin);
187         size_t count = 0;
188         for (auto range : chunk.data)
189             count += range.second - range.first;
190         REALM_ASSERT(count == chunk.count);
191     }
192 #endif
193 }
194
195 namespace {
196 class ChunkedRangeVectorBuilder {
197 public:
198     using value_type = std::pair<size_t, size_t>;
199
200     ChunkedRangeVectorBuilder(ChunkedRangeVector const& expected);
201     void push_back(size_t index);
202     void push_back(std::pair<size_t, size_t> range);
203     std::vector<ChunkedRangeVector::Chunk> finalize();
204 private:
205     std::vector<ChunkedRangeVector::Chunk> m_data;
206     size_t m_outer_pos = 0;
207 };
208
209 ChunkedRangeVectorBuilder::ChunkedRangeVectorBuilder(ChunkedRangeVector const& expected)
210 {
211     size_t size = 0;
212     for (auto const& chunk : expected.m_data)
213         size += chunk.data.size();
214     m_data.resize(size / ChunkedRangeVector::max_size + 1);
215     for (size_t i = 0; i < m_data.size() - 1; ++i)
216         m_data[i].data.reserve(ChunkedRangeVector::max_size);
217 }
218
219 void ChunkedRangeVectorBuilder::push_back(size_t index)
220 {
221     push_back({index, index + 1});
222 }
223
224 void ChunkedRangeVectorBuilder::push_back(std::pair<size_t, size_t> range)
225 {
226     auto& chunk = m_data[m_outer_pos];
227     if (chunk.data.empty()) {
228         chunk.data.push_back(range);
229         chunk.count = range.second - range.first;
230         chunk.begin = range.first;
231     }
232     else if (range.first == chunk.data.back().second) {
233         chunk.data.back().second = range.second;
234         chunk.count += range.second - range.first;
235     }
236     else if (chunk.data.size() < ChunkedRangeVector::max_size) {
237         chunk.data.push_back(range);
238         chunk.count += range.second - range.first;
239     }
240     else {
241         chunk.end = chunk.data.back().second;
242         ++m_outer_pos;
243         if (m_outer_pos >= m_data.size())
244             m_data.push_back({{range}, range.first, 0, 1});
245         else {
246             auto& chunk = m_data[m_outer_pos];
247             chunk.data.push_back(range);
248             chunk.begin = range.first;
249             chunk.count = range.second - range.first;
250         }
251     }
252 }
253
254 std::vector<ChunkedRangeVector::Chunk> ChunkedRangeVectorBuilder::finalize()
255 {
256     if (!m_data.empty()) {
257         m_data.resize(m_outer_pos + 1);
258         if (m_data.back().data.empty())
259             m_data.pop_back();
260         else
261             m_data.back().end = m_data.back().data.back().second;
262     }
263     return std::move(m_data);
264 }
265 }
266
267 IndexSet::IndexSet(std::initializer_list<size_t> values)
268 {
269     for (size_t v : values)
270         add(v);
271 }
272
273 bool IndexSet::contains(size_t index) const noexcept
274 {
275     auto it = const_cast<IndexSet*>(this)->find(index);
276     return it != end() && it->first <= index;
277 }
278
279 size_t IndexSet::count(size_t start_index, size_t end_index) const noexcept
280 {
281     auto it = const_cast<IndexSet*>(this)->find(start_index);
282     const auto end = this->end();
283     if (it == end || it->first >= end_index) {
284         return 0;
285     }
286     if (it->second >= end_index)
287         return std::min(it->second, end_index) - std::max(it->first, start_index);
288
289     size_t ret = 0;
290
291     if (start_index > it->first || it.offset() != 0) {
292         // Start index is in the middle of a chunk, so start by counting the
293         // rest of that chunk
294         ret = it->second - std::max(it->first, start_index);
295         for (++it; it != end && it->second < end_index && it.offset() != 0; ++it) {
296             ret += it->second - it->first;
297         }
298         if (it != end && it->first < end_index && it.offset() != 0)
299             ret += end_index - it->first;
300         if (it == end || it->second >= end_index)
301             return ret;
302     }
303
304     // Now count all complete chunks that fall within the range
305     while (it != end && it.outer()->end <= end_index) {
306         REALM_ASSERT_DEBUG(it.offset() == 0);
307         ret += it.outer()->count;
308         it.next_chunk();
309     }
310
311     // Cound all complete ranges within the last chunk
312     while (it != end && it->second <= end_index) {
313         ret += it->second - it->first;
314         ++it;
315     }
316
317     // And finally add in the partial last range
318     if (it != end && it->first < end_index)
319         ret += end_index - it->first;
320     return ret;
321 }
322
323 IndexSet::iterator IndexSet::find(size_t index) noexcept
324 {
325     return find(index, begin());
326 }
327
328 IndexSet::iterator IndexSet::find(size_t index, iterator begin) noexcept
329 {
330     auto it = std::find_if(begin.outer(), m_data.end(),
331                            [&](auto const& lft) { return lft.end > index; });
332     if (it == m_data.end())
333         return end();
334     if (index < it->begin)
335         return iterator(it, m_data.end(), &it->data[0]);
336     auto inner_begin = it->data.begin();
337     if (it == begin.outer())
338         inner_begin += begin.offset();
339     auto inner = std::lower_bound(inner_begin, it->data.end(), index,
340                                   [&](auto const& lft, auto) { return lft.second <= index; });
341     REALM_ASSERT_DEBUG(inner != it->data.end());
342
343     return iterator(it, m_data.end(), &*inner);
344 }
345
346 void IndexSet::add(size_t index)
347 {
348     do_add(find(index), index);
349 }
350
351 void IndexSet::add(IndexSet const& other)
352 {
353     auto it = begin();
354     for (size_t index : other.as_indexes()) {
355         it = do_add(find(index, it), index);
356     }
357 }
358
359 size_t IndexSet::add_shifted(size_t index)
360 {
361     iterator it = begin(), end = this->end();
362
363     // Shift for any complete chunks before the target
364     for (; it != end && it.outer()->end <= index; it.next_chunk())
365         index += it.outer()->count;
366
367     // And any ranges within the last partial chunk
368     for (; it != end && it->first <= index; ++it)
369         index += it->second - it->first;
370
371     do_add(it, index);
372     return index;
373 }
374
375 void IndexSet::add_shifted_by(IndexSet const& shifted_by, IndexSet const& values)
376 {
377     if (values.empty())
378         return;
379
380 #ifdef REALM_DEBUG
381     size_t expected = std::distance(as_indexes().begin(), as_indexes().end());
382     for (auto index : values.as_indexes()) {
383         if (!shifted_by.contains(index))
384             ++expected;
385     }
386 #endif
387
388     ChunkedRangeVectorBuilder builder(*this);
389
390     auto old_it = cbegin(), old_end = cend();
391     auto shift_it = shifted_by.cbegin(), shift_end = shifted_by.cend();
392
393     size_t skip_until = 0;
394     size_t old_shift = 0;
395     size_t new_shift = 0;
396     for (size_t index : values.as_indexes()) {
397         for (; shift_it != shift_end && shift_it->first <= index; ++shift_it) {
398             new_shift += shift_it->second - shift_it->first;
399             skip_until = shift_it->second;
400         }
401         if (index < skip_until)
402             continue;
403
404         for (; old_it != old_end && old_it->first <= index - new_shift + old_shift; ++old_it) {
405             for (size_t i = old_it->first; i < old_it->second; ++i)
406                 builder.push_back(i);
407             old_shift += old_it->second - old_it->first;
408         }
409
410         REALM_ASSERT(index >= new_shift);
411         builder.push_back(index - new_shift + old_shift);
412     }
413
414     copy(old_it, old_end, std::back_inserter(builder));
415     m_data = builder.finalize();
416
417 #ifdef REALM_DEBUG
418     REALM_ASSERT((size_t)std::distance(as_indexes().begin(), as_indexes().end()) == expected);
419 #endif
420 }
421
422 void IndexSet::set(size_t len)
423 {
424     clear();
425     if (len) {
426         push_back({0, len});
427     }
428 }
429
430 void IndexSet::insert_at(size_t index, size_t count)
431 {
432     REALM_ASSERT(count > 0);
433
434     auto pos = find(index);
435     auto end = this->end();
436     bool in_existing = false;
437     if (pos != end) {
438         if (pos->first <= index) {
439             in_existing = true;
440             pos.adjust(0, count);
441         }
442         else {
443             pos.shift(count);
444         }
445         for (auto it = std::next(pos); it != end; ++it)
446             it.shift(count);
447     }
448     if (!in_existing) {
449         for (size_t i = 0; i < count; ++i)
450             pos = std::next(do_add(pos, index + i));
451     }
452
453     verify();
454 }
455
456 void IndexSet::insert_at(IndexSet const& positions)
457 {
458     if (positions.empty())
459         return;
460     if (empty()) {
461         *this = positions;
462         return;
463     }
464
465     IndexIterator begin1 = cbegin(), begin2 = positions.cbegin();
466     IndexIterator end1 = cend(), end2 = positions.cend();
467
468     ChunkedRangeVectorBuilder builder(*this);
469     size_t shift = 0;
470     while (begin1 != end1 && begin2 != end2) {
471         if (*begin1 + shift < *begin2) {
472             builder.push_back(*begin1++ + shift);
473         }
474         else {
475             ++shift;
476             builder.push_back(*begin2++);
477         }
478     }
479     for (; begin1 != end1; ++begin1)
480         builder.push_back(*begin1 + shift);
481     for (; begin2 != end2; ++begin2)
482         builder.push_back(*begin2);
483
484     m_data = builder.finalize();
485 }
486
487 void IndexSet::shift_for_insert_at(size_t index, size_t count)
488 {
489     REALM_ASSERT(count > 0);
490
491     auto it = find(index);
492     if (it == end())
493         return;
494
495     for (auto pos = it, end = this->end(); pos != end; ++pos)
496         pos.shift(count);
497
498     // If the range contained the insertion point, split the range and move
499     // the part of it before the insertion point back
500     if (it->first < index + count) {
501         auto old_second = it->second;
502         it.set(it->first - count, index);
503         insert(std::next(it), {index + count, old_second});
504     }
505     verify();
506 }
507
508 void IndexSet::shift_for_insert_at(realm::IndexSet const& values)
509 {
510     if (empty() || values.empty())
511         return;
512     if (values.m_data.front().begin >= m_data.back().end)
513         return;
514
515     IndexIterator begin1 = cbegin(), begin2 = values.cbegin();
516     IndexIterator end1 = cend(), end2 = values.cend();
517
518     ChunkedRangeVectorBuilder builder(*this);
519     size_t shift = 0;
520     while (begin1 != end1 && begin2 != end2) {
521         if (*begin1 + shift < *begin2) {
522             builder.push_back(*begin1++ + shift);
523         }
524         else {
525             ++shift;
526             begin2++;
527         }
528     }
529     for (; begin1 != end1; ++begin1)
530         builder.push_back(*begin1 + shift);
531
532     m_data = builder.finalize();
533 }
534
535 void IndexSet::erase_at(size_t index)
536 {
537     auto it = find(index);
538     if (it != end())
539         do_erase(it, index);
540 }
541
542 void IndexSet::erase_at(IndexSet const& positions)
543 {
544     if (empty() || positions.empty())
545         return;
546
547     ChunkedRangeVectorBuilder builder(*this);
548
549     IndexIterator begin1 = cbegin(), begin2 = positions.cbegin();
550     IndexIterator end1 = cend(), end2 = positions.cend();
551
552     size_t shift = 0;
553     while (begin1 != end1 && begin2 != end2) {
554         if (*begin1 < *begin2) {
555             builder.push_back(*begin1++ - shift);
556         }
557         else if (*begin1 == *begin2) {
558             ++shift;
559             ++begin1;
560             ++begin2;
561         }
562         else {
563             ++shift;
564             ++begin2;
565         }
566     }
567     for (; begin1 != end1; ++begin1)
568         builder.push_back(*begin1 - shift);
569
570     m_data = builder.finalize();
571 }
572
573 size_t IndexSet::erase_or_unshift(size_t index)
574 {
575     auto shifted = index;
576     iterator it = begin(), end = this->end();
577
578     // Shift for any complete chunks before the target
579     for (; it != end && it.outer()->end <= index; it.next_chunk())
580         shifted -= it.outer()->count;
581
582     // And any ranges within the last partial chunk
583     for (; it != end && it->second <= index; ++it)
584         shifted -= it->second - it->first;
585
586     if (it == end)
587         return shifted;
588
589     if (it->first <= index)
590         shifted = npos;
591
592     do_erase(it, index);
593
594     return shifted;
595 }
596
597 void IndexSet::do_erase(iterator it, size_t index)
598 {
599     if (it->first <= index) {
600         if (it->first + 1 == it->second) {
601             it = erase(it);
602         }
603         else {
604             it.adjust(0, -1);
605             ++it;
606         }
607     }
608     else if (it != begin() && std::prev(it)->second + 1 == it->first) {
609         std::prev(it).adjust(0, it->second - it->first);
610         it = erase(it);
611     }
612
613     for (; it != end(); ++it)
614         it.shift(-1);
615 }
616
617 IndexSet::iterator IndexSet::do_remove(iterator it, size_t begin, size_t end)
618 {
619     for (it = find(begin, it); it != this->end() && it->first < end; it = find(begin, it)) {
620         // Trim off any part of the range to remove that's before the matching range
621         begin = std::max(it->first, begin);
622
623         // If the matching range extends to both sides of the range to remove,
624         // split it on the range to remove
625         if (it->first < begin && it->second > end) {
626             auto old_second = it->second;
627             it.set(it->first, begin);
628             it = std::prev(insert(std::next(it), {end, old_second}));
629         }
630         // Range to delete now coverages (at least) one end of the matching range
631         else if (begin == it->first && end >= it->second)
632             it = erase(it);
633         else if (begin == it->first)
634             it.set(end, it->second);
635         else
636             it.set(it->first, begin);
637     }
638     return it;
639 }
640
641 void IndexSet::remove(size_t index, size_t count)
642 {
643     do_remove(find(index), index, index + count);
644 }
645
646 void IndexSet::remove(realm::IndexSet const& values)
647 {
648     auto it = begin();
649     for (auto range : values) {
650         it = do_remove(it, range.first, range.second);
651         if (it == end())
652             return;
653     }
654 }
655
656 size_t IndexSet::shift(size_t index) const noexcept
657 {
658     // FIXME: optimize
659     for (auto range : *this) {
660         if (range.first > index)
661             break;
662         index += range.second - range.first;
663     }
664     return index;
665 }
666
667 size_t IndexSet::unshift(size_t index) const noexcept
668 {
669     REALM_ASSERT_DEBUG(!contains(index));
670     return index - count(0, index);
671 }
672
673 void IndexSet::clear() noexcept
674 {
675     m_data.clear();
676 }
677
678 IndexSet::iterator IndexSet::do_add(iterator it, size_t index)
679 {
680     verify();
681     bool more_before = it != begin(), valid = it != end();
682     REALM_ASSERT(!more_before || index >= std::prev(it)->second);
683     if (valid && it->first <= index && it->second > index) {
684         // index is already in set
685         return it;
686     }
687     if (more_before && std::prev(it)->second == index) {
688         auto prev = std::prev(it);
689         // index is immediately after an existing range
690         prev.adjust(0, 1);
691
692         if (valid && prev->second == it->first) {
693             // index joins two existing ranges
694             prev.adjust(0, it->second - it->first);
695             return std::prev(erase(it));
696         }
697         return prev;
698     }
699     if (valid && it->first == index + 1) {
700         // index is immediately before an existing range
701         it.adjust(-1, 0);
702         return it;
703     }
704
705     // index is not next to an existing range
706     return insert(it, {index, index + 1});
707 }