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 /**
22 * The <code>OrderedList</code> class represents an ordered collection
23 * of objects. The order of elements is based on their keys,
24 * represented as integer values.
25 *
26 * @see jgroup.relacs.registry.BindingList
27 * @author Alberto Montresor
28 * @since Jgroup 1.0
29 */
30 public class OrderedList {
31
32 ////////////////////////////////////////////////////////////////////////////////////////////
33 // Fields
34 ////////////////////////////////////////////////////////////////////////////////////////////
35
36 /** The identifier of this element */
37 public int key;
38
39 /** Reference to the next element */
40 protected OrderedList next;
41
42 ////////////////////////////////////////////////////////////////////////////////////////////
43 // Constructors
44 ////////////////////////////////////////////////////////////////////////////////////////////
45
46 /**
47 * Creates an empty list.
48 */
49 protected OrderedList()
50 {
51 next = null;
52 }
53
54 ////////////////////////////////////////////////////////////////////////////////////////////
55 // Methods
56 ////////////////////////////////////////////////////////////////////////////////////////////
57
58 /**
59 * Inserts the specified element in the OrderedList. If the object's
60 * key is already present in the OrderedList, the element is not
61 * inserted.
62 *
63 * @param object
64 * The element to be inserted in this OrderedList.
65 * @return
66 * True if the object has previously been inserted; false otherwise.
67 */
68 public boolean insert(OrderedList object)
69 {
70 OrderedList s; // Used to scan list
71
72 for (s = this; s.next != null && s.next.key < object.key; s = s.next);
73 if (s.next == null || s.next.key > object.key) {
74 object.next = s.next;
75 s.next = object;
76 return true;
77 }
78 return false;
79 }
80
81 /**
82 * Removes the first occurrence of an element with the specified key in this OrderedList.
83 * If the OrderedList does not contain the element, it is unchanged and the methods returns
84 * <code> null</code>.
85 *
86 * @param key the key to search for.
87 */
88 public OrderedList remove(int key)
89 {
90 OrderedList s; // Used to scan list
91 OrderedList ret; // Return value
92
93 for (s = this; s.next != null && s.next.key < key; s = s.next);
94 ret = null;
95 if (s.next != null && s.next.key == key) {
96 ret = s.next;
97 s.next = s.next.next;
98 }
99
100 return ret;
101 }
102
103 /**
104 *
105 * @param key the key to search for.
106 */
107 public void removeAll(int key)
108 {
109 OrderedList s;
110 for (s = this; s.next != null && s.next.key <= key; s = s.next);
111 this.next = s.next;
112 }
113
114 /**
115 * Removes and returns the first element of the list. If the list is
116 * empty, <code>null</code> will be returned.
117 */
118 public OrderedList removeFirst()
119 {
120 OrderedList ret = this.next;
121 if (this.next != null)
122 this.next = this.next.next;
123 return ret;
124 }
125
126 /**
127 * Returns the first occurrence in this OrderedList of a element with the specified
128 * key, or <code> null</code> if the element is not found.
129 *
130 * @param key the key to search for.
131 */
132 public OrderedList lookup(int key)
133 {
134 OrderedList s; // Used to scan list
135
136 for (s = this.next; s != null && s.key < key; s = s.next);
137 return ((s != null && s.key == key) ? s : null);
138 }
139
140 /**
141 * Returns the next element in the OrderedList.
142 */
143 public OrderedList getNext()
144 {
145 return next;
146 }
147
148 /**
149 * Returns the first element of the OrderedList
150 */
151 public OrderedList getFirst()
152 {
153 return next;
154 }
155
156 /**
157 * Returns true if this OrderedList contains no elements.
158 */
159 public boolean isEmpty()
160 {
161 return (next == null);
162 }
163
164 /**
165 * Count the number of elements in the list
166 */
167 public int count()
168 {
169 int count = 0;
170 OrderedList scan = next;
171 while (scan != null) {
172 count++;
173 scan = scan.next;
174 }
175 return count;
176 }
177
178
179 } // END OrderedList