include/AD/contain/sequence.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef applicative_sequence_h
  26 #define applicative_sequence_h
  27
  28 ////////////////////////////////////////////////////////////////////////////
  29 //  Class Sequence<T> allows the user to construct lists of a homogeneous
  30 //  type.  These lists are all applicative in nature and concatenation
  31 //  can be accomplished in O(1) time.   The lists are also symetric
  32 //  in nature and is not biased toward one end as is in the traditional
  33 //  representation.
  34 ////////////////////////////////////////////////////////////////////////////
  35
  36 #include <AD/generic/generic.h>
  37
  38 template <class T>
  39    class Sequence {
  40       struct SeqRep {
  41          int              ref_count;  // reference count
  42          int              len;        // length of the array
  43          const Sequence * left;       // left link
  44          const Sequence * right;      // right link
  45          const T        * array;      // array of elements
  46       };
  47
  48       SeqRep * list;            // pointer to actual representation
  49
  50    public:
  51
  52       /////////////////////////////////////////////////////////////
  53       // Constructor and destructor
  54       /////////////////////////////////////////////////////////////
  55       Sequence();
  56       Sequence(const Sequence&);
  57       Sequence(const T&);
  58       Sequence(const T[]);
  59      ~Sequence();
  60
  61       /////////////////////////////////////////////////////////////
  62       // Subsequence:
  63       /////////////////////////////////////////////////////////////
  64       Sequence operator () (int i, int j) const;
  65
  66       /////////////////////////////////////////////////////////////
  67       // Selectors
  68       /////////////////////////////////////////////////////////////
  69       const T& operator [] (int i) const;
  70       int      length() const;
  71
  72       /////////////////////////////////////////////////////////////
  73       // Concatenation
  74       /////////////////////////////////////////////////////////////
  75       friend Sequence operator + (const Sequence&, const Sequence&);
  76       friend Sequence operator + (const T&,        const Sequence&);
  77       friend Sequence operator + (const Sequence&, const T&);
  78       friend Sequence operator + (const T[],       const Sequence&);
  79       friend Sequence operator + (const Sequence&, const T[]);
  80    };
  81
  82 ///////////////////////////////////////////////////////////////////////
  83 //  Implementation of the template methods
  84 ///////////////////////////////////////////////////////////////////////
  85 template <class T>
  86    Sequence<T>::Sequence()
  87    {}
  88
  89 template <class T>
  90    Sequence<T>::Sequence(const Sequence<T>&)
  91    {}
  92
  93 template <class T>
  94    Sequence<T>::Sequence(const T&)
  95    {}
  96
  97 template <class T>
  98    Sequence<T>::Sequence(const T[])
  99    {}
 100
 101 template <class T>
 102    Sequence<T>::~Sequence()
 103    {}
 104
 105 template <class T>
 106    Sequence<T> operator + (const Sequence<T>&, const Sequence<T>&)
 107    {}
 108
 109 template <class T>
 110    Sequence<T> operator + (const Sequence<T>&, const T&)
 111    {}
 112
 113 template <class T>
 114    Sequence<T> operator + (const T&, const Sequence<T>&)
 115    {}
 116
 117 template <class T>
 118    Sequence<T> operator + (const Sequence<T>&, const T[])
 119    {}
 120
 121 template <class T>
 122    Sequence<T> operator + (const T[], const Sequence<T>&)
 123    {}
 124
 125 #endif