2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
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.
27 #ifndef ISet_DEF_INCLUDED
28 #define ISet_DEF_INCLUDED 1
33 namespace SP_NAMESPACE {
47 ISet<T>::ISet(const T *v, size_t n)
49 for (size_t i = 0; i < n; i++)
54 Boolean ISet<T>::contains(T x) const
56 for (size_t i = 0; i < r_.size(); i++)
58 return r_[i].min <= x ? 1 : 0;
63 void ISet<T>::addRange(T min, T max)
69 for (i = r_.size(); i > 0 && min - 1 <= r_[i - 1].max; i--)
72 // r_[i - 1].max < min - 1 <= r_[i].max
73 if (i < r_.size() && (r_[i].min == 0 || max >= r_[i].min - 1)) {
77 if (max > r_[i].max) {
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
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));
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--)
102 void ISet<T>::remove(T c)
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())
110 r_.resize(r_.size() - 1);
112 else if (c == r_[i].min)
114 else if (c == r_[i].max)
117 r_.resize(r_.size() + 1);
119 // subtracting 2 is safe since we know that the length is >= 2
120 for (size_t j = r_.size() - 2; j > i; j--)
122 r_[i + 1].max = r_[i].max;
123 r_[i + 1].min = c + 1;
132 void ISet<T>::check()
134 for (size_t i = 0; i < r_.size(); i++) {
135 if (r_[i].min > r_[i].max)
137 // adjacent ranges must be coalesced
138 if (i > 0 && r_[i].min - 1 <= r_[i - 1].max)
144 void ISet<T>::clear()
153 #endif /* not ISet_DEF_INCLUDED */