PLaSK library

Loading...
Searching...
No Matches
numbers_set.hpp
Go to the documentation of this file.
1/*
2 * This file is part of PLaSK (https://plask.app) by Photonics Group at TUL
3 * Copyright (c) 2022 Lodz University of Technology
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, version 3.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 */
14#ifndef PLASK__UTILS_NUMBERS_SET_H
15#define PLASK__UTILS_NUMBERS_SET_H
16
17#include <vector>
18#include <algorithm>
19#include <limits>
20#include <boost/iterator/iterator_facade.hpp>
21
22#include "../exceptions.hpp"
23
24 namespace plask {
25
31 template <typename number_t = std::size_t>
32 struct CompressedSetOfNumbers {
33
34 struct Segment {
35
36 number_t numberEnd;
37
38 number_t indexEnd;
39
40 static bool compareByIndexEnd(number_t i, const Segment& seg) { return i < seg.indexEnd; }
41
42 static bool compareByNumberEnd(number_t n, const Segment& seg) { return n < seg.numberEnd; }
43
44 Segment() = default;
45
46 Segment(number_t numberEnd, number_t indexEnd): numberEnd(numberEnd), indexEnd(indexEnd) {}
47
48 bool operator==(const Segment& other) const {
49 return numberEnd == other.numberEnd && indexEnd == other.indexEnd;
50 }
51
52 bool operator!=(const Segment& other) const {
53 return numberEnd != other.numberEnd || indexEnd != other.indexEnd;
54 }
55
56 };
57
58 std::vector<Segment> segments;
59
60 CompressedSetOfNumbers() = default;
61
62 CompressedSetOfNumbers(const std::initializer_list<number_t>& sorted_list) {
63 for (number_t n: sorted_list) push_back(n);
64 }
65
66 /*number_t sizeOfSegment(std::size_t seg_nr) const {
67 return (seg_nr == 0) ? segments.front().indexEnd : (segments[seg_nr].indexEnd - segments[seg_nr-1].indexEnd);
68 }*/
69
70 number_t sizeOfSegment(typename std::vector<Segment>::const_iterator it) const {
71 return (it == segments.begin()) ? it->indexEnd : (it->indexEnd - (it-1)->indexEnd);
72 }
73
79 number_t firstIndex(typename std::vector<Segment>::const_iterator it) const {
80 return (it == segments.begin()) ? 0 : (it-1)->indexEnd;
81 }
82
88 number_t firstNumber(typename std::vector<Segment>::const_iterator it) const {
89 return it->numberEnd - sizeOfSegment(it);
90 }
91
100 template <typename Derived, class Value = number_t, class Reference = Value>
101 struct ConstIteratorFacade: public boost::iterator_facade<Derived, Value, boost::random_access_traversal_tag, Reference> {
102
103 typedef typename std::vector<Segment>::const_iterator ConstSegmentIterator;
104
106 ConstSegmentIterator segmentIterator;
107
109 std::size_t index;
110
112 ConstIteratorFacade() {}
113
114 ConstIteratorFacade(std::size_t index, ConstSegmentIterator segmentIterator): segmentIterator(segmentIterator), index(index) {}
115
116 ConstIteratorFacade(std::size_t index) { setIndex(index); }
117
122 std::size_t getIndex() const { return index; }
123
124 void setIndex(std::size_t index) {
125 this->index = index;
126 segmentIterator = std::upper_bound(_set().segments.begin(), _set().segments.end(), index, Segment::compareByIndexEnd);
127 }
128
129 number_t getNumber() const {
130 return segmentIterator->numberEnd - segmentIterator->indexEnd + index;
131 }
132
133 private: //--- methods used by boost::iterator_facade: ---
134
135 friend class boost::iterator_core_access;
136
137 const CompressedSetOfNumbers<number_t>& _set() const {
138 return static_cast<const Derived*>(this)->set();
139 }
140
141 template <typename OtherT>
142 bool equal(const OtherT& other) const {
143 return index == other.index;
144 }
145
146 void increment() {
147 ++index;
148 if (index == segmentIterator->indexEnd) ++segmentIterator;
149 }
150
151 void decrement() {
152 --index;
153 if (index < _set().firstIndex(segmentIterator)) --segmentIterator;
154 }
155
156 void advance(std::ptrdiff_t to_add) {
157 setIndex(index + to_add);
158 }
159
160 template <typename OtherT>
161 std::ptrdiff_t distance_to(OtherT z) const { return std::ptrdiff_t(z.index) - std::ptrdiff_t(index); }
162
163 number_t dereference() const { // can be overrwritten by Derived class
164 return getNumber();
165 }
166
167 };
168
169 class const_iterator: public ConstIteratorFacade<const_iterator> {
170
171 const CompressedSetOfNumbers* _set;
172
173 public:
174
175 template <typename... CtorArgs>
176 explicit const_iterator(const CompressedSetOfNumbers& set, CtorArgs&&... ctorArgs)
177 : ConstIteratorFacade<const_iterator>(std::forward<CtorArgs>(ctorArgs)...), _set(&set) {}
178
179 const CompressedSetOfNumbers<number_t>& set() const { return *_set; }
180
181 };
182
183 typedef const_iterator iterator; // we don't support non-const iterators
184
185 const_iterator begin() const { return const_iterator(*this, 0, segments.begin()); }
186 const_iterator end() const { return const_iterator(*this, size(), segments.end()); }
187
188
189
196 std::size_t size() const { return segments.empty() ? 0 : segments.back().indexEnd; }
197
203 void shrink_to_fit() { segments.shrink_to_fit(); }
204
213 void reserve(std::size_t n) { segments.reserve(n); }
214
216 void clear() { segments.clear(); }
217
224 std::size_t segmentsCount() const { return segments.size(); }
225
232 bool empty() const { return segments.empty(); }
233
241 number_t operator[](std::size_t index) const {
242 auto seg_it = std::upper_bound(segments.begin(), segments.end(), index, Segment::compareByIndexEnd);
243 // here: index < seg_it->indexEnd
244 assert(seg_it != segments.end()); // true for valid index
245 return seg_it->numberEnd - seg_it->indexEnd + index; // must be non-negative as numberEnd >= indexEnd
246 }
247
255 number_t at(std::size_t index) const {
256 auto seg_it = std::upper_bound(segments.begin(), segments.end(), index, Segment::compareByIndexEnd);
257 if (seg_it == segments.end()) throw OutOfBoundsException("compressedSetOfNumbers::at", "index", index, 0, this->size()-1);
258 // here: index < seg_it->indexEnd
259 return seg_it->numberEnd + index - seg_it->indexEnd;
260 }
261
263 enum:std::size_t { NOT_INCLUDED = std::numeric_limits<std::size_t>::max() };
264
272 std::size_t indexOf(number_t number) const {
273 auto seg_it = std::upper_bound(segments.begin(), segments.end(), number, Segment::compareByNumberEnd);
274 if (seg_it == segments.end()) return NOT_INCLUDED; // number is too large
275 // here: number < seg_it->numberEnd
276 std::ptrdiff_t index = std::ptrdiff_t(seg_it->indexEnd) + std::ptrdiff_t(number) - std::ptrdiff_t(seg_it->numberEnd);
277 // index can even be negative here
278 return index >= std::ptrdiff_t(firstIndex(seg_it)) ? std::size_t(index) : NOT_INCLUDED;
279 }
280
286 bool includes(number_t number) const {
287 return indexOf(number) != NOT_INCLUDED;
288 }
289
296 void push_back(number_t number) {
297 if (empty()) {
298 segments.emplace_back(number+1, 1);
299 } else if (segments.back().numberEnd == number) {
300 ++(segments.back().numberEnd);
301 ++(segments.back().indexEnd);
302 } else
303 segments.emplace_back(number+1, segments.back().indexEnd+1);
304 }
305
312 void push_back_segment(number_t num_beg, number_t num_end) {
313 if (empty())
314 segments.emplace_back(num_end, num_end - num_beg);
315 else
316 segments.emplace_back(num_end, segments.back().indexEnd + num_end - num_beg);
317 }
318
325 void push_back_range(number_t num_beg, number_t num_end) {
326 if (num_beg >= num_end) return;
327 if (empty())
328 segments.emplace_back(num_end, num_end - num_beg);
329 else if (segments.back().numberEnd == num_beg) {
330 segments.back().numberEnd = num_end;
331 segments.back().indexEnd += num_end - num_beg;
332 } else
333 segments.emplace_back(num_end, segments.back().indexEnd + num_end - num_beg);
334 }
335
340 void assignRange(number_t num_beg, number_t num_end) {
341 segments.resize(1);
342 segments.front().numberEnd = num_end;
343 segments.front().indexEnd = num_end - num_beg;
344 }
345
350 void assignRange(number_t num_end) {
351 segments.resize(1);
352 segments.front().numberEnd = num_end;
353 segments.front().indexEnd = num_end;
354 }
355
362 void insert(number_t number) {
363 auto seg_it = std::upper_bound(segments.begin(), segments.end(), number, Segment::compareByNumberEnd);
364 if (seg_it == segments.end()) { // number is larger than all numbers in the set
365 push_back(number);
366 } else { // here: number < seg_it->numberEnd:
367 if (seg_it == segments.begin()) {
368 const number_t firstNumber = seg_it->numberEnd - seg_it->indexEnd;
369 if (number >= firstNumber) return; // already included
370 // here: 0 <= number < firstNumber and we will insert number with new index
371 for (auto it = seg_it; it != segments.end(); ++it) ++(it->indexEnd);
372 if (number+1 == firstNumber) return; // first segment has been enlarged by the new first element (indexEnd is already increased)
373 segments.emplace(seg_it, number+1, 1); // we can't enlarge first segment, so we need new one
374 } else {
375 auto prev_it = seg_it - 1;
376 const number_t firstNumber = seg_it->numberEnd + prev_it->indexEnd - seg_it->indexEnd;
377 if (number >= firstNumber) return; // already included
378 // we will insert number with new index
379 for (auto it = seg_it; it != segments.end(); ++it) ++(it->indexEnd);
380 if (number+1 == firstNumber) { // segment pointed by seg_it has been enlarged by new first element
381 if (prev_it->numberEnd == number) // if there was one element gap, and now it is no gap after the previous segment
382 segments.erase(prev_it); // we have to remove the previous segment
383 return;
384 }
385 // here: we can't enlarge seg_it segment
386 if (prev_it->numberEnd == number) { // we can append new element to the end of the previous segment (there is still a gap after it, number+1 is in the gap)
387 ++(prev_it->numberEnd);
388 ++(prev_it->indexEnd);
389 } else // we have to insert new segment
390 segments.emplace(seg_it, number+1, prev_it->indexEnd+1);
391 }
392 }
393 }
394
395 friend std::ostream& operator<<(std::ostream& out, const CompressedSetOfNumbers<number_t>& set) {
396 out << "{";
397 auto it = set.segments.begin();
398 if (it != set.segments.end()) {
399 out << (it->numberEnd - it->indexEnd);
400 if (it->indexEnd > 1) out << ".." << (it->numberEnd-1);
401 ++it;
402 while (it != set.segments.end()) {
403 auto size = it->indexEnd - (it-1)->indexEnd;
404 out << ", " << (it->numberEnd - size);
405 if (size > 1) out << ".." << (it->numberEnd-1);
406 ++it;
407 }
408 }
409 return out << "}";
410 }
411
412 bool operator==(const CompressedSetOfNumbers<number_t>& other) const {
413 return segments.size() == other.segments.size() && std::equal(segments.begin(), segments.end(), other.segments.begin());
414 }
415
416 bool operator!=(const CompressedSetOfNumbers<number_t>& other) const {
417 return !(*this == other);
418 }
419
420 private:
421
431 static bool intersectionStep(CompressedSetOfNumbers<number_t>& result, typename std::vector<Segment>::const_iterator& a_segment, typename std::vector<Segment>::const_iterator a_segment_end, number_t& a_first_number, number_t b_first_number) {
432 if (b_first_number < a_segment->numberEnd) // b_first < a_end <= b_end => [b_first, a_end) is common
433 result.push_back_segment(b_first_number, a_segment->numberEnd);
434 ++a_segment;
435 if (a_segment == a_segment_end) return true;
436 a_first_number = a_segment->numberEnd - (a_segment->indexEnd - (a_segment-1)->indexEnd);
437 return false;
438 }
439
440 public:
448 CompressedSetOfNumbers<number_t> intersection(const CompressedSetOfNumbers<number_t>& other) const {
449 if (this->empty() || other.empty()) return CompressedSetOfNumbers<number_t>();
450 CompressedSetOfNumbers<number_t> result;
451 result.reserve(this->size() + other.size()); // enough for sure
452 auto this_segment = this->segments.begin();
453 auto this_first_number = this_segment->numberEnd - this_segment->indexEnd;
454 auto other_segment = other.segments.begin();
455 auto other_first_number = other_segment->numberEnd - other_segment->indexEnd;
456 while (true) {
457 if (this_segment->numberEnd < other_segment->numberEnd) { // a can be included in b
458 if (intersectionStep(result, this_segment, this->segments.end(), this_first_number, other_first_number)) break;
459 } else { // b can be included in a
460 if (intersectionStep(result, other_segment, other.segments.end(), other_first_number, this_first_number)) break;
461 }
462 };
463 result.shrink_to_fit();
464 return result;
465 }
466
471 template <typename F>
472 void forEachSegment(F f) const {
473 for (auto it = this->segments.begin(); it != this->segments.end(); ++it)
474 f(firstNumber(it), it->numberEnd);
475 }
476
484 CompressedSetOfNumbers<number_t> shiftedLeft(number_t positions_count) const {
485 auto seg_it = std::upper_bound(segments.begin(), segments.end(), positions_count, Segment::compareByNumberEnd);
486 if (seg_it == segments.end()) return CompressedSetOfNumbers<number_t>();
487 CompressedSetOfNumbers<number_t> result;
488 result.reserve(segments.end() - seg_it);
489 auto first = firstNumber(seg_it);
490 auto indexShift = (positions_count > first ? positions_count - first : 0) + firstIndex(seg_it);
491 do {
492 result.segments.emplace_back(seg_it->numberEnd - positions_count, seg_it->indexEnd - indexShift);
493 } while (++seg_it != segments.end());
494 return result;
495 }
496
505 template <typename F>
506 CompressedSetOfNumbers<number_t> transformed(F f) const {
507 CompressedSetOfNumbers<number_t> result;
508 result.reserve(segments.size());
509 for (auto it = this->segments.begin(); it != this->segments.end(); ++it) {
510 number_t beg = firstNumber(it);
511 number_t end = it->numberEnd;
512 f(beg, end);
513 result.push_back_range(beg, end);
514 }
515 result.shrink_to_fit(); // some segments could be merged or removed
516 return result;
517 }
518
519};
520
521} // namespace plask
522
523#endif // PLASK__UTILS_NUMBERS_SET_H