Line data Source code
1 : ///////////////////////////////////////////////////////////////////////////
2 : // Spetabaru - Berenger Bramas MPCDF - 2017
3 : // Under LGPL Licence, please you must read the LICENCE file.
4 : ///////////////////////////////////////////////////////////////////////////
5 : #ifndef SPARRAYVIEW_HPP
6 : #define SPARRAYVIEW_HPP
7 :
8 : #include <type_traits>
9 : #include <vector>
10 : #include <cassert>
11 :
12 : #include "small_vector.hpp"
13 :
14 : /**
15 : * An array view should be used to include/exclude itmes
16 : * from an array when declaring dependences.
17 : * Please refer to the corresponding examples/tests.
18 : */
19 : class SpArrayView {
20 : template<class ForwardIt, class T, class Compare>
21 80 : static ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
22 : {
23 : ForwardIt it;
24 : typename std::iterator_traits<ForwardIt>::difference_type count, step;
25 80 : count = std::distance(first,last);
26 :
27 171 : while (count > 0) {
28 91 : it = first;
29 91 : step = count / 2;
30 91 : std::advance(it, step);
31 91 : if (comp(*it, value)) {
32 15 : first = ++it;
33 15 : count -= step + 1;
34 : }
35 : else
36 76 : count = step;
37 : }
38 80 : return first;
39 : }
40 :
41 : struct Interval {
42 : long int firstIdx;
43 : long int lastIdx;
44 : long int step;
45 :
46 57 : long int lastElement() const {
47 57 : return ((lastIdx-firstIdx-1)/step)*step + firstIdx;
48 : }
49 :
50 75 : bool isInside(const long int inIdx) const{
51 72 : return firstIdx <= inIdx && inIdx < lastIdx
52 147 : && (inIdx-firstIdx)%step == 0;
53 : }
54 :
55 87 : long int nbElements() const{
56 87 : return (lastIdx-firstIdx-1)/step + 1;
57 : }
58 : };
59 :
60 : small_vector<Interval> intervals;
61 :
62 : public:
63 : class Iterator{
64 : const SpArrayView& view;
65 : long int currentInterval;
66 : long int currentElement;
67 :
68 178 : explicit Iterator(const SpArrayView& inView, const long int inStartInterval = 0)
69 178 : : view(inView), currentInterval(inStartInterval), currentElement(0){
70 178 : }
71 : public:
72 :
73 571 : bool operator!=(const Iterator& other) const {
74 571 : return &this->view != &other.view || this->currentInterval != other.currentInterval
75 1142 : || this->currentElement != other.currentElement;
76 : }
77 :
78 482 : long int operator*() const {
79 482 : return view.intervals[currentInterval].firstIdx + currentElement;
80 : }
81 482 : Iterator& operator++() {
82 482 : currentElement += view.intervals[currentInterval].step;
83 482 : if(view.intervals[currentInterval].lastIdx <= view.intervals[currentInterval].firstIdx + currentElement){
84 137 : currentInterval += 1;
85 137 : currentElement = 0;
86 : }
87 482 : return *this;
88 : }
89 :
90 : friend SpArrayView;
91 : };
92 :
93 3 : SpArrayView(const long int inFirstIdx, const long int inLastIdx, const long int inStep = 1){
94 3 : if(inFirstIdx != inLastIdx){
95 3 : intervals.emplace_back(Interval{inFirstIdx, inLastIdx, inStep});
96 : }
97 3 : }
98 :
99 71 : SpArrayView(const long int inSize){
100 71 : if(inSize){
101 71 : intervals.emplace_back(Interval{0, inSize, 1});
102 : }
103 71 : }
104 :
105 89 : Iterator begin() const {
106 89 : return Iterator(*this);
107 : }
108 :
109 89 : Iterator end() const {
110 89 : return Iterator(*this, intervals.size());
111 : }
112 :
113 : SpArrayView& addInterval(const long int inFirstIdx, const long int inLastIdx, const long int inStep = 1){
114 : // TODO add with better complexity
115 : for(auto idx = inFirstIdx ; idx < inLastIdx ; idx += inStep){
116 : addItem(idx);
117 : }
118 : return *this;
119 : }
120 :
121 4 : SpArrayView& addItem(const long int inIdx){
122 4 : auto iter = lower_bound(intervals.begin(), intervals.end(), inIdx,
123 5 : [](const Interval& element, const long int& value){
124 5 : return element.lastIdx <= value;
125 : });
126 : // If the last block do not contains the idx, we are on end
127 4 : if(iter == intervals.end()){
128 : // If there is a block that can be extended
129 3 : if(intervals.size() && intervals.back().nbElements() == 1){
130 1 : intervals.back().lastIdx = inIdx + 1;
131 1 : intervals.back().step = inIdx - intervals.back().firstIdx;
132 : }
133 2 : else if(intervals.size() && intervals.back().lastElement() + intervals.back().step == inIdx ){
134 1 : intervals.back().lastIdx += intervals.back().step;
135 : }
136 : else{
137 1 : intervals.emplace_back(Interval{inIdx, inIdx+1, 1});
138 : }
139 : }
140 : // If already exist
141 1 : else if((*iter).isInside(inIdx)){
142 : }
143 : // If covered by an interval but not with the correct step
144 1 : else if((*iter).firstIdx <= inIdx){
145 1 : if((*iter).nbElements() == 1){
146 0 : (*iter).lastIdx = inIdx + 1;
147 0 : (*iter).step = inIdx - (*iter).firstIdx;
148 : }
149 1 : else if(inIdx - (*iter).firstIdx < (*iter).step){
150 1 : iter = intervals.insert(iter, Interval{(*iter).firstIdx, inIdx+1, inIdx-(*iter).firstIdx});
151 1 : ++iter;
152 1 : (*iter).firstIdx = (*iter).firstIdx + (*iter).step;
153 : }
154 0 : else if((*iter).lastElement() < inIdx){
155 0 : iter = intervals.insert(iter, Interval{(*iter).firstIdx, inIdx, (*iter).step});
156 0 : ++iter;
157 0 : (*iter).firstIdx = inIdx;
158 0 : (*iter).lastIdx = inIdx+1;
159 0 : (*iter).step = 1;
160 : }
161 : else{
162 0 : iter = intervals.insert(iter, Interval{(*iter).firstIdx, inIdx, (*iter).step});
163 0 : iter = intervals.insert(iter, Interval{inIdx, inIdx+1, 1});
164 0 : ++iter;
165 0 : (*iter).firstIdx = ((inIdx-(*iter).firstIdx + (*iter).step-1)/(*iter).step)*(*iter).step + (*iter).firstIdx;
166 : }
167 : }
168 0 : else if((*iter).nbElements() == 1
169 0 : || inIdx == (*iter).firstIdx - (*iter).step){
170 0 : if((*iter).nbElements() == 1){
171 0 : (*iter).step = (*iter).firstIdx - inIdx;
172 0 : (*iter).lastIdx = (*iter).firstIdx+1;
173 0 : (*iter).firstIdx = inIdx;
174 : }
175 : else{
176 0 : (*iter).firstIdx -= (*iter).step;
177 : }
178 : }
179 0 : else if(iter == intervals.begin()){
180 0 : intervals.insert(iter, Interval{inIdx, inIdx+1, 1});
181 : }
182 : else {
183 0 : --iter;
184 0 : if((*iter).nbElements() == 1){
185 0 : (*iter).step = inIdx - (*iter).firstIdx;
186 0 : (*iter).lastIdx = inIdx+1;
187 : }
188 0 : else if((*iter).lastElement() + (*iter).step == inIdx){
189 0 : (*iter).lastIdx += (*iter).step;
190 : }
191 : else{
192 0 : ++iter;
193 0 : intervals.insert(iter, Interval{inIdx, inIdx+1, 1});
194 : }
195 : }
196 4 : return *this;
197 : }
198 :
199 : SpArrayView& addItems(const std::initializer_list<long int> inIdxs){
200 : for(const long int& idx : inIdxs){
201 : addItem(idx);
202 : }
203 : return *this;
204 : }
205 :
206 : template <class ... Params>
207 : SpArrayView& addItems(Params ... inIdxs){
208 : addItems({inIdxs...});
209 : return *this;
210 : }
211 :
212 : SpArrayView& removeInterval(const long int inFirstIdx, const long int inLastIdx, const long int inStep = 1){
213 : // TODO remove with better complexity
214 : for(auto idx = inFirstIdx ; idx < inLastIdx ; idx += inStep){
215 : removeItem(idx);
216 : }
217 : return *this;
218 : }
219 :
220 76 : SpArrayView& removeItem(const long int inIdx){
221 76 : auto iter = lower_bound(intervals.begin(), intervals.end(), inIdx,
222 86 : [](const Interval& element, const long int& value) -> bool {
223 86 : return element.lastIdx <= value;
224 : });
225 76 : if(iter != intervals.end() && (*iter).isInside(inIdx)){
226 69 : assert((*iter).nbElements() != 0);
227 69 : if((*iter).firstIdx == inIdx){
228 14 : if((*iter).nbElements() == 1){
229 2 : intervals.erase(iter);
230 : } else {
231 12 : (*iter).firstIdx += (*iter).step;
232 : }
233 : }
234 55 : else if(inIdx == (*iter).lastElement()){
235 14 : (*iter).lastIdx -= (*iter).step;
236 : }
237 : else{
238 41 : auto beforeIter = intervals.insert(iter, *iter);
239 41 : (*beforeIter).lastIdx = inIdx;
240 41 : (*(beforeIter+1)).firstIdx = inIdx+(*(beforeIter+1)).step;
241 : }
242 : }
243 76 : return *this;
244 : }
245 :
246 7 : SpArrayView& removeItems(const std::initializer_list<long int> inIdxs){
247 17 : for(const long int& idx : inIdxs){
248 10 : removeItem(idx);
249 : }
250 7 : return *this;
251 : }
252 :
253 : template <class ... Params>
254 7 : SpArrayView& removeItems(Params ... inIdxs){
255 7 : removeItems({inIdxs...});
256 7 : return *this;
257 : }
258 :
259 9 : long int getNbIntervals() const {
260 9 : return static_cast<long int>(intervals.size());
261 : }
262 :
263 : friend Iterator;
264 : };
265 :
266 : #endif // SPARRAYVIEW_HPP
|
