1228060Sbapt/* Inline Functions for positions.{h,cc}. 2228060Sbapt 3228060Sbapt Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc. 4228060Sbapt Written by Douglas C. Schmidt <schmidt@ics.uci.edu> 5228060Sbapt and Bruno Haible <bruno@clisp.org>. 6228060Sbapt 7228060Sbapt This file is part of GNU GPERF. 8228060Sbapt 9228060Sbapt GNU GPERF is free software; you can redistribute it and/or modify 10228060Sbapt it under the terms of the GNU General Public License as published by 11228060Sbapt the Free Software Foundation; either version 2, or (at your option) 12228060Sbapt any later version. 13228060Sbapt 14228060Sbapt GNU GPERF is distributed in the hope that it will be useful, 15228060Sbapt but WITHOUT ANY WARRANTY; without even the implied warranty of 16228060Sbapt MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17228060Sbapt GNU General Public License for more details. 18228060Sbapt 19228060Sbapt You should have received a copy of the GNU General Public License 20228060Sbapt along with this program; see the file COPYING. 21228060Sbapt If not, write to the Free Software Foundation, Inc., 22228060Sbapt 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 23228060Sbapt 24228060Sbapt// This needs: 25228060Sbapt//#include <string.h> 26228060Sbapt 27228060Sbapt/* ---------------------------- Class Positions ---------------------------- */ 28228060Sbapt 29228060Sbapt/* Constructors. */ 30228060Sbapt 31228060SbaptINLINE 32228060SbaptPositions::Positions () 33228060Sbapt : _useall (false), 34228060Sbapt _size (0) 35228060Sbapt{ 36228060Sbapt} 37228060Sbapt 38228060SbaptINLINE 39228060SbaptPositions::Positions (int pos1) 40228060Sbapt : _useall (false), 41228060Sbapt _size (1) 42228060Sbapt{ 43228060Sbapt _positions[0] = pos1; 44228060Sbapt} 45228060Sbapt 46228060SbaptINLINE 47228060SbaptPositions::Positions (int pos1, int pos2) 48228060Sbapt : _useall (false), 49228060Sbapt _size (2) 50228060Sbapt{ 51228060Sbapt _positions[0] = pos1; 52228060Sbapt _positions[1] = pos2; 53228060Sbapt} 54228060Sbapt 55228060Sbapt/* Copy constructor. */ 56228060Sbapt 57228060SbaptINLINE 58228060SbaptPositions::Positions (const Positions& src) 59228060Sbapt : _useall (src._useall), 60228060Sbapt _size (src._size) 61228060Sbapt{ 62228060Sbapt memcpy (_positions, src._positions, _size * sizeof (_positions[0])); 63228060Sbapt} 64228060Sbapt 65228060Sbapt/* Assignment operator. */ 66228060Sbapt 67228060SbaptINLINE Positions& 68228060SbaptPositions::operator= (const Positions& src) 69228060Sbapt{ 70228060Sbapt _useall = src._useall; 71228060Sbapt _size = src._size; 72228060Sbapt memcpy (_positions, src._positions, _size * sizeof (_positions[0])); 73228060Sbapt return *this; 74228060Sbapt} 75228060Sbapt 76228060Sbapt/* Accessors. */ 77228060Sbapt 78228060SbaptINLINE bool 79228060SbaptPositions::is_useall () const 80228060Sbapt{ 81228060Sbapt return _useall; 82228060Sbapt} 83228060Sbapt 84228060SbaptINLINE int 85228060SbaptPositions::operator[] (unsigned int index) const 86228060Sbapt{ 87228060Sbapt return _positions[index]; 88228060Sbapt} 89228060Sbapt 90228060SbaptINLINE unsigned int 91228060SbaptPositions::get_size () const 92228060Sbapt{ 93228060Sbapt return _size; 94228060Sbapt} 95228060Sbapt 96228060Sbapt/* Write access. */ 97228060Sbapt 98228060SbaptINLINE void 99228060SbaptPositions::set_useall (bool useall) 100228060Sbapt{ 101228060Sbapt _useall = useall; 102228060Sbapt if (useall) 103228060Sbapt { 104228060Sbapt /* The positions are 0, 1, ..., MAX_KEY_POS-1, in descending order. */ 105228060Sbapt _size = MAX_KEY_POS; 106228060Sbapt int *ptr = _positions; 107228060Sbapt for (int i = MAX_KEY_POS - 1; i >= 0; i--) 108228060Sbapt *ptr++ = i; 109228060Sbapt } 110228060Sbapt} 111228060Sbapt 112228060SbaptINLINE int * 113228060SbaptPositions::pointer () 114228060Sbapt{ 115228060Sbapt return _positions; 116228060Sbapt} 117228060Sbapt 118228060SbaptINLINE void 119228060SbaptPositions::set_size (unsigned int size) 120228060Sbapt{ 121228060Sbapt _size = size; 122228060Sbapt} 123228060Sbapt 124228060Sbapt/* Sorts the array in reverse order. 125228060Sbapt Returns true if there are no duplicates, false otherwise. */ 126228060SbaptINLINE bool 127228060SbaptPositions::sort () 128228060Sbapt{ 129228060Sbapt if (_useall) 130228060Sbapt return true; 131228060Sbapt 132228060Sbapt /* Bubble sort. */ 133228060Sbapt bool duplicate_free = true; 134228060Sbapt int *base = _positions; 135228060Sbapt unsigned int len = _size; 136228060Sbapt 137228060Sbapt for (unsigned int i = 1; i < len; i++) 138228060Sbapt { 139228060Sbapt unsigned int j; 140228060Sbapt int tmp; 141228060Sbapt 142228060Sbapt for (j = i, tmp = base[j]; j > 0 && tmp >= base[j - 1]; j--) 143228060Sbapt if ((base[j] = base[j - 1]) == tmp) /* oh no, a duplicate!!! */ 144228060Sbapt duplicate_free = false; 145228060Sbapt 146228060Sbapt base[j] = tmp; 147228060Sbapt } 148228060Sbapt 149228060Sbapt return duplicate_free; 150228060Sbapt} 151228060Sbapt 152228060Sbapt/* Creates an iterator, returning the positions in descending order. */ 153228060SbaptINLINE PositionIterator 154228060SbaptPositions::iterator () const 155228060Sbapt{ 156228060Sbapt return PositionIterator (*this); 157228060Sbapt} 158228060Sbapt 159228060Sbapt/* Creates an iterator, returning the positions in descending order, 160228060Sbapt that apply to strings of length <= maxlen. */ 161228060SbaptINLINE PositionIterator 162228060SbaptPositions::iterator (int maxlen) const 163228060Sbapt{ 164228060Sbapt return PositionIterator (*this, maxlen); 165228060Sbapt} 166228060Sbapt 167228060Sbapt/* Creates an iterator, returning the positions in ascending order. */ 168228060SbaptINLINE PositionReverseIterator 169228060SbaptPositions::reviterator () const 170228060Sbapt{ 171228060Sbapt return PositionReverseIterator (*this); 172228060Sbapt} 173228060Sbapt 174228060Sbapt/* Creates an iterator, returning the positions in ascending order, 175228060Sbapt that apply to strings of length <= maxlen. */ 176228060SbaptINLINE PositionReverseIterator 177228060SbaptPositions::reviterator (int maxlen) const 178228060Sbapt{ 179228060Sbapt return PositionReverseIterator (*this, maxlen); 180228060Sbapt} 181228060Sbapt 182228060Sbapt/* ------------------------- Class PositionIterator ------------------------ */ 183228060Sbapt 184228060Sbapt/* Initializes an iterator through POSITIONS. */ 185228060SbaptINLINE 186228060SbaptPositionIterator::PositionIterator (Positions const& positions) 187228060Sbapt : _set (positions), 188228060Sbapt _index (0) 189228060Sbapt{ 190228060Sbapt} 191228060Sbapt 192228060Sbapt/* Initializes an iterator through POSITIONS, ignoring positions >= maxlen. */ 193228060SbaptINLINE 194228060SbaptPositionIterator::PositionIterator (Positions const& positions, int maxlen) 195228060Sbapt : _set (positions) 196228060Sbapt{ 197228060Sbapt if (positions._useall) 198228060Sbapt _index = (maxlen <= Positions::MAX_KEY_POS ? Positions::MAX_KEY_POS - maxlen : 0); 199228060Sbapt else 200228060Sbapt { 201228060Sbapt unsigned int index; 202228060Sbapt for (index = 0; 203228060Sbapt index < positions._size && positions._positions[index] >= maxlen; 204228060Sbapt index++) 205228060Sbapt ; 206228060Sbapt _index = index; 207228060Sbapt } 208228060Sbapt} 209228060Sbapt 210228060Sbapt/* Retrieves the next position, or EOS past the end. */ 211228060SbaptINLINE int 212228060SbaptPositionIterator::next () 213228060Sbapt{ 214228060Sbapt return (_index < _set._size ? _set._positions[_index++] : EOS); 215228060Sbapt} 216228060Sbapt 217228060Sbapt/* Returns the number of remaining positions, i.e. how often next() will 218228060Sbapt return a value != EOS. */ 219228060SbaptINLINE unsigned int 220228060SbaptPositionIterator::remaining () const 221228060Sbapt{ 222228060Sbapt return _set._size - _index; 223228060Sbapt} 224228060Sbapt 225228060Sbapt/* Copy constructor. */ 226228060SbaptINLINE 227228060SbaptPositionIterator::PositionIterator (const PositionIterator& src) 228228060Sbapt : _set (src._set), 229228060Sbapt _index (src._index) 230228060Sbapt{ 231228060Sbapt} 232228060Sbapt 233228060Sbapt/* --------------------- Class PositionReverseIterator --------------------- */ 234228060Sbapt 235228060Sbapt/* Initializes an iterator through POSITIONS. */ 236228060SbaptINLINE 237228060SbaptPositionReverseIterator::PositionReverseIterator (Positions const& positions) 238228060Sbapt : _set (positions), 239228060Sbapt _index (_set._size), 240228060Sbapt _minindex (0) 241228060Sbapt{ 242228060Sbapt} 243228060Sbapt 244228060Sbapt/* Initializes an iterator through POSITIONS, ignoring positions >= maxlen. */ 245228060SbaptINLINE 246228060SbaptPositionReverseIterator::PositionReverseIterator (Positions const& positions, int maxlen) 247228060Sbapt : _set (positions), 248228060Sbapt _index (_set._size) 249228060Sbapt{ 250228060Sbapt if (positions._useall) 251228060Sbapt _minindex = (maxlen <= Positions::MAX_KEY_POS ? Positions::MAX_KEY_POS - maxlen : 0); 252228060Sbapt else 253228060Sbapt { 254228060Sbapt unsigned int index; 255228060Sbapt for (index = 0; 256228060Sbapt index < positions._size && positions._positions[index] >= maxlen; 257228060Sbapt index++) 258228060Sbapt ; 259228060Sbapt _minindex = index; 260228060Sbapt } 261228060Sbapt} 262228060Sbapt 263228060Sbapt/* Retrieves the next position, or EOS past the end. */ 264228060SbaptINLINE int 265228060SbaptPositionReverseIterator::next () 266228060Sbapt{ 267228060Sbapt return (_index > _minindex ? _set._positions[--_index] : EOS); 268228060Sbapt} 269228060Sbapt 270228060Sbapt/* Returns the number of remaining positions, i.e. how often next() will 271228060Sbapt return a value != EOS. */ 272228060SbaptINLINE unsigned int 273228060SbaptPositionReverseIterator::remaining () const 274228060Sbapt{ 275228060Sbapt return _index - _minindex; 276228060Sbapt} 277228060Sbapt 278228060Sbapt/* Copy constructor. */ 279228060SbaptINLINE 280228060SbaptPositionReverseIterator::PositionReverseIterator (const PositionReverseIterator& src) 281228060Sbapt : _set (src._set), 282228060Sbapt _index (src._index), 283228060Sbapt _minindex (src._minindex) 284228060Sbapt{ 285228060Sbapt} 286