dynamic-stack.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2002 00008 * 00009 * Last modified: 00010 * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $ 00011 * $Revision: 9692 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 namespace Gecode { namespace Support { 00039 00045 template<class T, class A> 00046 class DynamicStack { 00047 private: 00049 A& a; 00051 int limit; 00053 int tos; 00055 T* stack; 00057 void resize(void); 00058 public: 00060 DynamicStack(A& a, int n=64); 00062 ~DynamicStack(void); 00063 00065 bool empty(void) const; 00067 int entries(void) const; 00068 00070 T pop(void); 00072 T& top(void) const; 00074 T& last(void) const; 00076 void push(const T& x); 00077 00078 00085 T& operator [](int i); 00092 const T& operator [](int i) const; 00093 00095 size_t size(void) const; 00096 private: 00098 static void* operator new(size_t s) throw() { (void) s; return NULL; } 00100 static void operator delete(void* p) { (void) p; }; 00102 DynamicStack(const DynamicStack& s) : a(s.a) {} 00104 const DynamicStack& operator =(const DynamicStack&) { return *this; } 00105 }; 00106 00107 00108 template<class T, class A> 00109 void 00110 DynamicStack<T,A>::resize(void) { 00111 int nl = (limit * 3) / 2; 00112 stack = a.template realloc<T>(stack,limit,nl); 00113 limit = nl; 00114 } 00115 00116 template<class T, class A> 00117 forceinline 00118 DynamicStack<T,A>::DynamicStack(A& a0, int n) 00119 : a(a0), limit(n), tos(0), stack(a.template alloc<T>(n)) {} 00120 00121 template<class T, class A> 00122 forceinline 00123 DynamicStack<T,A>::~DynamicStack(void) { 00124 a.free(stack,limit); 00125 } 00126 00127 template<class T, class A> 00128 forceinline T 00129 DynamicStack<T,A>::pop(void) { 00130 return stack[--tos]; 00131 } 00132 00133 template<class T, class A> 00134 forceinline T& 00135 DynamicStack<T,A>::top(void) const { 00136 return stack[tos-1]; 00137 } 00138 00139 template<class T, class A> 00140 forceinline T& 00141 DynamicStack<T,A>::last(void) const { 00142 return stack[tos]; 00143 } 00144 00145 template<class T, class A> 00146 forceinline void 00147 DynamicStack<T,A>::push(const T& x) { 00148 stack[tos++] = x; 00149 if (tos==limit) 00150 resize(); 00151 } 00152 00153 template<class T, class A> 00154 forceinline bool 00155 DynamicStack<T,A>::empty(void) const { 00156 return tos==0; 00157 } 00158 00159 template<class T, class A> 00160 forceinline int 00161 DynamicStack<T,A>::entries(void) const { 00162 return tos; 00163 } 00164 00165 template<class T, class A> 00166 forceinline T& 00167 DynamicStack<T,A>::operator [](int i) { 00168 return stack[i]; 00169 } 00170 00171 template<class T, class A> 00172 forceinline const T& 00173 DynamicStack<T,A>::operator [](int i) const { 00174 return stack[i]; 00175 } 00176 00177 template<class T, class A> 00178 forceinline size_t 00179 DynamicStack<T,A>::size(void) const { 00180 return (static_cast<size_t>(limit) * sizeof(T)) + 00181 sizeof(DynamicStack<T,A>); 00182 } 00183 00184 }} 00185 00186 // STATISTICS: support-any