core/library/structures/stack.h

   1 #ifndef STACK_CLASS
   2 #define STACK_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : stack                                                             *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 1990-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include <basis/array.h>
  19
  20 namespace structures {
  21
  22 //! An abstraction that represents a stack data structure.
  23 /*!
  24   This behaves like a standard stack of objects, but it additionally allows
  25   access to any item in the stack via an array style bracket operator.
  26 */
  27
  28 template <class contents>
  29 class stack
  30 {
  31 public:
  32   enum stack_kinds { BOUNDED, UNBOUNDED };
  33
  34   stack(int elements = 0);
  35     //!< Creates a stack with room for the specified number of "elements".
  36     /*!< If "elements" is zero, then the stack is an UNBOUNDED stack that
  37     has no set limit on the number of elements it can contain (besides the
  38     amount of memory available).  on an unbounded stack, a result of IS_FULL
  39     will never be returned--instead a memory allocation failure would occur.
  40     If "elements" is greater than zero, then the stack is a BOUNDED stack
  41     which can hold at maximum "elements" number of objects.  for bounded
  42     stacks, if there is to be an allocation failure, it will happen at the
  43     time of stack construction, rather than during execution. */
  44
  45   stack(const stack &to_copy);
  46     //!< constructs a stack as a copy of "to_copy".
  47
  48   ~stack();
  49     //!< destroys anything left on the stack.
  50
  51   void reset();
  52     //!< throws out all contents on the stack.
  53
  54   stack_kinds kind() const { return _kind; }
  55     //!< returns the type of stack that was constructed.
  56
  57   basis::outcome push(const contents &element);
  58     //!< Enters a new element onto the top of the stack.
  59     /*!< if the stack is too large to add another element, then IS_FULL is
  60     returned.  if the element to push is nil, the stack is unchanged and
  61     IS_EMPTY is returned. */
  62
  63   basis::outcome pop();
  64     //!< Removes the top element on the stack.
  65     /*!< If the stack has no elements to be popped off, then IS_EMPTY is
  66     returned.  The element that was popped is destroyed. */
  67
  68   contents &top();
  69     //!< Returns the top element from the stack but doesn't change the stack.
  70     /*!< This method does not pop the element!  If the stack is empty, then a
  71     bogus contents object is returned. */
  72
  73   basis::outcome acquire_pop(contents &to_stuff);
  74     //!< Used to grab the top off of the stack.
  75     /*!< this is basically a call to top() followed by a pop().  if there was
  76     no top, then IS_EMPTY is returned. */
  77
  78   int size() const;
  79     //!< returns the size of the stack.
  80     /*!< if the stack is empty, then 0 is returned. */
  81
  82   stack &operator =(const stack &to_copy);
  83     //!< makes this stack a copy of "to_copy".
  84
  85   contents &operator [](int index);
  86     //!< Accesses the item at position "index" in the stack.
  87     /*!< Allows access to the stack in an impure fashion; elements other than
  88     the top can be examined.  Efforts to access elements that do not exist
  89     are ignored.  The range for the element numbers is as in C and runs
  90     from 0 to size() - 1. */
  91
  92   void invert();
  93     //!< Inverts this stack, meaning that the old bottom is the new top.
  94
  95   int elements() const;
  96     //!< Returns the number of elements used by the stack.
  97     /*!< For a bounded stack, this returns the number of elements the stack
  98     was constructed to hold.  For an unbounded stack, it returns the current
  99     number of elements (which is the same as size()).  Note though that it is
 100     different from size() for a bounded size stack! */
 101
 102 private:
 103   basis::array<contents> _store;  //!< holds the contents of the stack.
 104   stack_kinds _kind;  //!< the type of stack we've got.
 105   int _valid_fields;  //!< count of the number of items actually in use here.
 106 };
 107
 108 //////////////
 109
 110 // implementations below...
 111
 112 template <class contents>
 113 stack<contents>::stack(int elements)
 114 : _store(elements >= 0? elements : 0),
 115   _kind(_store.length()? BOUNDED : UNBOUNDED),
 116   _valid_fields(0)
 117 {}
 118
 119 template <class contents>
 120 stack<contents>::stack(const stack &to_copy)
 121 : _store(0), _valid_fields(0)
 122 { operator = (to_copy); }
 123
 124 template <class contents> stack<contents>::~stack() {}
 125
 126 template <class contents>
 127 int stack<contents>::size() const { return _valid_fields; }
 128
 129 template <class contents>
 130 void stack<contents>::reset()
 131 {
 132   while (pop() == basis::common::OKAY) {}  // pop off elements until all are gone.
 133 }
 134
 135 template <class contents>
 136 int stack<contents>::elements() const { return _store.length(); }
 137
 138 template <class contents>
 139 basis::outcome stack<contents>::push(const contents &element)
 140 {
 141   if (_kind == BOUNDED) {
 142     if (_valid_fields >= elements()) return basis::common::IS_FULL;
 143     basis::outcome result = _store.put(_valid_fields, element);
 144     if (result != basis::common::OKAY) return basis::common::IS_FULL;
 145   } else _store.concatenate(element);
 146   _valid_fields++;
 147   return basis::common::OKAY;
 148 }
 149
 150 template <class contents>
 151 basis::outcome stack<contents>::pop()
 152 {
 153   if (_valid_fields < 1) return basis::common::IS_EMPTY;
 154   if (_kind == UNBOUNDED)
 155     _store.zap(_store.length() - 1, _store.length() - 1);
 156   _valid_fields--;
 157   return basis::common::OKAY;
 158 }
 159
 160 template <class contents>
 161 contents &stack<contents>::top()
 162 { return _store[_valid_fields - 1]; }
 163
 164 template <class contents>
 165 stack<contents> &stack<contents>::operator = (const stack &to_copy)
 166 {
 167   if (this == &to_copy) return *this;
 168   reset();
 169   _kind = to_copy._kind;
 170   _store.reset(to_copy._store.length());
 171   for (int i = 0; i < to_copy._store.length(); i++)
 172     _store.put(i, to_copy._store[i]);
 173   _valid_fields = to_copy._valid_fields;
 174   return *this;
 175 }
 176
 177 template <class contents>
 178 void stack<contents>::invert()
 179 {
 180   for (int i = 0; i < _store.length() / 2; i++) {
 181     contents hold = _store.get(i);
 182     int exchange_index = _store.length() - i - 1;
 183     _store.put(i, _store.get(exchange_index));
 184     _store.put(exchange_index, hold);
 185   }
 186 }
 187
 188 template <class contents>
 189 contents &stack<contents>::operator [](int index)
 190 {
 191   if (index >= _valid_fields) index = -1;  // force a bogus return.
 192   return _store[index];
 193 }
 194
 195 template <class contents>
 196 basis::outcome stack<contents>::acquire_pop(contents &to_stuff)
 197 {
 198   if (!_valid_fields) return basis::common::IS_EMPTY;
 199   to_stuff = _store[_valid_fields - 1];
 200   if (_kind == UNBOUNDED) _store.zap(elements()-1, elements()-1);
 201   _valid_fields--;
 202   return basis::common::OKAY;
 203 }
 204
 205 } //namespace.
 206
 207 #endif
 208