001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2005-2006, Geotools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation; either
009: * version 2.1 of the License, or (at your option) any later version.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.util;
017:
018: // J2SE dependencies
019: import java.util.List;
020: import java.util.ArrayList;
021: import java.util.Iterator;
022: import java.util.ListIterator;
023: import java.util.AbstractSequentialList;
024: import java.util.Map;
025: import java.util.TreeMap;
026: import java.util.SortedMap;
027: import java.util.Collections;
028: import java.util.NoSuchElementException;
029: import java.io.Serializable;
030:
031: /**
032: * List of elements sorted by a key which is not the element itself.
033: *
034: * @since 2.2
035: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/metadata/src/main/java/org/geotools/util/KeySortedList.java $
036: * @version $Id: KeySortedList.java 22443 2006-10-27 20:47:22Z desruisseaux $
037: * @author Simone Giannecchini
038: * @author Martin Desruisseaux
039: */
040: public class KeySortedList/*<K extends Comparable,V>*/extends
041: AbstractSequentialList/*<V>*/
042: implements Serializable {
043: /**
044: * Serial number for interoperability with different versions.
045: */
046: private static final long serialVersionUID = 6969483179756527012L;
047:
048: /**
049: * The sorted map of <var>key</var>-<var>list of values</var> pairs.
050: */
051: private final SortedMap/*<K,List<V>>*/map;
052:
053: /**
054: * Creates a new, initially empty list.
055: */
056: public KeySortedList() {
057: map = new TreeMap();
058: }
059:
060: /**
061: * Creates a list using the specified map of <var>key</var>-<var>list of values</var> pairs.
062: */
063: private KeySortedList(final SortedMap map) {
064: this .map = map;
065: }
066:
067: /**
068: * Removes all of the elements from this list.
069: */
070: public void clear() {
071: map.clear();
072: }
073:
074: /**
075: * Returns the number of elements in this list.
076: */
077: public int size() {
078: int count = 0;
079: for (final Iterator it = map.values().iterator(); it.hasNext();) {
080: count += ((List) it.next()).size();
081: }
082: return count;
083: }
084:
085: /**
086: * Inserts the specified element at a position determined by the specified key. If some
087: * elements were already inserted for the specified key, then this method do not replaces
088: * the old value (like what a {@link Map} would do), but instead add the new element with
089: * the same key.
090: *
091: * @param key Key to be used to find the right location.
092: * @param element Object to be inserted.
093: */
094: public void add(final Comparable key, final Object element) {
095: List values = (List) map.get(key);
096: if (values == null) {
097: values = new ArrayList();
098: map.put(key, values);
099: }
100: values.add(element);
101: }
102:
103: /**
104: * Removes all values that were {@linkplain #add(Comparable,Object) added} with the specified
105: * key. Returns the number of elements removed.
106: */
107: public int removeAll(final Comparable key) {
108: final List values = (List) map.remove(key);
109: return (values != null) ? values.size() : 0;
110: }
111:
112: /**
113: * Returns the number of elements {@linkplain #add(Comparable,Object) added} with the specified
114: * key.
115: */
116: public int count(final Comparable key) {
117: final List values = (List) map.get(key);
118: return (values != null) ? values.size() : 0;
119: }
120:
121: /**
122: * Returns {@code true} if the list contains an element {@linkplain #add(Comparable,Object)
123: * added} with the specified key. This is equivalent to testing
124: * <code>{@linkplain #count count}(key) != 0</code>.
125: */
126: public boolean containsKey(final Comparable key) {
127: return map.containsKey(key);
128: }
129:
130: /**
131: * Returns the first element
132: * {@linkplain #add(Comparable,Object) added} with the specified key.
133: *
134: * @param key The key for the element to search for.
135: * @return The first element added with the specified key.
136: * @throws NoSuchElementException if there is no element for the specified key.
137: */
138: public Object first(final Comparable key)
139: throws NoSuchElementException {
140: final List values = (List) map.get(key);
141: if (values == null || values.isEmpty()) {
142: throw new NoSuchElementException();
143: }
144: return values.get(0);
145: }
146:
147: /**
148: * Returns the last element
149: * {@linkplain #add(Comparable,Object) added} with the specified key.
150: *
151: * @param key The key for the element to search for.
152: * @return The last element added with the specified key.
153: * @throws NoSuchElementException if there is no element for the specified key.
154: */
155: public Object last(final Comparable key)
156: throws NoSuchElementException {
157: final List values = (List) map.get(key);
158: if (values == null || values.isEmpty()) {
159: throw new NoSuchElementException();
160: }
161: return values.get(values.size() - 1);
162: }
163:
164: /**
165: * Returns a list iterator of the elements in this list (in proper sequence), starting
166: * at the elements {@linkplain #add(Comparable,Object) added} with the specified key.
167: *
168: * @param fromKey The key of the first element to returns.
169: * @return A list iterator of the elements in this list (in proper sequence).
170: * @throws IndexOutOfBoundsException if the index is out of range.
171: */
172: public ListIterator listIterator(final Comparable fromKey) {
173: return new Iter(fromKey);
174: }
175:
176: /**
177: * Returns a list iterator of the elements in this list (in proper sequence), starting at the
178: * specified position. The specified index indicates the first element that would be returned
179: * by an initial call to the {@link ListIterator#next next()} method.
180: *
181: * @param index Index of first element to be returned from the list iterator.
182: * @return A list iterator of the elements in this list (in proper sequence).
183: * @throws IndexOutOfBoundsException if the index is out of range.
184: */
185: public ListIterator listIterator(final int index) {
186: return new Iter(index);
187: }
188:
189: /**
190: * The list iterator required for {@link AbstractSequentialList} implementation.
191: */
192: private final class Iter implements ListIterator {
193: /**
194: * The iterator over <var>key</var>-<var>list of values</var> pairs.
195: */
196: private Iterator entriesIter;
197:
198: /**
199: * The current key, or {@code null} if we are past the last entry.
200: */
201: private Comparable key;
202:
203: /**
204: * The values list for the current key.
205: */
206: private List values;
207:
208: /**
209: * The iterator over the current values list.
210: */
211: private ListIterator valuesIter;
212:
213: /**
214: * The base index for the current values list.
215: */
216: private int base;
217:
218: /**
219: * Creates an iterator initialy positioned to the first value of the specified key.
220: */
221: public Iter(final Comparable fromKey) {
222: entriesIter = map.entrySet().iterator();
223: while (entriesIter.hasNext()) {
224: final Map.Entry entry = (Map.Entry) entriesIter.next();
225: key = (Comparable) entry.getKey();
226: values = (List) entry.getValue();
227: if (fromKey.compareTo(key) <= 0) {
228: valuesIter = values.listIterator();
229: assert equals(new Iter(base));
230: return;
231: }
232: base += values.size();
233: }
234: key = null;
235: values = Collections.EMPTY_LIST;
236: valuesIter = values.listIterator();
237: }
238:
239: /**
240: * Creates an iterator initialy positioned to the specified index.
241: */
242: public Iter(int index) {
243: entriesIter = map.entrySet().iterator();
244: while (entriesIter.hasNext()) {
245: final Map.Entry entry = (Map.Entry) entriesIter.next();
246: key = (Comparable) entry.getKey();
247: values = (List) entry.getValue();
248: final int size = values.size();
249: if (index < size) {
250: valuesIter = values.listIterator(index);
251: return;
252: }
253: index -= size;
254: base += size;
255: }
256: if (index != 0) {
257: throw new IndexOutOfBoundsException();
258: }
259: key = null;
260: values = Collections.EMPTY_LIST;
261: valuesIter = values.listIterator();
262: }
263:
264: /**
265: * Returns {@code true} if this list iterator has more elements when traversing the list
266: * in the forward direction.
267: */
268: public boolean hasNext() {
269: return valuesIter.hasNext() || entriesIter.hasNext();
270: }
271:
272: /**
273: * Returns the next element in the list.
274: */
275: public Object next() {
276: while (!valuesIter.hasNext()) {
277: if (entriesIter.hasNext()) {
278: final Map.Entry entry = (Map.Entry) entriesIter
279: .next();
280: base += values.size(); // Must be before 'values' new assignement.
281: key = (Comparable) entry.getKey();
282: values = (List) entry.getValue();
283: valuesIter = values.listIterator();
284: } else {
285: key = null;
286: values = Collections.EMPTY_LIST;
287: valuesIter = values.listIterator();
288: break;
289: }
290: }
291: return valuesIter.next();
292: }
293:
294: /**
295: * Returns {@code true} if this list iterator has more elements when traversing the list
296: * in the reverse direction.
297: */
298: public boolean hasPrevious() {
299: return valuesIter.hasPrevious() || base != 0;
300: }
301:
302: /**
303: * Returns the previous element in the list.
304: */
305: public Object previous() {
306: while (!valuesIter.hasPrevious() && base != 0) {
307: /*
308: * Gets the key from the previous entry, and recreates a new entries iterator
309: * starting from this key (the assert statement ensure that). It should be the
310: * only place where this iterator needs to be recreated. Hopefully it should not
311: * happen often.
312: */
313: key = (Comparable) map.headMap(key).lastKey();
314: entriesIter = map.tailMap(key).entrySet().iterator();
315: final Map.Entry entry = (Map.Entry) entriesIter.next();
316: assert key == entry.getKey() : key;
317: /*
318: * Updates the values list, iterator and base index. It should now reflect the
319: * content of the list in the previous entry.
320: */
321: values = (List) entry.getValue();
322: final int size = values.size();
323: valuesIter = values.listIterator(Math.max(size - 1, 0));
324: base -= size; // Must be after 'values' new assignement.
325: assert base >= 0 : base;
326: }
327: return valuesIter.previous();
328: }
329:
330: /**
331: * Returns the index of the element that would be returned by a subsequent
332: * call to {@link #next}.
333: */
334: public int nextIndex() {
335: return base + valuesIter.nextIndex();
336: }
337:
338: /**
339: * Returns the index of the element that would be returned by a subsequent
340: * call to {@link #previous}.
341: */
342: public int previousIndex() {
343: return base + valuesIter.previousIndex();
344: }
345:
346: /**
347: * Removes from the list the last element that was returned by
348: * {@link #next} or {@link #previous}
349: */
350: public void remove() {
351: valuesIter.remove();
352: }
353:
354: /**
355: * Replaces the last element returned by {@link #next} or {@link #previous}
356: * with the specified element.
357: */
358: public void set(final Object o) {
359: valuesIter.set(o);
360: }
361:
362: /**
363: * Inserts the specified element into the list. The element will have the same key than
364: * the one from the previous call to {@link #next} or {@link #previous}.
365: */
366: public void add(final Object o) {
367: valuesIter.add(o);
368: }
369:
370: /**
371: * Compares two iterators for equality, assuming that they are iterator for the same
372: * {@link KeySortedList} (this is not verified). This method is used for assertions only.
373: */
374: private boolean equals(final Iter that) {
375: return this .key == that.key
376: && this .values == that.values
377: && this .base == that.base
378: && this .valuesIter.nextIndex() == that.valuesIter
379: .nextIndex();
380: }
381: }
382:
383: /**
384: * Returns a view of the portion of this list whose keys are strictly less than {@code toKey}.
385: * The returned list is backed by this list, so changes in the returned list are reflected in
386: * this list, and vice-versa.
387: *
388: * @param toKey high endpoint (exclusive) of the sub list.
389: * @return A view of the specified initial range of this list.
390: */
391: public KeySortedList headList(final Comparable toKey) {
392: return new KeySortedList(map.headMap(toKey));
393: }
394:
395: /**
396: * Returns a view of the portion of this list whose keys are greater than or equal to
397: * {@code fromKey}. The returned list is backed by this list, so changes in the returned
398: * list are reflected in this list, and vice-versa.
399: *
400: * @param fromKey low endpoint (inclusive) of the sub list.
401: * @return A view of the specified final range of this list.
402: */
403: public KeySortedList tailList(final Comparable fromKey) {
404: return new KeySortedList(map.tailMap(fromKey));
405: }
406: }
|