001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.util;
014
015 import java.util.Collection;
016 import java.util.Iterator;
017 import java.util.List;
018 import java.util.ListIterator;
019 import org.jikesrvm.VM;
020
021 /**
022 * Implementation of java.util.LinkedList for use in classes that
023 * end up in the boot image.
024 */
025 public final class LinkedListRVM<T> implements List<T> {
026
027 /** Element count */
028 private int count = 0;
029
030 /** pointer to first element in the list */
031 Element<T> head = null;
032
033 /** pointer to last element in the list */
034 Element<T> tail = null;
035
036 /**
037 * Insert an element at a given position in the list.
038 * <p>
039 * UNIMPLEMENTED
040 *
041 * @param pos Position in the list (0..size()-1)
042 * @param entry Element to insert
043 */
044 public void add(int pos, T entry) {
045 if (VM.VerifyAssertions) VM._assert(false);
046 }
047
048 /**
049 * Insert at the tail of the list
050 *
051 * @param entry The entry to add.
052 * @return true (as per java collections framework standard)
053 */
054 public boolean add(final T entry) {
055 final Element<T> element = new Element<T>(entry);
056 element.next = null;
057 if (head == null) {
058 if (VM.VerifyAssertions) VM._assert(tail == null);
059 head = element;
060 element.prev = null;
061 } else {
062 tail.next = element;
063 element.prev = tail;
064 }
065 tail = element;
066 count++;
067 return true;
068 }
069
070 /**
071 * Insert an entry after the given element. Used via the iterator.
072 *
073 * @param e List element
074 * @param t New list entry
075 */
076 void insertAfter(Element<T> e, T t) {
077 Element<T> newElement = new Element<T>(t);
078 if (e == null) {
079 newElement.next = head;
080 newElement.prev = null;
081 head = newElement;
082 } else {
083 newElement.next = e.next;
084 newElement.prev = e;
085 if (e.next != null) {
086 e.next.prev = newElement;
087 }
088 e.next = newElement;
089 }
090 if (tail == null || tail == e) {
091 tail = newElement;
092 }
093 count++;
094 }
095
096 /**
097 * Add all members of the given collection.
098 * <p>
099 * UNIMPLEMENTED
100 */
101 public boolean addAll(Collection<? extends T> arg0) {
102 if (VM.VerifyAssertions) VM._assert(false);
103 return false;
104 }
105
106 /**
107 * Add all members of the given collection after the given element.
108 * <p>
109 * UNIMPLEMENTED
110 */
111 public boolean addAll(int arg0, Collection<? extends T> arg1) {
112 if (VM.VerifyAssertions) VM._assert(false);
113 return false;
114 }
115
116 /**
117 * Discard all entries in the list
118 */
119 public void clear() {
120 head = tail = null;
121 count = 0;
122 }
123
124 /**
125 * Membership test
126 *
127 * @param arg0 Object to check
128 * @return true if the list contains arg0, false otherwise
129 */
130 public boolean contains(Object arg0) {
131 return indexOf(arg0) != -1;
132 }
133
134 /**
135 * Set inclusion test
136 *
137 * @param arg0 Objects to check
138 * @return true if the list contains all objects in arg0, false otherwise
139 */
140 public boolean containsAll(Collection<?> arg0) {
141 for (Object o : arg0) {
142 if (!contains(o)) {
143 return false;
144 }
145 }
146 return true;
147 }
148
149 /**
150 * Return the nth element of the list
151 * <p>
152 * UNIMPLEMENTED
153 * @param index
154 */
155 public T get(int index) {
156 /* Special-case getting the head of the list for speed */
157 if (index == 0 && head != null) {
158 return head.entry;
159 }
160
161 /* bounds check */
162 if (index < 0 || index >= size()) {
163 throw new IndexOutOfBoundsException();
164 }
165
166 Element<T> cursor = head;
167 for (int i = 0; i < index; i++) {
168 cursor = cursor.next;
169 }
170 return cursor.entry;
171 }
172
173 /**
174 * Return the position of the given element.
175 *
176 * @param arg0 Member to test for.
177 * @return Zero-based index of the element, or -1 if not found.
178 */
179 public int indexOf(Object arg0) {
180 int i = 0;
181 for (T t : this) {
182 if (t == arg0) {
183 return i;
184 }
185 i++;
186 }
187 return -1;
188 }
189
190 public boolean isEmpty() {
191 return count == 0;
192 }
193
194 public Iterator<T> iterator() {
195 return new LinkedListIteratorRVM<T>(this);
196 }
197
198 /** UNIMPLEMENTED */
199 public int lastIndexOf(Object arg0) {
200 if (VM.VerifyAssertions) VM._assert(false);
201 return 0;
202 }
203
204 public ListIterator<T> listIterator() {
205 return new LinkedListIteratorRVM<T>(this);
206 }
207
208 /** UNIMPLEMENTED */
209 public ListIterator<T> listIterator(int arg0) {
210 if (VM.VerifyAssertions) VM._assert(false);
211 return null;
212 }
213
214 /**
215 * Remove the nth element of the list.
216 *
217 * @param index n
218 * @return The nth element
219 */
220 public T remove(int index) {
221 /* bounds check */
222 if (index < 0 || index >= size()) {
223 throw new IndexOutOfBoundsException();
224 }
225
226 Element<T> cursor = head;
227 for (int i = 0; i < index; i++) {
228 cursor = cursor.next;
229 }
230 removeInternal(cursor);
231 return cursor.entry;
232 }
233
234 /**
235 * Remove the given element from the list
236 */
237 public boolean remove(Object arg0) {
238 Element<T> cursor = head;
239 while (cursor != null && !(arg0 == null ? cursor.entry == null : cursor.entry.equals(arg0))) {
240 cursor = cursor.next;
241 }
242 if (cursor == null) {
243 return false;
244 } else {
245 removeInternal(cursor);
246 return true;
247 }
248 }
249
250 void removeInternal(Element<T> e) {
251 if (e.prev == null) {
252 if (VM.VerifyAssertions) VM._assert(e == head);
253 head = e.next;
254 } else {
255 e.prev.next = e.next;
256 }
257
258 if (e.next == null) {
259 if (VM.VerifyAssertions) VM._assert(e == tail);
260 tail = e.prev;
261 } else {
262 e.next.prev = e.prev;
263 }
264
265 count--;
266 }
267
268 /** UNIMPLEMENTED */
269 public boolean removeAll(Collection<?> arg0) {
270 if (VM.VerifyAssertions) VM._assert(false);
271 return false;
272 }
273
274 /** UNIMPLEMENTED */
275 public boolean retainAll(Collection<?> arg0) {
276 if (VM.VerifyAssertions) VM._assert(false);
277 return false;
278 }
279
280 /** UNIMPLEMENTED */
281 public T set(int arg0, T arg1) {
282 if (VM.VerifyAssertions) VM._assert(false);
283 return null;
284 }
285
286 public int size() {
287 return count;
288 }
289
290 /** UNIMPLEMENTED */
291 public List<T> subList(int arg0, int arg1) {
292 if (VM.VerifyAssertions) VM._assert(false);
293 return null;
294 }
295
296 /** UNIMPLEMENTED */
297 public Object[] toArray() {
298 if (VM.VerifyAssertions) VM._assert(false);
299 return null;
300 }
301
302 /** UNIMPLEMENTED */
303 public <U> U[] toArray(U[] arg0) {
304 if (VM.VerifyAssertions) VM._assert(false);
305 return null;
306 }
307
308 /**
309 * Class for the actual elements of the list.
310 *
311 *
312 * @param <T> Type of the entry
313 */
314 static class Element<T> {
315 Element<T> next;
316 Element<T> prev;
317 T entry;
318
319 Element(T entry) {
320 this.entry = entry;
321 }
322 }
323 }