1 | /* Inline Functions for positions.{h,cc}. |
2 | |
3 | Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc. |
4 | Written by Douglas C. Schmidt <schmidt@ics.uci.edu> |
5 | and Bruno Haible <bruno@clisp.org>. |
6 | |
7 | This file is part of GNU GPERF. |
8 | |
9 | This program is free software: you can redistribute it and/or modify |
10 | it under the terms of the GNU General Public License as published by |
11 | the Free Software Foundation; either version 3 of the License, or |
12 | (at your option) any later version. |
13 | |
14 | This program is distributed in the hope that it will be useful, |
15 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
16 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
17 | GNU General Public License for more details. |
18 | |
19 | You should have received a copy of the GNU General Public License |
20 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
21 | |
22 | // This needs: |
23 | //#include <string.h> |
24 | |
25 | /* ---------------------------- Class Positions ---------------------------- */ |
26 | |
27 | /* Constructors. */ |
28 | |
29 | INLINE |
30 | Positions::Positions () |
31 | : _useall (false), |
32 | _size (0) |
33 | { |
34 | } |
35 | |
36 | INLINE |
37 | Positions::Positions (int pos1) |
38 | : _useall (false), |
39 | _size (1) |
40 | { |
41 | _positions[0] = pos1; |
42 | } |
43 | |
44 | INLINE |
45 | Positions::Positions (int pos1, int pos2) |
46 | : _useall (false), |
47 | _size (2) |
48 | { |
49 | _positions[0] = pos1; |
50 | _positions[1] = pos2; |
51 | } |
52 | |
53 | /* Copy constructor. */ |
54 | |
55 | INLINE |
56 | Positions::Positions (const Positions& src) |
57 | : _useall (src._useall), |
58 | _size (src._size) |
59 | { |
60 | memcpy (_positions, src._positions, _size * sizeof (_positions[0])); |
61 | } |
62 | |
63 | /* Assignment operator. */ |
64 | |
65 | INLINE Positions& |
66 | Positions::operator= (const Positions& src) |
67 | { |
68 | _useall = src._useall; |
69 | _size = src._size; |
70 | memcpy (_positions, src._positions, _size * sizeof (_positions[0])); |
71 | return *this; |
72 | } |
73 | |
74 | /* Accessors. */ |
75 | |
76 | INLINE bool |
77 | Positions::is_useall () const |
78 | { |
79 | return _useall; |
80 | } |
81 | |
82 | INLINE int |
83 | Positions::operator[] (unsigned int index) const |
84 | { |
85 | return _positions[index]; |
86 | } |
87 | |
88 | INLINE unsigned int |
89 | Positions::get_size () const |
90 | { |
91 | return _size; |
92 | } |
93 | |
94 | /* Write access. */ |
95 | |
96 | INLINE void |
97 | Positions::set_useall (bool useall) |
98 | { |
99 | _useall = useall; |
100 | if (useall) |
101 | { |
102 | /* The positions are 0, 1, ..., MAX_KEY_POS-1, in descending order. */ |
103 | _size = MAX_KEY_POS; |
104 | int *ptr = _positions; |
105 | for (int i = MAX_KEY_POS - 1; i >= 0; i--) |
106 | *ptr++ = i; |
107 | } |
108 | } |
109 | |
110 | INLINE int * |
111 | Positions::pointer () |
112 | { |
113 | return _positions; |
114 | } |
115 | |
116 | INLINE void |
117 | Positions::set_size (unsigned int size) |
118 | { |
119 | _size = size; |
120 | } |
121 | |
122 | /* Sorts the array in reverse order. |
123 | Returns true if there are no duplicates, false otherwise. */ |
124 | INLINE bool |
125 | Positions::sort () |
126 | { |
127 | if (_useall) |
128 | return true; |
129 | |
130 | /* Bubble sort. */ |
131 | bool duplicate_free = true; |
132 | int *base = _positions; |
133 | unsigned int len = _size; |
134 | |
135 | for (unsigned int i = 1; i < len; i++) |
136 | { |
137 | unsigned int j; |
138 | int tmp; |
139 | |
140 | for (j = i, tmp = base[j]; j > 0 && tmp >= base[j - 1]; j--) |
141 | if ((base[j] = base[j - 1]) == tmp) /* oh no, a duplicate!!! */ |
142 | duplicate_free = false; |
143 | |
144 | base[j] = tmp; |
145 | } |
146 | |
147 | return duplicate_free; |
148 | } |
149 | |
150 | /* Creates an iterator, returning the positions in descending order. */ |
151 | INLINE PositionIterator |
152 | Positions::iterator () const |
153 | { |
154 | return PositionIterator (*this); |
155 | } |
156 | |
157 | /* Creates an iterator, returning the positions in descending order, |
158 | that apply to strings of length <= maxlen. */ |
159 | INLINE PositionIterator |
160 | Positions::iterator (int maxlen) const |
161 | { |
162 | return PositionIterator (*this, maxlen); |
163 | } |
164 | |
165 | /* Creates an iterator, returning the positions in ascending order. */ |
166 | INLINE PositionReverseIterator |
167 | Positions::reviterator () const |
168 | { |
169 | return PositionReverseIterator (*this); |
170 | } |
171 | |
172 | /* Creates an iterator, returning the positions in ascending order, |
173 | that apply to strings of length <= maxlen. */ |
174 | INLINE PositionReverseIterator |
175 | Positions::reviterator (int maxlen) const |
176 | { |
177 | return PositionReverseIterator (*this, maxlen); |
178 | } |
179 | |
180 | /* ------------------------- Class PositionIterator ------------------------ */ |
181 | |
182 | /* Initializes an iterator through POSITIONS. */ |
183 | INLINE |
184 | PositionIterator::PositionIterator (Positions const& positions) |
185 | : _set (positions), |
186 | _index (0) |
187 | { |
188 | } |
189 | |
190 | /* Initializes an iterator through POSITIONS, ignoring positions >= maxlen. */ |
191 | INLINE |
192 | PositionIterator::PositionIterator (Positions const& positions, int maxlen) |
193 | : _set (positions) |
194 | { |
195 | if (positions._useall) |
196 | _index = (maxlen <= Positions::MAX_KEY_POS ? Positions::MAX_KEY_POS - maxlen : 0); |
197 | else |
198 | { |
199 | unsigned int index; |
200 | for (index = 0; |
201 | index < positions._size && positions._positions[index] >= maxlen; |
202 | index++) |
203 | ; |
204 | _index = index; |
205 | } |
206 | } |
207 | |
208 | /* Retrieves the next position, or EOS past the end. */ |
209 | INLINE int |
210 | PositionIterator::next () |
211 | { |
212 | return (_index < _set._size ? _set._positions[_index++] : EOS); |
213 | } |
214 | |
215 | /* Returns the number of remaining positions, i.e. how often next() will |
216 | return a value != EOS. */ |
217 | INLINE unsigned int |
218 | PositionIterator::remaining () const |
219 | { |
220 | return _set._size - _index; |
221 | } |
222 | |
223 | /* Copy constructor. */ |
224 | INLINE |
225 | PositionIterator::PositionIterator (const PositionIterator& src) |
226 | : _set (src._set), |
227 | _index (src._index) |
228 | { |
229 | } |
230 | |
231 | /* --------------------- Class PositionReverseIterator --------------------- */ |
232 | |
233 | /* Initializes an iterator through POSITIONS. */ |
234 | INLINE |
235 | PositionReverseIterator::PositionReverseIterator (Positions const& positions) |
236 | : _set (positions), |
237 | _index (_set._size), |
238 | _minindex (0) |
239 | { |
240 | } |
241 | |
242 | /* Initializes an iterator through POSITIONS, ignoring positions >= maxlen. */ |
243 | INLINE |
244 | PositionReverseIterator::PositionReverseIterator (Positions const& positions, int maxlen) |
245 | : _set (positions), |
246 | _index (_set._size) |
247 | { |
248 | if (positions._useall) |
249 | _minindex = (maxlen <= Positions::MAX_KEY_POS ? Positions::MAX_KEY_POS - maxlen : 0); |
250 | else |
251 | { |
252 | unsigned int index; |
253 | for (index = 0; |
254 | index < positions._size && positions._positions[index] >= maxlen; |
255 | index++) |
256 | ; |
257 | _minindex = index; |
258 | } |
259 | } |
260 | |
261 | /* Retrieves the next position, or EOS past the end. */ |
262 | INLINE int |
263 | PositionReverseIterator::next () |
264 | { |
265 | return (_index > _minindex ? _set._positions[--_index] : EOS); |
266 | } |
267 | |
268 | /* Returns the number of remaining positions, i.e. how often next() will |
269 | return a value != EOS. */ |
270 | INLINE unsigned int |
271 | PositionReverseIterator::remaining () const |
272 | { |
273 | return _index - _minindex; |
274 | } |
275 | |
276 | /* Copy constructor. */ |
277 | INLINE |
278 | PositionReverseIterator::PositionReverseIterator (const PositionReverseIterator& src) |
279 | : _set (src._set), |
280 | _index (src._index), |
281 | _minindex (src._minindex) |
282 | { |
283 | } |
284 | |