Liren Large Software Subsidy 7/07.iso/c/c221/6.ddi/MWHC.006/Q2

Text File | 1992-06-07 | 5.2 KB | 197 lines

#ifndef __RWTVORDVEC_H__
#define __RWTVORDVEC_H__
pragma push_align_members(64);

/*
 * Parameterized ordered vector.  Items ordered by order of insertion.
 *
 * $Header:   E:/vcs/rw/tvordvec.h_v   1.3   11 Mar 1992 15:23:40   KEFFER  $
 *
 ****************************************************************************
 *
 * Rogue Wave Software, Inc.
 * P.O. Box 2328
 * Corvallis, OR 97339
 *
 * Copyright (C) 1992. This software is subject to copyright
 * protection under the laws of the United States and other countries.
 *
 ***************************************************************************
 *
 * Stores a *copy* of the inserted item into the collection.
 *
 * Assumes that T has:
 *   - well-defined copy semantics (T::T(const T&) or equiv.);
 *   - well-defined assignment semantics (T::operator=(const T&) or equiv.);
 *   - well-defined equality semantics (T::operator==(const T&)).
 *
 * Note that while these are automatically defined for builtin types
 * (such as "int", "double", or any pointer), you may need to provide
 * appropriate operators for your own classes, particularly those with
 * constructors and/or pointers to other objects.
 *
 ***************************************************************************
 *
 * $Log:   E:/vcs/rw/tvordvec.h_v  $
 *
 *    Rev 1.3   11 Mar 1992 15:23:40   KEFFER
 *
 *    Rev 1.0   02 Mar 1992 16:10:54   KEFFER
 * Initial revision.
 */

//$DECLARE_TEMPLATE

#include "rw/tvvector.h"

template <class T> class RWTValOrderedVector : private RWTValVector<T> {

  typedef RWTValVector<T>    BASE;

protected:

  unsigned        _nitems;    // Number of items in the collection

public:

  RWTValOrderedVector(unsigned capac=RWDEFAULT_CAPACITY);

  BASE::operator[];
  BASE::operator();

  // Member functions:
  void            append(T val)        {insertAt(_nitems,val);}
  T&            at(int i)        {return (*this)[i];}
  T            at(int i) const        {return (*this)[i];}
  void            clear()            {_nitems=0; reshape(RWDEFAULT_CAPACITY);}
  RWBoolean        contains(T a) const    {return index(a) != -1;}
  BASE::data;
  unsigned        entries() const        {return _nitems;}
  RWBoolean        find(T a,T& ret) const;    // Find first occurrence
  T            first() const        {return (*this)(0);}
  int            index(T) const;
  void            insert(T val)        {insertAt(_nitems,val);}
  void            insertAt(int, T);
  RWBoolean        isEmpty() const        {return _nitems==0;}
  T            last() const        {return (*this)(_nitems-1);}
  unsigned        length() const        {return _nitems;}
  unsigned        occurrencesOf(T) const;
  void            prepend(T val)        {insertAt(0, val);}
  RWBoolean        remove(T);        // Remove first occurrence
  unsigned        removeAll(T);
  T            removeAt(int);
  T            removeFirst()        {return removeAt(0);}
  T            removeLast()        {return (*this)(--_nitems);}
  void            resize(unsigned);    // Cannot shrink below population

};

//$IMPLEMENT_TEMPLATE

template <class T>
RWTValOrderedVector<T>::RWTValOrderedVector(unsigned capac) :
  _nitems(0),
  RWTValVector<T>(capac)
{
}

template <class T> RWBoolean
RWTValOrderedVector<T>::find(T val, T& retVal) const
{
  int idx = index(val);
  return idx == -1 ? FALSE : ( retVal = _array[idx], TRUE);
}

template <class T> int
RWTValOrderedVector<T>::index(T val) const
{
  for (register i=0; i<(int)_nitems; i++)
    if ((*this)(i)==val) return i;
  return -1;
}

// Insert value at position "ipt"; value formerly at "ipt"
// gets moved to "ipt+1".
template <class T> void
RWTValOrderedVector<T>::insertAt(int ipt, T val)
{
  RWPRECONDITION(("RWTValOrderedVector::insertAfter(int,T): index out of range", ipt>=0 && ipt<=(int)_nitems));

  // Check for overflow:
  if(_nitems>=BASE::length())
    reshape(_nitems + RWDEFAULT_RESIZE);

  // Slide right (could be very expensive)
  for(register i=(int)_nitems; i>ipt; i--)
    (*this)(i) = (*this)(i-1);

  _nitems++;
  (*this)(ipt) = val;
}

template <class T> unsigned
RWTValOrderedVector<T>::occurrencesOf(T val) const
{
  unsigned count = 0;
  for (register i=0; i<(int)_nitems; i++)
    if ((*this)(i)==val) ++count;
  return count;
}

/*
 * Remove first occurrence of the value.
 */
template <class T> RWBoolean
RWTValOrderedVector<T>::remove(T val)
{
  int idx = index(val);
  if (idx==-1) return FALSE;
  removeAt(idx);
  return TRUE;
}

/*
 * Remove all occurrences of the value
 */
template <class T> unsigned
RWTValOrderedVector<T>::removeAll(T val)
{
  int j = 0;
  for (register i=0; i<(int)_nitems; i++) {
    // Are they unequal?  If so, this value should be saved.
    if (!((*this)(i)==val)) {
      // Avoid the copy if possible:
      if (i!=j) (*this)(j) = (*this)(i);
      ++j;
    }
  }

  int nremoved = _nitems-j;
  _nitems -= nremoved;
  return nremoved;
}

template <class T> T
RWTValOrderedVector<T>::removeAt(int ipt)
{
  RWPRECONDITION(("RWTValOrderedVector::removeAt(int,T): index out of range", ipt>=-1 && ipt<(int)_nitems));

  T temp = (*this)(ipt);

  // Slide left (could be very expensive):
  for(register i=ipt; i<_nitems-1; i++)
    (*this)(i) = (*this)(i+1);

  _nitems--;
  return temp;
}

template <class T> void
RWTValOrderedVector<T>::resize(unsigned N)
{
  if (N>=_nitems) reshape(N);
}

pragma pop_align_members();
#endif    /* __RWTVORDVEC_H__ */