SmartList.java

package org.icanttype;

import java.util.Iterator;
import java.util.Random;

/**
 * Created by chris.dombroski on 10/14/2014.
 */
public class SmartList<T extends Comparable<? super T>> {
    private int count = 0;
    private SmartListEntry<T> head;
    private SmartListEntry<T> top;

    public SmartList() {
        head = null;
        top = null;
    }

    public static void main(String... args) throws Exception {
        Random r = new Random();
        SmartList<Integer> list = new SmartList<>();
        int numElements = r.nextInt(40) + 1;
        for (int x = 0; x < numElements; x++) {
            list.push(r.nextInt(2001) - 1000);
        }
        displayList(list);
        int x = r.nextInt(2001) - 1000;
        System.out.println("Removing values greater than: " + x);
        list.removeGreater(x);
        displayList(list);
        int half = list.size() / 2;
        for (int i = 0; i < half; i++) {
            list.pop();
        }
        displayList(list);
    }

    private static void displayList(SmartList<Integer> list) {
        System.out.print("Stack order:");
        for (Iterator<Integer> i = list.stackOrder(); i.hasNext(); ) {
            System.out.print(" " + i.next());
        }
        System.out.println();
        System.out.print("Sorted order:");
        for (Iterator<Integer> i = list.sortOrder(); i.hasNext(); ) {
            System.out.print(" " + i.next());
        }
        System.out.println();
        System.out.flush();
        //DSutils.show(DSTreeParser.from(list.top), 50, 25);
    }

    public void push(T value) {
        count++;
        SmartListEntry<T> o = new SmartListEntry<>(value, head);
        if (head != null) {
            head.prev = o;
            insertValue(o, top);
        } else {
            top = o;
        }
        head = o;
    }

    public T pop() {
        SmartListEntry<T> rtrn = head;
        removeNode(rtrn);
        return rtrn.value;
    }

    public int size() {
        return count;
    }

    public void removeGreater(T value) {
        SmartListEntry<T> ptr = top;

        while (ptr.value.compareTo(value) > 0 && ptr.left != null) {
            ptr = ptr.left;
        }
        if (ptr.up != null) {
            ptr.up.left = null;
            ptr.up = null;
            trimTree(top);
        }
        top = ptr;
        while (ptr.value.compareTo(value) <= 0 && ptr.right != null) {
            ptr = ptr.right;
        }
        while (ptr != null) {
            while (ptr != null && ptr.value.compareTo(value) > 0) {
                if (ptr.right != null) {
                    trimTree(ptr.right);
                }
                ptr = removeNode(ptr);
            }
            if (ptr != null && ptr.right!= null && ptr.right.value.compareTo(value) > 0) {
                ptr = ptr.right;
            } else {
                ptr = null;
            }
        }
    }

    public Iterator<T> stackOrder() {
        return new Iterator<T>() {
            SmartListEntry<T> node = head;

            @Override
            public boolean hasNext() {
                return node != null;
            }

            @Override
            public T next() {
                T val = node.value;
                node = node.next;
                return val;
            }

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

    public Iterator<T> sortOrder() {
        return new Iterator<T>() {
            int returned = 0;
            SmartListEntry<T> node = top;

            {
                while (node.left != null) {
                    node = node.left;
                }
            }

            @Override
            public boolean hasNext() {
                return node != null && returned < count;
            }

            @Override
            public T next() {
                returned++;
                T val = node.value;
                if (node.right != null) {
                    node = node.right;
                    while (node.left != null) {
                        node = node.left;
                    }
                } else if (node.up != null) {
                    node = node.up;
                    while (node.value.compareTo(val) < 0 && node.up != null) {
                        node = node.up;
                    }
                    if (node.value.compareTo(val) < 0) {
                        if (node.right != null && node.right.value.compareTo(val) > 0) {
                            node = node.right;
                            while (node.left != null) {
                                node = node.left;
                            }
                        } else {
                            node = null;
                        }
                    }
                } else {
                    node = null;
                }
                return val;
            }

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

    private void trimTree(SmartListEntry<T> node) {
        if (node.left != null) {
            trimTree(node.left);
        }
        if (node.right != null) {
            trimTree(node.right);
        }
        removeNode(node);
    }

    private SmartListEntry<T> removeNode(SmartListEntry<T> removed) {
        count--;
        //handle stack
        if (removed.prev != null) {
            removed.prev.next = removed.next;
            if (removed.next != null) {
                removed.next.prev = removed.prev;
            }
        } else {
            head = removed.next;
            if (removed.next != null) {
                removed.next.prev = null;
            }
        }
        //handle tree
        SmartListEntry<T> nextNode;
        if (removed.left == null && removed.right != null) {
            nextNode = removed.right;
        } else if (removed.right == null && removed.left != null) {
            nextNode = removed.left;
        } else if (removed.right != null) {
            nextNode = removed.left;
            insertValue(removed.right, removed.left);
        } else {//no decedents
            nextNode = null;
        }

        if (removed.up != null) {
            if (nextNode != null) {
                nextNode.up = removed.up;
            }

            if (removed.up.left == removed) {
                removed.up.left = nextNode;
            } else {
                removed.up.right = nextNode;
            }
        }
        return nextNode;
    }


    private void insertValue(SmartListEntry<T> value, SmartListEntry<T> node) {
        if (value.value.compareTo(node.value) <= 0) {
            if (node.left == null) {
                node.left = value;
                value.up = node;
            } else {
                insertValue(value, node.left);
            }
        } else {
            if (node.right == null) {
                node.right = value;
                value.up = node;
            } else {
                insertValue(value, node.right);
            }
        }
    }

    private static class SmartListEntry<U> /*implements DSTreeNode*/ {
        U value;
        SmartListEntry<U> up;
        SmartListEntry<U> left;
        SmartListEntry<U> right;
        SmartListEntry<U> prev;
        SmartListEntry<U> next;

        SmartListEntry(U value, SmartListEntry<U> next) {
            this.value = value;
            this.next = next;
        }

        /*@Override
        public DSTreeNode[] DSgetChildren() {
            if (left == null && right == null) {
                return new DSTreeNode[0];
            } else {
                return new DSTreeNode[]{left, right};
            }
        }

        @Override
        public Object DSgetValue() {
            return value;
        }

        @Override
        public Color DSgetColor() {
            return null;
        }*/
    }
}