Changeset 733 for cpp/frams/util/multirange.cpp
 Timestamp:
 02/15/18 00:43:07 (6 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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 }
Note: See TracChangeset
for help on using the changeset viewer.