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

Last change on this file since 121 was 121, checked in by sz, 7 years ago

updated file headers and makefiles

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