package com.thoughtworks.xstream.core.util;

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * List that allows items to be added with a priority that will affect the order in which they are later iterated over.
 *
 * Objects with a high priority will appear before objects with a low priority in the list. If two objects of the same
 * priority are added to the list, the most recently added one will be iterated over first.
 *
 * Implementation uses a TreeSet, which has a garanteed add time of O(log(n)).
 * 
 * @author Joe Walnes
 * @author Guilherme Silveira
 */
public class PrioritizedList {
	
    private final Set set = new TreeSet();

    private int lowestPriority = Integer.MAX_VALUE;
    
    private int lastId = 0;

    public void add(Object item, int priority) {
    	if (this.lowestPriority > priority) {
			this.lowestPriority = priority;
		}
        this.set.add(new PrioritizedItem(item, priority, ++lastId));
    }

    public Iterator iterator() {
        return new PrioritizedItemIterator(this.set.iterator());
    }

    private static class PrioritizedItem implements Comparable {

        final Object value;
        final int priority;
		final int id;

        public PrioritizedItem(Object value, int Prioritized, int id) {
            this.value = value;
            this.priority = Prioritized;
            this.id = id;
        }

		public int compareTo(Object o) {
			PrioritizedItem other = (PrioritizedItem) o;
			if (this.priority != other.priority) {
				return (other.priority - this.priority);
			}
			return (other.id - this.id);
		}
		
		public boolean equals(Object obj) {
			return this.id == ((PrioritizedItem) obj).id; 
		}

    }

    private static class PrioritizedItemIterator implements Iterator {

	private Iterator iterator;

        public PrioritizedItemIterator(Iterator iterator) {
            this.iterator = iterator;
        }

        public void remove() {
            // call iterator.remove()?
            throw new UnsupportedOperationException();
        }

        public boolean hasNext() {
            return iterator.hasNext();
        }

        public Object next() {
            return ((PrioritizedItem)iterator.next()).value;
        }

    }

}

@@ -114,16 +114,17 @@
 eeSet;%0A%0A
+%0A
 /**%0A * L
@@ -239,19 +239,16 @@
 d over.%0A
- *%0A
  * Objec
@@ -453,14 +453,8 @@
 rst.
-%0A *%0A *
  Imp
@@ -471,16 +471,19 @@
 n uses a
+%0A *
  TreeSet
@@ -620,18 +620,17 @@
 dList %7B%0A
-%09
 %0A
+
     priv
@@ -721,13 +721,9 @@
 UE;%0A
-    
 %0A
+
     
@@ -800,17 +800,20 @@
 ) %7B%0A    
-%09
+    
 if (this
@@ -842,19 +842,28 @@
 rity) %7B%0A
-%09%09%09
+            
 this.low
@@ -886,18 +886,24 @@
 iority;%0A
-%09%09
+        
 %7D%0A      
@@ -1199,18 +1199,24 @@
 iority;%0A
-%09%09
+        
 final in
@@ -1404,18 +1404,24 @@
      %7D%0A%0A
-%09%09
+        
 public i
@@ -1445,19 +1445,28 @@
 ct o) %7B%0A
-%09%09%09
+            
 Prioriti
@@ -1502,15 +1502,23 @@
 tem)
- 
 o;%0A
-%09%09%09
+            
 if (
@@ -1556,12 +1556,24 @@
 ) %7B%0A
-%09%09%09%09
+                
 retu
@@ -1613,16 +1613,34 @@
 y);%0A
-%09%09%09%7D%0A%09%09%09
+            %7D%0A            
 retu
@@ -1668,17 +1668,27 @@
 d);%0A
-%09%09%7D%0A%09%09%0A%09%09
+        %7D%0A%0A        
 publ
@@ -1723,11 +1723,20 @@
 ) %7B%0A
-%09%09%09
+            
 retu
@@ -1771,17 +1771,16 @@
 tem)
- 
 obj).id;
  %0A%09%09
@@ -1779,12 +1779,17 @@
 .id;
- %0A%09%09
+%0A        
 %7D%0A%0A 
@@ -1870,9 +1870,16 @@
  %7B%0A%0A
-%09
+        
 priv

Fix strange formatting.