/**
  * 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 with ordered single linked lists.

    Ordered linked lists require a total ordering
    on the key value. This is reflected by the
    constraint on the type variable K.

    This is a PERSISTENT implementation.
*/

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 static ds.util.KV.mkPair;

import ds.util.Function2;
import ds.util.Invariant;
import ds.util.NullIterator;
import ds.util.Pair;
import ds.util.Predicate;

import java.util.Iterator;

import static java.lang.Integer.signum;
import static ds.util.Undef.undefined;

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

public abstract
    class OrderedList
    implements Map {

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

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

    // singleton list
    public static OrderedList singleton(K k, V v) {
	return
	    EMPTY.cons(k, v);
    }

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

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

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

    public abstract OrderedList
	insert(K k, V v);

    public abstract OrderedList
	remove(K k);

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

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

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

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

    public OrderedList copy() {
	return
	    this;
    }

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

    // getter
    Node        node()  { return nodeExpected(); }
    K           key()   { return nodeExpected(); }
    V           value() { return nodeExpected(); }
    OrderedList next()  { return nodeExpected(); }

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

    // cons
    protected
	Node cons(K k, V v) {
	return
	    new Node(k, v, this);
    }

    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 list implemented by applying
    // the singleton design pattern

    // the "generic" empty list object

    private static final OrderedList EMPTY
	= new Empty();

    // the singleton class for the empty list object

    private static final
	class Empty
	extends OrderedList {

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

	public int size() {
	    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>();
	}

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

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

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

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

	Empty() { }

    }

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

    private static final
	class Node
	extends OrderedList {

	/* persistent */
        final K           k;
        final V           v;
        final OrderedList next;

	/* destructive *
	   K           k;
	   V           v;
	   OrderedList next;
	   /**/

        Node(K k, V v, OrderedList next) {
            assert k != null;

            this.k    = k;
            this.v    = v;
            this.next = next;
            ++cntNode;
        }

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

	public boolean isEmpty() {
	    return false;
	}

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

	public V lookup(K k) {
	    assert k != null;

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

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

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

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

	public boolean inv() {
	    if ( next.isEmpty() )
		return
		    true;
	    return
		k.compareTo(next.key()) < 0
		&&
		next.inv();
	}

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

	// getter

	Node        node()  { return this; }
	K           key()   { return k;    }
	V           value() { return v;    }
	OrderedList next()  { return next; }

	// setter

	private Node setNext(OrderedList next) {
	    /* persistent */
	    if ( next == this.next )
		return
		    this;
	    return
		next.cons(this.k, this.v);

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

	private Node setV(V v) {
	    /* persistent */
	    return
		( v == this.v )
		? this
		: next.cons(this.k, v);

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

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

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

	    switch ( signum(k.compareTo(this.k)) ) {
	    case -1: // add to the front
		return
		    this.cons(k, v);
	    case 0: // already there: update value
		return
		    setV(v);
	    case +1: // continue search
		return
		    setNext(next.insert(k, v));
	    }
	    // never executed, but required by javac
	    return
		null;
	}

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

	    switch ( signum(k.compareTo(this.k)) ) {
	    case -1: // not there: nothing to remove
		return
		    this;
	    case 0: // found: remove head of list
		return
		    next;
	    case +1: // continue search
		return
		    setNext(next.remove(k));
	    }
	    // never executed, but required by javac
	    return
		null;
	}

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

	public OrderedList
	    unionWith(Function2<V,V,V> op,
		      Map m2) {
	    if ( m2.isEmpty() )
		return
		    this;

	    Node n2 = ((OrderedList)m2).node();
	    switch ( signum(n2.k.compareTo(this.k)) ) {

	    case -1: // add head of m2 to the front of the result
		return
		    n2.setNext(unionWith(op, n2.next));

	    case 0: // same key, ignore head of m2
		return
		    setV(op.apply(v, n2.v)).setNext(next.unionWith(op, n2.next));

	    case +1: // add head to the result and merge tail with m2
		return
		    setNext(next.unionWith(op, m2));
	    }
	    // never executed, but required by javac
	    return
		null;
	}

	public OrderedList
	    differenceWith(Function2<V,V,V> op,
			   Map m2) {
	    if ( m2.isEmpty() )
		return // nothing to do
		    this;

	    Node n2 = ((OrderedList)m2).node();
	    switch ( signum(n2.k.compareTo(this.k)) ) {

	    case -1: // ignore head of m2
		return
		    unionWith(op, n2.next);

	    case 0: // same key, combine values or remove key
		V                      v1 = op.apply(v, n2.v);
		OrderedList l1 = next.unionWith(op, n2.next);
		if ( v1 == null )
		    return // remove key
			l1;
		return // update value and next
		    setV(v1).setNext(l1);

	    case +1: // take head as it is and continue
		return
		    setNext(next.unionWith(op, m2));
	    }
	    // never executed, but required by javac
	    return
		null;
	}

	/* destructive *
	public OrderedList copy() {
	    return
		next.copy().cons(k, v);
	}
	/**/

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

	// ascending enumeration

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

	    OrderedList queue;

	    NodeIterator(Node n) {
		queue = n;
		++cntIter;
	    }

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

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

		Node n = queue.node();
		queue  = queue.next();
		return
		    mkPair(n.k, n.v);
	    }
	}
    }

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

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

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

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

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