/**
  * 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.map;

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

    Binary search trees require a total ordering
    on the key.
*/

import ds.interfaces.Map;

import ds.util.K;         // example class for keys
import ds.util.V;         // example class for values
import ds.util.KV;        // key value pair
import ds.util.Queue;     // for iterators
import ds.util.Function2;
import ds.util.NullIterator;

import static ds.util.KV.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 BinaryTree
    implements Map {

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

    // empty tree
    public static
	BinaryTree empty() {
	return
	    EMPTY;
    }

    // singleton tree
    public static
	BinaryTree singleton(K k, V v) {
	return
	    new Node(k, v, EMPTY, EMPTY);
    }

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

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

    // smart constructor for building a balanced search tree
    // out of an ascending sorted sequence of values
    // The length of the sequence must be known in advance

    public static
	BinaryTree rebuild(Iterator<KV> elems, int len) {

        if ( len == 0 )
            return EMPTY;

        int lenL = len / 2;
        int lenR = len - lenL - 1;

        BinaryTree l = rebuild(elems, lenL);
        KV         p = elems.next();
        BinaryTree r = rebuild(elems, lenR);

        return
            new Node(p.fst, p.snd, l, r);
    }

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

    public abstract BinaryTree insert(K k, V v);
    public abstract BinaryTree remove(K k);

    public boolean member(K k) {
	return
	    lookup(k) != null;
    }

    public BinaryTree
	union(Map m2) {
	return
	    unionWith(const2, m2);
    }

    // general unionWith by iterating over m2
    // this has poor runtime, Why? O(???)?

    public BinaryTree
	unionWith(Function2<V,V,V> op,
		  Map m2) {
	Iterator<KV> i = m2.iterator();
	BinaryTree res = this;

	while ( i.hasNext() ) {
	    KV kv2 = i.next();
	    K  k2  = kv2.fst;
	    V  v2  = kv2.snd;
	    V  v1  = res.lookup(k2);
	    V  vr  = v1 == null ? v2 : op.apply(v1, v2);
	    res = res.insert(k2, vr);
	}
	return
	    res;
    }

    public BinaryTree
	difference(Map m2) {
	return
	    differenceWith(null2, m2);
    }

    public BinaryTree
	differenceWith(Function2<V,V,V> op,
		       Map m2) {
	// general differenceWith by iterating over m2
	// this has also poor runtime, Why? O(???)

	Iterator<KV> i = m2.iterator();
	BinaryTree res = this;

	while ( i.hasNext() ) {
	    KV kv2 = i.next();
	    K  k2  = kv2.fst;
	    V  v2  = kv2.snd;
	    V  v1  = res.lookup(k2);

	    if ( v1 != null ) { // key found in res
		V  vr  = op.apply(v1, v2);
		if ( vr == null )
		    res = res.remove(k2);
		else
		    res = res.insert(k2, vr);
	    }
	}
	return
	    res;
    }

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

    public BinaryTree copy() {
	return
	    this;
    }

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

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

    public boolean balanced() {
        return
            depth() <= minDepth() + 1;
    }

    public BinaryTree balance() {
        return
            rebuild(iterator(), size());
    }

    // 2. iterator for descending enumeration
    abstract public Iterator<KV> iteratorDesc();

    abstract public Iterator<KV> iteratorBreadthFirst();

    public KV findRoot() {
	return nodeExpected();
    }

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

    // getter
    Node       node()  { return nodeExpected(); }
    K          key()   { return nodeExpected(); }
    V          value() { return nodeExpected(); }
    BinaryTree left()  { return nodeExpected(); }
    BinaryTree right() { return nodeExpected(); }

    // helper for inv
    abstract boolean allLS(K k);
    abstract boolean allGT(K k);

    // helper for union
    // split a tree into letf and right part
    // and optinally a root with key k and attr v
    // here k and v of the result may be null
    abstract Node splitAt(K k);

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

    // helper for ***With functions
    private static Function2<V,V,V> const2
	= new Function2<V,V,V>() {
	public V apply(V x, V y) {
	    return y;
	}
    };

    private static Function2<V,V,V> null2
	= new Function2<V,V,V>() {
	public V apply(V x, V y) {
	    return null;
	}
    };

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

    // the "generic" empty tree object

    private static final BinaryTree EMPTY
	= new Empty();

    // the singleton class for the empty tree object

    private static final
	class Empty
	extends BinaryTree {

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

	public int size() {
	    return 0;
	}

	public int depth() {
	    return 0;
	}

	public int minDepth() {
	    return 0;
	}

	public V lookup(K k) {
	    return null;
	}

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

	public KV findMax() {
	    return nodeExpected();
	}

	public boolean inv() {
	    return true;
	}

	public Iterator<KV> iterator() {
	    ++cntIter;
	    return
		new NullIterator<KV>();
	}

	public Iterator<KV> iteratorDesc() {
	    return
		iterator();
	}

	public Iterator<KV> iteratorBreadthFirst() {
	    return
		iterator();
	}

	// tree manipulation
	public BinaryTree insert(K k, V v) {
	    return
		singleton(k, v);
	}

	public BinaryTree remove(K k) {
	    return
		this;
	}

	public BinaryTree
	    unionWith(Function2<V,V,V> op,
		      Map m2) {
	    return
		(BinaryTree)m2;
	}

	public BinaryTree
	    differenceWith(Function2<V,V,V> op,
			   Map m2) {
	    return
		this;
	}

	public BinaryTree balance() {
	    return
		this;
	}

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

	Empty() { }

	boolean allLS(K k) {
	    return true;
	}
	boolean allGT(K k) {
	    return true;
	}

	Node splitAt(K k) {
	    return
		new Node(null, null, EMPTY, EMPTY);
	}
    }

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

    private static final
	class Node
	extends BinaryTree {

	/* persistent */
        final K          k;
        final V          v;
        final BinaryTree l;
        final BinaryTree r;

	/* destructive *
        K          k;
	V          v;
	BinaryTree l;
	BinaryTree r;
	/**/

        Node(K k, V v, BinaryTree l, BinaryTree r) {
            assert k != null;

            this.k = k;
            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 V lookup(K k) {
	    assert k != null;

	    switch (signum(k.compareTo(this.k))) {
	    case -1:
		return
		    l.lookup(k);
	    case 0:
		return
		    v;
	    case +1:
		return
		    r.lookup(k);
	    }
	    // never executed, but required by javac
	    return
		null;
	}

	public boolean inv() {
	    return
		l.allLS(k)
		&&
		r.allGT(k)
		&&
		l.inv()
		&&
		r.inv();
	}

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

	public KV findRoot() {
	    return
		mkPair(key(), value());
	}


	public KV findMin() {
	    if ( l.isEmpty() )
		return
		    mkPair(k, v);
	    return
		l.findMin();
	}

	public KV findMax() {
	    if ( r.isEmpty() )
		return
		    mkPair(k, v);
	    return
		r.findMax();
	}

	public Iterator<KV> iterator() {
	    return
		new NodeIterator(this);
	}

	public Iterator<KV> iteratorDesc() {
	    return
		new NodeIteratorDescending(this);
	}

	public Iterator<KV> iteratorBreadthFirst() {
	    return
		new NodeIteratorBF(this);
	}
	//----------------------------------------
	// internal methods

	// getter
	Node       node()  { return this; }
	K          key()   { return k; }
	V          value() { return v; }
	BinaryTree left()  { return l; }
	BinaryTree right() { return r; }


	// helper for inv

	boolean allLS(K k) {
	    return
		this.k.compareTo(k) < 0
		&&
		r.allLS(k)
		// &&         // redundant if only
		// l.allLS(k) // used by inv
		;
	}

	boolean allGT(K k) {
	    return
		this.k.compareTo(k) > 0
		&&
		l.allGT(k)
		// &&         // redundant if only
		// r.allGT(k) // used by inv
		;
	}

	// helper for union

 	Node splitAt(K k) {
	    switch ( signum(k.compareTo(this.k)) ) {
	    case -1:
		Node rl = l.splitAt(k);
		return
		    rl.setR(this.setL(rl.r));
	    case  0:
		return
		    this;
	    case +1:
		Node rr = r.splitAt(k);
		return
		    rr.setL(this.setR(rr.l));
	    }
	    // dead code
	    return
		null;
	}


	// setter

	private Node set(K k, V v,
			 BinaryTree l,
			 BinaryTree r) {
	    /* persistent */
	    if ( k == this.k && v == this.v
		 &&
		 l == this.l && r == this.r
		 )
		return
		    this;
	    return
		new Node(k, v, l, r);

	    /* destructive *
	    this.k = k;
	    this.v = v;
	    this.l = l;
	    this.r = r;
	    return
		this;
	    /**/
	}
	private Node setL(BinaryTree l) {
	    /* persistent */
	    if ( l == this.l )
		return
		    this;
	    return
		new Node(this.k, this.v, l, this.r);

	    /* destructive *
	    this.l = l;
	    return
		this;
	    /**/
	}
	private Node setR(BinaryTree r) {
	    /* persistent */
	    if ( r == this.r )
		return
		    this;
	    return
		new Node(this.k, this.v, this.l, r);

	    /* destructive *
	    this.r = r;
	    return
		this;
	    /**/
	}
	private Node setV(V v) {
	    /* persistent */
	    return
		( v == this.v )
		? this
		: new Node(this.k, v, this.l, this.r);

	    /* destructive *
	    this.v = v;
	    return
		this;
	    /**/
	}

	//----------------------------------------
	// tree manipulation

	public BinaryTree insert(K k, V v) {
	    assert k != null;

	    switch ( signum(k.compareTo(this.k)) ) {
	    case -1:
		return
		    setL(l.insert(k,v));
	    case 0:
		return
		    setV(v);
	    case +1:
		return
		    setR(r.insert(k, v));
	    }
	    // never executed, but required by javac
	    return
		null;
	}

	public BinaryTree remove(K k) {
	    assert k != null;

	    switch ( signum(k.compareTo(this.k)) ) {
	    case -1:
		return
		    setL(l.remove(k));
	    case 0:
		return
		    removeRoot();
	    case +1:
		return
		    setR(r.remove(k));
	    }
	    // never executed, but required by javac
	    return
		null;
	}

	private BinaryTree removeRoot() {
	    if ( l.isEmpty() )
		return
		    r;
	    if ( r.isEmpty() )
		return
		    l;

	    // take maximum value in left tree as new root
	    KV         maxL = l.findMax();
	    BinaryTree newL = l.remove(maxL.fst);

	    return
		set(maxL.fst, maxL.snd, newL, r);
	}

	// fast union
	// merging of trees is done with respect to order in m2
	public BinaryTree
	    unionWith(Function2<V,V,V> op,
		      Map m2) {
	    BinaryTree t2 = (BinaryTree)m2;
	    if ( t2.isEmpty() )
		return
		    this;

	    Node splitm2 = t2.splitAt(k);
	    BinaryTree lr = l.unionWith(op, splitm2.l);
	    BinaryTree rr = r.unionWith(op, splitm2.r);
	    V   vr = splitm2.k == null ? v : op.apply(v, splitm2.v);
	    return
		set(k, vr, lr, rr);
	}


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

	//----------------------------------------
	// iterators

	// ascending enumeration

	private static
	    class NodeIterator
	    extends ds.util.Iterator<KV> {

	    Queue queue;

	    NodeIterator(Node n) {
		queue = Queue.empty();
		add(n);
		++cntIter;
	    }

	    void add(Node n) {
		queue = queue.cons(n);
		if ( ! n.l.isEmpty() ) {
		    add(n.l.node()); // downcast
		}
	    }

	    void addSubNodes(Node n) {
		if ( ! n.r.isEmpty() )
		    add(n.r.node());
	    }

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

	    public KV next() {
		if ( queue.isEmpty() )
		    return
			undefined("empty tree");

		Node n = (Node)queue.head();
		queue  = queue.tail();
		addSubNodes(n);
		return
		    mkPair(n.k, n.v);
	    }
	}   // end NodeIterator

	// descending enumeration
	private
	    class NodeIteratorDescending
	    extends NodeIterator {

	    NodeIteratorDescending(Node n) {
		super(n);
	    }

	    void add(Node n) {
		queue = queue.cons(n);
		if ( ! n.r.isEmpty() )
		    add(n.r.node()); // downcast
	    }

	    void addSubNodes(Node n) {
		if ( ! n.l.isEmpty() )
		    add(n.l.node());
	    }
	}   // end NodeIteratorDescending

	// descending enumeration
	private
	    class NodeIteratorBF
	    extends NodeIterator {

	    NodeIteratorBF(Node n) {
		super(n);
	    }

	    void add(Node n) {
		// add the nodes at the bottom
		queue = queue.append(n);
	    }

	    void addSubNodes(Node n) {
		if ( ! n.l.isEmpty() )
		    add(n.l.node());
		if ( ! n.r.isEmpty() )
		    add(n.r.node());
	    }
	}   // end NodeIteratorBF
    }

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

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

    public static String stats() {
	return
	    "stats for ds.persistent.map.BinaryTree:\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.map.BinaryTree object:\n" +
	    "# elements (size)      : " + s + "\n" +
	    "# objects              : " + o + "\n" +
	    "# fields               : " + f + "\n" +
	    "# mem words            : " + m + "\n";
    }
}