package com.thoughtworks.xstream.core.util;

import java.util.Iterator;

/**
 * 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.
 *
 * @author Joe Walnes
 */
public class PrioritizedList {

    /**
     * Start of forward only linked list. Each item contains a value, priority and pointer to next item.
     */
    private LinkedItem first;

    /**
     * Add an item with a default priority of zero.
     */
    public void add(Object item) {
        add(item, 0);
    }

    public void add(Object item, int priority) {
        if (first == null || priority >= first.priority) {
            first = new LinkedItem(item, priority, first);
        } else {
            // Note: this is quite efficient if the client tends to add low priority items before high priority items
            // as it will not have to iterate over much of the list. However for the other way round, maybe some
            // optimizations can be made? -joe
            for (LinkedItem current = first; current != null; current = current.next) {
                if (current.next == null || priority >= current.next.priority) {
                    current.next = new LinkedItem(item, priority, current.next);
                    return;
                }
            }
        }
    }

    public Iterator iterator() {
        return new LinkedItemIterator(first);
    }

    private static class LinkedItem {

        final Object value;
        final int priority;

        LinkedItem next;

        public LinkedItem(Object value, int priority, LinkedItem next) {
            this.value = value;
            this.priority = priority;
            this.next = next;
        }

    }

    private static class LinkedItemIterator implements Iterator {

        private LinkedItem current;

        public LinkedItemIterator(LinkedItem current) {
            this.current = current;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public boolean hasNext() {
            return current != null;
        }

        public Object next() {
            Object result = current.value;
            current = current.next;
            return result;
        }

    }

}

@@ -578,16 +578,223 @@
 t item.%0A
+     * The first item does not contain a value, rather just a pointer to the next real item. This makes%0A     * the add() algorithm easier as there is no special case for adding to the beginning of the list.%0A
      */%0A
@@ -797,32 +797,38 @@
  */%0A    private 
+final 
 LinkedItem first
@@ -822,21 +822,62 @@
 kedItem 
-first
+pointerToFirst = new LinkedItem(null, 0, null)
 ;%0A%0A    /
@@ -1056,147 +1056,8 @@
 ) %7B%0A
-        if (first == null %7C%7C priority %3E= first.priority) %7B%0A            first = new LinkedItem(item, priority, first);%0A        %7D else %7B%0A    
     
@@ -1174,20 +1174,16 @@
         
-   
- 
 // as it
@@ -1283,20 +1283,16 @@
         
-    
 // optim
@@ -1330,17 +1330,8 @@
     
-    for (
 Link
@@ -1351,77 +1351,37 @@
 t = 
-first; current != null; current = current.next) %7B%0A                if 
+pointerToFirst;%0A        while
 (cur
@@ -1394,18 +1394,18 @@
 ext 
-=
+!
 = null 
-%7C%7C
+&&
  pri
@@ -1414,10 +1414,9 @@
 ity 
-%3E=
+%3C
  cur
@@ -1441,32 +1441,66 @@
 ) %7B%0A            
+current = current.next;%0A        %7D%0A
         current.
@@ -1556,78 +1556,8 @@
 t);%0A
-                    return;%0A                %7D%0A            %7D%0A        %7D%0A
     
@@ -1630,20 +1630,34 @@
 terator(
-firs
+pointerToFirst.nex
 t);%0A    

Cleaned up algorithm