1 // Copyright (c) 1994 James Clark 2 // See the file COPYING for copying permission. 3 #pragma ident "%Z%%M% %I% %E% SMI" 4 5 #ifndef ISet_DEF_INCLUDED 6 #define ISet_DEF_INCLUDED 1 7 8 #include <stdlib.h> 9 10 #ifdef SP_NAMESPACE 11 namespace SP_NAMESPACE { 12 #endif 13 14 template<class T> ISet()15ISet<T>::ISet() 16 { 17 } 18 19 template<class T> ~ISet()20ISet<T>::~ISet() 21 { 22 } 23 24 template<class T> ISet(const T * v,size_t n)25ISet<T>::ISet(const T *v, size_t n) 26 { 27 for (size_t i = 0; i < n; i++) 28 add(v[i]); 29 } 30 31 template<class T> contains(T x) const32Boolean ISet<T>::contains(T x) const 33 { 34 for (size_t i = 0; i < r_.size(); i++) 35 if (r_[i].max >= x) 36 return r_[i].min <= x ? 1 : 0; 37 return 0; 38 } 39 40 template<class T> addRange(T min,T max)41void ISet<T>::addRange(T min, T max) 42 { 43 size_t i; 44 if (min == 0) 45 i = 0; 46 else { 47 for (i = r_.size(); i > 0 && min - 1 <= r_[i - 1].max; i--) 48 ; 49 } 50 // r_[i - 1].max < min - 1 <= r_[i].max 51 if (i < r_.size() && (r_[i].min == 0 || max >= r_[i].min - 1)) { 52 // we can coelesce 53 if (min < r_[i].min) 54 r_[i].min = min; 55 if (max > r_[i].max) { 56 r_[i].max = max; 57 size_t j; 58 for (j = i + 1; j < r_.size() && r_[i].max >= r_[j].min - 1; j++) 59 r_[i].max = r_[j].max; 60 // get rid of i + 1 ... j - 1 61 if (j > i + 1) { 62 for (size_t k = j; k < r_.size(); k++) 63 r_[k - (j - i - 1)] = r_[k]; 64 r_.resize(r_.size() - (j - i - 1)); 65 } 66 } 67 } 68 else { 69 // r_[i - 1].max < min - 1 70 // max + 1 < r_[i].min 71 r_.resize(r_.size() + 1); 72 for (size_t j = r_.size() - 1; j > i; j--) 73 r_[j] = r_[j - 1]; 74 r_[i].max = max; 75 r_[i].min = min; 76 } 77 } 78 79 template<class T> remove(T c)80void ISet<T>::remove(T c) 81 { 82 for (size_t i = 0; i < r_.size(); i++) 83 if (r_[i].max >= c) { 84 if (r_[i].min <= c) { 85 if (r_[i].min == r_[i].max) { 86 while (++i < r_.size()) 87 r_[i - 1] = r_[i]; 88 r_.resize(r_.size() - 1); 89 } 90 else if (c == r_[i].min) 91 r_[i].min += 1; 92 else if (c == r_[i].max) 93 r_[i].max -= 1; 94 else { 95 r_.resize(r_.size() + 1); 96 // split the range 97 // subtracting 2 is safe since we know that the length is >= 2 98 for (size_t j = r_.size() - 2; j > i; j--) 99 r_[j + 1] = r_[j]; 100 r_[i + 1].max = r_[i].max; 101 r_[i + 1].min = c + 1; 102 r_[i].max = c - 1; 103 } 104 } 105 break; 106 } 107 } 108 109 template<class T> check()110void ISet<T>::check() 111 { 112 for (size_t i = 0; i < r_.size(); i++) { 113 if (r_[i].min > r_[i].max) 114 abort(); 115 // adjacent ranges must be coalesced 116 if (i > 0 && r_[i].min - 1 <= r_[i - 1].max) 117 abort(); 118 } 119 } 120 121 template<class T> clear()122void ISet<T>::clear() 123 { 124 r_.resize(0); 125 } 126 127 #ifdef SP_NAMESPACE 128 } 129 #endif 130 131 #endif /* not ISet_DEF_INCLUDED */ 132