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: Partition.C /main/1 1996/07/29 17:01:30 cde-hp $ */
24 // Copyright (c) 1994 James Clark
25 // See the file COPYING for copying permission.
28 #pragma implementation
31 #include "Partition.h"
34 #include "SubstTable.h"
37 #include "IListIter.h"
40 #include "EquivClass.h"
45 namespace SP_NAMESPACE {
48 static void refineByChar(IList<EquivClass> *, Char);
49 static void refineBySet(IList<EquivClass> *, const ISet<Char> &, unsigned);
52 // Work around MSVC 2.0 bug.
53 typedef SubstTable<Char> _msvc_dummy;
56 Partition::Partition(const ISet<Char> &chars,
57 const ISet<Char> **sets,
59 const SubstTable<Char> &subst)
60 : map_(0) // eE gets code 0
62 IList<EquivClass> classes;
63 classes.insert(new EquivClass);
64 classes.head()->set.addRange(0, charMax);
67 ISetIter<Char> iter(chars);
69 while (iter.next(min, max)) {
71 refineByChar(&classes, subst[min]);
72 } while (min++ != max);
77 for (i = 0; i < nSets; i++)
78 refineBySet(&classes, *sets[i], (1 << i));
82 setCodes_.resize(nSets);
84 for (IListIter<EquivClass> listIter(classes);
88 ASSERT(maxCode_ != 0);
89 EquivClass *p = listIter.cur();
90 for (i = 0; i < nSets; i++)
91 if ((1 << i) & p->inSets)
92 setCodes_[i] += maxCode_;
93 ISetIter<Char> setIter(p->set);
95 while (setIter.next(min, max))
96 map_.setRange(min, max, maxCode_);
100 ISetIter<Char> iter(chars);
102 while (iter.next(min, max)) {
104 StringC str(subst.inverse(min));
105 EquivCode code = map_[min];
106 for (size_t i = 0; i < str.size(); i++)
107 map_.setChar(str[i], code);
108 } while (min++ != max);
114 void refineByChar(IList<EquivClass> *classes, Char c)
116 // Avoid modifying *classes, while there's an active iter on it.
117 EquivClass *found = 0;
119 for (IListIter<EquivClass> iter(*classes); !iter.done(); iter.next()) {
120 if (iter.cur()->set.contains(c)) {
126 if (found && !found->set.isSingleton()) {
127 found->set.remove(c);
128 classes->insert(new EquivClass(found->inSets));
129 classes->head()->set.add(c);
134 void addUpTo(ISet<Char> *to, Char limit, const ISet<Char> &from)
136 ISetIter<Char> iter(from);
138 while (iter.next(min, max) && min < limit)
139 to->addRange(min, max >= limit ? limit - 1 : max);
142 enum RefineResult { allIn, allOut, someInSomeOut };
145 RefineResult refine(const ISet<Char> &set, const ISet<Char> &refiner,
146 ISet<Char> *inp, ISet<Char> *outp)
148 Char setMin, setMax, refMin, refMax;
149 ISetIter<Char> refIter(refiner);
150 ISetIter<Char> setIter(set);
154 if (!refIter.next(refMin, refMax))
156 while (setIter.next(setMin, setMax)) {
157 while (setMin <= setMax) {
158 while (refMax < setMin && refIter.next(refMin, refMax))
160 if (refMax < setMin || setMin < refMin) {
163 addUpTo(inp, setMin, set);
166 if (refMax < setMin || refMin > setMax) {
168 outp->addRange(setMin, setMax);
173 outp->addRange(setMin, refMin - 1);
180 addUpTo(outp, setMin, set);
183 if (setMax <= refMax) {
185 inp->addRange(setMin, setMax);
191 inp->addRange(setMin, refMax);
192 // avoid wrapping round
193 if (refMax == charMax)
201 return oneOut ? someInSomeOut : allIn;
207 void refineBySet(IList<EquivClass> *classes, const ISet<Char> &set,
210 Owner<EquivClass> in(new EquivClass), out(new EquivClass);
211 IList<EquivClass> newClasses;
213 EquivClass *p = classes->head();
217 out = new EquivClass;
218 switch (refine(p->set, set, &in->set, &out->set)) {
220 in->inSets = p->inSets | setFlag;
221 newClasses.insert(in.extract());
222 out->inSets = p->inSets;
223 newClasses.insert(out.extract());
229 p->inSets |= setFlag;
230 newClasses.insert(classes->get());
233 newClasses.insert(classes->get());
237 classes->swap(newClasses);