001: /*
002: Copyright (c) 2006, Matthew Estes
003: All rights reserved.
004:
005: Redistribution and use in source and binary forms, with or without
006: modification, are permitted provided that the following conditions are met:
007:
008: * Redistributions of source code must retain the above copyright
009: notice, this list of conditions and the following disclaimer.
010: * Redistributions in binary form must reproduce the above copyright
011: notice, this list of conditions and the following disclaimer in the
012: documentation and/or other materials provided with the distribution.
013: * Neither the name of Metanotion Software nor the names of its
014: contributors may be used to endorse or promote products derived from this
015: software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
018: IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
019: THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
020: PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
021: CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
022: EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
023: PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
024: PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
025: LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
026: NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
027: SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: */
029: package net.metanotion.util.skiplist;
030:
031: import java.util.ListIterator;
032: import java.util.NoSuchElementException;
033:
034: /** A basic iterator for a skip list.
035: This is not a complete ListIterator, in particular, since the
036: skip list is a map and is therefore indexed by Comparable objects instead
037: of int's, the nextIndex and previousIndex methods are not really relevant.
038: */
039: public class SkipIterator implements ListIterator {
040: SkipSpan ss;
041: int index;
042:
043: protected SkipIterator() {
044: }
045:
046: public SkipIterator(SkipSpan ss, int index) {
047: if (ss == null) {
048: throw new NullPointerException();
049: }
050: this .ss = ss;
051: this .index = index;
052: }
053:
054: public boolean hasNext() {
055: if (index < ss.nKeys) {
056: return true;
057: }
058: return false;
059: }
060:
061: public Object next() {
062: Object o;
063: if (index < ss.nKeys) {
064: o = ss.vals[index];
065: } else {
066: throw new NoSuchElementException();
067: }
068:
069: if (index < (ss.nKeys - 1)) {
070: index++;
071: } else if (ss.next != null) {
072: ss = ss.next;
073: index = 0;
074: } else {
075: index = ss.nKeys;
076: }
077: return o;
078: }
079:
080: public Comparable nextKey() {
081: Comparable c;
082: if (index < ss.nKeys) {
083: return ss.keys[index];
084: }
085: throw new NoSuchElementException();
086: }
087:
088: public boolean hasPrevious() {
089: if (index > 0) {
090: return true;
091: }
092: if ((ss.prev != null) && (ss.prev.nKeys > 0)) {
093: return true;
094: }
095: return false;
096: }
097:
098: public Object previous() {
099: if (index > 0) {
100: index--;
101: } else if (ss.prev != null) {
102: ss = ss.prev;
103: if (ss.nKeys <= 0) {
104: throw new NoSuchElementException();
105: }
106: index = (ss.nKeys - 1);
107: }
108: return ss.vals[index];
109: }
110:
111: // Optional methods
112: public void add(Object o) {
113: throw new UnsupportedOperationException();
114: }
115:
116: public void remove() {
117: throw new UnsupportedOperationException();
118: }
119:
120: public void set(Object o) {
121: throw new UnsupportedOperationException();
122: }
123:
124: public int nextIndex() {
125: throw new UnsupportedOperationException();
126: }
127:
128: public int previousIndex() {
129: throw new UnsupportedOperationException();
130: }
131:
132: }
|