Changeset 733
 Timestamp:
 02/15/18 00:43:07 (5 years ago)
 Location:
 cpp/frams/util
 Files:

 5 edited
Legend:
 Unmodified
 Added
 Removed

cpp/frams/util/list.h
r286 r733 16 16 class SListStats 17 17 { 18 19 int objects, allocations, copied, totalmem, usedmem;20 SListStats():objects(0),allocations(0),copied(0),totalmem(0),usedmem() {}21 ~SListStats()18 public: 19 int objects, allocations, copied, totalmem, usedmem; 20 SListStats():objects(0),allocations(0),copied(0),totalmem(0),usedmem() {} 21 ~SListStats() 22 22 { 23 printf("\n"24 25 26 27 28 29 30 31 23 printf("\n" 24 " SListStats:\n" 25 " objects = %ld\n" 26 " allocations = %ld\n" 27 " copied = %ld\n" 28 " total mem = %ld\n" 29 " usage = %ld %%\n" 30 "\n", 31 objects,allocations,copied,totalmem,(usedmem*100)/totalmem); 32 32 } 33 33 }; … … 38 38 { 39 39 protected: 40 int have,used,pos; // ile,zaj,poz41 T *mem;42 void resize(int x)40 int have, used, pos; // ile,zaj,poz 41 T *mem; 42 void resize(int x) 43 43 { 44 if (mem  x)44 if (mem  x) 45 45 { 46 mem=(T*)realloc(mem,x*sizeof(T));46 mem = (T*)realloc(mem, x*sizeof(T)); 47 47 #ifdef SLISTSTATS 48 SListStats::stats.allocations++;49 SListStats::stats.copied+=sizeof(T)*min(x,have);48 SListStats::stats.allocations++; 49 SListStats::stats.copied+=sizeof(T)*min(x,have); 50 50 #endif 51 51 } 52 have=x;52 have = x; 53 53 } 54 54 55 55 public: 56 56 57 SListTempl(const SListTempl<T>& src):have(0),used(0),pos(0),mem(0) 58 {(*this)=src;} 59 SListTempl():have(0),used(0),pos(0),mem(0) 57 SListTempl(const SListTempl<T>& src) :have(0), used(0), pos(0), mem(0) 58 { 59 (*this) = src; 60 } 61 SListTempl() :have(0), used(0), pos(0), mem(0) 60 62 {} 61 ~SListTempl()63 ~SListTempl() 62 64 { 63 65 #ifdef SLISTSTATS 64 SListStats::stats.objects++;65 SListStats::stats.totalmem+=sizeof(T)*have;66 SListStats::stats.usedmem+=sizeof(T)*used;66 SListStats::stats.objects++; 67 SListStats::stats.totalmem+=sizeof(T)*have; 68 SListStats::stats.usedmem+=sizeof(T)*used; 67 69 #endif 68 hardclear();70 hardclear(); 69 71 } 70 72 71 void needSize(int s) 72 { if (s>have) resize(s+3+s/8); } 73 void operator+=(const T& e) ///< append one element 74 {append(e);} 75 void operator=(const T& e) ///< remove one element 76 {int i; if ((i=find(e))>=0) remove(i);} 77 void remove(int i,int n=1) ///< remove n elements from position i 73 void needSize(int s) 78 74 { 79 if ((i>=size())(i<0)) return; 80 if (i>(size()n)) n=size()i; 81 if (pos>=i) pos=n; 82 memmove(mem+i,mem+i+n,sizeof(T)*(usedni)); 83 used=n; 75 if (s > have) resize(s + 3 + s / 8); 84 76 } 85 void operator=(int i) {remove(i);} ///< remove element from position i 86 T& operator()(int i) const ///< return element at position i 87 {return mem[i];} 88 bool hasMore() {return pos<size();} 89 int operator==(const SListTempl<T>& l) const ///< compare list 90 { 91 if (size() != l.size()) return 0; 92 for (int i=0;i<size();i++) if (l.mem[i] != mem[i]) return 0; 93 return 1; 94 } 95 int find(const T& e) const ///< return position of element, or 1 if not found 96 { for (int i=0;i<size();i++) if (mem[i]==e) return i; return 1; } 97 void append(const T& data) ///< add 1 element 98 {needSize(size()+1); mem[used++]=data;} 99 void append(const T* data,int n) ///< add n elements 77 void operator+=(const T& e) ///< append one element 100 78 { 101 needSize(size()+n); 102 memcpy(mem+used,data,sizeof(T)*n); 103 used+=n; 79 append(e); 104 80 } 105 void insert(int p,T* data,int n) ///< insert n elements at position p 81 void operator=(const T& e) ///< remove one element 106 82 { 107 if (p>size()) p=size(); 108 needSize(size()+n); 109 memmove(mem+p+n,mem+p,sizeof(T)*(size()p)); 110 memcpy(mem+p,data,sizeof(T)*n); 111 if (pos>p) pos+=n; 83 int i; if ((i = find(e)) >= 0) remove(i); 112 84 } 113 void insert(int p,const T& data) ///< insert 1 element at position p 85 void remove(int i, int n = 1) ///< remove n elements from position i 114 86 { 115 if (p>size()) p=size(); 116 needSize(size()+1); 117 memmove(mem+p+1,mem+p,sizeof(T)*(size()p)); 118 if (pos>p) pos++; 119 mem[p]=data; 120 used++; 87 if ((i >= size())  (i<0)) return; 88 if (i>(size()  n)) n = size()  i; 89 if (pos >= i) pos = n; 90 memmove(mem + i, mem + i + n, sizeof(T)*(used  n  i)); 91 used = n; 121 92 } 122 void set(int p,const T& d) 123 { needSize(p+1); mem[p]=d; if (used<(p+1)) used=p+1;} 124 void setSize(int s) 125 { needSize(s); used=s;} 126 T& get(int i) const {return operator()(i);} 127 void clear() {used=0;} ///< remove all elements 128 void hardclear() {resize(0); used=0;} ///< remove all elements and free mem 129 int size() const {return used;} ///< list size 130 void operator=(const SListTempl<T>&src) ///duplicate 131 { 132 setSize(src.size()); 133 memcpy(mem, src.mem, src.size()*sizeof(T)); 134 } 135 void operator+=(const SListTempl<T>&src) ///< append src contents 136 { 137 needSize(size()+src.size()); 138 memcpy(mem+used, src.mem, src.size()*sizeof(T)); 139 used+=src.used; 140 } 141 void trim(int newsiz) 142 {if (newsiz<used) used=newsiz;} 93 void operator=(int i) { remove(i); } ///< remove element from position i 94 T& operator()(int i) const ///< return element at position i 95 { 96 return mem[i]; 97 } 98 bool hasMore() { return pos < size(); } 99 int operator==(const SListTempl<T>& l) const ///< compare list 100 { 101 if (size() != l.size()) return 0; 102 for (int i = 0; i<size(); i++) if (l.mem[i] != mem[i]) return 0; 103 return 1; 104 } 105 int find(const T& e) const ///< return position of element, or 1 if not found 106 { 107 for (int i = 0; i<size(); i++) if (mem[i] == e) return i; return 1; 108 } 109 void append(const T& data) ///< add 1 element 110 { 111 needSize(size() + 1); mem[used++] = data; 112 } 113 void append(const T* data, int n) ///< add n elements 114 { 115 needSize(size() + n); 116 memcpy(mem + used, data, sizeof(T)*n); 117 used += n; 118 } 119 void insert(int p, T* data, int n) ///< insert n elements at position p 120 { 121 if (p>size()) p = size(); 122 needSize(size() + n); 123 memmove(mem + p + n, mem + p, sizeof(T)*(size()  p)); 124 memcpy(mem + p, data, sizeof(T)*n); 125 if (pos > p) pos += n; 126 } 127 void insert(int p, const T& data) ///< insert 1 element at position p 128 { 129 if (p > size()) p = size(); 130 needSize(size() + 1); 131 memmove(mem + p + 1, mem + p, sizeof(T)*(size()  p)); 132 if (pos > p) pos++; 133 mem[p] = data; 134 used++; 135 } 136 void set(int p, const T& d) 137 { 138 needSize(p + 1); mem[p] = d; if (used < (p + 1)) used = p + 1; 139 } 140 void setSize(int s) 141 { 142 needSize(s); used = s; 143 } 144 T& get(int i) const { return operator()(i); } 145 void clear() { used = 0; } ///< remove all elements 146 void hardclear() { resize(0); used = 0; } ///< remove all elements and free mem 147 int size() const { return used; } ///< list size 148 void operator=(const SListTempl<T>&src) ///duplicate 149 { 150 setSize(src.size()); 151 memcpy(mem, src.mem, src.size()*sizeof(T)); 152 } 153 void operator+=(const SListTempl<T>&src) ///< append src contents 154 { 155 needSize(size() + src.size()); 156 memcpy(mem + used, src.mem, src.size()*sizeof(T)); 157 used += src.used; 158 } 159 void trim(int newsiz) 160 { 161 if (newsiz < used) used = newsiz; 162 } 143 163 }; 144 164 … … 148 168 // usage example: FOREACH(char*,t,thelist) printf("t=%s\n",t); 149 169 150 template<class T> class PtrListTempl : public SListTempl<T>170 template<class T> class PtrListTempl : public SListTempl < T > 151 171 { 152 public: 153 T operator()(int i) const ///< return element at position i 154 {if (i>=this>size()) return 0; else return this>mem[i];} 172 public: 173 T operator()(int i) const ///< return element at position i 174 { 175 if (i >= this>size()) return 0; else return this>mem[i]; 176 } 155 177 156 T get(int i) const {return operator()(i);}157 T& getref(int i) const {return SListTempl<T>::get(i);}178 T get(int i) const { return operator()(i); } 179 T& getref(int i) const { return SListTempl<T>::get(i); } 158 180 }; 159 181 160 182 161 typedef PtrListTempl<void*> SList;183 typedef PtrListTempl<void*> SList; 162 184 163 185 #endif 
cpp/frams/util/multimap.cpp
r286 r733 8 8 int MultiMap::getBegin() const 9 9 { 10 if (isEmpty()) return 0;11 return getBegin(0);10 if (isEmpty()) return 0; 11 return getBegin(0); 12 12 } 13 13 14 14 int MultiMap::getEnd() const 15 15 { 16 if (isEmpty()) return 1;17 return getBegin(mappingCount()1)1;16 if (isEmpty()) return 1; 17 return getBegin(mappingCount()  1)  1; 18 18 } 19 19 20 20 int MultiMap::findData(int x) const 21 21 { 22 if (isEmpty()) return 1;23 if (getBegin(0)>x) return 1;24 int a,b,c;25 int n=mappingCount()1;26 a=0; b=n; // find c = last range with begin<=x27 while(1){28 c=(a+b+1)/2;29 if (getBegin(c)<=x)22 if (isEmpty()) return 1; 23 if (getBegin(0) > x) return 1; 24 int a, b, c; 25 int n = mappingCount()  1; 26 a = 0; b = n; // find c = last range with begin<=x 27 while (1){ 28 c = (a + b + 1) / 2; 29 if (getBegin(c) <= x) 30 30 { 31 if ((c==n)(getBegin(c+1)>x)) return c; 32 a=c; 33 } 31 if ((c == n)  (getBegin(c + 1) > x)) return c; 32 a = c; 33 } 34 else 35 { 36 b = c  1; 37 } 38 } 39 } 40 41 int MultiMap::addRange(int &r, const MultiRange& mr) 42 { 43 // precondition: 0 <= r < (mappingCount()1) 44 // 1.maybe change mapping in this range 45 int ret = 0; 46 SingleMapping *sm = getMapping(r); 47 if (sm>to.contains(mr)) return 0; // do nothing 48 sm>to.add(mr); 49 // after adding mr to this mapping it could be the same as the previous/next one 50 if (r > 0) // prev exists 51 { 52 SingleMapping *prev = getMapping(r  1); 53 if (prev>to == sm>to) 54 { // splice with prev 55 removeData(r); 56 delete sm; 57 sm = prev; 58 r; 59 ret; 60 } 61 } 62 if (r < (mappingCount()  2)) // next exists 63 { 64 SingleMapping *next = getMapping(r + 1); 65 if (next>to == sm>to) 66 { // splice with next 67 removeData(r + 1); 68 delete next; 69 ret; 70 r; 71 } 72 } 73 return ret; 74 } 75 76 int MultiMap::addRangeBeginEnd(int &r, int begin, int end, const MultiRange& mr) 77 { 78 // precondition: 1 <= r < mappingCount() 79 // begin <= end 80 // begin >= mapping.begin 81 // end < nextmapping.begin 82 SingleMapping *m, *m2, *m1; 83 if (r < 0) 84 { 85 if (mappingCount()) 86 { 87 m = getMapping(0); 88 if (end == (m>begin  1)) 89 { // adjacent to m 90 if (m>to == mr) 91 { // shift only 92 m>begin = begin; 93 return 0; 94 } 95 // single add 96 SingleMapping *newmap = new SingleMapping(begin, mr); 97 addData(0, newmap); 98 r = 0; 99 return 1; 100 } 101 } 102 // double add 103 SingleMapping *newmap = new SingleMapping(begin, mr); 104 SingleMapping *newmap2 = new SingleMapping(end + 1); 105 addData(0, newmap); 106 addData(1, newmap2); 107 r = 1; 108 return 2; 109 } 110 111 if (r == (mappingCount()  1)) 112 { 113 m = getMapping(r); 114 m1 = getMapping(r  1); 115 if (begin == m>begin) 116 { // adjacent 117 if (m1>to == mr) 118 { // shift only 119 m>begin = end + 1; 120 return 0; 121 } 122 // single add 123 m>begin = end + 1; 124 SingleMapping *newmap = new SingleMapping(begin, mr); 125 addData(r, newmap); 126 return 1; 127 } 128 // double add 129 SingleMapping *newmap = new SingleMapping(begin, mr); 130 SingleMapping *newmap2 = new SingleMapping(end + 1); 131 addData(r + 1, newmap); 132 addData(r + 2, newmap2); 133 r += 2; 134 return 2; 135 } 136 137 m = getMapping(r); 138 if (m>to.contains(mr)) return 0; 139 if (begin == m>begin) // begin at range boundary 140 { 141 m2 = getMapping(r + 1); 142 if (end == (m2>begin  1)) return addRange(r, mr); 143 144 SingleMapping *newmap = new SingleMapping(begin, m>to); 145 newmap>to.add(mr); 146 if (r > 0) 147 { // join prev possible... 148 m1 = getMapping(r  1); 149 if (m1>to == newmap>to) 150 { // joint prev = shift 151 delete newmap; 152 m>begin = end + 1; 153 return 0; 154 } 155 } 156 // single add: 157 m>begin = end + 1; 158 addData(r, newmap); 159 return 1; 160 } 161 162 m2 = getMapping(r + 1); 163 if (end == (m2>begin  1)) // end at range boundary 164 { 165 SingleMapping *newmap = new SingleMapping(begin, m>to); 166 newmap>to.add(mr); 167 if (r < (mappingCount()  2)) 168 { // join next possible... 169 if (m2>to == newmap>to) 170 { // joint next = shift 171 m2>begin = begin; 172 delete newmap; 173 return 0; 174 } 175 } 176 // single add 177 r++; 178 addData(r, newmap); 179 return 1; 180 } 181 // double add: 182 SingleMapping *newmap = new SingleMapping(begin, m>to); 183 newmap>to.add(mr); 184 SingleMapping *newmap2 = new SingleMapping(end + 1, m>to); 185 addData(r + 1, newmap); 186 addData(r + 2, newmap2); 187 r += 2; 188 return 2; 189 } 190 191 void MultiMap::add(int begin, int end, const MultiRange& to) 192 { 193 if (to.isEmpty()) return; 194 if (end < begin) return; 195 int r1 = findData(begin); 196 int r2 = findData(end); 197 if (r1 == r2) 198 { 199 addRangeBeginEnd(r1, begin, end, to); 200 } 34 201 else 202 { 203 r2 += addRangeBeginEnd(r1, begin, getBegin(r1 + 1)  1, to); 204 r1++; 205 for (; r1 < r2; r1++) 206 r2 += addRange(r1, to); 207 addRangeBeginEnd(r1, getBegin(r1), end, to); 208 } 209 } 210 211 const MultiRange& MultiMap::map(int x) const 212 { 213 static MultiRange empty; 214 int m = findData(x); 215 if (m < 0) return empty; 216 SingleMapping *sm = getMapping(m); 217 return sm>to; 218 } 219 220 MultiRange MultiMap::map(int begin, int end) const 221 { 222 MultiRange mr; 223 int m = findData(begin); 224 for (; m < rangeCount(); m++) 225 if (m >= 0) 35 226 { 36 b=c1; 37 } 38 } 39 } 40 41 int MultiMap::addRange(int &r,const MultiRange& mr) 42 { 43 // precondition: 0 <= r < (mappingCount()1) 44 // 1.maybe change mapping in this range 45 int ret=0; 46 SingleMapping *sm=getMapping(r); 47 if (sm>to.contains(mr)) return 0; // do nothing 48 sm>to.add(mr); 49 // after adding mr to this mapping it could be the same as the previous/next one 50 if (r>0) // prev exists 51 { 52 SingleMapping *prev=getMapping(r1); 53 if (prev>to == sm>to) 54 { // splice with prev 55 removeData(r); 56 delete sm; 57 sm=prev; 58 r; 59 ret; 60 } 61 } 62 if (r<(mappingCount()2)) // next exists 63 { 64 SingleMapping *next=getMapping(r+1); 65 if (next>to == sm>to) 66 { // splice with next 67 removeData(r+1); 68 delete next; 69 ret; 70 r; 71 } 72 } 73 return ret; 74 } 75 76 int MultiMap::addRangeBeginEnd(int &r,int begin,int end,const MultiRange& mr) 77 { 78 // precondition: 1 <= r < mappingCount() 79 // begin <= end 80 // begin >= mapping.begin 81 // end < nextmapping.begin 82 SingleMapping *m,*m2,*m1; 83 if (r<0) 84 { 85 if (mappingCount()) 86 { 87 m=getMapping(0); 88 if (end==(m>begin1)) 89 { // adjacent to m 90 if (m>to==mr) 91 { // shift only 92 m>begin=begin; 93 return 0; 94 } 95 // single add 96 SingleMapping *newmap=new SingleMapping(begin,mr); 97 addData(0,newmap); 98 r=0; 99 return 1; 100 } 101 } 102 // double add 103 SingleMapping *newmap=new SingleMapping(begin,mr); 104 SingleMapping *newmap2=new SingleMapping(end+1); 105 addData(0,newmap); 106 addData(1,newmap2); 107 r=1; 108 return 2; 109 } 110 111 if (r==(mappingCount()1)) 112 { 113 m=getMapping(r); 114 m1=getMapping(r1); 115 if (begin==m>begin) 116 { // adjacent 117 if (m1>to==mr) 118 { // shift only 119 m>begin=end+1; 120 return 0; 121 } 122 // single add 123 m>begin=end+1; 124 SingleMapping *newmap=new SingleMapping(begin,mr); 125 addData(r,newmap); 126 return 1; 127 } 128 // double add 129 SingleMapping *newmap=new SingleMapping(begin,mr); 130 SingleMapping *newmap2=new SingleMapping(end+1); 131 addData(r+1,newmap); 132 addData(r+2,newmap2); 133 r+=2; 134 return 2; 135 } 136 137 m=getMapping(r); 138 if (m>to.contains(mr)) return 0; 139 if (begin==m>begin) // begin at range boundary 140 { 141 m2=getMapping(r+1); 142 if (end==(m2>begin1)) return addRange(r,mr); 143 144 SingleMapping *newmap=new SingleMapping(begin,m>to); 145 newmap>to.add(mr); 146 if (r>0) 147 { // join prev possible... 148 m1=getMapping(r1); 149 if (m1>to==newmap>to) 150 { // joint prev = shift 151 delete newmap; 152 m>begin=end+1; 153 return 0; 154 } 155 } 156 // single add: 157 m>begin=end+1; 158 addData(r,newmap); 159 return 1; 160 } 161 162 m2=getMapping(r+1); 163 if (end==(m2>begin1)) // end at range boundary 164 { 165 SingleMapping *newmap=new SingleMapping(begin,m>to); 166 newmap>to.add(mr); 167 if (r<(mappingCount()2)) 168 { // join next possible... 169 if (m2>to==newmap>to) 170 { // joint next = shift 171 m2>begin=begin; 172 delete newmap; 173 return 0; 174 } 175 } 176 // single add 177 r++; 178 addData(r,newmap); 179 return 1; 180 } 181 // double add: 182 SingleMapping *newmap=new SingleMapping(begin,m>to); 183 newmap>to.add(mr); 184 SingleMapping *newmap2=new SingleMapping(end+1,m>to); 185 addData(r+1,newmap); 186 addData(r+2,newmap2); 187 r+=2; 188 return 2; 189 } 190 191 void MultiMap::add(int begin,int end,const MultiRange& to) 192 { 193 if (to.isEmpty()) return; 194 if (end<begin) return; 195 int r1=findData(begin); 196 int r2=findData(end); 197 if (r1==r2) 198 { 199 addRangeBeginEnd(r1,begin,end,to); 200 } 201 else 202 { 203 r2+=addRangeBeginEnd(r1,begin,getBegin(r1+1)1,to); 204 r1++; 205 for (;r1<r2;r1++) 206 r2+=addRange(r1,to); 207 addRangeBeginEnd(r1,getBegin(r1),end,to); 208 } 209 } 210 211 const MultiRange& MultiMap::map(int x) const 212 { 213 static MultiRange empty; 214 int m=findData(x); 215 if (m<0) return empty; 216 SingleMapping *sm=getMapping(m); 217 return sm>to; 218 } 219 220 MultiRange MultiMap::map(int begin,int end) const 221 { 222 MultiRange mr; 223 int m=findData(begin); 224 for (;m<rangeCount();m++) 225 if (m>=0) 226 { 227 SingleMapping *sm=getMapping(m); 228 if (sm>begin > end) break; 229 mr.add(sm>to); 230 } 231 return mr; 227 SingleMapping *sm = getMapping(m); 228 if (sm>begin > end) break; 229 mr.add(sm>to); 230 } 231 return mr; 232 232 } 233 233 234 234 MultiRange MultiMap::map(const MultiRange& ranges) const 235 235 { 236 MultiRange mr;237 for(int i=0;i<ranges.rangeCount();i++)238 mr.add(map(ranges.getRange(i)));239 return mr;236 MultiRange mr; 237 for (int i = 0; i < ranges.rangeCount(); i++) 238 mr.add(map(ranges.getRange(i))); 239 return mr; 240 240 } 241 241 242 242 IRange MultiMap::getRange(int i) const 243 243 { 244 if ((i<0)(i>(data.size()1))) return IRange();245 return IRange(getBegin(i),getBegin(i+1)1);244 if ((i<0)  (i>(data.size()  1))) return IRange(); 245 return IRange(getBegin(i), getBegin(i + 1)  1); 246 246 } 247 247 248 248 void MultiMap::operator=(const MultiMap& mm) 249 249 { 250 clear();251 for(int i=0;i<mm.mappingCount();i++)252 addData(i,new SingleMapping(*mm.getMapping(i)));253 } 254 255 void MultiMap::addCombined(const MultiMap& m1, const MultiMap& m2)256 { 257 for(int i=0;i<m1.rangeCount();i++)258 { 259 IRange r=m1.getRange(i);260 add(r,m2.map(m1.getMapping(i)>to));261 } 262 } 263 264 void MultiMap::add(const MultiRange& from, const MultiRange& to)265 { 266 for(int i=0;i<from.rangeCount();i++)267 add(from.getRange(i),to);250 clear(); 251 for (int i = 0; i < mm.mappingCount(); i++) 252 addData(i, new SingleMapping(*mm.getMapping(i))); 253 } 254 255 void MultiMap::addCombined(const MultiMap& m1, const MultiMap& m2) 256 { 257 for (int i = 0; i < m1.rangeCount(); i++) 258 { 259 IRange r = m1.getRange(i); 260 add(r, m2.map(m1.getMapping(i)>to)); 261 } 262 } 263 264 void MultiMap::add(const MultiRange& from, const MultiRange& to) 265 { 266 for (int i = 0; i < from.rangeCount(); i++) 267 add(from.getRange(i), to); 268 268 } 269 269 270 270 void MultiMap::addReversed(const MultiMap& m) 271 271 { 272 for(int i=0;i<m.rangeCount();i++)273 { 274 IRange r=m.getRange(i);275 const MultiRange& mr=m.getMapping(i)>to;276 for (int j=0;j<mr.rangeCount();j++)277 add(mr.getRange(j),r);272 for (int i = 0; i < m.rangeCount(); i++) 273 { 274 IRange r = m.getRange(i); 275 const MultiRange& mr = m.getMapping(i)>to; 276 for (int j = 0; j < mr.rangeCount(); j++) 277 add(mr.getRange(j), r); 278 278 } 279 279 } 280 280 281 281 MultiMap::~MultiMap() 282 { clear();} 282 { 283 clear(); 284 } 283 285 284 286 void MultiMap::clear() 285 287 { 286 for(int i=0;i<data.size();i++)287 delete getData(i);288 data.clear();288 for (int i = 0; i < data.size(); i++) 289 delete getData(i); 290 data.clear(); 289 291 } 290 292 … … 293 295 void MultiMap::print() const 294 296 { 295 printf("{ ");296 for (int i=0;i<(mappingCount()1);i++)297 { 298 if (i) printf(" ");299 SingleMapping *sm=getMapping(i);300 SingleMapping *sm2=getMapping(i+1);301 if (sm2>begin==sm>begin+1)302 printf("[%d] > ",sm>begin);303 else304 printf("[%d%d] > ",sm>begin,sm2>begin1);305 sm>to.print();306 printf("\n");307 } 308 printf("}\n");297 printf("{ "); 298 for (int i = 0; i < (mappingCount()  1); i++) 299 { 300 if (i) printf(" "); 301 SingleMapping *sm = getMapping(i); 302 SingleMapping *sm2 = getMapping(i + 1); 303 if (sm2>begin == sm>begin + 1) 304 printf("[%d] > ", sm>begin); 305 else 306 printf("[%d%d] > ", sm>begin, sm2>begin  1); 307 sm>to.print(); 308 printf("\n"); 309 } 310 printf("}\n"); 309 311 } 310 312 311 313 void MultiMap::print2() const 312 314 { 313 int y;314 int id=0,id2;315 if (isEmpty())316 { 317 printf("{ empty }\n");318 return;319 } 320 printf("{\n");321 for (y=getBegin();y<=getEnd();y++)322 { 323 id2=findMappingId(y+1);324 printf("%2d %c",y,(id2!=id)?'_':' ');325 id=id2;326 map(y).print2();327 printf("\n");328 } 329 printf("}\n");330 } 315 int y; 316 int id = 0, id2; 317 if (isEmpty()) 318 { 319 printf("{ empty }\n"); 320 return; 321 } 322 printf("{\n"); 323 for (y = getBegin(); y <= getEnd(); y++) 324 { 325 id2 = findMappingId(y + 1); 326 printf("%2d %c", y, (id2 != id) ? '_' : ' '); 327 id = id2; 328 map(y).print2(); 329 printf("\n"); 330 } 331 printf("}\n"); 332 } 
cpp/frams/util/multimap.h
r304 r733 10 10 class SingleMapping 11 11 { 12 13 SingleMapping(int b,const MultiRange& t):begin(b),to(t) {}14 SingleMapping(int b):begin(b) {}15 SingleMapping(const SingleMapping& sm):begin(sm.begin),to(sm.to) {}16 int begin;17 MultiRange to;12 public: 13 SingleMapping(int b, const MultiRange& t) :begin(b), to(t) {} 14 SingleMapping(int b) :begin(b) {} 15 SingleMapping(const SingleMapping& sm) :begin(sm.begin), to(sm.to) {} 16 int begin; 17 MultiRange to; 18 18 }; 19 19 20 20 /** MultiMap  used for conversion mapping. 21 22 23 */21 Read about how mappings work: http://www.framsticks.com/files/common/GeneticMappingsInArtificialGenomes.pdf 22 see @ref convmap 23 */ 24 24 class MultiMap 25 25 { 26 /** list of (SingleMapping*) */27 SList data;26 /** list of (SingleMapping*) */ 27 SList data; 28 28 29 SingleMapping* getData(int i) const {return (SingleMapping*)data(i);}30 void addData(int i,SingleMapping* mapping) {data.insert(i,(void*)mapping);}31 void removeData(int i) {data.remove(i);}32 int findData(int x) const;33 int getBegin(int i) const {return getData(i)>begin;}29 SingleMapping* getData(int i) const { return (SingleMapping*)data(i); } 30 void addData(int i, SingleMapping* mapping) { data.insert(i, (void*)mapping); } 31 void removeData(int i) { data.remove(i); } 32 int findData(int x) const; 33 int getBegin(int i) const { return getData(i)>begin; } 34 34 35 // addRangeXXX return the shift for range numbers > r36 int addRange(int &r,const MultiRange& mr);37 // value of 'r' is adjusted according to its range number change38 int addRangeBeginEnd(int &r,int begin,int end,const MultiRange& mr);35 // addRangeXXX return the shift for range numbers > r 36 int addRange(int &r, const MultiRange& mr); 37 // value of 'r' is adjusted according to its range number change 38 int addRangeBeginEnd(int &r, int begin, int end, const MultiRange& mr); 39 39 40 41 MultiMap() {}42 MultiMap(const MultiMap& mm) {operator=(mm);}43 ~MultiMap();44 void operator=(const MultiMap& mm);40 public: 41 MultiMap() {} 42 MultiMap(const MultiMap& mm) { operator=(mm); } 43 ~MultiMap(); 44 void operator=(const MultiMap& mm); 45 45 46 void clear();47 int isEmpty() const {return data.size()==0;}48 int mappingCount() const {return data.size();}49 SingleMapping* getMapping(int i) const {return (SingleMapping*)getData(i);}50 int findMappingId(int x) const {return findData(x);}51 int rangeCount() const {return isEmpty()?0:data.size()1;}52 IRange getRange(int i) const;46 void clear(); 47 int isEmpty() const { return data.size() == 0; } 48 int mappingCount() const { return data.size(); } 49 SingleMapping* getMapping(int i) const { return (SingleMapping*)getData(i); } 50 int findMappingId(int x) const { return findData(x); } 51 int rangeCount() const { return isEmpty() ? 0 : data.size()  1; } 52 IRange getRange(int i) const; 53 53 54 int getBegin() const;55 int getEnd() const;54 int getBegin() const; 55 int getEnd() const; 56 56 57 void add(const IRange& from,const IRange& to) {add(from.begin, from.end, MultiRange(to));}58 void add(const IRange& from,const MultiRange& to) {add(from.begin, from.end, to);}59 void add(int from1,int from2,int to1,int to2) {add(from1,from2,MultiRange(to1,to2));}60 void add(int from1,int from2,const MultiRange& to);61 void add(const MultiRange& from,const MultiRange& to);62 void add(const MultiMap& mm);63 void addCombined(const MultiMap& m1,const MultiMap& m2);64 void addReversed(const MultiMap& mm);57 void add(const IRange& from, const IRange& to) { add(from.begin, from.end, MultiRange(to)); } 58 void add(const IRange& from, const MultiRange& to) { add(from.begin, from.end, to); } 59 void add(int from1, int from2, int to1, int to2) { add(from1, from2, MultiRange(to1, to2)); } 60 void add(int from1, int from2, const MultiRange& to); 61 void add(const MultiRange& from, const MultiRange& to); 62 void add(const MultiMap& mm); 63 void addCombined(const MultiMap& m1, const MultiMap& m2); 64 void addReversed(const MultiMap& mm); 65 65 66 const MultiRange& map(int x) const;67 MultiRange map(int begin,int end) const;68 MultiRange map(const IRange& range) const {return map(range.begin, range.end);}69 MultiRange map(const MultiRange& ranges) const;66 const MultiRange& map(int x) const; 67 MultiRange map(int begin, int end) const; 68 MultiRange map(const IRange& range) const { return map(range.begin, range.end); } 69 MultiRange map(const MultiRange& ranges) const; 70 70 71 void print() const;72 void print2() const;71 void print() const; 72 void print2() const; 73 73 }; 74 74 
cpp/frams/util/multirange.cpp
r286 r733 10 10 int IRange::operator==(const IRange& r) 11 11 { 12 if (isEmpty()&&r.isEmpty()) return 1;13 return (begin==r.begin)&&(end==r.end);12 if (isEmpty() && r.isEmpty()) return 1; 13 return (begin == r.begin) && (end == r.end); 14 14 } 15 15 16 16 void IRange::intersect(const IRange& r) 17 17 { 18 if (r.begin>begin) begin=r.begin;19 if (r.end<end) end=r.end;18 if (r.begin > begin) begin = r.begin; 19 if (r.end < end) end = r.end; 20 20 } 21 21 void IRange::add(const IRange& r) 22 22 { 23 if (r.begin<begin) begin=r.begin;24 if (r.end>end) end=r.end;23 if (r.begin < begin) begin = r.begin; 24 if (r.end > end) end = r.end; 25 25 } 26 26 27 27 void IRange::print() const 28 28 { 29 if (begin==end) printf("[%d]",begin);30 else printf("[%d%d]",begin,end);29 if (begin == end) printf("[%d]", begin); 30 else printf("[%d%d]", begin, end); 31 31 } 32 32 … … 35 35 void MultiRange::print() const 36 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("]");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 47 } 48 48 49 49 void MultiRange::print2() const 50 50 { 51 const IRange& r=singleRange();52 for(int i=0;i<=r.end;i++)53 printf(contains(i)?"X":".");51 const IRange& r = singleRange(); 52 for (int i = 0; i <= r.end; i++) 53 printf(contains(i) ? "X" : "."); 54 54 } 55 55 56 56 void MultiRange::shift(int delta) 57 57 { 58 for(int i=0;i<data.size();i++)59 data.get(i)+=delta;58 for (int i = 0; i<data.size(); i++) 59 data.get(i) += delta; 60 60 } 61 61 62 62 int MultiRange::findRange(int x) const 63 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<=x69 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 else77 { 78 b=c1;79 } 80 } 81 } 82 83 void MultiRange::addRange(int i, int b,int e)84 { 85 data.insert(2*i,b);86 data.insert(2*i+1,e);87 } 88 89 void MultiRange::removeRanges(int r1, int r2)90 { 91 //data.remove(2*r1,(r2r1)*2+2);92 for (;r2>=r1;r2)93 removeRange(r2);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 83 void MultiRange::addRange(int i, int b, int e) 84 { 85 data.insert(2 * i, b); 86 data.insert(2 * i + 1, e); 87 } 88 89 void MultiRange::removeRanges(int r1, int r2) 90 { 91 //data.remove(2*r1,(r2r1)*2+2); 92 for (; r2 >= r1; r2) 93 removeRange(r2); 94 94 } 95 95 96 96 void MultiRange::removeRange(int i) 97 97 { 98 data.remove(2*i,2);98 data.remove(2 * i, 2); 99 99 } 100 100 101 101 void MultiRange::clear() 102 {data.clear();} 102 { 103 data.clear(); 104 } 103 105 104 106 int MultiRange::isEmpty() const 105 107 { 106 return rangeCount()==0;108 return rangeCount() == 0; 107 109 } 108 110 109 111 IRange MultiRange::singleRange() const 110 112 { 111 if (isEmpty()) return IRange();112 int b=getData(0);113 int e=getData(data.size()1);114 return IRange(b,e);113 if (isEmpty()) return IRange(); 114 int b = getData(0); 115 int e = getData(data.size()  1); 116 return IRange(b, e); 115 117 } 116 118 117 119 int MultiRange::rangeCount() const 118 120 { 119 return data.size()/2;121 return data.size() / 2; 120 122 } 121 123 122 124 IRange MultiRange::getRange(int i) const 123 125 { 124 if ((i<0)(i>=rangeCount())) return IRange();125 return IRange(getData(2*i),getData(2*i+1));126 if ((i < 0)  (i >= rangeCount())) return IRange(); 127 return IRange(getData(2 * i), getData(2 * i + 1)); 126 128 } 127 129 128 130 void MultiRange::remove(int begin, int end) 129 131 { 130 if (end<begin) return; // NOP131 int count=rangeCount();132 if (!count) return;133 int r1=findRange(begin);134 int r2=findRange(end);135 if (r2<0) return; // NOP136 if (r1==r2)137 { 138 int e=getEnd(r1);139 int b=getBegin(r1);140 if (begin<=e)141 { 142 if (end>=e)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) 143 145 { 144 if (begin>b) 145 setEnd(r1,begin1); 146 if (begin>b) 147 setEnd(r1, begin  1); 148 else 149 removeRange(r1); 150 } 146 151 else 147 removeRange(r1);148 }149 else150 152 { 151 if (begin>b)153 if (begin > b) 152 154 { //split 153 addRange(r1+1,end+1,e);154 setEnd(r1,begin1);155 addRange(r1 + 1, end + 1, e); 156 setEnd(r1, begin  1); 155 157 } 156 else158 else 157 159 { 158 setBegin(r1,end+1);160 setBegin(r1, end + 1); 159 161 } 160 162 } 161 163 } 162 164 } 163 else164 { 165 if (r1>=0)166 { 167 int e1=getEnd(r1);168 int b1=getBegin(r1);169 if (begin<=e1)165 else 166 { 167 if (r1 >= 0) 168 { 169 int e1 = getEnd(r1); 170 int b1 = getBegin(r1); 171 if (begin <= e1) 170 172 { 171 if (begin==b1)173 if (begin == b1) 172 174 { 173 removeRange(r1);174 r2;175 r1;175 removeRange(r1); 176 r2; 177 r1; 176 178 } 177 else179 else 178 180 { 179 setEnd(r1,begin1);181 setEnd(r1, begin  1); 180 182 } 181 183 } 182 184 } 183 int e2=getEnd(r2);184 if (end<e2)185 { 186 setBegin(r2,end+1);187 removeRanges(r1+1,r21);188 } 189 else190 { 191 removeRanges(r1+1,r2);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); 192 194 } 193 195 } … … 196 198 void MultiRange::add(int begin, int end) 197 199 { 198 if (end<begin) return; // NOP199 int count=rangeCount();200 int last=count1;201 int r1=findRange(begin);202 int r2=findRange(end);203 if (r2<0) // special case: before first range204 { 205 if (count&&(getData(0)==(end+1)))206 setData(0,begin);207 else208 addRange(0,begin,end);209 return;210 } 211 if (r1<0) // special case: begin is before first range212 { 213 setData(0,begin);214 r1=0;215 } 216 // now r1>=0 and r2>=0217 int joinbegin=(begin<=(getEnd(r1)+1));218 int joinend=(r2<last)&&(end>=(getBegin(r2+1)1));219 const int SAME=1;220 const int JOINBEGIN=2;221 const int JOINEND=4;222 int action=((r1==r2)?SAME:0)+(joinbegin?JOINBEGIN:0)+(joinend?JOINEND:0);223 switch(action)224 { 225 case SAME +JOINBEGIN+JOINEND: // remove 1 range226 setEnd(r1, getEnd(r1+1));227 removeRange(r1 +1);228 break; 229 case SAME +JOINBEGIN: // extend 1 range230 setEnd(r1, max(getEnd(r2),end));231 break; 232 case SAME +JOINEND: // extend 1 range233 setBegin(r1 +1,begin);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, max(getEnd(r2), end)); 233 break; 234 case SAME + JOINEND: // extend 1 range 235 setBegin(r1 + 1, begin); 234 236 break; 235 237 case SAME: // add 1 range 236 addRange(r1 +1,begin,end);237 break; 238 239 case JOINBEGIN +JOINEND: // extend r2+1240 setBegin(r2 +1,getBegin(r1));241 removeRanges(r1, r2);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); 242 244 break; 243 245 case JOINBEGIN: // extend r1 244 setEnd(r1, max(end,getEnd(r2)));245 removeRanges(r1 +1,r2);246 setEnd(r1, max(end, getEnd(r2))); 247 removeRanges(r1 + 1, r2); 246 248 break; 247 249 case JOINEND: // extend r2+1 248 setBegin(r2 +1,begin);249 removeRanges(r1 +1,r2);250 setBegin(r2 + 1, begin); 251 removeRanges(r1 + 1, r2); 250 252 break; 251 253 case 0: // extend r2 252 setBegin(r2, begin);253 setEnd(r2, max(end,getEnd(r2)));254 removeRanges(r1 +1,r21);254 setBegin(r2, begin); 255 setEnd(r2, max(end, getEnd(r2))); 256 removeRanges(r1 + 1, r2  1); 255 257 break; 256 258 } … … 259 261 void MultiRange::remove(const MultiRange &mr) 260 262 { 261 for(int i=0;i<mr.rangeCount();i++)262 { 263 IRange r=mr.getRange(i);264 remove(r);263 for (int i = 0; i < mr.rangeCount(); i++) 264 { 265 IRange r = mr.getRange(i); 266 remove(r); 265 267 } 266 268 } … … 268 270 void MultiRange::add(const MultiRange &mr) 269 271 { 270 for(int i=0;i<mr.rangeCount();i++)271 { 272 IRange r=mr.getRange(i);273 add(r);272 for (int i = 0; i < mr.rangeCount(); i++) 273 { 274 IRange r = mr.getRange(i); 275 add(r); 274 276 } 275 277 } … … 277 279 void MultiRange::intersect(const MultiRange &mr) 278 280 { 279 // = this  (1mr)280 MultiRange full(singleRange());281 full.remove(mr);282 remove(full);281 // = this  (1mr) 282 MultiRange full(singleRange()); 283 full.remove(mr); 284 remove(full); 283 285 } 284 286 285 287 int MultiRange::contains(const MultiRange &mr) const 286 288 { 287 for(int i=0;i<mr.rangeCount();i++)288 { 289 IRange r=mr.getRange(i);290 if (!contains(r)) return 0;291 } 292 return 1;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; 293 295 } 294 296 295 297 int MultiRange::contains(int x) const 296 298 { 297 int r=findRange(x);298 if (r<0) return 0;299 return getEnd(r)>=x;299 int r = findRange(x); 300 if (r < 0) return 0; 301 return getEnd(r) >= x; 300 302 } 301 303 302 304 int MultiRange::contains(const IRange& r) const 303 305 { 304 if (r.isEmpty()) return 0;305 int r1=findRange(r.begin);306 if (r1<0) return 0;307 return getRange(r1).contains(r);306 if (r.isEmpty()) return 0; 307 int r1 = findRange(r.begin); 308 if (r1 < 0) return 0; 309 return getRange(r1).contains(r); 308 310 } 309 311 310 312 void MultiRange::intersect(int begin, int end) 311 313 { 312 if (isEmpty()) return;313 if (end<begin) {clear(); return;}314 IRange sr=singleRange();315 remove(sr.begin, begin1);316 remove(end+1, sr.end);317 } 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 } 
cpp/frams/util/multirange.h
r286 r733 12 12  (a,a) contains single integer: a 13 13  (a,b) contains [ba+1] integers 14 */14 */ 15 15 class IRange 16 16 { 17 18 int begin,end;19 IRange():begin(0),end(0) {}20 IRange(int b,int e):begin(b),end(e) {}21 IRange(const IRange& r):begin(r.begin),end(r.end) {}22 int size() const {return endbegin+1;}23 int isEmpty() const {return end<begin;}24 void makeEmpty() {end=begin;}25 void set(int b,int e) {begin=b; end=e;}26 void intersect(const IRange& r);27 void add(const IRange& r);28 /** all empty ranges are equal */29 int operator==(const IRange& r);30 void operator=(const IRange& r) {begin=r.begin; end=r.end;}31 int contains(int x) {return (x>=begin)&&(x<=end);}32 int contains(const IRange& r) {return !r.isEmpty()&&contains(r.begin)&&contains(r.end);}33 void print() const;17 public: 18 int begin, end; 19 IRange() :begin(0), end(0) {} 20 IRange(int b, int e) :begin(b), end(e) {} 21 IRange(const IRange& r) :begin(r.begin), end(r.end) {} 22 int size() const { return end  begin + 1; } 23 int isEmpty() const { return end < begin; } 24 void makeEmpty() { end = begin; } 25 void set(int b, int e) { begin = b; end = e; } 26 void intersect(const IRange& r); 27 void add(const IRange& r); 28 /** all empty ranges are equal */ 29 int operator==(const IRange& r); 30 void operator=(const IRange& r) { begin = r.begin; end = r.end; } 31 int contains(int x) { return (x >= begin) && (x <= end); } 32 int contains(const IRange& r) { return !r.isEmpty() && contains(r.begin) && contains(r.end); } 33 void print() const; 34 34 }; 35 35 … … 37 37 class MultiRange 38 38 { 39 /** subsequent ranges in array, stored as: {begin1,end1,begin2,end2,...}40 41 42 43 44 SListTempl<int> data;45 int getData(int i) const {return (int)data(i);}46 void setData(int i,int x) {data.set(i,x);}47 int getBegin(int i) const {return getData(2*i);}48 int getEnd(int i) const {return getData(2*i+1);}49 void setBegin(int i,int x) {setData(2*i,x);}50 void setEnd(int i,int x) {setData(2*i+1,x);}51 /** find the last range with begin<=x52 @return 1 if not found */53 int findRange(int x) const;54 void addRange(int i,int b,int e);55 void removeRange(int i);56 void removeRanges(int r1,int r2);39 /** subsequent ranges in array, stored as: {begin1,end1,begin2,end2,...} 40 there are data.size()/2 ranges. 41 all ranges are sorted by 'begin' value. 42 ranges cannot intersect. 43 */ 44 SListTempl<int> data; 45 int getData(int i) const { return (int)data(i); } 46 void setData(int i, int x) { data.set(i, x); } 47 int getBegin(int i) const { return getData(2 * i); } 48 int getEnd(int i) const { return getData(2 * i + 1); } 49 void setBegin(int i, int x) { setData(2 * i, x); } 50 void setEnd(int i, int x) { setData(2 * i + 1, x); } 51 /** find the last range with begin<=x 52 @return 1 if not found */ 53 int findRange(int x) const; 54 void addRange(int i, int b, int e); 55 void removeRange(int i); 56 void removeRanges(int r1, int r2); 57 57 58 59 MultiRange() {}60 MultiRange(const MultiRange &mr) {data=mr.data;}61 void operator=(const MultiRange &mr) {data=mr.data;}62 MultiRange(const IRange &r) {add(r);}63 MultiRange(int begin,int end) {add(begin,end);}64 MultiRange(int x) {add(x);}58 public: 59 MultiRange() {} 60 MultiRange(const MultiRange &mr) { data = mr.data; } 61 void operator=(const MultiRange &mr) { data = mr.data; } 62 MultiRange(const IRange &r) { add(r); } 63 MultiRange(int begin, int end) { add(begin, end); } 64 MultiRange(int x) { add(x); } 65 65 66 int operator==(const MultiRange &mr) const {return data==mr.data;}66 int operator==(const MultiRange &mr) const { return data == mr.data; } 67 67 68 void clear();69 int isEmpty() const;68 void clear(); 69 int isEmpty() const; 70 70 71 IRange singleRange() const;72 int rangeCount() const;73 IRange getRange(int i) const;71 IRange singleRange() const; 72 int rangeCount() const; 73 IRange getRange(int i) const; 74 74 75 void add(int x) {add(x,x);}76 void add(const IRange& r) {add(r.begin,r.end);}77 void add(int begin, int end);78 void add(const MultiRange &mr);75 void add(int x) { add(x, x); } 76 void add(const IRange& r) { add(r.begin, r.end); } 77 void add(int begin, int end); 78 void add(const MultiRange &mr); 79 79 80 void remove(int x) {remove(x,x);}81 void remove(const IRange& r) {remove(r.begin,r.end);}82 void remove(int begin, int end);83 void remove(const MultiRange &mr);80 void remove(int x) { remove(x, x); } 81 void remove(const IRange& r) { remove(r.begin, r.end); } 82 void remove(int begin, int end); 83 void remove(const MultiRange &mr); 84 84 85 int contains(int x) const;86 int contains(const IRange& r) const;87 int contains(const MultiRange &mr) const;85 int contains(int x) const; 86 int contains(const IRange& r) const; 87 int contains(const MultiRange &mr) const; 88 88 89 void intersect(const IRange& r) {intersect(r.begin,r.end);}90 void intersect(int begin, int end);91 void intersect(const MultiRange &mr);89 void intersect(const IRange& r) { intersect(r.begin, r.end); } 90 void intersect(int begin, int end); 91 void intersect(const MultiRange &mr); 92 92 93 void shift(int delta);93 void shift(int delta); 94 94 95 void print() const;96 void print2() const;95 void print() const; 96 void print2() const; 97 97 }; 98 98 99 99 #endif 100 101 102 103 104
Note: See TracChangeset
for help on using the changeset viewer.