usr/src/cmd/man/src/util/nsgmls.src/include/RangeMap.cxx

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