/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

package ds.persistent.queue;

/** Persistent implementation of binary heap tree.
    Operations manipulating trees always create copies
    of the objects to be manipulated. This assures, that
    old trees remains unchanged.

    Binary heap trees require a total ordering
    on the priority value.
*/

import ds.interfaces.PriorityQueue;

import ds.util.P;         // example class for prios
import ds.util.V;         // example class for values
import ds.util.PV;        // prio value pair

import static ds.util.PV.mkPair;
import static ds.util.Integer.max;
import static ds.util.Integer.min;
import static ds.util.Undef.undefined;

import java.util.Iterator;

import static java.lang.Integer.signum;

//----------------------------------------

public abstract
    class BinaryHeap
    implements PriorityQueue {

    //----------------------------------------
    // the smart constructors

    // empty list
    public static
	BinaryHeap empty() {
	return
	    EMPTY;
    }

    // singleton list
    public static
	BinaryHeap singleton(P p, V v) {
	return
	    new Node(p, v, EMPTY, EMPTY);
    }

    // build search tree from arbitrary sequence (iterator)
    public static
	BinaryHeap fromIterator(Iterator<PV> elems) {

	BinaryHeap res = empty();
        while ( elems.hasNext() ) {
            PV p = elems.next();
	    res = res.insert(p.fst, p.snd);
        }
        return
	    res;
    }

    //----------------------------------------
    // public methods

    public abstract BinaryHeap insert(P p, V v);
    public abstract BinaryHeap removeMin();

    public String toString() {
	return
	    iterator().toString();
    }

    public Iterator<PV> iterator() {
	return
	    new HeapIterator(this);
    }

    public BinaryHeap copy() {
	return
	    this;
    }

    //----------------------------------------
    // special binary tree methods

    abstract public int depth();
    abstract public int minDepth();

    //----------------------------------------
    // internal methods

    // helper
    abstract boolean childGE(P p);

    abstract BinaryHeap merge(BinaryHeap h2);
    abstract BinaryHeap merge2(Node n1);

    private static <A> A nodeExpected() {
	return
	    undefined("Node expected");
    }

    //----------------------------------------
    // the empty tree implemented by applying
    // the singleton design pattern

    // the "generic" empty tree object

    private static final BinaryHeap EMPTY
	= new Empty();

    // the singleton class for the empty tree object

    private static final
	class Empty
	extends BinaryHeap {

	// predicates and attributes
	public boolean isEmpty() {
	    return true;
	}

	public int size() {
	    return 0;
	}

	public int depth() {
	    return 0;
	}

	public int minDepth() {
	    return 0;
	}

	public PV findMin() {
	    return nodeExpected();
	}

	public BinaryHeap insert(P p, V v) {
	    return
		singleton(p, v);
	}

	public BinaryHeap removeMin() {
	    return nodeExpected();
	}

	public boolean inv() {
	    return true;
	}

	//----------------------------------------
	// not public stuff

	Empty() { }

	boolean childGE(P p) {
	    return true;
	}

	BinaryHeap merge(BinaryHeap h2) {
	    return h2;
	}
	BinaryHeap merge2(Node n1) {
	    return n1;
	}

    }

    //----------------------------------------
    // the node class for none empty trees

    private static final
	class Node
	extends BinaryHeap {

	/* persistent */
        final P          p;
        final V          v;
        final BinaryHeap l;
        final BinaryHeap r;

	/* destructive *
        P          p;
	V          v;
	BinaryHeap l;
	BinaryHeap r;
	/**/

        Node(P p, V v, BinaryHeap l, BinaryHeap r) {
            assert p != null;

            this.p = p;
            this.v = v;
            this.l = l;
            this.r = r;
            ++cntNode;
        }

	//----------------------------------------
	// predicates and attributes

	public boolean isEmpty() {
	    return false;
	}

	public int size() {
	    return
		1 + l.size() + r.size();
	}

	public int depth() {
	    return
		1 + max(l.depth(), r.depth());
	}

	public int minDepth() {
	    return
		1 + min(l.minDepth(), r.minDepth());
	}

	public PV findMin() {
	    return
		mkPair(p, v);
	}

	public BinaryHeap insert(P p, V v) {
	    return
		this.merge(singleton(p, v));
	}

	public BinaryHeap removeMin() {
	    // forget the root
	    return
		l.merge(r);
	}

	/* destructive *
	public BinaryHeap copy() {
	    return
		new Node(p, v,
                         l.copy(),
                         r.copy());
	}
	/**/

	public boolean inv() {
	    return
		l.childGE(p)
		&&
		r.childGE(p)
		&&
		l.inv()
		&&
		r.inv();
	}

	//----------------------------------------
	// internal methods

	// helper for inv
	boolean childGE(P p) {
	    return
		this.p.compareTo(p) >= 0;
	}

	// the workers: merge and join
	// merge and merge2 simulate double dispatch
	// over both heaps

	BinaryHeap merge(BinaryHeap h2) {
	    return
		h2.merge2(this);
	}

	BinaryHeap merge2(Node n1) {
	    if ( this.p.compareTo(n1.p) <= 0)
		return
		    this.join(n1);
	    return
		n1.join(this);
	}

	BinaryHeap join(Node n2) {
	    return
		setLR(this.r, this.l.merge(n2));
	}

	// setter

	private Node setLR(BinaryHeap l, BinaryHeap r) {
	    /* persistent */
	    if ( l == this.l && r == this.r )
		return
		    this;
	    return
		new Node(this.p, this.v, l, r);

	    /* destructive *
	    this.l = l;
            this.r = r;
	    return
		this;
	    /**/
	}

    } // end Node

    //----------------------------------------
    // iterator
    // ascending enumeration

    private static
	class HeapIterator
	extends ds.util.Iterator<PV> {

	BinaryHeap queue;

	HeapIterator(BinaryHeap n) {
	    /* persistent */
	    queue = n;

	    /* destructive *
	    // we need a copy of the heap,
	    // else the queue is destroied by the iterator
	    queue = n.copy();

	    /**/
	    ++cntIter;
	}

	public boolean hasNext() {
	    return
		! queue.isEmpty();
	}

	public PV next() {
	    if ( queue.isEmpty() )
		return
		    undefined("empty heap");

	    PV res = queue.findMin();
	    queue  = queue.removeMin();
	    return
		res;
	}
    }   // end HeapIterator

    //----------------------------------------
    // profiling

    private static int cntNode = 0;
    private static int cntIter = 0;

    public static String stats() {
	return
	    "stats for ds.persistent.queue.BinaryHeap:\n" +
	    "# new Node()               : " + cntNode + "\n" +
	    "# new Iterator()           : " + cntIter + "\n";
    }

    public String objStats() {
	int s = size();
	int o = s;
	int f = 4 * s;
	int m = o + f;

	return
	    "mem stats for ds.persistent.queue.BinaryHeap object:\n" +
	    "# elements (size)      : " + s + "\n" +
	    "# objects              : " + o + "\n" +
	    "# fields               : " + f + "\n" +
	    "# mem words            : " + m + "\n";
    }
}