001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.lib;
032:
033: /**
034: * Intended as an asynchronous alternative to HsqlArrayList. Use HsqlArrayList if
035: * the list won't be initialized sequentially and if frequent references to
036: * specific element positions will be made.
037: *
038: * @author jcpeck@users
039: * @version 1.7.2
040: * @since 1.7.2
041: */
042: public class HsqlLinkedList extends BaseList implements HsqlList {
043:
044: /**
045: * A reference to the head of the list. It is a dummy head (that is, the
046: * Node for index 0 is actually first.next).
047: */
048: private Node first;
049:
050: /** A reference to the tail of the list */
051: private Node last;
052:
053: /**
054: * Creates a new instance of HsqlLinkedList.
055: */
056: public HsqlLinkedList() {
057:
058: first = new Node(null, null);
059: last = first;
060: elementCount = 0;
061: }
062:
063: /**
064: * Inserts <code>element</code> at <code>index</code>.
065: * @throws IndexOutOfBoundsException if <code>index</code> < 0 or is >
066: * <code>size</code>.
067: */
068: public void add(int index, Object element) {
069:
070: if (index == size()) {
071: add(element); //Add to the end of this.
072: }
073:
074: //If index > size() an exception should be thrown with a slightly
075: //different message than the exception thrown by getInternal.
076: else if (index > size()) {
077: throw new IndexOutOfBoundsException("Index out of bounds: "
078: + index + " > " + size());
079: } else {
080: Node current = getInternal(index);
081: Node newNext = new Node(current.data, current.next);
082:
083: current.data = element;
084: current.next = newNext;
085:
086: elementCount++;
087:
088: //If they inserted at the last valid index, then a new last element
089: //was created, therfore update the last pointer
090: if (last == current) {
091: last = newNext;
092: }
093: }
094: }
095:
096: /**
097: * Appends <code>element</code> to the end of this list.
098: * @return true
099: */
100: public boolean add(Object element) {
101:
102: last.next = new Node(element, null);
103: last = last.next;
104:
105: elementCount++;
106:
107: return true;
108: }
109:
110: public void clear() {
111: first.next = null;
112: }
113:
114: /**
115: * Gets the element at given position
116: * @throws <code>IndexOutOfBoundsException</code> if index is not valid
117: * index within the list (0 <= <code>index</code> <
118: * <code>size</code>).
119: */
120: public Object get(int index) {
121: return getInternal(index).data;
122: }
123:
124: /**
125: * Removes and returns the element at <code>index</code>.
126: * @throws <code>IndexOutOfBoundsException</code> if index is not valid
127: * index within the list (0 <= <code>index</code> <
128: * <code>size</code>).
129: */
130: public Object remove(int index) {
131:
132: //Check that the index is less than size because the getInternal
133: //method is being called with index - 1 and its checks will therefore
134: //not be useful in this case.
135: if (index >= size()) {
136: throw new IndexOutOfBoundsException("Index out of bounds: "
137: + index + " >= " + size());
138: }
139:
140: //Get the node that is previous to the node being removed
141: Node previousToRemove;
142:
143: if (index == 0) {
144: previousToRemove = first;
145: } else {
146: previousToRemove = getInternal(index - 1);
147: }
148:
149: //previousToRemove.next will never be null because of the check above
150: //that index < size.
151: Node toRemove = previousToRemove.next;
152:
153: previousToRemove.next = toRemove.next;
154:
155: elementCount--;
156:
157: //If they removed at the last valid index, then a the last element
158: //was removed, therfore update the last pointer
159: if (last == toRemove) {
160: last = previousToRemove;
161: }
162:
163: return toRemove.data;
164: }
165:
166: /**
167: * Replaces the current element at <code>index/code> with
168: * <code>element</code>.
169: * @return The current element at <code>index</code>.
170: */
171: public Object set(int index, Object element) {
172:
173: Node setMe = getInternal(index);
174: Object oldData = setMe.data;
175:
176: setMe.data = element;
177:
178: return oldData;
179: }
180:
181: /**
182: * Accessor for the size of this linked list. The size is the total number
183: * of elements in the list and is one greater than the largest index in the
184: * list.
185: * @return The size of this.
186: */
187: public final int size() {
188: return elementCount;
189: }
190:
191: /**
192: * Helper method that returns the Node at <code>index</code>.
193: * @param index The index of the Node to return.
194: * @return The Node at the given index.
195: * @throws <code>IndexOutOfBoundsException</code> if index is not valid
196: * index within the list (0 <= <code>index</code> <
197: * <code>size</code>).
198: */
199: protected final Node getInternal(int index) {
200:
201: //Check preconditions for the index variable
202: if (index >= size()) {
203: throw new IndexOutOfBoundsException("Index out of bounds: "
204: + index + " >= " + size());
205: }
206:
207: if (index < 0) {
208: throw new IndexOutOfBoundsException("Index out of bounds: "
209: + index + " < 0");
210: }
211:
212: if (index == 0) {
213: return first.next;
214: } else if (index == (size() - 1)) {
215: return last;
216: } else {
217: Node pointer = first.next;
218:
219: for (int i = 0; i < index; i++) {
220: pointer = pointer.next;
221: }
222:
223: return pointer;
224: }
225: }
226:
227: /**
228: * Inner class that represents nodes within the linked list. This should
229: * be a static inner class to avoid the uneccesary overhead of the
230: * containing class "this" pointer.
231: * jcpeck@users
232: * @version 05/24/2002
233: */
234: private static class Node {
235:
236: public Node next;
237: public Object data;
238:
239: public Node() {
240: next = null;
241: data = null;
242: }
243:
244: public Node(Object data) {
245: this .next = null;
246: this .data = data;
247: }
248:
249: public Node(Object data, Node next) {
250: this.next = next;
251: this.data = data;
252: }
253: }
254: }
|