path: root/src/positions.icc

/* Inline Functions for positions.{h,cc}.

   Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc.
   Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
   and Bruno Haible <bruno@clisp.org>.

   This file is part of GNU GPERF.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

// This needs:
//#include <string.h>

/* ---------------------------- Class Positions ---------------------------- */

/* Constructors.  */

INLINE
Positions::Positions ()
  : _useall (false),
    _size (0)
{
}

INLINE
Positions::Positions (int pos1)
  : _useall (false),
    _size (1)
{
  _positions[0] = pos1;
}

INLINE
Positions::Positions (int pos1, int pos2)
  : _useall (false),
    _size (2)
{
  _positions[0] = pos1;
  _positions[1] = pos2;
}

/* Copy constructor.  */

INLINE
Positions::Positions (const Positions& src)
  : _useall (src._useall),
    _size (src._size)
{
  memcpy (_positions, src._positions, _size * sizeof (_positions[0]));
}

/* Assignment operator.  */

INLINE Positions&
Positions::operator= (const Positions& src)
{
  _useall = src._useall;
  _size = src._size;
  memcpy (_positions, src._positions, _size * sizeof (_positions[0]));
  return *this;
}

/* Accessors.  */

INLINE bool
Positions::is_useall () const
{
  return _useall;
}

INLINE int
Positions::operator[] (unsigned int index) const
{
  return _positions[index];
}

INLINE unsigned int
Positions::get_size () const
{
  return _size;
}

/* Write access.  */

INLINE void
Positions::set_useall (bool useall)
{
  _useall = useall;
  if (useall)
    {
      /* The positions are 0, 1, ..., MAX_KEY_POS-1, in descending order.  */
      _size = MAX_KEY_POS;
      int *ptr = _positions;
      for (int i = MAX_KEY_POS - 1; i >= 0; i--)
        *ptr++ = i;
    }
}

INLINE int *
Positions::pointer ()
{
  return _positions;
}

INLINE void
Positions::set_size (unsigned int size)
{
  _size = size;
}

/* Sorts the array in reverse order.
   Returns true if there are no duplicates, false otherwise.  */
INLINE bool
Positions::sort ()
{
  if (_useall)
    return true;

  /* Bubble sort.  */
  bool duplicate_free = true;
  int *base = _positions;
  unsigned int len = _size;

  for (unsigned int i = 1; i < len; i++)
    {
      unsigned int j;
      int tmp;

      for (j = i, tmp = base[j]; j > 0 && tmp >= base[j - 1]; j--)
        if ((base[j] = base[j - 1]) == tmp) /* oh no, a duplicate!!! */
          duplicate_free = false;

      base[j] = tmp;
    }

  return duplicate_free;
}

/* Creates an iterator, returning the positions in descending order.  */
INLINE PositionIterator
Positions::iterator () const
{
  return PositionIterator (*this);
}

/* Creates an iterator, returning the positions in descending order,
   that apply to strings of length <= maxlen.  */
INLINE PositionIterator
Positions::iterator (int maxlen) const
{
  return PositionIterator (*this, maxlen);
}

/* Creates an iterator, returning the positions in ascending order.  */
INLINE PositionReverseIterator
Positions::reviterator () const
{
  return PositionReverseIterator (*this);
}

/* Creates an iterator, returning the positions in ascending order,
   that apply to strings of length <= maxlen.  */
INLINE PositionReverseIterator
Positions::reviterator (int maxlen) const
{
  return PositionReverseIterator (*this, maxlen);
}

/* ------------------------- Class PositionIterator ------------------------ */

/* Initializes an iterator through POSITIONS.  */
INLINE
PositionIterator::PositionIterator (Positions const& positions)
  : _set (positions),
    _index (0)
{
}

/* Initializes an iterator through POSITIONS, ignoring positions >= maxlen.  */
INLINE
PositionIterator::PositionIterator (Positions const& positions, int maxlen)
  : _set (positions)
{
  if (positions._useall)
    _index = (maxlen <= Positions::MAX_KEY_POS ? Positions::MAX_KEY_POS - maxlen : 0);
  else
    {
      unsigned int index;
      for (index = 0;
           index < positions._size && positions._positions[index] >= maxlen;
           index++)
        ;
      _index = index;
    }
}

/* Retrieves the next position, or EOS past the end.  */
INLINE int
PositionIterator::next ()
{
  return (_index < _set._size ? _set._positions[_index++] : EOS);
}

/* Returns the number of remaining positions, i.e. how often next() will
   return a value != EOS.  */
INLINE unsigned int
PositionIterator::remaining () const
{
  return _set._size - _index;
}

/* Copy constructor.  */
INLINE
PositionIterator::PositionIterator (const PositionIterator& src)
  : _set (src._set),
    _index (src._index)
{
}

/* --------------------- Class PositionReverseIterator --------------------- */

/* Initializes an iterator through POSITIONS.  */
INLINE
PositionReverseIterator::PositionReverseIterator (Positions const& positions)
  : _set (positions),
    _index (_set._size),
    _minindex (0)
{
}

/* Initializes an iterator through POSITIONS, ignoring positions >= maxlen.  */
INLINE
PositionReverseIterator::PositionReverseIterator (Positions const& positions, int maxlen)
  : _set (positions),
    _index (_set._size)
{
  if (positions._useall)
    _minindex = (maxlen <= Positions::MAX_KEY_POS ? Positions::MAX_KEY_POS - maxlen : 0);
  else
    {
      unsigned int index;
      for (index = 0;
           index < positions._size && positions._positions[index] >= maxlen;
           index++)
        ;
      _minindex = index;
    }
}

/* Retrieves the next position, or EOS past the end.  */
INLINE int
PositionReverseIterator::next ()
{
  return (_index > _minindex ? _set._positions[--_index] : EOS);
}

/* Returns the number of remaining positions, i.e. how often next() will
   return a value != EOS.  */
INLINE unsigned int
PositionReverseIterator::remaining () const
{
  return _index - _minindex;
}

/* Copy constructor.  */
INLINE
PositionReverseIterator::PositionReverseIterator (const PositionReverseIterator& src)
  : _set (src._set),
    _index (src._index),
    _minindex (src._minindex)
{
}