Mercurial > projects > ldc

comparison tango/tango/util/collection/impl/CLCell.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
1 /*
2 File: CLCell.d
3
4 Originally written by Doug Lea and released into the public domain.
5 Thanks for the assistance and support of Sun Microsystems Labs, Agorics
6 Inc, Loral, and everyone contributing, testing, and using this code.
7
8 History:
9 Date Who What
10 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file
11 13Oct95 dl Changed protection statuses
12
13 */
14
15
16 module tango.util.collection.impl.CLCell;
17
18 private import tango.util.collection.impl.Cell;
19
20
21 /**
22 *
23 *
24 * CLCells are cells that are always arranged in circular lists
25 * They are pure implementation tools
26 *
27 author: Doug Lea
28 * @version 0.93
29 *
30 * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
31 **/
32
33 public class CLCell(T) : Cell!(T)
34 {
35 // instance variables
36
37 private CLCell next_;
38 private CLCell prev_;
39
40 // constructors
41
42 /**
43 * Make a cell with contents v, previous cell p, next cell n
44 **/
45
46 public this (T v, CLCell p, CLCell n)
47 {
48 super(v);
49 prev_ = p;
50 next_ = n;
51 }
52
53 /**
54 * Make a singular cell
55 **/
56
57 public this (T v)
58 {
59 super(v);
60 prev_ = this;
61 next_ = this;
62 }
63
64 /**
65 * Make a singular cell with null contents
66 **/
67
68 public this ()
69 {
70 super(T.init);
71 prev_ = this;
72 next_ = this;
73 }
74
75 /**
76 * return next cell
77 **/
78
79 public final CLCell next()
80 {
81 return next_;
82 }
83
84 /**
85 * Set next cell. You probably don't want to call this
86 **/
87
88 public final void next(CLCell n)
89 {
90 next_ = n;
91 }
92
93
94 /**
95 * return previous cell
96 **/
97 public final CLCell prev()
98 {
99 return prev_;
100 }
101
102 /**
103 * Set previous cell. You probably don't want to call this
104 **/
105 public final void prev(CLCell n)
106 {
107 prev_ = n;
108 }
109
110
111 /**
112 * Return true if current cell is the only one on the list
113 **/
114
115 public final bool isSingleton()
116 {
117 return next_ is this;
118 }
119
120 public final void linkNext(CLCell p)
121 {
122 if (p !is null)
123 {
124 next_.prev_ = p;
125 p.next_ = next_;
126 p.prev_ = this;
127 next_ = p;
128 }
129 }
130
131 /**
132 * Make a cell holding v and link it immediately after current cell
133 **/
134
135 public final void addNext(T v)
136 {
137 CLCell p = new CLCell(v, this, next_);
138 next_.prev_ = p;
139 next_ = p;
140 }
141
142 /**
143 * make a node holding v, link it before the current cell, and return it
144 **/
145
146 public final CLCell addPrev(T v)
147 {
148 CLCell p = prev_;
149 CLCell c = new CLCell(v, p, this);
150 p.next_ = c;
151 prev_ = c;
152 return c;
153 }
154
155 /**
156 * link p before current cell
157 **/
158
159 public final void linkPrev(CLCell p)
160 {
161 if (p !is null)
162 {
163 prev_.next_ = p;
164 p.prev_ = prev_;
165 p.next_ = this;
166 prev_ = p;
167 }
168 }
169
170 /**
171 * return the number of cells in the list
172 **/
173
174 public final int _length()
175 {
176 int c = 0;
177 CLCell p = this;
178 do {
179 ++c;
180 p = p.next();
181 } while (p !is this);
182 return c;
183 }
184
185 /**
186 * return the first cell holding element found in a circular traversal starting
187 * at current cell, or null if no such
188 **/
189
190 public final CLCell find(T element)
191 {
192 CLCell p = this;
193 do {
194 if (p.element() == (element))
195 return p;
196 p = p.next();
197 } while (p !is this);
198 return null;
199 }
200
201 /**
202 * return the number of cells holding element found in a circular
203 * traversal
204 **/
205
206 public final int count(T element)
207 {
208 int c = 0;
209 CLCell p = this;
210 do {
211 if (p.element() == (element))
212 ++c;
213 p = p.next();
214 } while (p !is this);
215 return c;
216 }
217
218 /**
219 * return the nth cell traversed from here. It may wrap around.
220 **/
221
222 public final CLCell nth(int n)
223 {
224 CLCell p = this;
225 for (int i = 0; i < n; ++i)
226 p = p.next_;
227 return p;
228 }
229
230
231 /**
232 * Unlink the next cell.
233 * This has no effect on the list if isSingleton()
234 **/
235
236 public final void unlinkNext()
237 {
238 CLCell nn = next_.next_;
239 nn.prev_ = this;
240 next_ = nn;
241 }
242
243 /**
244 * Unlink the previous cell.
245 * This has no effect on the list if isSingleton()
246 **/
247
248 public final void unlinkPrev()
249 {
250 CLCell pp = prev_.prev_;
251 pp.next_ = this;
252 prev_ = pp;
253 }
254
255
256 /**
257 * Unlink self from list it is in.
258 * Causes it to be a singleton
259 **/
260
261 public final void unlink()
262 {
263 CLCell p = prev_;
264 CLCell n = next_;
265 p.next_ = n;
266 n.prev_ = p;
267 prev_ = this;
268 next_ = this;
269 }
270
271 /**
272 * Make a copy of the list and return new head.
273 **/
274
275 public final CLCell copyList()
276 {
277 CLCell hd = this;
278
279 CLCell newlist = new CLCell(hd.element(), null, null);
280 CLCell current = newlist;
281
282 for (CLCell p = next_; p !is hd; p = p.next_)
283 {
284 current.next_ = new CLCell(p.element(), current, null);
285 current = current.next_;
286 }
287 newlist.prev_ = current;
288 current.next_ = newlist;
289 return newlist;
290 }
291 }
292