01: /*
02: * Copyright (C) 2005, 2006 Joe Walnes.
03: * Copyright (C) 2006, 2007 XStream Committers.
04: * All rights reserved.
05: *
06: * The software in this package is published under the terms of the BSD
07: * style license a copy of which has been included with this distribution in
08: * the LICENSE.txt file.
09: *
10: * Created on 06. February 2005 by Joe Walnes
11: */
12: package com.thoughtworks.xstream.core.util;
13:
14: import java.util.Iterator;
15: import java.util.Set;
16: import java.util.TreeSet;
17:
18: /**
19: * List that allows items to be added with a priority that will affect the order in which they are later iterated over.
20: * Objects with a high priority will appear before objects with a low priority in the list. If two objects of the same
21: * priority are added to the list, the most recently added one will be iterated over first. Implementation uses a
22: * TreeSet, which has a guaranteed add time of O(log(n)).
23: *
24: * @author Joe Walnes
25: * @author Guilherme Silveira
26: */
27: public class PrioritizedList {
28:
29: private final Set set = new TreeSet();
30:
31: private int lowestPriority = Integer.MAX_VALUE;
32:
33: private int lastId = 0;
34:
35: public void add(Object item, int priority) {
36: if (this .lowestPriority > priority) {
37: this .lowestPriority = priority;
38: }
39: this .set.add(new PrioritizedItem(item, priority, ++lastId));
40: }
41:
42: public Iterator iterator() {
43: return new PrioritizedItemIterator(this .set.iterator());
44: }
45:
46: private static class PrioritizedItem implements Comparable {
47:
48: final Object value;
49: final int priority;
50: final int id;
51:
52: public PrioritizedItem(Object value, int Prioritized, int id) {
53: this .value = value;
54: this .priority = Prioritized;
55: this .id = id;
56: }
57:
58: public int compareTo(Object o) {
59: PrioritizedItem other = (PrioritizedItem) o;
60: if (this .priority != other.priority) {
61: return (other.priority - this .priority);
62: }
63: return (other.id - this .id);
64: }
65:
66: public boolean equals(Object obj) {
67: return this .id == ((PrioritizedItem) obj).id;
68: }
69:
70: }
71:
72: private static class PrioritizedItemIterator implements Iterator {
73:
74: private Iterator iterator;
75:
76: public PrioritizedItemIterator(Iterator iterator) {
77: this .iterator = iterator;
78: }
79:
80: public void remove() {
81: // call iterator.remove()?
82: throw new UnsupportedOperationException();
83: }
84:
85: public boolean hasNext() {
86: return iterator.hasNext();
87: }
88:
89: public Object next() {
90: return ((PrioritizedItem) iterator.next()).value;
91: }
92:
93: }
94:
95: }
|