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

/** Implementation of maps by a binary Patricia tree.
    Runtime for lookup, insert and remove is O(1),
    (it does not depend on the size of the map).
    This is guaranted by limiting the depth of the tree
    by the # of bits (32) used for an int value.

    The keys are restricted to int values

    This is a PERSISTENT implementation.
*/

import ds.persistent.genlist.LinkedList;

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 ds.util.Function2;
import ds.util.Invariant;
import ds.util.Pair;
import ds.util.Predicate;
import ds.util.NullIterator;
import ds.util.SingletonIterator;

import static ds.util.K.mkK;
import static ds.util.KV.mkPair;
import static ds.util.Integer.max;
import static ds.util.Integer.min;
import static ds.util.Integer.compareUnsigned;
import static ds.util.Integer.getPrefix;
import static ds.util.Integer.commonPrefixMask;
import static ds.util.Integer.matchPrefix;
import static ds.util.Integer.shorterMask;
import static ds.util.Integer.toStringBS;
import static ds.util.Integer.toStringPX;
import static ds.util.Undef.undefined;

import java.util.Iterator;

import static java.lang.Integer.MIN_VALUE;

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

public abstract
    class IntMap
    implements Map {

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

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

    // singleton tree
    public static
	IntMap singleton(K k, V v) {
        return
            new Leaf(k.intValue(), v);
    }

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

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

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

    public boolean isEmpty() {
	return false;
    }

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

    public V lookup(K k) {
	return
	    lookup1(k.intValue());
    }

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

    public KV findMin()      { return leafExpected(); }
    public KV findMax()      { return leafExpected(); }


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

    abstract public
	IntMap unionWith(Function2<V,V,V> op,
			 Map m2);

    abstract public
	IntMap differenceWith(Function2<V,V,V> op,
			      Map m2);

    public IntMap union(Map m2) {
	Function2<V,V,V> op = new Function2<V,V,V>() {
	    public V apply(V v1, V v2) {
		return
		    v1;
	    }
	};
	return
	    unionWith(op, m2);
    }

    public IntMap difference(Map m2) {
	Function2<V,V,V> op = new Function2<V,V,V>() {
	    public V apply(V v1, V v2) {
		return
		    null;
	    }
	};
	return
	    differenceWith(op, m2);
    }

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

    public IntMap copy() {
	return
	    this;
    }

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

    boolean isLeaf()          { return false; }
    boolean isFork()          { return false; }

    // getter
    K      key()   { return leafExpected(); }
    K      value() { return leafExpected(); }
    IntMap left()  { return forkExpected(); }
    IntMap right() { return forkExpected(); }

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

    abstract V lookup1(int k);

    Fork getFork() { return forkExpected(); }
    Leaf getLeaf() { return leafExpected(); }

    private static <A> A leafExpected() {
        return
            undefined("Leaf expected");
    }
    private static <A> A forkExpected() {
        return
            undefined("Fork expected");
    }

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

    // the "generic" empty list object (with a raw type)

    private static final IntMap EMPTY
        = new Empty();

    // the singleton class for the empty list object

    private static final
        class Empty
        extends IntMap {

        // predicates and attributes
        public boolean isEmpty()   { return true;  }
        public int     size()      { return 0;     }
        public int     depth()     { return 0;     }
        public int     minDepth()  { return 0;     }

        public boolean inv()       { return true; }
        public String  toString()  { return "<empty>"; }

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

	V lookup1(int k) {
	    return
		null;
	}

        public IntMap insert(K k, V v) {
            return
                singleton(k, v);
        }

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

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

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

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

        Empty() { }
    }

    //----------------------------------------
    // the Leaf class for storing a key value pair

    private static final
	class Leaf
	extends IntMap {

        final int k;

        /* persistent */
        final V v;

        /* destructive *
        V v;
        /**/

        Leaf(int k, V v) {
            this.k = k;
            this.v = v;
            ++cntLeaf;
        }

	/* destructive *
	public IntMap copy() {
	    return
		new Leaf(k, v);
	}
	/**/

        public boolean inv()      { return true; }
        public boolean isLeaf()   { return true; }
        public int     depth()    { return 1;     }
        public int     minDepth() { return 1;     }
        public int     size()     { return 1; }

        Leaf getLeaf() { return this; }


        public KV findMin() {
            return
                mkPair(mkK(k), v);
        }

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

        public V lookup1(int k) {
            return
                k == this.k
                ? v
                : (V)null;
        }

        public IntMap insert(K k, V v) {
	    int k0 = k.intValue();

            if ( k0 == this.k ) {
		return
		    setValue(v);
            }
            return
                join(k0, singleton(k, v),
                     this.k, this);
        }

        public IntMap remove(K k) {
            if ( k.intValue() == this.k ) {
                return
                    empty(); // the only place where an empty tree is given back
            }
            return
                this;
        }

        public IntMap unionWith(Function2<V,V,V> op,
				Map m) {
	    IntMap m2 = (IntMap)m;

            // case 1: m2 is empty

            if ( m2.isEmpty() )
                return
                    this;

            // case 2: m2 is a leaf: union of 2 leafs
            // this is the only case where the op is used

            if ( m2.isLeaf() ) {
                Leaf l2 = m2.getLeaf();
                if ( l2.k == this.k )
                    return
                        setValue(op.apply(v, l2.v));

                return
                    join(  l2.k, l2,
                         this.k, this);
            }

            // case 3: m2 is a fork
            // "insert" this.k and this.v into m2

            Fork f2 = m2.getFork();

            if ( ! matchPrefix(k, f2.prefix, f2.mask) )
                return
                    join(k,         this,
                         f2.prefix, f2);

            if ( (k & f2.mask) != 0 )
                return
                    f2.setR(unionWith(op, f2.r));
            return
                f2.setL(unionWith(op, f2.l));
        }

        public IntMap differenceWith(Function2<V,V,V> op,
				     Map m) {
	    IntMap m2 = (IntMap)m;

	    V v2 = m2.lookup1(k);
	    if ( v2 == null ) // not there, do nothing
		return
		    this;

	    V v1 = op.apply(v, v2); // combine values
	    if ( v1 == null ) // remove leaf
		return
		    empty();

	    // update value
	    return
		setValue(v1);
	}

        public Iterator<KV> iterator() {
            return
                new SingletonIterator<KV>(mkPair(mkK(k), v));
        }

        Leaf setValue(V v) {
            /* persistent */
            if ( v == this.v )    // nothing will change
                return
                    this;
            return
                new Leaf(k, v);
            /* destructive *
            this.v = v;
            return
                this;
            /**/
        }
    }

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

    private static
	class Fork
	extends IntMap {

        final int prefix;
        final int mask;

        /* persistent */
        final IntMap l;
        final IntMap r;

        /* destructive *
	   IntMap l;
	   IntMap r;
	   /**/

	Fork(int prefix, int mask, IntMap l, IntMap r) {
	    this.prefix = prefix;
	    this.mask   = mask;
	    this.l      = l;
	    this.r      = r;
	    ++cntFork;
	}

	/* destructive *
	   public IntMap copy() {
	   return
	   new Fork(prefix, mask,
	   l.copy(),
	   r.copy());
	   }
	   /**/


	boolean isFork() {
	    return true;
	}
	Fork getFork() {
	    return this;
	}

	public boolean inv() {
	    return
		! l.isEmpty() && ! r.isEmpty()
		&&
		( compareUnsigned(findMin().fst.intValue(),
				  findMax().fst.intValue()
				  ) < 0 )
		&&
		l.inv()
		&&
		r.inv();
	}

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

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

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

	V lookup1(int k) {
	    if ( matchPrefix(k, prefix, mask) ) {

		IntMap t1 = (k & mask) != 0 ? r : l;
		return
		    t1.lookup1(k);

	    }
	    return
		null;
	}

	public KV findMin() {
	    return
		l.findMin();
	}

	public KV findMax() {
	    return
		r.findMax();
	}

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


	public IntMap insert(K k, V v) {
	    int k0 = k.intValue();

	    if ( ! matchPrefix(k0, prefix, mask) )
		return
		    join(k0, singleton(k, v),
			 prefix, this);

	    if ( (k0 & mask) != 0 )
		return
		    setR(r.insert(k, v));
	    return
		setL(l.insert(k, v));
	}

	public IntMap remove(K k) {
	    int k0 = k.intValue();

	    if ( ! matchPrefix(k0, prefix, mask) )
		return
		    this;
	    if ( (k0 & mask) != 0 ) {
		IntMap r1 = r.remove(k);
		if ( r1.isEmpty() )  // no more fork needed
		    return
			l;
		return
		    setR(r1);
	    } else {
		IntMap l1 = l.remove(k);
		if ( l1.isEmpty() )  // no more fork needed
		    return
			r;
		return
		    setL(l1);
	    }
	}

	public IntMap unionWith(Function2<V,V,V> op,
				Map m) {
	    IntMap m2 = (IntMap)m;

	    // case 1: m2 is empty

	    if ( m2.isEmpty() )
		return
		    this;

	    // case 2: m2 is a leaf

	    if ( m2.isLeaf() ) {
		Leaf l2 = m2.getLeaf();

		// "insert" l2.k and l2.v
		if ( ! matchPrefix(l2.k, prefix, mask) )
		    return
			join(l2.k, l2, prefix, this);

		if ( (l2.k & mask) != 0 )
		    return
			setR(r.unionWith(op, m2));
		return
		    setL(l.unionWith(op, m2));
	    }

	    // case 3: two forks must be merged

	    Fork f2 = m2.getFork();

	    // this fork is nearer by the root than fork f2
	    if ( shorterMask(mask, f2.mask) ) {

		// prefixes don't match, add a fork for storing both subtrees
		if ( ! matchPrefix(f2.prefix, prefix, mask) )
		    return
			join(prefix, this, f2.prefix, f2);

		// prefixes match, merge f2 with lefth or right subtree
		if ( (f2.prefix & mask) == 0 )
		    return
			setL(l.unionWith(op, f2));

		return
		    setR(r.unionWith(op, f2));
	    }

	    // symmetric case, fork f2 is nearer by the root than this
	    if ( shorterMask(f2.mask, mask) ) {
		if ( ! matchPrefix(prefix, f2.prefix, f2.mask) )
		    return
			join(f2.prefix, f2, prefix, this);
		if ( (prefix & f2.mask) == 0 )
		    return
			f2.setL(f2.l.unionWith(op, this));
		return
		    f2.setR(f2.r.unionWith(op, this));
	    }

	    // masks are equal and prefixes are equal
	    // merge left and right subtrees
	    if ( prefix == f2.prefix )
		return
		    setL(l.unionWith(op, f2.l)).
		    setR(r.unionWith(op, f2.r));

	    // prefixes don't match, join them like in the two 1. subcases above
	    return
		join(prefix, this, f2.prefix, f2);
	}

	public IntMap differenceWith(Function2<V,V,V> op,
				     Map m) {
	    IntMap m2 = (IntMap)m;

	    // case 1: m2 is empty

	    if ( m2.isEmpty() )
		return
		    this;

	    // case 2: m2 is a leaf

	    if ( m2.isLeaf() ) {
		Leaf l2 = m2.getLeaf();

		// "delete" l2.k
		if ( ! matchPrefix(l2.k, prefix, mask) )
		    // nothing to delete
		    return
			this;

		// delete l2.k in one of the children
		if ( (l2.k & mask) != 0)
		    return
			setR(r.differenceWith(op, m2));
		return
		    setL(l.differenceWith(op, m2));
	    }

	    // case 3: diff with a fork

	    Fork f2 = m2.getFork();

	    // this for is nearer by the root than fork f2
	    if ( shorterMask(mask, f2.mask) ) {

		// prefixes don't match, nothing to remove
		if ( ! matchPrefix(f2.prefix, prefix, mask) )
		    return
			this;

		// prefixes match, remove elements within one of the children
		if ( (f2.prefix & mask) == 0 )
		    return
			setL(l.differenceWith(op, f2));
		return
		    setR(r.differenceWith(op, f2));

	    }
	    if ( shorterMask(f2.mask, mask) ) {

		// prefixes don't match, nothing to remove
		if ( ! matchPrefix(prefix, f2.prefix, f2.mask) )
		    return
			this;

		// remove all elems given in f2.l
		if ( (prefix & f2.mask) == 0 )
		    return
			differenceWith(op, f2.l);

		// remove all elems given in f2.r
		return
		    differenceWith(op, f2.r);

	    }

	    // masks and prefixes are equal
	    if ( prefix == f2.prefix )
		return
		    setL(l.differenceWith(op, f2.l)).
		    setR(r.differenceWith(op, f2.r));

	    // prefixes don't match, nothing to remove
	    return
		this;
	}

	Fork setL(IntMap l) {
	    /* persistent */
	    if ( l == this.l ) // nothing will change, may occurs with remove
		return
		    this;
	    return
		new Fork(prefix, mask, l, this.r);
	    /* destructive *
               this.l = l;
               return
	       this;
               /**/
	}
	Fork setR(IntMap r) {
	    /* persistent */
	    if ( r == this.r ) // nothing will change, may occurs with remove
		return
		    this;
	    return
		new Fork(prefix, mask, this.l, r);
	    /* destructive *
               this.r = r;
               return
	       this;
               /**/
	}
    }

    private static  IntMap join(int px1, IntMap t1,
				int px2, IntMap t2) {
        int mask = commonPrefixMask(px1, px2);
        int px   = getPrefix(px1, mask);

        if ( (px1 & mask) != 0 )
            return
                new Fork(px, mask, t2, t1);

        return
            new Fork(px, mask, t1, t2);
    }

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

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

	Queue queue;

        IntMapIteratorAscending(Fork f) {
            queue = Queue.empty();
            add(f);
            ++cntIter;
        }

        void add(IntMap m) {
            if ( ! m.isEmpty() )
                queue = queue.cons(m);
        }

        void destruct(Fork f) {
            // insertion is done by taking keys as unsigned int
            // so for the Fork with the sign bit set
            // the subtrees are swapped

            if ( f.mask == MIN_VALUE ) {
                queue = queue.cons(f.l).cons(f.r);
            } else {
                queue = queue.cons(f.r).cons(f.l);
            }
        }

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

        public KV next() {
            if ( queue.isEmpty() )
                return
                    undefined("empty IntMap");
            IntMap m = (IntMap)queue.head();
            queue = queue.tail();
            if ( m.isLeaf() ) {
                Leaf l = m.getLeaf();
                return
                    mkPair(mkK(l.k), l.v);
            }
            assert m.isFork();
            destruct(m.getFork());
            return
                next();
        }
    }

    private static
        class IntMapIteratorDescending
        extends IntMapIteratorAscending {
        IntMapIteratorDescending(Fork f) {
            super(f);
        }

        void destruct(Fork f) {
            if ( f.mask == MIN_VALUE ) {
                queue = queue.cons(f.r).cons(f.l);
            } else {
                queue = queue.cons(f.l).cons(f.r);
            }
        }
    }

    //----------------------------------------
    // test output trees

    static void indent(StringBuffer out, int level) {
        for (int i = 0; i < level; ++i)
            out.append(' ');
    }

    void showIntMap(StringBuffer out, int level) {
        indent(out, level);
        if ( this.isEmpty() ) {
            out.append("Nil\n");
            return;
        }
        if ( this.isLeaf() ) {
            Leaf l = this.getLeaf();
            out.append("\"");
            out.append(toStringBS(l.k));
            out.append("\"\t");
            out.append(l.v.toString());
            out.append("\n");
            return;
        }
        {
            Fork f = this.getFork();
            out.append("\"");
            out.append(toStringPX(f.prefix, f.mask));
            out.append("\"\n");
            f.l.showIntMap(out, level + 2);
            f.r.showIntMap(out, level + 2);
        }
    }

    void showIntMap(StringBuffer out, String s) {
        // out.append(s);
        // out.append(this.toString());
        // out.append("\n");
        showIntMap(out, 0);
        // out.append("\n");
    }

    public String showIntMap() {
        StringBuffer out = new StringBuffer();
        showIntMap(out, "");
        return
            new String(out);
    }

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

    private static int cntFork = 0;
    private static int cntLeaf = 0;
    private static int cntIter = 0;

    public static String stats() {
        return
            "stats for ds.persistent.map.IntMap:\n" +
            "# new Fork()           : " + cntFork + "\n" +
            "# new Leaf()           : " + cntLeaf + "\n" +
            "# new IntMapIterator() : " + cntIter + "\n";
    }

    public String objStats() {
        int s = size();
        int o = s + (s - 1) + 1;   // leafs + forks + anchor
        int l = 2 * s;
        int f = 4 * (s - 1);
        int m = o + 1 + l + f;

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