contrib/gperf/src/positions.icc

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