Edinburgh Speech Tools  2.1-release
EST_TDeque.cc
Go to the documentation of this file.
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>
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>
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>
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>
76 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>
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>
135 {
136  return p_front==p_back;
137 }
138 
139 template <class T>
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>
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>
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>
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>
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>
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 
void back_push(T &item)
Definition: EST_TDeque.cc:204
void clear(void)
Empty it out.
Definition: EST_TDeque.cc:140
void push(T &item)
Definition: EST_TDeque.cc:148
T & pop(void)
Definition: EST_TDeque.cc:167
bool is_empty(void) const
Is there anything to get?
Definition: EST_TDeque.cc:134
T & back_pop(void)
Definition: EST_TDeque.cc:223
Double ended queue.
Definition: EST_TDeque.h:49
#define EST_error
Definition: EST_error.h:104
T & nth(int i)
Definition: EST_TDeque.cc:180
std::ostream & print(std::ostream &s) const
print picture of state. Mostly useful for debugging.
Definition: EST_TDeque.cc:76
static const T * Filler
Used to fill empty spaces when possible.
Definition: EST_TDeque.h:65
int expand
Definition: rxp.c:20
Template vector.
Definition: EST_TVector.h:145
INLINE ssize_t n() const
number of items in vector.
Definition: EST_TVector.h:251
EST_TDeque(void)
Definition: EST_TDeque.cc:66