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
29INLINE
30Positions::Positions ()
31 : _useall (false),
32 _size (0)
33{
34}
35
36INLINE
37Positions::Positions (int pos1)
38 : _useall (false),
39 _size (1)
40{
41 _positions[0] = pos1;
42}
43
44INLINE
45Positions::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
55INLINE
56Positions::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
65INLINE Positions&
66Positions::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
76INLINE bool
77Positions::is_useall () const
78{
79 return _useall;
80}
81
82INLINE int
83Positions::operator[] (unsigned int index) const
84{
85 return _positions[index];
86}
87
88INLINE unsigned int
89Positions::get_size () const
90{
91 return _size;
92}
93
94/* Write access. */
95
96INLINE void
97Positions::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
110INLINE int *
111Positions::pointer ()
112{
113 return _positions;
114}
115
116INLINE void
117Positions::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. */
124INLINE bool
125Positions::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. */
151INLINE PositionIterator
152Positions::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. */
159INLINE PositionIterator
160Positions::iterator (int maxlen) const
161{
162 return PositionIterator (*this, maxlen);
163}
164
165/* Creates an iterator, returning the positions in ascending order. */
166INLINE PositionReverseIterator
167Positions::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. */
174INLINE PositionReverseIterator
175Positions::reviterator (int maxlen) const
176{
177 return PositionReverseIterator (*this, maxlen);
178}
179
180/* ------------------------- Class PositionIterator ------------------------ */
181
182/* Initializes an iterator through POSITIONS. */
183INLINE
184PositionIterator::PositionIterator (Positions const& positions)
185 : _set (positions),
186 _index (0)
187{
188}
189
190/* Initializes an iterator through POSITIONS, ignoring positions >= maxlen. */
191INLINE
192PositionIterator::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. */
209INLINE int
210PositionIterator::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. */
217INLINE unsigned int
218PositionIterator::remaining () const
219{
220 return _set._size - _index;
221}
222
223/* Copy constructor. */
224INLINE
225PositionIterator::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. */
234INLINE
235PositionReverseIterator::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. */
243INLINE
244PositionReverseIterator::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. */
262INLINE int
263PositionReverseIterator::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. */
270INLINE unsigned int
271PositionReverseIterator::remaining () const
272{
273 return _index - _minindex;
274}
275
276/* Copy constructor. */
277INLINE
278PositionReverseIterator::PositionReverseIterator (const PositionReverseIterator& src)
279 : _set (src._set),
280 _index (src._index),
281 _minindex (src._minindex)
282{
283}
284