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

/** A linked ring is an efficient implementation
    for FIFO buffers (queues).

    A ring is always a destructive data structure,
    every modifying operation changes some references
    in the LinkedRing objects.
 */

import ds.interfaces.List;
import ds.util.NullIterator;
import ds.util.E;
import java.util.Iterator;

import static ds.util.Undef.undefined;

public abstract class LinkedRing
    implements List {

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

    // empty ring
    public static LinkedRing empty() {
	return
	    EMPTY;
    }

    // singleton ring
    public static LinkedRing singleton(E e) {
	return
	    new Node(e);
    }

    // list from iterator
    public static LinkedRing fromIterator(Iterator<E> elems) {
	LinkedRing acc = empty();
	while ( elems.hasNext() ) {
	    E info = elems.next();
	    acc = acc.append(info);
	}
        return
            acc;
    }

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

    public boolean inv() {
	return
	    true;
    }

    public abstract LinkedRing concat(List l2);

    public LinkedRing append(E e) {
        return
            this.concat(singleton(e));
    }

    public LinkedRing cons(E e) {
        return
	    singleton(e).concat(this);
    }

    //----------------------------------------
    // generally usable methods
    // working with iterators

    public E at(int i) {
	Iterator<E> xs = iterator();
	while ( i != 0 ) {
	    xs.next();
	    --i;
	}
	return
	    xs.next();
    }

    public boolean member(E e) {
	for (E x : this)
	    if ( e.equalTo(x) )
		return
		    true;
	return
	    false;
    }

    public int length() {
	int res = 0;
	for (E x : this)
	    ++res;
	return
	    res;
    }

    public LinkedRing copy() {
	LinkedRing res = empty();
	for (E x : this)
	    res = res.append(x);
	return
	    res;
    }

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

    //----------------------------------------
    // the empty ring

    // the "generic" empty ring object

    private static final LinkedRing EMPTY
	= new Empty();

    // the singleton class for the empty list object

    private static final
	class Empty
	extends LinkedRing {

	public boolean isEmpty() {
	    return true;
	}

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

	public int length() {
	    return 0;
	}

	public E head() {
	    return
		undefined("head of empty list");
	}

	public LinkedRing tail() {
	    return
		undefined("tail of empty list");
	}

	public E last() {
	    return
		undefined("last of empty list");
	}

	public LinkedRing init() {
	    return
		undefined("init of empty list");
	}

	public LinkedRing concat(List l2) {
	    // only linked rings are allowed for l2
	    return
		(LinkedRing)l2;
	}
	public LinkedRing reverse() {
	    return
		this;
	}
	public LinkedRing copy() {
	    return
		this;
	}

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

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

	Empty() { }
    }

    // downcast from LinkedRing to Node
    Node node() {
	return
	    undefined("Node expected");
    }

    //----------------------------------------
    // the none empty list class

    private static final
	class Node
	extends LinkedRing {

	public boolean isEmpty() {
	    return false;
	}

	public E head() {
	    return
		next.info;
	}

	public LinkedRing tail() {
	    if ( next == this ) // singleton ring
		return
		    empty();
	    next = next.next;
	    return
		this;
	}

	public E last() {
	    return
		info;
	}

	public LinkedRing init() {
	    if ( next == this ) // singleton ring
		return
		    empty();

	    // search the node in front of this
	    Node cur = this.next.node();
	    while ( cur.next != this ) {
		cur = cur.next.node();
	    }
	    cur.next = this.next;
	    return
		cur;
	}

	public LinkedRing concat(List l2) {
	    // only linked rings are allowed for l2
	    LinkedRing r2 = (LinkedRing)l2;

	    if ( r2.isEmpty() )
		return
		    this;

	    Node n2   = r2.node();
	    Node  t   = n2.next;
	    n2  .next = next;
	    this.next = t;
	    return
		n2;
	}

	public LinkedRing reverse() {
	    Node cur = this.next.node();
	    Node prv = this;
	    while ( cur != this ) {
		Node tmp = cur.next.node();
		cur.next = prv;
		prv      = cur;
                cur      = tmp;
	    }
            Node res = this.next;
	    this.next = prv;
	    return
		res;
	}

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

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

        private E    info;
        private Node next;

        Node(E e) {
            info = e;
            next = this;
            ++cntNode;
        }

	// downcast from LinkedRing to Node
	Node node() {
	    return this;
	}

	// iterator for none empty rings
	private static final
	    class NodeIterator
	    extends ds.util.Iterator<E> {

	    Node    r;
	    Node    cur;
	    boolean first;

	    NodeIterator(Node r) {
		this.r     = r;
		this.cur   = r;
		this.first = true;
	    }

	    public boolean hasNext() {
		return
		    first || r != cur;
	    }

	    public E next() {
		if ( ! hasNext() )
		    return
			undefined("ring exhausted");

		first = false;
		cur   = cur.next;
		return
		    cur.info;
	    }
	}
    }

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

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

    public static String stats() {
        return
            "stats for ds.destructive.list.LinkedRing:\n" +
            "# new Node()         : " + cntNode + "\n" +
            "# new ListIterator() : " + cntIter + "\n";
    }
}