meaningless comment

[ephemerata.git] / KezvhLib / src-lib / net / kezvh / collections / heaps / PairingHeap.java

package net.kezvh.collections.heaps;

import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import net.kezvh.collections.ComparableComparator;
import net.kezvh.collections.MapEntryImpl;
import net.kezvh.development.UnimplementedException;
import net.kezvh.lang.AlgorithmException;

/**
 * @author mjacob
 *
 * see
 * http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm
 * http://en.wikipedia.org/wiki/Pairing_heap
 *
 * @param <E> COMMENT
 * @param <W> COMMENT
 */
public class PairingHeap<E, W extends Comparable<W>> extends AbstractHeap<E, W> {
        /**
         * alright, node now knows 1 child, and is in a circularly linked list with its siblings.
         * either i'm an idiot, or there's no way to remove a node from the tree without knowing
         * your parent is.
         * @author mjacob
         *
         */
        private final class PairingHeapNode extends MapEntryImpl<E, W> implements Comparable<PairingHeapNode> {
                private PairingHeapNode child = null;
                private PairingHeapNode nextSibling = null;
                private PairingHeapNode previousSibling = null;
                private PairingHeapNode parent = null;

                public PairingHeapNode(final E key, final W value) {
                        super(key, value);
                }

                @Override
                public W setValue(final W arg0) {
                        return this.setImplValue(arg0);
                }

                /**
                 * any parent/siblings defined in the newchild will be overriden
                 * @param newChild the new child
                 */
                public void addChild(final PairingHeapNode newChild) {
                        if (newChild == this)
                                throw new AlgorithmException();

                        newChild.parent = this;
                        if (this.child == null)
                                this.child = newChild.previousSibling = newChild.nextSibling = newChild;
                        else { // insert before child (@ end of loop)
                                newChild.nextSibling = this.child;
                                newChild.previousSibling = this.child.previousSibling;
                                this.child.previousSibling.nextSibling = newChild;
                                this.child.previousSibling = newChild;
                        }
                }

                @Override
                public int compareTo(final PairingHeapNode o) {
                        return PairingHeap.this.comparator.compare(this.getValue(), o.getValue());
                }

                /**
                 * @return the next sibling after the two merged nodes
                 */
                public PairingHeapNode mergeWithSibling() {
                        if (this.nextSibling == this)
                                return this;

                        final PairingHeapNode mergeParent = this.parent; // we won't be able to rely on the "this" pointer after the merge
                        final PairingHeapNode oldSibling = this.nextSibling; // the sibling to merge with
                        final PairingHeapNode mergeNext = oldSibling.nextSibling;

                        if (this == mergeNext) {
                                // this and oldSibling are the only two children
                                final PairingHeapNode newNode = PairingHeap.this.merge(this, oldSibling);

                                newNode.previousSibling = newNode.nextSibling = newNode;
                                mergeParent.child = newNode;
                        } else {
                                final boolean first = (this.parent.child == this || this.parent.child == oldSibling); // wheter we need to reset the parent's child after we merge
                                final PairingHeapNode mergePrevious = this.previousSibling; // we'll need to reset the "next" value on this

                                final PairingHeapNode newNode = PairingHeap.this.merge(this, oldSibling);

                                if (first) // we might have merged the child the parent knew about lower into the tree
                                        mergeParent.child = newNode;

                                newNode.previousSibling = mergePrevious;
                                newNode.nextSibling = mergeNext;

                                mergePrevious.nextSibling = mergeNext.previousSibling = newNode;
                        }
                        return mergeNext;
                }

                public PairingHeapNode getChild() {
                        return this.child;
                }

                public boolean hasMultipleChildren() {
                        return this.child != null && this.child != this.child.nextSibling;
                }

                public void setAsRoot() {
                        this.parent = null;
                }

                public void pruneSelf() {
                        if (this.parent.child == this) // removing the first child
                                if (this.nextSibling == this) // removing the only child
                                        this.parent.child = null;
                                else
                                        this.parent.child = this.nextSibling; // if there's more than 1 child, have parent point to the next one
                        if (this.nextSibling != this) { // we need to close the loop.
                                this.nextSibling.previousSibling = this.previousSibling;
                                this.previousSibling.nextSibling = this.nextSibling;
                        }
                        this.parent = null;
                        this.nextSibling = this.previousSibling = this;
                }

                @Override
                public String toString() {
                        return "node " + this.getKey() + " (" + this.getValue() + ")";
                }

