dynamic-stack.hh
Go to the documentation of this file.00001 /* 00002 * Main authors: 00003 * Christian Schulte <schulte@gecode.org> 00004 * 00005 * Copyright: 00006 * Christian Schulte, 2002 00007 * 00008 * Last modified: 00009 * $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $ 00010 * $Revision: 3188 $ 00011 * 00012 * This file is part of Gecode, the generic constraint 00013 * development environment: 00014 * http://www.gecode.org 00015 * 00016 * See the file "LICENSE" for information on usage and 00017 * redistribution of this file, and for a 00018 * DISCLAIMER OF ALL WARRANTIES. 00019 * 00020 */ 00021 00022 #ifndef __GECODE_SUPPORT_DYNAMIC_STACK_HH__ 00023 #define __GECODE_SUPPORT_DYNAMIC_STACK_HH__ 00024 00025 #include "gecode/kernel.hh" 00026 00027 namespace Gecode { namespace Support { 00028 00035 template <class T> 00036 class DynamicStack { 00037 private: 00039 unsigned int limit; 00041 unsigned int tos; 00043 T* stack; 00045 void resize(void); 00046 public: 00048 DynamicStack(unsigned int n=64); 00050 ~DynamicStack(void); 00051 00053 bool empty(void) const; 00055 T pop(void); 00057 T& top(void); 00059 void push(T); 00060 00061 00063 unsigned int entries(void) const; 00070 T& operator[](int i); 00077 const T& operator [] (int i) const; 00078 00080 size_t size(void) const; 00081 }; 00082 00083 00084 template <class T> 00085 void 00086 DynamicStack<T>::resize(void) { 00087 unsigned int nl = (limit * 3) / 2; 00088 stack = Memory::brealloc<T>(stack,limit,nl); 00089 limit = nl; 00090 } 00091 00092 template <class T> 00093 forceinline 00094 DynamicStack<T>::DynamicStack(unsigned int n) 00095 : limit(n), tos(0), stack(Memory::bmalloc<T>(n)) {} 00096 00097 template <class T> 00098 forceinline 00099 DynamicStack<T>::~DynamicStack(void) { 00100 Memory::free(stack); 00101 } 00102 00103 template <class T> 00104 forceinline T 00105 DynamicStack<T>::pop(void) { 00106 return stack[--tos]; 00107 } 00108 00109 template <class T> 00110 forceinline T& 00111 DynamicStack<T>::top(void) { 00112 return stack[tos-1]; 00113 } 00114 00115 template <class T> 00116 forceinline void 00117 DynamicStack<T>::push(T x) { 00118 stack[tos++] = x; 00119 if (tos==limit) 00120 resize(); 00121 } 00122 00123 template <class T> 00124 forceinline bool 00125 DynamicStack<T>::empty(void) const { 00126 return tos==0; 00127 } 00128 00129 template <class T> 00130 forceinline unsigned int 00131 DynamicStack<T>::entries(void) const { 00132 return tos; 00133 } 00134 00135 template <class T> 00136 forceinline T& 00137 DynamicStack<T>::operator [] (int i) { 00138 return stack[i]; 00139 } 00140 00141 template <class T> 00142 forceinline const T& 00143 DynamicStack<T>::operator [] (int i) const { 00144 return stack[i]; 00145 } 00146 00147 template <class T> 00148 forceinline size_t 00149 DynamicStack<T>::size(void) const { 00150 return (limit * sizeof(T)) + sizeof(DynamicStack<T>); 00151 } 00152 00153 }} 00154 00155 #endif 00156 00157 // STATISTICS: support-any