cde/programs/nsgmls/RangeMap.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: RangeMap.C /main/1 1996/07/29 17:02:17 cde-hp $ */
  24 // Copyright (c) 1994 James Clark
  25 // See the file COPYING for copying permission.
  26
  27 #ifndef RangeMap_DEF_INCLUDED
  28 #define RangeMap_DEF_INCLUDED 1
  29
  30 #include "RangeMap.h"
  31 #include "ISet.h"
  32 #include "types.h"
  33
  34 #ifdef SP_NAMESPACE
  35 namespace SP_NAMESPACE {
  36 #endif
  37
  38 template<class From, class To>
  39 RangeMap<From, To>::RangeMap()
  40 {
  41 }
  42
  43 template<class From, class To>
  44 Boolean RangeMap<From, To>::map(From from, To &to, From &alsoMax) const
  45 {
  46   // FIXME use binary search
  47   for (size_t i = 0; i < ranges_.size(); i++) {
  48     const RangeMapRange<From,To> &r = ranges_[i];
  49     if (r.fromMin <= from && from <= r.fromMax) {
  50       to = r.toMin + (from - r.fromMin);
  51       alsoMax = r.fromMax;
  52       return 1;
  53     }
  54   }
  55   return 0;
  56 }
  57
  58
  59 typedef ISet<WideChar> RangeMap_dummy;
  60
  61 template<class From, class To>
  62 unsigned RangeMap<From, To>::inverseMap(To to, From &from,
  63                                         ISet<WideChar> &fromSet,
  64                                         WideChar &count) const
  65 {
  66   // FIXME use binary search
  67   unsigned ret = 0;
  68   for (size_t i = 0; i < ranges_.size(); i++) {
  69     const RangeMapRange<From,To> &r = ranges_[i];
  70     if (r.toMin <= to && to <= r.toMin + (r.fromMax - r.fromMin)) {
  71       From n = r.fromMin + (to - r.toMin);
  72       WideChar thisCount = r.fromMax - r.fromMin + 1;
  73       if (ret > 1) {
  74         fromSet.add(n);
  75         if (thisCount < count)
  76           count = thisCount;
  77       }
  78       else if (ret == 1) {
  79         fromSet.add(from);
  80         fromSet.add(n);
  81         ret = 2;
  82         if (thisCount < count)
  83           count = thisCount;
  84       }
  85       else {
  86         count = thisCount;
  87         from = n;
  88         ret = 1;
  89       }
  90     }
  91   }
  92   return ret;
  93 }
  94
  95 template<class From, class To>
  96 RangeMapIter<From, To>::RangeMapIter(const RangeMap<From, To> &map)
  97 : count_(map.ranges_.size()), ptr_(map.ranges_.begin())
  98 {
  99 }
 100
 101 // If the new range overlaps an existing one, the new
 102 // one takes precedence.
 103
 104 template<class From, class To>
 105 void RangeMap<From, To>::addRange(From fromMin, From fromMax, To toMin)
 106 {
 107   // FIXME use binary search
 108   size_t i;
 109   for (i = ranges_.size(); i > 0; i--)
 110     if (fromMin > ranges_[i - 1].fromMax)
 111       break;
 112   // fromMin <= ranges[i].fromMax
 113   Boolean coalesced = 0;
 114   if (i > 0
 115       && ranges_[i - 1].fromMax + 1 == fromMin
 116       && ranges_[i - 1].toMin + (fromMin - ranges_[i - 1].fromMin) == toMin) {
 117     // coalesce with previous
 118     ranges_[i - 1].fromMax = fromMax;
 119     i--;
 120     coalesced = 1;
 121   }
 122   else if (i < ranges_.size() && fromMax >= ranges_[i].fromMin - 1) {
 123     // overlap
 124     if (fromMin <= ranges_[i].fromMin) {
 125       if (toMin + (ranges_[i].fromMin - fromMin) == ranges_[i].toMin) {
 126         ranges_[i].fromMin = fromMin;
 127         if (fromMax <= ranges_[i].fromMax)
 128           return;
 129         ranges_[i].fromMax = fromMax;
 130         coalesced = 1;
 131       }
 132     }
 133     else {
 134       // fromMin > ranges_[i].fromMin
 135       if (ranges_[i].toMin + (fromMin - ranges_[i].fromMin) == toMin) {
 136         if (fromMax < ranges_[i].fromMax)
 137           return;
 138         ranges_[i].fromMax = fromMax;
 139         coalesced = 1;
 140       }
 141     }
 142   }
 143   if (!coalesced) {
 144     // insert
 145     ranges_.resize(ranges_.size() + 1);
 146     for (size_t j = ranges_.size() - 1; j > i; j--)
 147       ranges_[j] = ranges_[j - 1];
 148     ranges_[i].fromMin = fromMin;
 149     ranges_[i].fromMax = fromMax;
 150     ranges_[i].toMin = toMin;
 151   }
 152   // Delete overlapping ranges starting at i + 1.
 153   size_t j;
 154   for (j = i + 1; j < ranges_.size(); j++) {
 155     if (fromMax < ranges_[j].fromMax) {
 156       if (fromMax >= ranges_[j].fromMin)
 157         ranges_[j].fromMin = fromMax + 1;
 158       break;
 159     }
 160   }
 161   if (j > i + 1) {
 162     // delete i + 1 ... j - 1
 163     // j -> i + 1
 164     // j - 1 -> i + 2
 165     size_t count = ranges_.size() - j;
 166     for (size_t k = 0; k < count; k++)
 167       ranges_[i + 1 + count] = ranges_[j + count];
 168     ranges_.resize(ranges_.size() - (j - (i + 1)));
 169   }
 170 }
 171
 172 #ifdef SP_NAMESPACE
 173 }
 174 #endif
 175
 176 #endif /* not RangeMap_DEF_INCLUDED */