cde/programs/nsgmls/ISet.C

   1 /* $XConsortium: ISet.C /main/1 1996/07/29 16:54:10 cde-hp $ */
   2 // Copyright (c) 1994 James Clark
   3 // See the file COPYING for copying permission.
   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>
  15 ISet<T>::ISet()
  16 {
  17 }
  18
  19 template<class T>
  20 ISet<T>::~ISet()
  21 {
  22 }
  23
  24 template<class T>
  25 ISet<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>
  32 Boolean 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>
  41 void 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>
  80 void 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>
 110 void 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>
 122 void ISet<T>::clear()
 123 {
 124   r_.resize(0);
 125 }
 126
 127 #ifdef SP_NAMESPACE
 128 }
 129 #endif
 130
 131 #endif /* not ISet_DEF_INCLUDED */