source: cpp/frams/util/multirange.cpp @ 1181

Last change on this file since 1181 was 1130, checked in by Maciej Komosinski, 3 years ago

Used std::min(), std::max() explicitly to avoid compiler confusion. Used std::size() explicitly instead of the equivalent macro

  • Property svn:eol-style set to native
File size: 5.8 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2021  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#include "multirange.h"
6#include <algorithm>
7
8#include <stdio.h>
9
10int IRange::operator==(const IRange& r)
11{
12        if (isEmpty() && r.isEmpty()) return 1;
13        return (begin == r.begin) && (end == r.end);
14}
15
16void IRange::intersect(const IRange& r)
17{
18        if (r.begin > begin) begin = r.begin;
19        if (r.end < end) end = r.end;
20}
21void IRange::add(const IRange& r)
22{
23        if (r.begin < begin) begin = r.begin;
24        if (r.end > end) end = r.end;
25}
26
27void IRange::print() const
28{
29        if (begin == end) printf("[%d]", begin);
30        else printf("[%d-%d]", begin, end);
31}
32
33////////////////////////////////////////
34
35void MultiRange::print() const
36{
37        printf("[");
38        for (int i = 0; i < data.size(); i += 2)
39        {
40                int b = getData(i);
41                int e = getData(i + 1);
42                if (i) printf(",");
43                if (b == e) printf("%d", b);
44                else printf("%d-%d", b, e);
45        }
46        printf("]");
47}
48
49void MultiRange::print2() const
50{
51        const IRange& r = singleRange();
52        for (int i = 0; i <= r.end; i++)
53                printf(contains(i) ? "X" : ".");
54}
55
56void MultiRange::shift(int delta)
57{
58        for (int i = 0; i<data.size(); i++)
59                data.get(i) += delta;
60}
61
62int MultiRange::findRange(int x) const
63{
64        if (isEmpty()) return -1;
65        if (getData(0)>x) return -1;
66        int a, b, c;
67        int n = rangeCount() - 1;
68        a = 0; b = n; // find c = last range with begin<=x
69        while (1){
70                c = (a + b + 1) / 2;
71                if (getBegin(c) <= x)
72                {
73                        if ((c == n) || (getBegin(c + 1) > x)) return c;
74                        a = c;
75                }
76                else
77                {
78                        b = c - 1;
79                }
80        }
81}
82
83void MultiRange::addRange(int i, int b, int e)
84{
85        data.insert(2 * i, b);
86        data.insert(2 * i + 1, e);
87}
88
89void MultiRange::removeRanges(int r1, int r2)
90{
91        //data.remove(2*r1,(r2-r1)*2+2);
92        for (; r2 >= r1; r2--)
93                removeRange(r2);
94}
95
96void MultiRange::removeRange(int i)
97{
98        data.remove(2 * i, 2);
99}
100
101void MultiRange::clear()
102{
103        data.clear();
104}
105
106int MultiRange::isEmpty() const
107{
108        return rangeCount() == 0;
109}
110
111IRange MultiRange::singleRange() const
112{
113        if (isEmpty()) return IRange();
114        int b = getData(0);
115        int e = getData(data.size() - 1);
116        return IRange(b, e);
117}
118
119int MultiRange::rangeCount() const
120{
121        return data.size() / 2;
122}
123
124IRange MultiRange::getRange(int i) const
125{
126        if ((i < 0) || (i >= rangeCount())) return IRange();
127        return IRange(getData(2 * i), getData(2 * i + 1));
128}
129
130void MultiRange::remove(int begin, int end)
131{
132        if (end < begin) return; // NOP
133        int count = rangeCount();
134        if (!count) return;
135        int r1 = findRange(begin);
136        int r2 = findRange(end);
137        if (r2<0) return; // NOP
138        if (r1 == r2)
139        {
140                int e = getEnd(r1);
141                int b = getBegin(r1);
142                if (begin <= e)
143                {
144                        if (end >= e)
145                        {
146                                if (begin>b)
147                                        setEnd(r1, begin - 1);
148                                else
149                                        removeRange(r1);
150                        }
151                        else
152                        {
153                                if (begin > b)
154                                { //split
155                                        addRange(r1 + 1, end + 1, e);
156                                        setEnd(r1, begin - 1);
157                                }
158                                else
159                                {
160                                        setBegin(r1, end + 1);
161                                }
162                        }
163                }
164        }
165        else
166        {
167                if (r1 >= 0)
168                {
169                        int e1 = getEnd(r1);
170                        int b1 = getBegin(r1);
171                        if (begin <= e1)
172                        {
173                                if (begin == b1)
174                                {
175                                        removeRange(r1);
176                                        r2--;
177                                        r1--;
178                                }
179                                else
180                                {
181                                        setEnd(r1, begin - 1);
182                                }
183                        }
184                }
185                int e2 = getEnd(r2);
186                if (end < e2)
187                {
188                        setBegin(r2, end + 1);
189                        removeRanges(r1 + 1, r2 - 1);
190                }
191                else
192                {
193                        removeRanges(r1 + 1, r2);
194                }
195        }
196}
197
198void MultiRange::add(int begin, int end)
199{
200        if (end < begin) return; // NOP
201        int count = rangeCount();
202        int last = count - 1;
203        int r1 = findRange(begin);
204        int r2 = findRange(end);
205        if (r2 < 0) // special case: before first range
206        {
207                if (count && (getData(0) == (end + 1)))
208                        setData(0, begin);
209                else
210                        addRange(0, begin, end);
211                return;
212        }
213        if (r1 < 0) // special case: begin is before first range
214        {
215                setData(0, begin);
216                r1 = 0;
217        }
218        // now r1>=0 and r2>=0
219        int joinbegin = (begin <= (getEnd(r1) + 1));
220        int joinend = (r2 < last) && (end >= (getBegin(r2 + 1) - 1));
221        const int SAME = 1;
222        const int JOINBEGIN = 2;
223        const int JOINEND = 4;
224        int action = ((r1 == r2) ? SAME : 0) + (joinbegin ? JOINBEGIN : 0) + (joinend ? JOINEND : 0);
225        switch (action)
226        {
227        case SAME + JOINBEGIN + JOINEND: // remove 1 range
228                setEnd(r1, getEnd(r1 + 1));
229                removeRange(r1 + 1);
230                break;
231        case SAME + JOINBEGIN: // extend 1 range
232                setEnd(r1, std::max(getEnd(r2), end));
233                break;
234        case SAME + JOINEND: // extend 1 range
235                setBegin(r1 + 1, begin);
236                break;
237        case SAME: // add 1 range
238                addRange(r1 + 1, begin, end);
239                break;
240
241        case JOINBEGIN + JOINEND: // extend r2+1
242                setBegin(r2 + 1, getBegin(r1));
243                removeRanges(r1, r2);
244                break;
245        case JOINBEGIN: // extend r1
246                setEnd(r1, std::max(end, getEnd(r2)));
247                removeRanges(r1 + 1, r2);
248                break;
249        case JOINEND: // extend r2+1
250                setBegin(r2 + 1, begin);
251                removeRanges(r1 + 1, r2);
252                break;
253        case 0: // extend r2
254                setBegin(r2, begin);
255                setEnd(r2, std::max(end, getEnd(r2)));
256                removeRanges(r1 + 1, r2 - 1);
257                break;
258        }
259}
260
261void MultiRange::remove(const MultiRange &mr)
262{
263        for (int i = 0; i < mr.rangeCount(); i++)
264        {
265                IRange r = mr.getRange(i);
266                remove(r);
267        }
268}
269
270void MultiRange::add(const MultiRange &mr)
271{
272        for (int i = 0; i < mr.rangeCount(); i++)
273        {
274                IRange r = mr.getRange(i);
275                add(r);
276        }
277}
278
279void MultiRange::intersect(const MultiRange &mr)
280{
281        // = this - (1-mr)
282        MultiRange full(singleRange());
283        full.remove(mr);
284        remove(full);
285}
286
287int MultiRange::contains(const MultiRange &mr) const
288{
289        for (int i = 0; i < mr.rangeCount(); i++)
290        {
291                IRange r = mr.getRange(i);
292                if (!contains(r)) return 0;
293        }
294        return 1;
295}
296
297int MultiRange::contains(int x) const
298{
299        int r = findRange(x);
300        if (r < 0) return 0;
301        return getEnd(r) >= x;
302}
303
304int MultiRange::contains(const IRange& r) const
305{
306        if (r.isEmpty()) return 0;
307        int r1 = findRange(r.begin);
308        if (r1 < 0) return 0;
309        return getRange(r1).contains(r);
310}
311
312void MultiRange::intersect(int begin, int end)
313{
314        if (isEmpty()) return;
315        if (end < begin) { clear(); return; }
316        IRange sr = singleRange();
317        remove(sr.begin, begin - 1);
318        remove(end + 1, sr.end);
319}
Note: See TracBrowser for help on using the repository browser.