Stack.hpp

   1 /* Cycript - The Truly Universal Scripting Language
   2  * Copyright (C) 2009-2016  Jay Freeman (saurik)
   3 */
   4
   5 /* GNU Affero General Public License, Version 3 {{{ */
   6 /*
   7  * This program is free software: you can redistribute it and/or modify
   8  * it under the terms of the GNU Affero General Public License as published by
   9  * the Free Software Foundation, either version 3 of the License, or
  10  * (at your option) any later version.
  11
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU Affero General Public License for more details.
  16
  17  * You should have received a copy of the GNU Affero General Public License
  18  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 **/
  20 /* }}} */
  21
  22 #ifndef YY_CY_STACK_HH_INCLUDED
  23 #define YY_CY_STACK_HH_INCLUDED
  24
  25 namespace cy {
  26
  27 #if 0
  28 template <class Type_>
  29 class stack {
  30   public:
  31     typedef std::vector<Type_> Data_;
  32     typedef typename Data_::const_reverse_iterator const_iterator;
  33
  34   private:
  35     Data_ data_;
  36
  37   public:
  38     stack() {
  39         data_.reserve(200);
  40     }
  41
  42     _finline Type_ &operator [](size_t i) {
  43         return data_[data_.size() - 1 - i];
  44     }
  45
  46     _finline const Type_ &operator [](size_t i) const {
  47         return data_[data_.size() - 1 - i];
  48     }
  49
  50     _finline void push(Type_ &t) {
  51         data_.push_back(t);
  52     }
  53
  54     _finline void pop() {
  55         data_.pop_back();
  56     }
  57
  58     _finline void pop(unsigned int size) {
  59         for (; size != 0; --size)
  60             pop();
  61     }
  62
  63     void clear() {
  64         data_.clear();
  65     }
  66
  67     _finline size_t size() const {
  68         return data_.size();
  69     }
  70
  71     _finline const_iterator begin() const {
  72         return data_.rbegin();
  73     }
  74
  75     _finline const_iterator end() const {
  76         return data_.rend();
  77     }
  78
  79   private:
  80     stack(const stack &);
  81     stack &operator =(const stack &);
  82 };
  83 #else
  84 template <class Type_>
  85 class stack {
  86   public:
  87     typedef std::reverse_iterator<Type_ *> const_iterator;
  88
  89   private:
  90     Type_ *begin_;
  91     Type_ *end_;
  92     Type_ *capacity_;
  93
  94     void destroy() {
  95         for (Type_ *i(begin_); i != end_; ++i)
  96             i->~Type_();
  97     }
  98
  99     void reserve() {
 100         size_t capacity(capacity_ - begin_);
 101         if (capacity == 0)
 102             capacity = 200;
 103         else
 104             capacity *= 2;
 105
 106         Type_ *data(static_cast<Type_ *>(::operator new(sizeof(Type_) * capacity)));
 107
 108         size_t size(end_ - begin_);
 109         for (size_t i(0); i != size; ++i) {
 110             Type_ &old(begin_[i]);
 111             new (data + i) Type_(old);
 112             old.~Type_();
 113         }
 114
 115         ::operator delete(begin_);
 116
 117         begin_ = data;
 118         end_ = data + size;
 119         capacity_ = data + capacity;
 120     }
 121
 122   public:
 123     stack() :
 124         begin_(NULL),
 125         end_(NULL),
 126         capacity_(NULL)
 127     {
 128         reserve();
 129     }
 130
 131     ~stack() {
 132         destroy();
 133         ::operator delete(begin_);
 134     }
 135
 136     _finline Type_ &operator [](size_t i) {
 137         return end_[-1 - i];
 138     }
 139
 140     _finline const Type_ &operator [](size_t i) const {
 141         return end_[-1 - i];
 142     }
 143
 144     _finline void push(Type_ &t) {
 145         if (end_ == capacity_)
 146             reserve();
 147         new (end_++) Type_(t);
 148     }
 149
 150     _finline void pop() {
 151         (--end_)->~Type_();
 152     }
 153
 154     _finline void pop(unsigned int size) {
 155         for (; size != 0; --size)
 156             pop();
 157     }
 158
 159     void clear() {
 160         destroy();
 161         end_ = begin_;
 162     }
 163
 164     _finline size_t size() const {
 165         return end_ - begin_;
 166     }
 167
 168     _finline const_iterator begin() const {
 169         return const_iterator(end_);
 170     }
 171
 172     _finline const_iterator end() const {
 173         return const_iterator(begin_);
 174     }
 175
 176   private:
 177     stack(const stack &);
 178     stack &operator =(const stack &);
 179 };
 180 #endif
 181
 182 template <class Type_, class Stack_ = stack<Type_> >
 183 class slice {
 184   public:
 185     slice(const Stack_ &stack, unsigned int range) :
 186         stack_(stack),
 187         range_(range)
 188     {
 189     }
 190
 191     _finline const Type_ &operator [](unsigned int i) const {
 192         return stack_[range_ - i];
 193     }
 194
 195   private:
 196     const Stack_ &stack_;
 197     unsigned int range_;
 198 };
 199
 200 }
 201
 202 #endif/*YY_CY_STACK_HH_INCLUDED*/