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: 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.
27 #ifndef RangeMap_DEF_INCLUDED
28 #define RangeMap_DEF_INCLUDED 1
35 namespace SP_NAMESPACE {
38 template<class From, class To>
39 RangeMap<From, To>::RangeMap()
43 template<class From, class To>
44 Boolean RangeMap<From, To>::map(From from, To &to, From &alsoMax) const
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);
59 typedef ISet<WideChar> RangeMap_dummy;
61 template<class From, class To>
62 unsigned RangeMap<From, To>::inverseMap(To to, From &from,
63 ISet<WideChar> &fromSet,
64 WideChar &count) const
66 // FIXME use binary search
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;
75 if (thisCount < count)
82 if (thisCount < count)
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())
101 // If the new range overlaps an existing one, the new
102 // one takes precedence.
104 template<class From, class To>
105 void RangeMap<From, To>::addRange(From fromMin, From fromMax, To toMin)
107 // FIXME use binary search
109 for (i = ranges_.size(); i > 0; i--)
110 if (fromMin > ranges_[i - 1].fromMax)
112 // fromMin <= ranges[i].fromMax
113 Boolean coalesced = 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;
122 else if (i < ranges_.size() && fromMax >= ranges_[i].fromMin - 1) {
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)
129 ranges_[i].fromMax = fromMax;
134 // fromMin > ranges_[i].fromMin
135 if (ranges_[i].toMin + (fromMin - ranges_[i].fromMin) == toMin) {
136 if (fromMax < ranges_[i].fromMax)
138 ranges_[i].fromMax = fromMax;
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;
152 // Delete overlapping ranges starting at i + 1.
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;
162 // delete i + 1 ... j - 1
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)));
176 #endif /* not RangeMap_DEF_INCLUDED */