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>
RangeMap()17 RangeMap<From, To>::RangeMap()
18 {
19 }
20
21 template<class From, class To>
map(From from,To & to,From & alsoMax) const22 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>
inverseMap(To to,From & from,ISet<WideChar> & fromSet,WideChar & count) const45 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>
RangeMapIter(const RangeMap<From,To> & map)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>
addRange(From fromMin,From fromMax,To toMin)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 */
163