home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / ARRAYS.H < prev    next >
C/C++ Source or Header  |  1996-07-08  |  15KB  |  493 lines
  1. /****************************************************************************
  2.     $Id: arrays.h 501.0 1995/03/07 12:26:40 RON Exp $
  3.  
  4.     Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
  5.  
  6.     Project:    Tarma Library for C++ V5.0
  7.     Author:    Ron van der Wal
  8.  
  9.     Declarations of collection templates based on vectors:
  10.  
  11.     TLVBase<T>    - template for vector base class
  12.     TLVector<T>    - template for 0-based vectors of type T
  13.     TLArray<T>    - template for arrays of type T
  14.     TLSeqBase<T>- template for sequence-like collections
  15.     TLSeq<T>     - template for vector-based sequences of type T
  16.     TLQueue<T>    - template for vector-based queues of type T
  17.     TLStack<T>    - template for vector-based stacks of type T
  18.  
  19.     $Log: arrays.h $
  20.     Revision 501.0  1995/03/07 12:26:40  RON
  21.     Updated for TLX 5.01
  22.     Revision 1.9  1995/01/31 16:29:14  RON
  23.     Update for release 012
  24.     Added partial support for SunPro C++ compiler
  25.     Revision 1.8  1994/11/16  15:19:04  ron
  26.     Added lint directive
  27.  
  28.     Revision 1.7  1994/10/07  17:07:14  ron
  29.     Added Array<T>::SetLimits()
  30.  
  31.     Revision 1.6  1994/09/28  14:24:56  ron
  32.     Removed Macintosh-style #include references
  33.  
  34.     Revision 1.5  1994/09/27  20:24:46  ron
  35.     Changed path separator from / to \
  36.  
  37.     Revision 1.4  1994/09/26  15:14:10  ron
  38.     Moved inline functions to bottom of the file
  39.  
  40.     Revision 1.3  1994/09/12  14:49:14  ron
  41.     Small formatting changes
  42.  
  43.     Revision 1.2  1994/09/06  13:57:14  ron
  44.     Adapted to changes in tlx.h
  45.  
  46.     Revision 1.1  1994/08/16  18:06:43  ron
  47.     Initial revision
  48.  
  49. ****************************************************************************/
  50.  
  51. #ifndef _TLX_ARRAYS_H
  52. #define _TLX_ARRAYS_H
  53.  
  54. //-----    System headers
  55.  
  56. #include <stdarg.h>
  57.  
  58. //-----    Library headers
  59.  
  60. #ifndef _TLX_TLX_H
  61. #include <tlx\501\tlx.h>
  62. #endif
  63.  
  64. class _RTLCLASS ostream;    // In iostream.h
  65.  
  66. /*----------------------------------------------------------------------------
  67.     TLVBase<T> -
  68.  
  69.     Base class template for all vector-like collections
  70. *----------------------------------------------------------------------------*/
  71.  
  72. template<class T> class TLVBase
  73. {
  74. public:
  75.     //lint -esym(578,tCompareFunc,tOutputFunc)
  76.     typedef int     (*tCompareFunc)(const T &, const T &);
  77.     typedef void     (*tOutputFunc)(ostream &, const T &);
  78.  
  79.     static int        DefaultCompare(const T &, const T &);
  80.     static void        DefaultOutput(ostream &, const T &);
  81.  
  82. protected:
  83.     T *            mVect;        // TLVector of T
  84.     size_t         mSize;        // TLVector size
  85.     tCompareFunc     mCompare;       // Element comparison
  86.     tOutputFunc     mOutF;        // Element output
  87.  
  88. public:
  89.   #if defined (__BORLANDC__) //&& defined (__OS2__)
  90.     // Borland C++ for OS/2 bug fix
  91.     static char *    sPre;        // TLVector prefix for print()
  92.     static char *    sPreSep;    // Element prefix for print()
  93.     static char *    sPostSep;    // Element postfix for print()
  94.     static char *    sPost;        // TLVector postfix for print()
  95.   #elif defined(__SC__)
  96.     // Symantec C++ bug fix -- members are global
  97.   #else
  98.     static const char *    sPre;        // TLVector prefix for print()
  99.     static const char *    sPreSep;    // Element prefix for print()
  100.     static const char *    sPostSep;    // Element postfix for print()
  101.     static const char *    sPost;        // TLVector postfix for print()
  102.   #endif
  103.  
  104. public:
  105.     // Indexed access to vector items, either by index or by iterator
  106.  
  107.     T &            operator [](index_t);
  108.     const T &        operator [](index_t) const;
  109.     T &            operator [](iter_t i) { return mVect[i.ix]; }
  110.     const T &        operator [](iter_t i) const { return mVect[i.ix]; }
  111.  
  112.     // Index boundaries
  113.  
  114.     virtual index_t     Mini() const { return 0; }
  115.     virtual index_t     Maxi() const { return mSize - 1; }
  116.     bool          IsValidIndex(index_t) const;
  117.  
  118.     // TLVBase size information
  119.  
  120.     static size_t     MaxSize() { return kMaxAlloc / sizeof(T); }
  121.     size_t         Size() const { return mSize; }
  122.     virtual size_t     Count() const { return mSize; }
  123.  
  124.     // TLVBase class invariant
  125.  
  126.     virtual bool      OK() const;
  127.  
  128.     // Membership tests, perform a linear search
  129.  
  130.     int            Compare(const TLVBase<T> &) const;
  131.     bool          Contains(const T &) const;
  132.     virtual index_t     IndexOf(const T &) const;
  133.  
  134.     // Filling the vector up to its current size
  135.  
  136.     virtual void     Fill(const T &);
  137.  
  138.     // Printing a vector
  139.  
  140.     virtual ostream &     PrintOn(ostream &) const;
  141.  
  142.     // Built-in iteration
  143.  
  144.     void __cdecl    DoAll(void (*)(T &, va_list), ...);
  145.     void __cdecl    DoAll(void (*)(const T &, va_list), ...) const;
  146.     index_t __cdecl    DoWhile(bool (*)(T &, va_list), ...);
  147.     index_t __cdecl    DoWhile(bool (*)(const T &, va_list), ...) const;
  148.     index_t __cdecl    DoUntil(bool (*)(T &, va_list), ...);
  149.     index_t __cdecl    DoUntil(bool (*)(const T &, va_list), ...) const;
  150.  
  151.     // External iterators
  152.  
  153.     virtual bool      IterFirst(iter_t &) const;
  154.     virtual bool      IterLast(iter_t &) const;
  155.     virtual bool      IterNext(iter_t &) const;
  156.     virtual bool      IterPrev(iter_t &) const;
  157.  
  158.     // Element comparison and output functions
  159.  
  160.     tCompareFunc     GetCompare() const { return mCompare; }
  161.     tCompareFunc     SetCompare(tCompareFunc f)
  162.                 {
  163.                 tCompareFunc oldf = mCompare;
  164.                 if (f) mCompare = f;
  165.                 return oldf;
  166.                 }
  167.     tOutputFunc     GetOutput() const { return mOutF; }
  168.     tOutputFunc     SetOutput(tOutputFunc f)
  169.                 {
  170.                       tOutputFunc oldf = mOutF;
  171.                 if (f) mOutF = f;
  172.                 return oldf;
  173.                 }
  174.  
  175.     friend int         operator ==(const TLVBase<T> &v1, const TLVBase<T> &v2)
  176.                 { return v1.Compare(v2) == 0; }
  177.     friend int         operator !=(const TLVBase<T> &v1, const TLVBase<T> &v2)
  178.                 { return v1.Compare(v2) != 0; }
  179.     friend int         operator < (const TLVBase<T> &v1, const TLVBase<T> &v2)
  180.                 { return v1.Compare(v2) < 0; }
  181.     friend int         operator <=(const TLVBase<T> &v1, const TLVBase<T> &v2)
  182.                 { return v1.Compare(v2) <= 0; }
  183.     friend int         operator > (const TLVBase<T> &v1, const TLVBase<T> &v2)
  184.                 { return v1.Compare(v2) > 0; }
  185.     friend int         operator >=(const TLVBase<T> &v1, const TLVBase<T> &v2)
  186.                 { return v1.Compare(v2) >= 0; }
  187.     friend ostream &    operator <<(ostream &os, const TLVBase<T> &v)
  188.                 { return v.PrintOn(os); }
  189.  
  190. //protected:
  191.     // Constructors and destructor
  192.  
  193.     TLVBase(size_t = 0);
  194.     TLVBase(const T &);
  195.     TLVBase(const T *, size_t);
  196.     TLVBase(const TLVBase<T> &);
  197.     virtual ~TLVBase();
  198.  
  199. protected:
  200.     // Assignment operators
  201.  
  202.     TLVBase<T> &    operator =(const T &);
  203.     TLVBase<T> &    operator =(const TLVBase<T> &);
  204.  
  205.     // Resize operations
  206.  
  207.     void         ExpandBy(size_t);
  208.     void         ShrinkBy(size_t);
  209.     void         Resize(size_t);
  210.  
  211.     virtual index_t     MapIndex(index_t i) const { return i; }
  212.     virtual index_t     UnmapIndex(index_t i) const { return i; }
  213.  
  214.     void        AssertIndex(index_t) const;
  215.  
  216. private:
  217.     void         Duplicate(const T *, size_t);
  218. };
  219.  
  220. #if defined(__SC__)
  221.     // Symantec C++ bug fix -- members are global
  222.     extern const char *    sPre;        // TLVector prefix for print()
  223.     extern const char *    sPreSep;    // Element prefix for print()
  224.     extern const char *    sPostSep;    // Element postfix for print()
  225.     extern const char *    sPost;        // TLVector postfix for print()
  226. #endif
  227.  
  228. /*---------------------------------------------------------------------------
  229.     TLVector<T>
  230. ---------------------------------------------------------------------------*/
  231.  
  232. template<class T> class TLVector: public TLVBase<T>
  233. {
  234. public:
  235.     TLVector(size_t = 0);
  236.     TLVector(const T &);
  237.     TLVector(const T *, size_t);
  238.  
  239.     // Assignment operators
  240.     TLVector<T> &    operator =(const TLVector<T> &t);
  241.  
  242.     T &            PeekAt(index_t i) { return mVect[i]; }
  243.     const T &        PeekAt(index_t i) const { return mVect[i]; }
  244.  
  245.     void         ExpandBy(size_t sz) { TLVBase<T>::ExpandBy(sz); }
  246.     void         ShrinkBy(size_t sz) { TLVBase<T>::ShrinkBy(sz); }
  247.     void         Resize(size_t sz) { TLVBase<T>::Resize(sz); }
  248. };
  249.  
  250. /*---------------------------------------------------------------------------
  251.     TLArray<T>
  252. ---------------------------------------------------------------------------*/
  253.  
  254. template<class T> class TLArray: public TLVBase<T>
  255. {
  256.     int         mLower;     // Index base
  257.  
  258. public:
  259.     TLArray(size_t = 0);
  260.     TLArray(index_t, index_t);
  261.     TLArray(const T &);
  262.     TLArray(const T *, size_t);
  263.  
  264.     TLArray<T> &    operator =(const TLArray<T> &);
  265.  
  266.     T &            PeekAt(index_t i) { return mVect[i - mLower]; }
  267.     const T &        PeekAt(index_t i) const { return mVect[i - mLower]; }
  268.  
  269.     void         ExpandBy(size_t sz) { TLVBase<T>::ExpandBy(sz); }
  270.     void         ShrinkBy(size_t sz) { TLVBase<T>::ShrinkBy(sz); }
  271.     void         Resize(size_t sz) { TLVBase<T>::Resize(sz); }
  272.  
  273.     // Index bounds
  274.  
  275.     virtual index_t     Maxi() const { return mLower + Size() - 1; }
  276.     virtual index_t     Mini() const { return mLower; }
  277.     index_t         SetMini(index_t);
  278.     void        SetLimits(index_t, index_t);
  279.  
  280. protected:
  281.     virtual index_t     MapIndex(index_t i) const { return i - mLower; }
  282.     virtual index_t     UnmapIndex(index_t i) const { return i + mLower; }
  283. };
  284.  
  285. /*---------------------------------------------------------------------------
  286.     TLSeqBase<T>
  287. ---------------------------------------------------------------------------*/
  288.  
  289. template<class T> class TLSeqBase: public TLVBase<T>
  290. {
  291. protected:
  292.     size_t         mCount;
  293.     size_t         mDelta;
  294.  
  295. public:
  296.     TLSeqBase<T> &    operator =(const TLSeqBase<T> &);
  297.  
  298.     size_t         Count() const { return mCount; }
  299.     size_t         Available() const { return mSize - mCount; }
  300.     virtual void    RemoveAll() { mCount = 0; }
  301.     bool          IsEmpty() const { return mCount == 0; }
  302.     bool          IsFull() const { return mCount == mSize; }
  303.     bool          IsFlexible() const { return mDelta > 0; }
  304.     size_t         SetDelta(size_t);
  305.     void         Freeze() { mDelta = 0; }
  306.  
  307.     virtual index_t     Mini() const { return 1; }
  308.     virtual index_t     Maxi() const { return mCount; }
  309.  
  310.     // Class invariant
  311.  
  312.     virtual bool      OK() const { return 1; }
  313.  
  314. protected:
  315.     TLSeqBase(size_t = 0, size_t = 0);
  316.     TLSeqBase(const T &);
  317.     TLSeqBase(const T *, size_t);
  318.  
  319.     virtual void     Expand();
  320.     virtual void     CompactStorage();
  321.     virtual index_t     MapIndex(index_t i) const { return i - 1; }
  322.     virtual index_t     UnmapIndex(index_t i) const { return i + 1; }
  323.  
  324.     void        AssertNonEmpty() const;
  325.     void        AssertNonFull();
  326. };
  327.  
  328. /*---------------------------------------------------------------------------
  329.     TLSeq<T>
  330. ---------------------------------------------------------------------------*/
  331.  
  332. template<class T> class TLSeq: public TLSeqBase<T>
  333. {
  334.     index_t        mLower;        // Index base
  335.  
  336. public:
  337.     TLSeq(size_t = 0, size_t = 0);
  338.     TLSeq(const T &);
  339.     TLSeq(const T *, size_t);
  340.  
  341.     // Assignment operators
  342.  
  343.     TLSeq<T> &        operator =(const T &);
  344.     TLSeq<T> &        operator =(const TLSeq<T> &);
  345.     TLSeq<T> &        operator +=(const T &t) { Append(t); return *this; }
  346.     TLSeq<T> &        operator +=(const TLSeq<T> &s) { Append(s); return *this; }
  347.     TLSeq<T> &        operator -=(const T &t) { Extract(t); return *this; }
  348.  
  349.     // Additions of new items
  350.  
  351.     void         Append(const T &t) { InsertAt(mCount + 1, t); }
  352.     void         Append(const T &, const T &);
  353.     void         Append(const TLSeq<T> &);
  354.     void         Prepend(const T &t) { InsertAt(1, t); }
  355.     void         Prepend(const T &, const T &);
  356.     void         Prepend(const TLSeq<T> &);
  357.     void         Insert(const T &);
  358.     void         InsertAt(index_t, const T &);
  359.  
  360.     // Removal of items
  361.  
  362.     T             Extract(const T &);
  363.     T             ExtractAt(index_t);
  364.     T             ExtractFirst();
  365.     T             ExtractLast();
  366.     void        Remove(const T &);
  367.     void        RemoveAt(index_t);
  368.     void        RemoveFirst();
  369.     void        RemoveLast();
  370.  
  371.     // Access to items in the sequence
  372.  
  373.     T &            PeekFirst();
  374.     const T &        PeekFirst() const;
  375.     T &            PeekLast();
  376.     const T &        PeekLast() const;
  377.     T &            PeekValue(const T &);
  378.     const T &        PeekValue(const T &) const;
  379.     T &            PeekAt(index_t);
  380.     const T &        PeekAt(index_t) const;
  381.  
  382.     // Membership tests
  383.  
  384.     index_t         Search(const T &) const;
  385.     void         Sort();
  386.  
  387.     virtual bool      IterFirst(iter_t &) const;
  388.     virtual bool      IterLast(iter_t &) const;
  389.     virtual bool      IterNext(iter_t &) const;
  390.     virtual bool      IterPrev(iter_t &) const;
  391.  
  392.     virtual index_t     Mini() const { return 1; }
  393.     virtual index_t     Maxi() const { return mCount; }
  394.  
  395.     void        Reserve(size_t aSize) { Resize(aSize); mCount = aSize; }
  396. private:
  397.     bool          FindInsertPos(const T &, index_t &) const;
  398.     index_t        QPart(index_t, index_t);
  399.     void        QSort(index_t, index_t);
  400. };
  401.  
  402. /*---------------------------------------------------------------------------
  403.     TLQueue<T>
  404. ---------------------------------------------------------------------------*/
  405.  
  406. template<class T> class TLQueue: public TLSeqBase<T>
  407. {
  408.     index_t         mLeft, mRight;
  409.  
  410. public:
  411.     TLQueue(size_t = 0, size_t = 0);
  412.     TLQueue(const T &);
  413.  
  414.     // Assignment operators
  415.     TLQueue<T> &    operator =(const T &);
  416.     TLQueue<T> &    operator =(const TLQueue<T> &);
  417.  
  418.     void         RemoveAll();
  419.  
  420.     // Single-ended queue operations
  421.  
  422.     void         EnqueueUnique(const T &);
  423.     void         Enqueue(const T &t) { AddRight(t); }
  424.     T             Dequeue() { return ExtractLeft(); }
  425.     void        RemoveHead() { RemoveLeft(); }
  426.     T &            PeekHead() { return PeekLeft(); }
  427.     const T &        PeekHead() const { return PeekLeft(); }
  428.     T &            PeekTail() { return PeekRight(); }
  429.     const T &        PeekTail() const { return PeekRight(); }
  430.  
  431.     // Double-ended queue operations
  432.  
  433.     void         AddLeft(const T &);
  434.     void         AddRight(const T &);
  435.     T             ExtractLeft();
  436.     T             ExtractRight();
  437.     void        RemoveLeft();
  438.     void        RemoveRight();
  439.     T &            PeekLeft();
  440.     const T &        PeekLeft() const;
  441.     T &            PeekRight();
  442.     const T &        PeekRight() const;
  443.  
  444.     // Class invariant
  445.  
  446.     virtual bool      OK() const;
  447.  
  448.     virtual bool      IterFirst(iter_t &) const;
  449.     virtual bool      IterLast(iter_t &) const;
  450.     virtual bool      IterNext(iter_t &) const;
  451.     virtual bool      IterPrev(iter_t &) const;
  452.  
  453. protected:
  454.     void         Expand();
  455.     void         CompactStorage();
  456.     virtual index_t     MapIndex(index_t) const;
  457.     virtual index_t     UnmapIndex(index_t) const;
  458. };
  459.  
  460. /*---------------------------------------------------------------------------
  461.     TLStack<T>
  462. ---------------------------------------------------------------------------*/
  463.  
  464. template<class T> class TLStack: public TLSeqBase<T>
  465. {
  466. public:
  467.     TLStack(size_t = 0, size_t = 0);
  468.     TLStack(const T &);
  469.  
  470.     // Assignment operators
  471.  
  472.     TLStack<T> &    operator =(const T &);
  473.     TLStack<T> &    operator =(const TLStack<T> &);
  474.  
  475.     // Adding and removing items
  476.  
  477.     void         Push(const T &);
  478.     T             Pop();
  479.     void        RemoveTop();
  480.  
  481.     // Access to stack items
  482.  
  483.     T &            PeekTop();
  484.     const T &        PeekTop() const;
  485.  
  486.     virtual bool      IterFirst(iter_t &) const;
  487.     virtual bool      IterLast(iter_t &) const;
  488.     virtual bool      IterNext(iter_t &) const;
  489.     virtual bool      IterPrev(iter_t &) const;
  490. };
  491.  
  492. #endif    // _TLX_ARRAYS_H
  493.