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

/** Implementation of sets with ordered single linked lists.

    Ordered linked lists require a total ordering
    on the elem domain.

    This is a PERSISTENT implementation.
*/

import ds.interfaces.Set;

import ds.util.E;          // example class for elements
import ds.util.Invariant;

import java.util.Iterator;

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

public abstract
    class OrderedList
    implements Set {

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

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

    // singleton list
    public static OrderedList singleton(E e) {
	return
	    EMPTY.cons(e);
    }

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

	OrderedList res = empty();
        while ( elems.hasNext() ) {
            E e = elems.next();
	    res = res.insert(e);
        }
        return
	    res;
    }

    public abstract OrderedList insert(E e);
    public abstract OrderedList remove(E e);
    public abstract OrderedList union(Set m2);
    public abstract OrderedList intersect(Set m2);
    public abstract OrderedList difference(Set m2);

    public Iterator<E> iterator() {
	++cntIter;
	return
	    new ListIterator(this);
    }

    public OrderedList copy() {
	return
	    this;
    }

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

    // cons
    protected Node cons(E e) {
	return
	    new Node(e, this);
    }

    // access methods, only legal for Node objects
    // not defined for Empty object

    Node        node() { return nodeExpected(); }
    E           elem() { return nodeExpected(); }
    OrderedList next() { return nodeExpected(); }

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

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

    // the 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 {

	public boolean isEmpty() {
	    return true;
	}

	public boolean member(E e) {
	    return false;
	}

	public int size() {
	    return 0;
	}

	public E findMin() {
	    nodeExpected();
	    return null;
	}

	public E findMax() {
	    nodeExpected();
	    return null;
	}

	public OrderedList insert(E e) {
	    return
		singleton(e);
	}

	public OrderedList remove(E e) {
	    return
		this;
	}

	public OrderedList union(Set m2) {
	    return
		(OrderedList)m2;
	}

	public OrderedList intersect(Set m2) {
	    return
		this;
	}

	public OrderedList difference(Set m2) {
	    return
		this;
	}

	public boolean inv() {
	    return true;
	}

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

	Empty() { }

    }

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

    private static final
	class Node
	extends OrderedList {

	/* persistent */
        final E           e;
        final OrderedList next;

	/* destructive *
        E           e;
	OrderedList next;
	/**/

        Node(E e, OrderedList next) {
            assert e    != null;
	    assert next != null;

            this.e    = e;
            this.next = next;
            ++cntNode;
        }

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

	public boolean isEmpty() {
	    return false;
	}

	public boolean member(E e) {
	    assert e != null;

	    switch (signum(e.compareTo(this.e))) {
	    case -1:
		return
		    false;
	    case 0:
		return
		    true;
	    case +1:
		return
		    next.member(e);
	    }
	    // never executed, but required by javac
	    return
		false;
	}

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

	public E findMin() {
	    return e;
	}

	public E findMax() {
	    if ( next.isEmpty() )
		return e;
	    return
		next.findMax();
	}

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

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

	Node        node() { return this; }
	E           elem() { return e;    }
	OrderedList next() { return next; }

	// setter

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

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

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

	public OrderedList insert(E e) {
	    assert e != null;

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

	public OrderedList remove(E e) {
	    assert e != null;

	    switch ( signum(e.compareTo(this.e)) ) {
	    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(e));
	    }
	    // never executed, but required by javac
	    return
		null;
	}

	public OrderedList union(Set m2) {
	    assert m2 != null;

	    OrderedList l2 = (OrderedList)m2;

	    if ( l2.isEmpty() )
		return
		    this;

	    Node n2 = l2.node();
	    switch ( signum(n2.e.compareTo(this.e)) ) {

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

	    case 0: // same elem, ignore head of m2
		return
		    setNext(next.union(n2.next));

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

	public OrderedList intersect(Set m2) {
	    assert m2 != null;

	    OrderedList l2 = (OrderedList)m2;

	    if ( l2.isEmpty() )
		return
		    l2;

	    Node n2 = l2.node();
	    switch ( signum(n2.e.compareTo(this.e)) ) {

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

	    case 0: // head remains in result
		return
		    setNext(next.intersect(n2.next));

	    case +1: // ignore head
		return
		    next.intersect(m2);
	    }
	    // never executed, but required by javac
	    return
		null;
	}

	public OrderedList difference(Set m2) {
	    assert m2 != null;

	    OrderedList l2 = (OrderedList)m2;

	    if ( l2.isEmpty() ) // nothing to do
		return
		    this;

	    Node n2 = l2.node();
	    switch ( signum(n2.e.compareTo(this.e)) ) {

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

	    case 0: // same elem, remove elem
		return
		    next.difference(n2.next);

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

	/* destructive *
	public OrderedList copy() {
	    return
		next.copy().cons(e);
	}
	/**/
    }

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

    // ascending enumeration

    private static
	class ListIterator
	extends ds.util.Iterator<E> {

	OrderedList queue;

	ListIterator(OrderedList n) {
	    assert n != null;

	    queue = n;
	    ++cntIter;
	}

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

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

	    Node n = queue.node();
	    queue  = queue.next();
	    return
		n.e;
	}
    }

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

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

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

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

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