cde/programs/nsgmls/ISet.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: ISet.C /main/1 1996/07/29 16:54:10 cde-hp $ */
  24 // Copyright (c) 1994 James Clark
  25 // See the file COPYING for copying permission.
  26
  27 #ifndef ISet_DEF_INCLUDED
  28 #define ISet_DEF_INCLUDED 1
  29
  30 #include <stdlib.h>
  31
  32 #ifdef SP_NAMESPACE
  33 namespace SP_NAMESPACE {
  34 #endif
  35
  36 template<class T>
  37 ISet<T>::ISet()
  38 {
  39 }
  40
  41 template<class T>
  42 ISet<T>::~ISet()
  43 {
  44 }
  45
  46 template<class T>
  47 ISet<T>::ISet(const T *v, size_t n)
  48 {
  49   for (size_t i = 0; i < n; i++)
  50     add(v[i]);
  51 }
  52
  53 template<class T>
  54 Boolean ISet<T>::contains(T x) const
  55 {
  56   for (size_t i = 0; i < r_.size(); i++)
  57     if (r_[i].max >= x)
  58       return r_[i].min <= x ? 1 : 0;
  59   return 0;
  60 }
  61
  62 template<class T>
  63 void ISet<T>::addRange(T min, T max)
  64 {
  65   size_t i;
  66   if (min == 0)
  67     i = 0;
  68   else {
  69     for (i = r_.size(); i > 0 && min - 1 <= r_[i - 1].max; i--)
  70       ;
  71   }
  72   // r_[i - 1].max < min - 1 <= r_[i].max
  73   if (i < r_.size() && (r_[i].min == 0 || max >= r_[i].min - 1)) {
  74     // we can coelesce
  75     if (min < r_[i].min)
  76       r_[i].min = min;
  77     if (max > r_[i].max) {
  78       r_[i].max = max;
  79       size_t j;
  80       for (j = i + 1; j < r_.size() && r_[i].max >= r_[j].min - 1; j++)
  81         r_[i].max = r_[j].max;
  82       // get rid of i + 1 ... j - 1
  83       if (j > i + 1) {
  84         for (size_t k = j; k < r_.size(); k++)
  85           r_[k - (j - i - 1)] = r_[k];
  86         r_.resize(r_.size() - (j - i - 1));
  87       }
  88     }
  89   }
  90   else {
  91     // r_[i - 1].max < min - 1
  92     // max + 1 < r_[i].min
  93     r_.resize(r_.size() + 1);
  94     for (size_t j = r_.size() - 1; j > i; j--)
  95       r_[j] = r_[j - 1];
  96     r_[i].max = max;
  97     r_[i].min = min;
  98   }
  99 }
 100
 101 template<class T>
 102 void ISet<T>::remove(T c)
 103 {
 104   for (size_t i = 0; i < r_.size(); i++)
 105     if (r_[i].max >= c) {
 106       if (r_[i].min <= c) {
 107         if (r_[i].min == r_[i].max) {
 108           while (++i < r_.size())
 109             r_[i - 1] = r_[i];
 110           r_.resize(r_.size() - 1);
 111         }
 112         else if (c == r_[i].min)
 113           r_[i].min += 1;
 114         else if (c == r_[i].max)
 115           r_[i].max -= 1;
 116         else {
 117           r_.resize(r_.size() + 1);
 118           // split the range
 119           // subtracting 2 is safe since we know that the length is >= 2
 120           for (size_t j = r_.size() - 2; j > i; j--)
 121             r_[j + 1] = r_[j];
 122           r_[i + 1].max = r_[i].max;
 123           r_[i + 1].min = c + 1;
 124           r_[i].max = c - 1;
 125         }
 126       }
 127       break;
 128     }
 129 }
 130
 131 template<class T>
 132 void ISet<T>::check()
 133 {
 134   for (size_t i = 0; i < r_.size(); i++) {
 135     if (r_[i].min > r_[i].max)
 136       abort();
 137     // adjacent ranges must be coalesced
 138     if (i > 0 && r_[i].min - 1 <= r_[i - 1].max)
 139       abort();
 140   }
 141 }
 142
 143 template<class T>
 144 void ISet<T>::clear()
 145 {
 146   r_.resize(0);
 147 }
 148
 149 #ifdef SP_NAMESPACE
 150 }
 151 #endif
 152
 153 #endif /* not ISet_DEF_INCLUDED */