main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:08 for Gecode by
doxygen
1.8.4
gecode
support
dynamic-stack.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2002
8
*
9
* Last modified:
10
* $Date: 2013-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
11
* $Revision: 13840 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
namespace
Gecode {
namespace
Support {
39
45
template
<
class
T,
class
A>
46
class
DynamicStack
{
47
private
:
49
A& a;
51
int
limit;
53
int
tos;
55
T* stack;
57
void
resize(
void
);
58
public
:
60
DynamicStack
(A& a,
int
n
=64);
62
~DynamicStack
(
void
);
63
65
bool
empty
(
void
)
const
;
67
int
entries
(
void
)
const
;
68
70
T
pop
(
void
);
72
T&
top
(
void
)
const
;
74
T&
last
(
void
)
const
;
76
void
push
(
const
T&
x
);
77
78
85
T&
operator []
(
int
i
);
92
const
T&
operator []
(
int
i)
const
;
93
private
:
95
static
void
*
operator
new
(
size_t
s)
throw
() { (void) s;
return
NULL; }
97
static
void
operator
delete
(
void
*
p
) { (void)
p
; };
99
DynamicStack
(
const
DynamicStack
& s) : a(s.a) {}
101
const
DynamicStack
& operator =(
const
DynamicStack
&) {
return
*
this
; }
102
};
103
104
105
template
<
class
T,
class
A>
106
void
107
DynamicStack<T,A>::resize
(
void
) {
108
int
nl = (limit * 3) / 2;
109
stack =
a
.template realloc<T>(stack,limit,nl);
110
limit = nl;
111
}
112
113
template
<
class
T,
class
A>
114
forceinline
115
DynamicStack<T,A>::DynamicStack
(A& a0,
int
n
)
116
:
a
(a0), limit(n), tos(0), stack(
a
.template alloc<T>(n)) {}
117
118
template
<
class
T,
class
A>
119
forceinline
120
DynamicStack<T,A>::~DynamicStack
(
void
) {
121
a
.free(stack,limit);
122
}
123
124
template
<
class
T,
class
A>
125
forceinline
T
126
DynamicStack<T,A>::pop
(
void
) {
127
return
stack[--tos];
128
}
129
130
template
<
class
T,
class
A>
131
forceinline
T&
132
DynamicStack<T,A>::top
(
void
)
const
{
133
return
stack[tos-1];
134
}
135
136
template
<
class
T,
class
A>
137
forceinline
T&
138
DynamicStack<T,A>::last
(
void
)
const
{
139
return
stack[tos];
140
}
141
142
template
<
class
T,
class
A>
143
forceinline
void
144
DynamicStack<T,A>::push
(
const
T&
x
) {
145
stack[tos++] =
x
;
146
if
(tos==limit)
147
resize();
148
}
149
150
template
<
class
T,
class
A>
151
forceinline
bool
152
DynamicStack<T,A>::empty
(
void
)
const
{
153
return
tos==0;
154
}
155
156
template
<
class
T,
class
A>
157
forceinline
int
158
DynamicStack<T,A>::entries
(
void
)
const
{
159
return
tos;
160
}
161
162
template
<
class
T,
class
A>
163
forceinline
T&
164
DynamicStack<T,A>::operator []
(
int
i
) {
165
return
stack[
i
];
166
}
167
168
template
<
class
T,
class
A>
169
forceinline
const
T&
170
DynamicStack<T,A>::operator []
(
int
i
)
const
{
171
return
stack[
i
];
172
}
173
174
}}
175
176
// STATISTICS: support-any