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

Text File | 1992-06-07 | 5.4 KB | 206 lines

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

/*
 * Parameterized sorted vector.  Inserts values using an insertion sort.
 *
 * $Header:   E:/vcs/rw/tvsrtvec.h_v   1.3   17 Mar 1992 11:30:26   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 according
 * to an ordering determined by the less-than (<) operator.
 *
 * 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&));
 *   - well-defined less-than 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.
 *
 * This class uses binary searches for efficient value-based retrievals.
 *
 ***************************************************************************
 *
 * $Log:   E:/vcs/rw/tvsrtvec.h_v  $
 *
 *    Rev 1.3   17 Mar 1992 11:30:26   KEFFER
 *
 *    Rev 1.2   11 Mar 1992 15:23:44   KEFFER
 *
 *    Rev 1.0   02 Mar 1992 16:10:54   KEFFER
 * Initial revision.
 */

//$DECLARE_TEMPLATE

#include "rw/tvvector.h"
#include "rw/tbsearch.h"

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

  typedef RWTValVector<T>    BASE;

protected:

  unsigned        _nitems;    // Number of items in the collection

public:

  RWTValSortedVector(unsigned capac = RWDEFAULT_CAPACITY);

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

  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);
  RWBoolean        isEmpty() const        {return _nitems==0;}
  T            last() const        {return (*this)(_nitems-1);}
  unsigned        length() const        {return _nitems;}
  unsigned        occurrencesOf(T) const;
  RWBoolean        remove(T);
  unsigned        removeAll(T);
  T            removeAt(int);
  T            removeFirst()        {return removeAt(0);}
  T            removeLast()        {return (*this)(--_nitems);}
  void            resize(unsigned newCapacity);
};



//$IMPLEMENT_TEMPLATE

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

template <class T> RWBoolean
RWTValSortedVector<T>::find(T a, T& ret) const
{
  int idx = index(a);
  if (idx>=0) {
    ret = (*this)(idx);
    return TRUE;
  }
  return FALSE;
}

template <class T> int
RWTValSortedVector<T>::index(T item) const
{
  int idx = RWTbsearch(item, data(), _nitems);
  if (idx>=_nitems || !(item==(*this)(idx))) idx = -1;
  return idx;                                            \
}

template <class T> void
RWTValSortedVector<T>::insert(T item)
{
  int idx = RWTbsearch(item, data(), _nitems);

  /* If duplicates are present, search for the last one: */
  while (idx<_nitems && item==(*this)(idx)) ++idx;

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

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

  (*this)(idx) = item;
  _nitems++;
}

template <class T> unsigned
RWTValSortedVector<T>::occurrencesOf(T val) const
{
  // Do a binary search to find the first match:
  int istart = index(val);
  if (istart == -1) return 0;

  // Now do a linear search, looking for the last match:
  int i = istart+1;
  while ( i<_nitems && (*this)(i)==val) ++i;

  return i-istart;
}

template <class T> RWBoolean
RWTValSortedVector<T>::remove(T val)
{
  int idx = index(val);
  if (idx==-1) return FALSE;
  removeAt(idx);
  return TRUE;
}

template <class T> unsigned
RWTValSortedVector<T>::removeAll(T val)
{
  // Do a binary search to find the first match:
  int istart = index(val);
  if (istart == -1) return 0;

  // Now do a linear search, looking for the last match:
  int i = istart+1;
  while ( i<_nitems && (*this)(i)==val) ++i;

  unsigned nremoved = i-istart;

  // Do a "solid body" slide left of the remaining items in the collection:
  while (i<_nitems)
    (*this)(istart++) = (*this)(i++);

  _nitems -= nremoved;
  return nremoved;
}

template <class T> T
RWTValSortedVector<T>::removeAt(int ipt)
{
  RWPRECONDITION(("RWTValSortedVector::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
RWTValSortedVector<T>::resize(unsigned N)
{ if(N>_nitems) reshape(N); }

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