Mercurial > projects > ldc

comparison tango/tango/util/collection/impl/LLCell.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: LLCell.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
12 */
13
14
15 module tango.util.collection.impl.LLCell;
16
17 private import tango.util.collection.impl.Cell;
18
19 private import tango.util.collection.model.Comparator;
20
21 /**
22 *
23 *
24 * LLCells extend Cells with standard linkedlist next-fields,
25 * and provide a standard operations on them.
26 * <P>
27 * LLCells are pure implementation tools. They perform
28 * no argument checking, no result screening, and no synchronization.
29 * They rely on user-level classes (see for example LinkedList) to do such things.
30 * Still, the class is made `public' so that you can use them to
31 * build other kinds of collections or whatever, not just the ones
32 * currently supported.
33 *
34 author: Doug Lea
35 * @version 0.93
36 *
37 * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
38 **/
39
40 public class LLCell(T) : Cell!(T)
41 {
42 alias Comparator!(T) ComparatorT;
43
44
45 protected LLCell next_;
46
47 /**
48 * Return the next cell (or null if none)
49 **/
50
51 public LLCell next()
52 {
53 return next_;
54 }
55
56 /**
57 * set to point to n as next cell
58 * @param n, the new next cell
59 **/
60
61 public void next(LLCell n)
62 {
63 next_ = n;
64 }
65
66 public this (T v, LLCell n)
67 {
68 super(v);
69 next_ = n;
70 }
71
72 public this (T v)
73 {
74 this(v, null);
75 }
76
77 public this ()
78 {
79 this(T.init, null);
80 }
81
82
83 /**
84 * Splice in p between current cell and whatever it was previously
85 * pointing to
86 * @param p, the cell to splice
87 **/
88
89 public final void linkNext(LLCell p)
90 {
91 if (p !is null)
92 p.next_ = next_;
93 next_ = p;
94 }
95
96 /**
97 * Cause current cell to skip over the current next() one,
98 * effectively removing the next element from the list
99 **/
100
101 public final void unlinkNext()
102 {
103 if (next_ !is null)
104 next_ = next_.next_;
105 }
106
107 /**
108 * Linear search down the list looking for element (using T.equals)
109 * @param element to look for
110 * Returns: the cell containing element, or null if no such
111 **/
112
113 public final LLCell find(T element)
114 {
115 for (LLCell p = this; p !is null; p = p.next_)
116 if (p.element() == element)
117 return p;
118 return null;
119 }
120
121 /**
122 * return the number of cells traversed to find first occurrence
123 * of a cell with element() element, or -1 if not present
124 **/
125
126 public final int index(T element)
127 {
128 int i = 0;
129 for (LLCell p = this; p !is null; p = p.next_)
130 {
131 if (p.element() == element)
132 return i;
133 else
134 ++i;
135 }
136 return -1;
137 }
138
139 /**
140 * Count the number of occurrences of element in list
141 **/
142
143 public final int count(T element)
144 {
145 int c = 0;
146 for (LLCell p = this; p !is null; p = p.next_)
147 if (p.element() == element)
148 ++c;
149 return c;
150 }
151
152 /**
153 * return the number of cells in the list
154 **/
155
156 public final int _length()
157 {
158 int c = 0;
159 for (LLCell p = this; p !is null; p = p.next_)
160 ++c;
161 return c;
162 }
163
164 /**
165 * return the cell representing the last element of the list
166 * (i.e., the one whose next() is null
167 **/
168
169 public final LLCell tail()
170 {
171 LLCell p = this;
172 for ( ; p.next_ !is null; p = p.next_)
173 {}
174 return p;
175 }
176
177 /**
178 * return the nth cell of the list, or null if no such
179 **/
180
181 public final LLCell nth(int n)
182 {
183 LLCell p = this;
184 for (int i = 0; i < n; ++i)
185 p = p.next_;
186 return p;
187 }
188
189
190 /**
191 * make a copy of the list; i.e., a new list containing new cells
192 * but including the same elements in the same order
193 **/
194
195 public final LLCell copyList()
196 {
197 LLCell newlist = null;
198 newlist = duplicate();
199 LLCell current = newlist;
200
201 for (LLCell p = next_; p !is null; p = p.next_)
202 {
203 current.next_ = p.duplicate();
204 current = current.next_;
205 }
206 current.next_ = null;
207 return newlist;
208 }
209
210 /**
211 * Clone is SHALLOW; i.e., just makes a copy of the current cell
212 **/
213
214 private final LLCell duplicate()
215 {
216 return new LLCell(element(), next_);
217 }
218
219 /**
220 * Basic linkedlist merge algorithm.
221 * Merges the lists head by fst and snd with respect to cmp
222 * @param fst head of the first list
223 * @param snd head of the second list
224 * @param cmp a Comparator used to compare elements
225 * Returns: the merged ordered list
226 **/
227
228 public final static LLCell merge(LLCell fst, LLCell snd, ComparatorT cmp)
229 {
230 LLCell a = fst;
231 LLCell b = snd;
232 LLCell hd = null;
233 LLCell current = null;
234 for (;;)
235 {
236 if (a is null)
237 {
238 if (hd is null)
239 hd = b;
240 else
241 current.next(b);
242 return hd;
243 }
244 else
245 if (b is null)
246 {
247 if (hd is null)
248 hd = a;
249 else
250 current.next(a);
251 return hd;
252 }
253
254 int diff = cmp.compare(a.element(), b.element());
255 if (diff <= 0)
256 {
257 if (hd is null)
258 hd = a;
259 else
260 current.next(a);
261 current = a;
262 a = a.next();
263 }
264 else
265 {
266 if (hd is null)
267 hd = b;
268 else
269 current.next(b);
270 current = b;
271 b = b.next();
272 }
273 }
274 return null;
275 }
276
277 /**
278 * Standard list splitter, used by sort.
279 * Splits the list in half. Returns the head of the second half
280 * @param s the head of the list
281 * Returns: the head of the second half
282 **/
283
284 public final static LLCell split(LLCell s)
285 {
286 LLCell fast = s;
287 LLCell slow = s;
288
289 if (fast is null || fast.next() is null)
290 return null;
291
292 while (fast !is null)
293 {
294 fast = fast.next();
295 if (fast !is null && fast.next() !is null)
296 {
297 fast = fast.next();
298 slow = slow.next();
299 }
300 }
301
302 LLCell r = slow.next();
303 slow.next(null);
304 return r;
305
306 }
307
308 /**
309 * Standard merge sort algorithm
310 * @param s the list to sort
311 * @param cmp, the comparator to use for ordering
312 * Returns: the head of the sorted list
313 **/
314
315 public final static LLCell mergeSort(LLCell s, ComparatorT cmp)
316 {
317 if (s is null || s.next() is null)
318 return s;
319 else
320 {
321 LLCell right = split(s);
322 LLCell left = s;
323 left = mergeSort(left, cmp);
324 right = mergeSort(right, cmp);
325 return merge(left, right, cmp);
326 }
327 }
328
329 }
330