source: cpp/gdk/multirange.cpp @ 5

Last change on this file since 5 was 5, checked in by sz, 15 years ago

added the GDK (Genotype Development Kit)

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