home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / sequence.h < prev    next >
C/C++ Source or Header  |  1995-04-08  |  18KB  |  447 lines
  1.  
  2.  
  3. #ifndef _sequence_h_ /* Tue Dec 22 11:41:35 1992 */
  4. #define _sequence_h_
  5.  
  6.  
  7.  
  8.  
  9.  
  10. /*
  11.  *
  12.  *          Copyright (C) 1994, M. A. Sridhar
  13.  *  
  14.  *
  15.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  16.  *     to copy, modify or distribute this software  as you see fit,
  17.  *     and to use  it  for  any  purpose, provided   this copyright
  18.  *     notice and the following   disclaimer are included  with all
  19.  *     copies.
  20.  *
  21.  *                        DISCLAIMER
  22.  *
  23.  *     The author makes no warranties, either expressed or implied,
  24.  *     with respect  to  this  software, its  quality, performance,
  25.  *     merchantability, or fitness for any particular purpose. This
  26.  *     software is distributed  AS IS.  The  user of this  software
  27.  *     assumes all risks  as to its quality  and performance. In no
  28.  *     event shall the author be liable for any direct, indirect or
  29.  *     consequential damages, even if the  author has been  advised
  30.  *     as to the possibility of such damages.
  31.  *
  32.  */
  33.  
  34.  
  35.  
  36.  
  37. // A Sequence is a container object, representing a sequence whose elements
  38. // can be  accessed and modified  via the subscript  operator. In addition,
  39. // the Sequence container supports the  Add, Insert and Remove operations
  40. // that provide for  automatic growth  and shrinkage   of the  sequence  as
  41. // necessary, and the  InsertByRank method  for  insertion in sorted  order
  42. // assuming that the sequence is sorted.
  43. // 
  44. // The Sequence  object also provides Sort() as  well as LinearSearch() and
  45. // BinarySearch() methods for sorting and searching for elements.
  46. // 
  47. // The Sequence  is  a template  class,  and its base  type  is required to
  48. // support  the Compare method  as  well as a   copy constructor, a default
  49. // constructor (that takes no parameters) and an assignment operator.
  50. // 
  51. // Methods that modify the   sequence (i.e., Insert,  InsertByRank, Remove,
  52. // Add, Sort) will return  without modifying the sequence  if any of  the
  53. // pre-change dependents refuses permission. However, the sequence does not
  54. // check for modification of the    contained objects (those returned   via
  55. // {\tt operator[]}).
  56. //
  57. // When the Sequence is instantiated  as a container for pointers (as  are
  58. // {\small\tt CL_Sequence <CL_ObjectPtr>} or CL_ObjectSequence), the
  59. // sequence does {\it not\/} own the objects  that the pointers  point to,
  60. // and  therefore 
  61. // does not  delete them when  it is  destroyed.  The {\tt DestroyContents}
  62. // method  is provided  on  {\tt  CL_ObjectSequence}  to  provide  explicit
  63. // control over destruction of contents.
  64. //
  65. // The implementation uses a "segmented array" technique that allows
  66. // creating sequences with size up to $2^{26}$, or approximately 64 million,
  67. // even under MS-Windows, thus alleviating the 64K  limitation under
  68. // MS-Windows (provided, of course, there is enough main memory available).
  69.  
  70.  
  71.  
  72. #ifdef __GNUC__
  73. #pragma interface
  74. #endif
  75.  
  76. #include "base/iofilter.h"
  77.  
  78.  
  79. template <class T> class CL_Set;
  80. class CL_EXPORT CL_IntegerSet;
  81.  
  82.  
  83.  
  84. template <class BaseType>
  85. class CL_EXPORT  CL_Sequence: public CL_Object {
  86.  
  87. public:
  88.     //
  89.     // ------------------------ Creation and destruction --------------
  90.     //
  91.     CL_Sequence (long initial_size = 0, CL_ObjectIOFilter* builder = 0);
  92.     // Create a sequence with given size. The second parameter is used
  93.     // only if this is a sequence of pointers, and then only for restoring
  94.     // this sequence from a stream. If specified, the iofilter object must
  95.     // exist whenever the sequence needs to save or restore itself from a
  96.     // stream; the sequence does not take responsibility for the (memory
  97.     // used by the) iofilter object.
  98.  
  99.     CL_Sequence (const BaseType data[], long count,
  100.                  CL_ObjectIOFilter* builder = 0);
  101.     // Convenience constructor: create this sequence from a C-style array.
  102.     
  103.     CL_Sequence (const CL_Sequence<BaseType>& seq);
  104.     // Copy constructor. If the template parameter {\small\tt BaseType>}
  105.     // is a first-class object, the copy constructor of the {\small\tt
  106.     // BaseType} is used to copy each entry in the sequence; if it's a
  107.     // pointer, just the pointer is copied. Also, the iofilter pointer of
  108.     // the  parameter is copied into this object.
  109.  
  110.     ~CL_Sequence();
  111.     // Destructor.
  112.  
  113.  
  114.     //
  115.     // ------------------------ Element access ---------------------------
  116.  
  117.     long Size() const {return _size;};
  118.     // Return the number of elements in the sequence. This is an inline
  119.     // method that takes small constant time.
  120.  
  121.     virtual BaseType& operator[] (long i) const;
  122.     // Return the i-th element. The index i must be in the range 0
  123.     // to Size()-1; this is checked by the method, and a fatal error is
  124.     // caused if the index is out of range. The return value is
  125.     // a reference that may be modified by the caller.
  126.     //
  127.     // This method is implemented with merely two shift operations and two
  128.     // indexed accesses on the segmented sequence, so it is quite efficient.
  129.  
  130.     virtual bool Insert (const BaseType& o, long index = -1);
  131.     // Insert the given element into the sequence, immediately to the right of
  132.     // the given index, and expand the sequence size by 1. Return TRUE if
  133.     // successful, FALSE if failed for some reason (e.g. the index was
  134.     // less than -1 or greater than Size()-1). Specifying an index of
  135.     // -1 inserts the element at the left end of the sequence.
  136.     //
  137.     // The implementation performs {\small\tt Size() - index} pointer
  138.     // movements. These are pointer movements even when the {\small\tt
  139.     // BaseType} is a first-class object.
  140.  
  141.     virtual long InsertByRank (const BaseType& o);
  142.     // Insert the given object o into the sequence at the smallest position
  143.     // i such that all elements in the sequence between indices 0 and i-1
  144.     // are less than o, according to the Compare method on o. (Note that
  145.     // this formulation does not assume that the sequence is sorted,
  146.     // although InsertByRank maintains sorted order if it were.) Return the
  147.     // index i at which it was inserted, after increasing the size of the
  148.     // sequence by 1.
  149.     //    This method returns -1 if memory allocation failed or a
  150.     // pre-change dependent refused permission to change.
  151.     //
  152.     // The implementation performs {\small\tt Size() - index} pointer
  153.     // movements, where {\small\tt index} is the position at which the
  154.     // insertion occurs. These are pointer movements even when the {\small\tt
  155.     // BaseType} is a first-class object.
  156.     
  157.     virtual long Add (const BaseType& o);
  158.     // Append an element to the end of the sequence, expanding the sequence
  159.     // automatically if needed. Return the index at which the element
  160.     // was added.
  161.     //
  162.     // This method is very efficient (constant-time) in most cases; it
  163.     // needs extra time only when the size has to increase, and that
  164.     // happens very infrequently.
  165.  
  166.     virtual BaseType Remove (long i);
  167.     // Remove the i-th element of the sequence, and close the hole, so
  168.     // that all elements formerly at indices higher than i will now
  169.     // have their indices decremented by 1. Return the removed element,
  170.     // and return the null value of the BaseType if removal failed (e.g.,
  171.     // for an invalid index i).
  172.     //
  173.     // The implementation performs {\small\tt Size() - index} pointer
  174.     // movements. These are pointer movements even when the {\small\tt
  175.     // BaseType} is a first-class object.
  176.  
  177.     virtual BaseType ExtractLeftmost ();
  178.     // Remove and return the leftmost element of the sequence. Return the
  179.     // null value of the base type if failed (e.g. because the sequence is
  180.     // empty).
  181.     //
  182.     // The implementation performs {\small\tt Size()} pointer
  183.     // movements. These are pointer movements even when the {\small\tt
  184.     // BaseType} is a first-class object.
  185.  
  186.     virtual BaseType ExtractRightmost ();
  187.     // Remove and return the rightmost element of the sequence. Return the
  188.     // null value of the base type if failed.
  189.     //
  190.     // This method is very efficient (constant-time) in most cases; it
  191.     // needs extra time only when the size has to decrease, and that
  192.     // happens very infrequently.
  193.  
  194.  
  195.     virtual long LinearSearch (const BaseType& o) const;
  196.     // Do a linear search for the given object in the sequence. Return
  197.     // the index at which it was found, or -1 if not found.
  198.  
  199.     virtual bool BinarySearch (const BaseType& o, long& index) const;
  200.     // Assuming that the sequence is sorted, search for a given element,
  201.     // and return a boolean whether it was found. Return the index of
  202.     // the greatest element not exceeding the given element in the
  203.     // second parameter. This method performs a binary search for
  204.     // sequences larger than 7 elements, but does not check whether the
  205.     // sequence is sorted; so it must only be used on sequences that are
  206.     // known to be sorted. (See the {\small\tt Sort} method.)
  207.  
  208.     
  209.     
  210.     // ------------------- Sequence methods ------------------------
  211.  
  212.     virtual CL_Sequence<BaseType>& operator= (const CL_Sequence<BaseType>&);
  213.     // Assign to this sequence from the given sequence. If the template
  214.     // parameter {\small\tt BaseType>} 
  215.     // is a first-class object, the copy constructor of the {\small\tt
  216.     // BaseType} is used to copy each entry in the sequence; if it's a
  217.     // pointer, just the pointer is copied.
  218.  
  219.  
  220.     void operator= (const CL_Object& o);
  221.     // Check that the given object has the same class id as the sequence,
  222.     // and then perform a sequence assignment after casting down.
  223.     
  224.  
  225.     virtual CL_Sequence<BaseType>& operator+= (const CL_Sequence<BaseType>& s);
  226.     // Concatenate the given sequence onto the end of this sequence. If
  227.     // the template parameter {\small\tt BaseType>} 
  228.     // is a first-class object, the copy constructor of the {\small\tt
  229.     // BaseType} is used to copy each entry in the sequence {\small\tt s};
  230.     // if it's a pointer, just the pointer is copied.
  231.  
  232. #ifndef __GNUC__ // Temporarily disable these methods to work around
  233.                  // the GCC bug
  234.     virtual CL_Sequence<BaseType> Subsequence (const CL_IntegerSet& s)
  235.         const;
  236.     // Return the subsequence  of this sequence containing those
  237.     // elements whose positions are in the given set.
  238.         
  239.     virtual CL_Sequence<BaseType> operator- (const CL_IntegerSet& s) const;
  240.     // Return the sequence obtained by removing from this sequence those
  241.     // elements whose indices are in the given set. If the {\small\tt
  242.     // BaseType} of this sequence is a pointer,
  243.     // the pointers are copied into the returned
  244.     // sequence; if the {\small\tt BaseType} is a first-class objects, the copy
  245.     // constructor of the {\small\tt BaseType} is used to copy the objects
  246.     // into the returned sequence.
  247.  
  248.  
  249.     virtual void operator-= (const CL_IntegerSet& s);
  250.     // Remove from this sequence those elements whose indices are in the
  251.     // given set. The implementation uses no more than n = Size() pointer
  252.     // movements, regardless of how big s is.
  253.  
  254. #endif    // __GNUC__
  255.   
  256.     
  257.     
  258.     virtual bool ChangeSize (long new_size);
  259.     // Expand ourselves to the given size. If new_size is less than
  260.     // the current size, this operation truncates the sequence, i.e. the
  261.     // elements with higher indices are lost. If the new sequence is
  262.     // longer, the additional elements are initialized with the null value
  263.     // of the {\small\tt BaseType} (i.e., the NULL pointer for pointer
  264.     // types, and the value returned by the default constructor for
  265.     // first-class objects).
  266.     //    The method returns TRUE if successful, FALSE if no more memory.
  267.  
  268.     virtual void MakeEmpty ();
  269.     // Delete all contained objects, and set our size to 0. If this is a
  270.     // sequence of Object pointers, the contained objects are {\it not\/}
  271.     // deleted.
  272.  
  273.     virtual bool ShiftRightAt (long pos, long amount = 1);
  274.     // Shift all elements, beginning at position {\tt pos}, right by
  275.     // {\tt amount} cells; then set the cells {\tt pos} through {\tt
  276.     // pos+amount-1}  to
  277.     // the null value of the base type. The new sequence will have its size
  278.     // increased by {\tt amount}. The value {\tt pos} must be in the range 0 to
  279.     // {\tt Size()-1}.
  280.     //    This method returns TRUE on success, FALSE on failure (e.g., memory
  281.     // allocation failure).
  282.     //
  283.     // The implementation performs {\small\tt Size() - pos} pointer
  284.     // movements. These are pointer movements even when the {\small\tt
  285.     // BaseType} is a first-class object.
  286.     
  287.     virtual bool ShiftLeftAt (long pos, long amount = 1);
  288.     // Shift all elements, beginning at position "pos" upto our last
  289.     // element, left by "amount" cells; this causes the sequence to lose the
  290.     // elements that were at positions pos-amount through pos-1.
  291.     // The new sequence will have its size decreased by "amount".
  292.     //    Return TRUE on success, false on failure (e.g., memory
  293.     // allocation failure).
  294.     //
  295.     // The implementation performs {\small\tt Size() - pos} pointer
  296.     // movements. These are pointer movements even when the {\small\tt
  297.     // BaseType} is a first-class object.
  298.     
  299.  
  300.     bool Sort () {return Sort (0, Size());};
  301.     // Sort the elements into ascending order. Return FALSE if either the
  302.     // sequence was already sorted, memory allocation failed, or one of
  303.     // the pre-change dependents refused permission, and TRUE otherwise. The
  304.     // implementation forwards the call to the two-parameter version of {\tt
  305.     // Sort}.
  306.  
  307.     virtual bool Sort (long pos, long len);
  308.     // Sort the segment of the Sequence beginning at position {\tt pos},
  309.     // containing {\tt len} elements. The implementation uses 
  310.     // the _QuickSort method, and the latter uses the _Compare method for
  311.     // comparison.
  312.     
  313.     virtual bool IsSorted () const;
  314.     // Is this sequence sorted?
  315.  
  316.  
  317.     // -------------------- Storage and retrieval ---------------------
  318.  
  319.     long StorableFormWidth () const;
  320.     // Override the method inherited from {\small\tt CL_Object}.
  321.  
  322.     bool ReadFrom (const CL_Stream&);
  323.     // Override the method inherited from {\small\tt CL_Object}.
  324.  
  325.     bool WriteTo  (CL_Stream&) const;
  326.     // Override the method inherited from {\small\tt CL_Object}.
  327.  
  328.     
  329.     // -------------------- Basic methods --------------------
  330.  
  331.     CL_Object* Clone () const;
  332.     // Override the method inherited from {\small\tt CL_Object}.
  333.     
  334.     const char* ClassName() const {return "CL_Sequence";};
  335.     // Override the method inherited from {\small\tt CL_Object}.
  336.  
  337.     CL_ClassId ClassId() const { return _CL_Sequence_CLASSID;};
  338.     // Override the method inherited from {\small\tt CL_Object}.
  339.  
  340.  
  341.  
  342.     // -------------------- End public protocol ---------------------------
  343.  
  344.     
  345. protected:
  346.  
  347.     //
  348.     // Instance variables
  349.     //
  350.     void*              _idata;
  351.     long               _size;
  352.     CL_ObjectIOFilter* _builder;
  353.  
  354.     virtual bool       _QuickSort (long left, long right);
  355.     // Apply QuickSort on the  segment of the sequence beginning at {\tt
  356.     // left} and ending at {\tt right}. Return FALSE if this segment was
  357.     // already sorted, and TRUE otherwise. This method does not perform
  358.     // notification.
  359.  
  360.     virtual bool       _ReadElement (const CL_Stream& s, long i);
  361.     // Read the i-th element of the sequence from the stream. This method
  362.     // is used by {\tt ReadFrom}. The return value is TRUE if the
  363.     // operation succeeds, and FALSE otherwise. The default implementation
  364.     // simply calls {\tt CL_RestoreFrom} in {\tt basicops.h}.
  365.     
  366.     virtual bool       _WriteElement (CL_Stream& s, long i) const;
  367.     // Write the i-th element of the sequence to the stream. This method
  368.     // is used by {\tt WriteTo}. The return value is TRUE if the
  369.     // operation succeeds, and FALSE otherwise. The default implementation
  370.     // simply calls {\tt CL_SaveTo} in {\tt basicops.h}.
  371.     
  372.     virtual short      _Compare (const BaseType&, const BaseType&) const;
  373.     // Compare two objects. All comparisons needed by all methods in the
  374.     // Sequence are done by this method. The default implementation uses
  375.     // the CL_Basics<BaseType>::Compare function.
  376.     
  377.  
  378.  
  379. private:
  380.  
  381.     bool           _ShiftRightAt (long pos, long amount);
  382.     // Do the ShiftRight without notifying clients.
  383.  
  384.     bool          _ShiftLeftAt  (long pos, long amount);
  385.     // Do the ShiftLeft without notifying clients.
  386.  
  387.     short          _ChangeSize (long new_size);
  388.     // Do the ChangeSize without notifying clients.
  389.     
  390.     short          _DoInsert (const BaseType& o, long index);
  391.     // Do the Insert without notifying clients.
  392.  
  393.     void           _DoMakeEmpty ();
  394.     // Do the MakeEmpty without notifying clients.
  395.  
  396. };
  397.  
  398.  
  399.  
  400.  
  401. // A SequenceIterator iterates through a Sequence. It is used only to fit
  402. // into the framework of iterators, so that algorithms may be expressed
  403. // entirely in terms of iterators.
  404.  
  405. template <class ItemType>
  406. class CL_EXPORT CL_SequenceIterator: public CL_Iterator<ItemType> {
  407.  
  408. public:
  409.     CL_SequenceIterator (const CL_Sequence<ItemType>&);
  410.     // Constructor. The parameter specifies the sequence to be inspected.
  411.  
  412.     CL_SequenceIterator (const CL_SequenceIterator<BaseType>& itr);
  413.     // Copy constructor. The copy inspects the same sequence as {\tt itr}, and
  414.     // (unless reset) begins  its iteration at the same object that itr is
  415.     // currently positioned.
  416.     
  417.     virtual void Reset();
  418.  
  419.     virtual bool More();
  420.  
  421.     virtual const BaseType& Next();
  422.  
  423.     virtual const char* ClassName () const {return "CL_SequenceIterator";};
  424.     
  425.  
  426. protected:
  427.     const CL_Sequence<BaseType>& _sequence;
  428.     long                         _index;
  429.  
  430. };
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437. template <class BaseType>
  438. inline CL_Object* CL_Sequence<BaseType>::Clone () const
  439. {
  440.     return new CL_Sequence<BaseType> (*this);
  441. }
  442.  
  443.  
  444.  
  445. #endif  /* _sequence_h_ */
  446.  
  447.