                /**
                 * debug method
                 *
                 * @param prefix COMMENT
                 * @param loopStart COMMENT
                 * @param termination COMMENT
                 */
                public void printTree(final String prefix, final PairingHeapNode loopStart, final int termination) {
                        if (termination == 0)
                                throw new AlgorithmException();
                        System.out.println(prefix + this);
                        if (this.child != null)
                                this.child.printTree(" " + prefix, null, termination - 1);
                        if (this.nextSibling != loopStart && this.nextSibling != this)
                                this.nextSibling.printTree(prefix, loopStart == null ? this : loopStart, termination - 1);
                }
        }

        private PairingHeapNode root;
        private final Map<E, PairingHeapNode> map = new HashMap<E, PairingHeapNode>();
        private final Comparator<? super W> comparator;

        /**
         *
         */
        public PairingHeap() {
                this(new ComparableComparator<W>());
        }

        /**
         * @param comparator COMMENT
         */
        public PairingHeap(final Comparator<? super W> comparator) {
                this.comparator = comparator;
        }

        @Override
        public void merge(final Heap<E, W> other) {
                if (other == null || this.getClass() != other.getClass())
                        throw new IllegalArgumentException();

                final PairingHeap<E, W> otherHeap = (PairingHeap<E, W>) other;
                this.root = this.merge(this.root, otherHeap.root);
                this.map.putAll(otherHeap.map);
                otherHeap.clear();
        }

        /* assuming that remove() removes the minimum element; thus, we assume we do the usual
         * heap thing if the new weight is "less than" the current weight
         *
         * (non-Javadoc)
         * @see net.kezvh.collections.heaps.Heap#reweight(java.lang.Object, java.lang.Object)
         */
        @Override
        public W reweight(final E t, final W newWeight) {
                if (!(this.map.containsKey(t)))
                        throw new IllegalArgumentException("element " + t + " must be in the heap in order to reweight it");

                final PairingHeapNode node = this.map.get(t);
                final W oldWeight = node.getValue();

                try {
                        return node.setValue(newWeight);
                } finally {
                        if (this.root == node) {
                                if (this.size() != 1)
                                        if (this.comparator.compare(newWeight, oldWeight) > 0)
                                                throw new UnimplementedException("haven't yet implemented increasing the root node's weight (node " + t + " old weight: " + oldWeight + " new eight: " + newWeight);
                        } else {
                                node.pruneSelf();
                                this.root = this.merge(this.root, node);
                        }
                }
        }

        private PairingHeapNode merge(final PairingHeapNode a, final PairingHeapNode b) {
                if (a == null)
                        return b;
                if (b == null)
                        return a;
                if (a.compareTo(b) <= 0) {
                        a.addChild(b);
                        return a;
                }
                b.addChild(a);
                return b;
        }

        @Override
        public W add(final E t, final W weight) {
                if (this.map.containsKey(t))
                        return this.reweight(t, weight);

                final PairingHeapNode newNode = new PairingHeapNode(t, weight);
                this.root = this.merge(this.root, newNode);
                this.map.put(t, newNode);
                return null;
        }

        @Override
        public E peek() {
                if (this.root == null)
                        return null;
                return this.root.getKey();
        }

        /**
         * this can do 1 of 3 things
         * 1) iterate over the heap out of order (easy)
         * 2) destroy the heap as you iterate (easy)
         * 3) clone the heap, destroy that as you iterate (harder)
         */
        @Override
        public Iterator<E> iterator() {
                throw new UnimplementedException(); // FIXME
        }

        @Override
        public void clear() {
                this.map.clear();
                this.root = null;
        }

        @Override
        public boolean contains(final Object o) {
                return this.map.containsKey(o);
        }

        @Override
        public boolean containsAll(final Collection<?> c) {
                return this.map.entrySet().containsAll(c);
        }

        @Override
        public boolean isEmpty() {
                return this.map.isEmpty();
        }

        @Override
        public E remove() {
                try {
                        final E minValue = this.root.getKey();
                        this.map.remove(minValue);
                        return minValue;
                } finally {
                        PairingHeapNode nextNode = this.root.getChild();
                        while (this.root.hasMultipleChildren())
                                nextNode = nextNode.mergeWithSibling(); // the value retured is the node AFTER the two that were merged
                        this.root = this.root.getChild();
                        if (this.root != null)
                                this.root.setAsRoot();
                }
        }

        /**
         * this should be easy.
         * basically, you prune the node for the object, the removeMin() from that tree, then join.
         */
        @Override
        public boolean remove(final Object o) {
                throw new UnimplementedException(); // FIXME
        }

        @Override
        public int size() {
                return this.map.size();
        }

        @Override
        public Comparator<? super W> comparator() {
                return this.comparator;
        }
}