cde/programs/nsgmls/Partition.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 libraries 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: 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.
  26
  27 #ifdef __GNUG__
  28 #pragma implementation
  29 #endif
  30 #include "splib.h"
  31 #include "Partition.h"
  32 #include "ISet.h"
  33 #include "ISetIter.h"
  34 #include "SubstTable.h"
  35 #include "Link.h"
  36 #include "IList.h"
  37 #include "IListIter.h"
  38 #include "Owner.h"
  39 #include "macros.h"
  40 #include "EquivClass.h"
  41 #include "constant.h"
  42 #include "StringC.h"
  43
  44 #ifdef SP_NAMESPACE
  45 namespace SP_NAMESPACE {
  46 #endif
  47
  48 static void refineByChar(IList<EquivClass> *, Char);
  49 static void refineBySet(IList<EquivClass> *, const ISet<Char> &, unsigned);
  50
  51 #if _MSC_VER == 900
  52 // Work around MSVC 2.0 bug.
  53 typedef SubstTable<Char> _msvc_dummy;
  54 #endif
  55
  56 Partition::Partition(const ISet<Char> &chars,
  57                      const ISet<Char> **sets,
  58                      int nSets,
  59                      const SubstTable<Char> &subst)
  60 : map_(0)                       // eE gets code 0
  61 {
  62   IList<EquivClass> classes;
  63   classes.insert(new EquivClass);
  64   classes.head()->set.addRange(0, charMax);
  65
  66   {
  67     ISetIter<Char> iter(chars);
  68     Char min, max;
  69     while (iter.next(min, max)) {
  70       do {
  71         refineByChar(&classes, subst[min]);
  72       } while (min++ != max);
  73     }
  74   }
  75
  76   int i;
  77   for (i = 0; i < nSets; i++)
  78     refineBySet(&classes, *sets[i], (1 << i));
  79
  80   maxCode_ = 0;
  81
  82   setCodes_.resize(nSets);
  83
  84   for (IListIter<EquivClass> listIter(classes);
  85        !listIter.done();
  86        listIter.next()) {
  87     ++maxCode_;
  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);
  94     Char min, max;
  95     while (setIter.next(min, max))
  96       map_.setRange(min, max, maxCode_);
  97   }
  98
  99   {
 100     ISetIter<Char> iter(chars);
 101     Char min, max;
 102     while (iter.next(min, max)) {
 103       do {
 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);
 109     }
 110   }
 111 }
 112
 113 static
 114 void refineByChar(IList<EquivClass> *classes, Char c)
 115 {
 116   // Avoid modifying *classes, while there's an active iter on it.
 117   EquivClass *found = 0;
 118   {
 119     for (IListIter<EquivClass> iter(*classes); !iter.done(); iter.next()) {
 120       if (iter.cur()->set.contains(c)) {
 121         found = iter.cur();
 122         break;
 123       }
 124     }
 125   }
 126   if (found && !found->set.isSingleton()) {
 127     found->set.remove(c);
 128     classes->insert(new EquivClass(found->inSets));
 129     classes->head()->set.add(c);
 130   }
 131 }
 132
 133 static
 134 void addUpTo(ISet<Char> *to, Char limit, const ISet<Char> &from)
 135 {
 136   ISetIter<Char> iter(from);
 137   Char min, max;
 138   while (iter.next(min, max) && min < limit)
 139     to->addRange(min, max >= limit ? limit - 1 : max);
 140 }
 141
 142 enum RefineResult { allIn, allOut, someInSomeOut };
 143
 144 static
 145 RefineResult refine(const ISet<Char> &set, const ISet<Char> &refiner,
 146                     ISet<Char> *inp, ISet<Char> *outp)
 147 {
 148   Char setMin, setMax, refMin, refMax;
 149   ISetIter<Char> refIter(refiner);
 150   ISetIter<Char> setIter(set);
 151   Boolean oneIn = 0;
 152   Boolean oneOut = 0;
 153
 154   if (!refIter.next(refMin, refMax))
 155     return allOut;
 156   while (setIter.next(setMin, setMax)) {
 157     while (setMin <= setMax) {
 158       while (refMax < setMin && refIter.next(refMin, refMax))
 159         ;
 160       if (refMax < setMin || setMin < refMin) {
 161         if (!oneOut) {
 162           if (oneIn)
 163             addUpTo(inp, setMin, set);
 164           oneOut = 1;
 165         }
 166         if (refMax < setMin || refMin > setMax) {
 167           if (oneIn)
 168             outp->addRange(setMin, setMax);
 169           break;
 170         }
 171         else {
 172           if (oneIn)
 173             outp->addRange(setMin, refMin - 1);
 174           setMin = refMin;
 175         }
 176       }
 177       else {
 178         if (!oneIn) {
 179           if (oneOut)
 180             addUpTo(outp, setMin, set);
 181           oneIn = 1;
 182         }
 183         if (setMax <= refMax) {
 184           if (oneOut)
 185             inp->addRange(setMin, setMax);
 186           break;
 187         }
 188         else {
 189           // refMax < setMax
 190           if (oneOut)
 191             inp->addRange(setMin, refMax);
 192           // avoid wrapping round
 193           if (refMax == charMax)
 194             break;
 195           setMin = refMax + 1;
 196         }
 197       }
 198     }
 199   }
 200   if (oneIn)
 201     return oneOut ? someInSomeOut : allIn;
 202   else
 203     return allOut;
 204 }
 205
 206 static
 207 void refineBySet(IList<EquivClass> *classes, const ISet<Char> &set,
 208                  unsigned setFlag)
 209 {
 210   Owner<EquivClass> in(new EquivClass), out(new EquivClass);
 211   IList<EquivClass> newClasses;
 212   for (;;) {
 213     EquivClass *p = classes->head();
 214     if (!p)
 215       break;
 216     if (!out)
 217       out = new EquivClass;
 218     switch (refine(p->set, set, &in->set, &out->set)) {
 219     case someInSomeOut:
 220       in->inSets = p->inSets | setFlag;
 221       newClasses.insert(in.extract());
 222       out->inSets = p->inSets;
 223       newClasses.insert(out.extract());
 224       in = classes->get();
 225       in->set.clear();
 226       in->inSets = 0;
 227       break;
 228     case allIn:
 229       p->inSets |= setFlag;
 230       newClasses.insert(classes->get());
 231       break;
 232     case allOut:
 233       newClasses.insert(classes->get());
 234       break;
 235     }
 236   }
 237   classes->swap(newClasses);
 238 }
 239
 240 #ifdef SP_NAMESPACE
 241 }
 242 #endif