1 /************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1996,1997 */
6 /* All Rights Reserved. */
7 /* */
8 /* Permission is hereby granted, free of charge, to use and distribute */
9 /* this software and its documentation without restriction, including */
10 /* without limitation the rights to use, copy, modify, merge, publish, */
11 /* distribute, sublicense, and/or sell copies of this work, and to */
12 /* permit persons to whom this work is furnished to do so, subject to */
13 /* the following conditions: */
14 /* 1. The code must retain the above copyright notice, this list of */
15 /* conditions and the following disclaimer. */
16 /* 2. Any modifications must be clearly marked as such. */
17 /* 3. Original authors' names are not deleted. */
18 /* 4. The authors' names are not used to endorse or promote products */
19 /* derived from this software without specific prior written */
20 /* permission. */
21 /* */
22 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30 /* THIS SOFTWARE. */
31 /* */
32 /*************************************************************************/
33 /* */
34 /* Author: Richard Caley (rjc@cstr.ed.ac.uk) */
35 /* -------------------------------------------------------------------- */
36 /* Double ended queue. */
37 /* */
38 /* Implemented in a vector used as a circular buffer. When more space */
39 /* is needed we expand the vector and copy the data to the beginning */
40 /* of the buffer. */
41 /* */
42 /*************************************************************************/
43
44 #include "EST_error.h"
45 #include "EST_TDeque.h"
46
47 template <class T>
EST_TDeque(unsigned int capacity,unsigned int increment)48 EST_TDeque<T>::EST_TDeque(unsigned int capacity, unsigned int increment)
49 : p_vector(capacity)
50 {
51 p_increment = increment;
52 p_front=0;
53 p_back=0;
54 }
55
56 template <class T>
EST_TDeque(unsigned int capacity)57 EST_TDeque<T>::EST_TDeque(unsigned int capacity)
58 : p_vector(capacity)
59 {
60 p_increment = 10;
61 p_front=0;
62 p_back=0;
63 }
64
65 template <class T>
EST_TDeque()66 EST_TDeque<T>::EST_TDeque()
67 {
68 p_vector.resize(10);
69 p_increment = 10;
70 p_front=0;
71 p_back=0;
72 }
73
74
75 template <class T>
print(ostream & s) const76 ostream &EST_TDeque<T>::print(ostream &s) const
77 {
78 s << "{" << p_vector.n() << "|";
79
80 if (p_front >= p_back)
81 {
82 for(int i0=0; i0<p_back; i0++)
83 s << "<>" << "//";
84 for(int i=p_back; i<p_front; i++)
85 s << p_vector(i) << "//";
86 for(int in=p_front; in <p_vector.n(); in++)
87 s << "<>" << "//";
88 }
89 else
90 {
91 for(int ii=0; ii<p_front; ii++)
92 s << p_vector(ii) << "//";
93 for(int i0=p_front; i0<p_back; i0++)
94 s << "<>" << "//";
95 for(int i=p_back; i<p_vector.n(); i++)
96 s << p_vector(i) << "//";
97 }
98
99 return s << "}";
100 }
101
102 template <class T>
expand()103 void EST_TDeque<T>::expand()
104 {
105 EST_TVector<T> tmp(p_vector);
106
107 if (p_back==0)
108 // special case for pure stack
109 p_vector.resize(p_vector.n()+p_increment, true);
110 else
111 {
112 p_vector.resize(p_vector.n()+p_increment, false);
113
114 if (p_front >= p_back)
115 for(int i=p_back, j=0; i<p_front; i++, j++)
116 p_vector[j] = tmp[i];
117 else
118 {
119 int j=0;
120 for(int i=p_back; i<tmp.n(); i++, j++)
121 p_vector[j] = tmp[i];
122
123 for(int ii=0; ii<p_front; ii++, j++)
124 p_vector[j] = tmp[ii];
125
126 p_back=0;
127 p_front=j;
128 }
129 }
130 }
131
132
133 template <class T>
is_empty() const134 bool EST_TDeque<T>::is_empty() const
135 {
136 return p_front==p_back;
137 }
138
139 template <class T>
clear()140 void EST_TDeque<T>::clear()
141 {
142 p_front=p_back=0;
143 for(int i=0; i<p_vector.n(); i++)
144 p_vector[i]=*Filler;
145 }
146
147 template <class T>
push(T & it)148 void EST_TDeque<T>::push(T& it)
149 {
150 int next_front= p_front+1;
151 if (next_front >= p_vector.n())
152 next_front= 0;
153
154 if (next_front==p_back)
155 {
156 expand();
157 push(it);
158 }
159 else
160 {
161 p_vector[p_front] = it;
162 p_front=next_front;
163 }
164 }
165
166 template <class T>
pop()167 T &EST_TDeque<T>::pop()
168 {
169 if (is_empty())
170 EST_error("empty stack!");
171
172 p_front--;
173 if (p_front < 0)
174 p_front=p_vector.n()-1;
175
176 return p_vector[p_front];
177 }
178
179 template <class T>
nth(int n)180 T &EST_TDeque<T>::nth(int n)
181 {
182 if (is_empty())
183 EST_error("empty stack!");
184
185 int pos = p_front-1-n;
186
187 if (p_front < p_back)
188 {
189 if (pos < 0)
190 {
191 pos += p_vector.n();
192 if (pos < p_back)
193 EST_error("looking too far up stack!");
194 }
195 }
196 else
197 if (pos < p_back)
198 EST_error("looking too far up stack!");
199
200 return p_vector[pos];
201 }
202
203 template <class T>
back_push(T & it)204 void EST_TDeque<T>::back_push(T& it)
205 {
206 int next_back = p_back-1;
207
208 if (next_back < 0)
209 next_back = p_vector.n()-1;
210
211 if (next_back == p_front)
212 {
213 expand();
214 back_push(it);
215 }
216 else
217 {
218 p_vector[p_back=next_back] = it;
219 }
220 }
221
222 template <class T>
back_pop()223 T &EST_TDeque<T>::back_pop()
224 {
225 if (is_empty())
226 EST_error("empty stack!");
227
228 int old_back = p_back;
229 p_back++;
230 if (p_back >= p_vector.n())
231 p_back=0;
232
233 return p_vector[old_back];
234 }
235
236