1 /*
2 * Copyright (c) 1998-2002 The Jgroup Team.
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License version 2 as
6 * published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU Lesser General Public License for more details.
12 *
13 * You should have received a copy of the GNU Lesser General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
16 *
17 */
18
19 package jgroup.util;
20
21 import java.io.Externalizable;
22 import java.io.IOException;
23 import java.io.ObjectInput;
24 import java.io.ObjectOutput;
25
26 /**
27 * The <CODE>IntList</CODE> class represents ordered lists of integers.
28 * This class has been optimized to maintain list of integers
29 * containing long sequence of consecutive numbers. It is particularly
30 * useful for maintaining list of received ack numbers, that are
31 * normally consecutive (except in the case of connectivity problems).
32 * <p>
33 * The list is maintained by a chain of integer pairs; in each pair,
34 * the first integer represents the beginning of a consecutive sequence,
35 * while the second integer represents the end of a consecutive sequence.
36 * <p>
37 * For example, a list of this type:
38 * <pre> 1 2 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 </pre>
39 * is mantained in this way:
40 * <pre> (1-5),(7-11),(13-23) </pre>
41 * thus saving both memory and time to scan a list searching for a number.
42 * <p>
43 * <CODE>IntList</CODE> contains methods to add, lookup and remove
44 * integers, and to merge the contents of other <CODE>IntList</CODE>s.
45 * <p>
46 * Implementation note: As mentioned, <CODE>IntList</CODE> is based on a
47 * linked list of pairs. Each of these pairs are <CODE>IntList</CODE>
48 * objects, to avoid the need to introduce a inner class to hold pairs.
49 * For this reason, each integer list starts with an "empty"
50 * <CODE>IntList</CODE> containing no pair. The first pair of an
51 * <CODE>IntList</CODE> l is contained in <CODE>l.next</CODE>.
52 *
53 * @author Alberto Montresor
54 * @author Hein Meling
55 * @since Jgroup 0.3
56 */
57 public final class IntList
58 implements Externalizable
59 {
60
61 ////////////////////////////////////////////////////////////////////////////////////////////
62 // Fields
63 ////////////////////////////////////////////////////////////////////////////////////////////
64
65 private static final long serialVersionUID = -6522311553289690117L;
66
67 /** First element in a consecutive sequence */
68 private int start;
69
70 /** Last element in a consecutive sequence */
71 private int stop;
72
73 /** Next sequence in the list */
74 private IntList next;
75
76
77 ////////////////////////////////////////////////////////////////////////////////////////////
78 // Constructors
79 ////////////////////////////////////////////////////////////////////////////////////////////
80
81 /**
82 * Build an empty <CODE>IntList</CODE>.
83 */
84 public IntList()
85 {
86 }
87
88 /**
89 * Instantiates a pair representing a sequence
90 * starting and ending with <CODE>key</CODE>,
91 * and whose next element is <CODE>next</CODE>.
92 * For private use in the class.
93 */
94 private IntList(int key, IntList next)
95 {
96 this.start = key;
97 this.stop = key;
98 this.next = next;
99 }
100
101 /**
102 * Instantiates a pair representing a sequence
103 * starting with <CODE>start</CODE> and ending
104 * with <CODE>stop</CODE>. The next pair is set
105 * to null. For private use in the class.
106 */
107 private IntList(int start, int stop)
108 {
109 this.start = start;
110 this.stop = stop;
111 this.next = null;
112 }
113
114
115 ////////////////////////////////////////////////////////////////////////////////////////////
116 // Methods
117 ////////////////////////////////////////////////////////////////////////////////////////////
118
119 /**
120 * Returns the first element of the list, or -1 if the list is empty.
121 */
122 public int getFirst()
123 {
124 if (next != null)
125 return next.start;
126 else
127 return -1;
128 }
129
130 /**
131 * Returns the last element of the list, or -1 if the list is empty.
132 */
133 public int getLast()
134 {
135 IntList scan = this.next;
136 if (scan == null)
137 return -1;
138 while (scan.next != null)
139 scan = scan.next;
140 return scan.stop;
141 }
142
143 /**
144 * Returns true if the list is empty; false otherwise.
145 */
146 public boolean isEmpty()
147 {
148 if (next == null)
149 return true;
150 else
151 return false;
152 }
153
154 /**
155 * Returns the end value of the first consecutive sequence of integers
156 * contained in the list. For example, if the list contains
157 * <pre> 1 2 3 4 5 7 8 9 10 11 </pre>
158 * this methods return 5. If the list is empty, it returns -1.
159 */
160 public int getMaxConsecutive()
161 {
162 if (next != null)
163 return next.stop;
164 else
165 return -1;
166 }
167
168 /**
169 * Returns true if value <CODE>key</CODE> is contained in this
170 * <CODE>IntList</CODE>.
171 */
172 public boolean contains(int key)
173 {
174 // Used to scan the list
175 IntList scan = this.next;
176 while (scan != null && key >= scan.start) {
177 if (key <= scan.stop)
178 return true;
179 scan = scan.next;
180 }
181 return false;
182 }
183
184 /**
185 * Insert value <CODE>key</CODE> in the <CODE>IntList</CODE>.
186 */
187 public void insert(int key)
188 {
189 // Used to scan the list
190 IntList scan = this;
191
192 // Scan the list
193 while (scan.next != null && key > scan.next.stop + 1)
194 scan = scan.next;
195 if (scan.next == null || key < scan.next.start - 1) {
196 // Append at the beginning
197 scan.next = new IntList(key, scan.next);
198 } else if (key == scan.next.stop + 1) {
199 // Increment the stop position
200 IntList item = scan.next.next; // Temporary variable
201 if (item != null && item.start == key + 1) {
202 // Merge with the next item
203 scan.next.stop = item.stop;
204 scan.next.next = item.next;
205 } else {
206 // Just increment
207 scan.next.stop = key;
208 }
209 } else if (key > scan.next.stop + 1) {
210 // Append at the end
211 scan.next.next = new IntList(key, scan.next.next);
212 } else if (key == scan.next.start - 1) {
213 // Decrement start
214 scan.next.start = key;
215 }
216 }
217
218 /**
219 * Merge <CODE>IntList addend</CODE> to the <CODE>IntList</CODE>.
220 */
221 public void merge(IntList addend)
222 {
223 if (addend == null)
224 return;
225
226 IntList scan = this;
227 addend = addend.next;
228 while (addend != null) {
229 IntList snext = scan.next;
230 if (snext == null) {
231 // Append the rest of <addend> at the end of the list
232 scan.next = new IntList(addend.start, addend.stop);
233 addend = addend.next;
234 scan = snext;
235 }
236 else if (addend.stop < snext.start - 1) {
237 // Insert the current entry of <addend> before the
238 // current entry of the list
239 IntList temp = snext;
240 scan.next = new IntList(addend.start, addend.stop);
241 snext.next = temp;
242 scan = snext;
243 addend = addend.next;
244 }
245 else if (snext.stop+1 < addend.start) {
246 // Skip to the next entry of the list
247 scan = snext;
248 }
249 else {
250 // The current entry of <addend> and the current entry of
251 // the list intersect
252 if (snext.start > addend.start)
253 snext.start = addend.start;
254 if (snext.stop < addend.stop) {
255 snext.stop = addend.stop;
256 IntList temp = snext.next;
257 if (temp != null && temp.start <= addend.stop + 1) {
258 // Merge two elements
259 snext.next = temp.next;
260 snext.stop = temp.stop;
261 }
262 }
263 addend = addend.next;
264 }
265 }
266 }
267
268
269 /**
270 * Split the <code>IntList</code> at position <code>key</code>,
271 * leaving the upper part in this <code>IntList</code>, while
272 * returning the lower part of the list, <code>key</code> inclusive.
273 *
274 * @param key the position in the list to make the split.
275 * @return the lower part of this list is returned.
276 */
277 public IntList split(int key)
278 {
279 IntList ret = copy();
280 IntList toRemove = new IntList();
281 toRemove.next = new IntList(key + 1, getLast());
282 ret.remove(toRemove);
283 toRemove.next = new IntList(getFirst(), key);
284 remove(toRemove);
285 return ret;
286 }
287
288
289 /**
290 * Remove range from <code>start</code> to <code>stop</code>. If
291 * <code>stop</code> is zero, the remainder of the list is deleted.
292 */
293 public void remove(int start, int stop)
294 {
295 IntList toRemove = new IntList();
296 if (stop == 0)
297 stop = getLast();
298 if (getLast() != stop)
299 stop--;
300 toRemove.next = new IntList(start, stop);
301 remove(toRemove);
302 }
303
304
305 /**
306 * Returns and removes the first element of the list; -1 is returned
307 * if the list is empty.
308 */
309 public int removeFirst()
310 {
311 if (next != null) {
312 int ret = next.start;
313 remove(ret);
314 return ret;
315 } else
316 return -1;
317 }
318
319
320 /**
321 * Remove value <CODE>key</CODE> from the <CODE>IntList</CODE>.
322 */
323 public void remove(int key)
324 {
325 IntList toRemove = new IntList();
326 toRemove.insert(key);
327 remove(toRemove);
328 }
329
330
331 /**
332 * Remove <CODE>IntList removed</CODE> from the <CODE>IntList</CODE>.
333 */
334 public void remove(IntList removed)
335 {
336 if (removed == null)
337 return;
338
339 IntList scan = this;
340 removed = removed.next;
341 while (removed != null && scan.next != null) {
342 if (removed.stop < scan.next.start) {
343 /*
344 * The current <removed> entry is less than the current entry of
345 * the list; skip to the next <removed> entry.
346 */
347 removed = removed.next;
348 }
349 else if (scan.next.stop < removed.start) {
350 /*
351 * The current entry of the list is less than the current
352 * <removed> entry; skip to the next entry of the list.
353 */
354 scan = scan.next;
355 }
356 else if (removed.start > scan.next.start && removed.stop < scan.next.stop) {
357 /*
358 * The current <removed> entry is included in a list entry;
359 * split the list entry in two entries.
360 */
361 IntList temp = scan.next.next;
362 scan.next.next = new IntList(removed.stop+1, scan.next.stop);
363 scan.next.stop = removed.start-1;
364 scan.next.next.next = temp;
365 }
366 else {
367 /*
368 * The current <removed> entry is included in a list entry,
369 * either entirely or starting from the beginning or ending at
370 * the same number; reorganize the list or remove it entirely.
371 */
372 if (removed.stop >= scan.next.stop)
373 scan.next.stop = removed.start-1;
374 if (removed.start <= scan.next.start)
375 scan.next.start = removed.stop+1;
376 if (scan.next.stop < scan.next.start)
377 scan.next = scan.next.next;
378 }
379 }
380 }
381
382 /**
383 * Return an <CODE>int</CODE> array containing the values contained
384 * in this <CODE>IntList</CODE>.
385 */
386 public int[] toIntArray()
387 {
388 IntList scan;
389
390 int size = 0;
391 for (scan = this.next; scan != null; scan = scan.next)
392 size += (scan.stop - scan.start + 1);
393 int[] ret = new int[size];
394
395 int i = 0;
396 for (scan = this.next; scan != null; scan = scan.next)
397 for (int j = scan.start; j <= scan.stop; i++, j++)
398 ret[i] = j;
399 return ret;
400 }
401
402 /**
403 * Clear the content of this <CODE>IntList</CODE>.
404 */
405 public void clean()
406 {
407 this.next = null;
408 }
409
410 /**
411 * Deep clone this <CODE>IntList</CODE>.
412 */
413 public IntList copy()
414 {
415 IntList ret = new IntList();
416 IntList scan1 = ret;
417 IntList scan2 = this.next;
418 while (scan2 != null) {
419 scan1.next = new IntList(scan2.start, scan2.stop);
420 scan1 = scan1.next;
421 scan2 = scan2.next;
422 }
423 return ret;
424 }
425
426 ////////////////////////////////////////////////////////////////////////////////////////////
427 // Methods from External
428 ////////////////////////////////////////////////////////////////////////////////////////////
429
430 /**
431 * Write the contents of this <CODE>IntList</CODE> to
432 * the object output stream <CODE>out</CODE>. The external
433 * format of the string is the following: each pair is
434 * written to the stream, terminated by -1.
435 *
436 * @param out the stream to be written
437 */
438 public void writeExternal(ObjectOutput out)
439 throws IOException
440 {
441 IntList scan = this.next;
442 while (scan != null) {
443 out.writeInt(scan.start);
444 out.writeInt(scan.stop);
445 scan = scan.next;
446 }
447 out.writeInt(-1);
448 }
449
450 /**
451 * Restores the content of this object from the marshalled data contained
452 * in the specified input stream.
453 *
454 * @param in the stream to be read
455 */
456 public void readExternal(ObjectInput in)
457 throws IOException, ClassNotFoundException
458 {
459 // Used to construct the IntList
460 IntList scan = this;
461
462 // Start value
463 int v1;
464 while ((v1 = in.readInt()) != -1) {
465 scan.next = new IntList(v1, in.readInt());
466 scan = scan.next;
467 }
468 }
469
470 ////////////////////////////////////////////////////////////////////////////////////////////
471 // Object methods
472 ////////////////////////////////////////////////////////////////////////////////////////////
473
474 /**
475 * Returns a string representation of this object
476 */
477 public String toString()
478 {
479 StringBuilder buf = new StringBuilder();
480 buf.append("[IntList: {");
481 IntList scan = next;
482 while (scan != null) {
483 buf.append(scan.start);
484 buf.append("-");
485 buf.append(scan.stop);
486 scan = scan.next;
487 if (scan != null)
488 buf.append(", ");
489 }
490 buf.append("}]");
491 return buf.toString();
492 }
493
494 } // END IntList