/* ITI 1121/1521. Introduction to Computer Science II
 * Assignment/Devoir 3
 *
 *
 */

import java.util.NoSuchElementException;

public class Sequence<E> {

    //  ----------------------------------------------------------
    //  A static nested class to store the elements of the sequence
    //  ----------------------------------------------------------

    private static class Node<E> {
        private E value;
        private Node<E> next;
        private Node( E value, Node<E> next ) {
            this.value = value;
            this.next  = next;
        }
    }

    // Instance variables

    private Node<E> first;
    private Node<E> last;

    // Constructor

    public Sequence() {
        first = null;
        last = null;
    }

    //  ----------------------------------------------------------
    //  Sequence methods
    //  ----------------------------------------------------------

    public void addFirst( E item ) {

        first = new Node<E>( item, first );
        if ( last == null ) { 
            last = first; // the sequence was empty
        }
    }

    public void add( E item ) {

        if ( first == null ) {
            first = new Node<E>( item, null );
            last = first;
        } else {
            last.next = new Node<E>( item, null );
            last = last.next;
        }
    }

    public void deleteFirst() {
        if ( isEmpty() ) {
            throw new NoSuchElementException();
        }

        Node<E> p = first;
        first = first.next;
        if ( first == null ) { 
            last = null; // the sequence is now empty
        }

        p.value = null; // ``scrubbing''
        p.next = null;
    }

    public boolean isEmpty() { 
        return first == null; 
    }

    //  ----------------------------------------------------------
    //  Methods related to recursive processing
    //  ----------------------------------------------------------

    public E head() {
        if ( isEmpty() ) {
            throw new NoSuchElementException();
        }
        return first.value;
    }

    public Sequence<E> split() {
        if ( isEmpty() ) {
            throw new NoSuchElementException();
        }
        Sequence<E> tail = new Sequence<E>();

        tail.first = first.next; // disconnecting the two sequences

        if ( tail.first == null ) {
            tail.last = null;
        } else {
            tail.last = last;
        }

        first.next = null;  // this sequence is a singleton
        last = first;

        return tail;
    }

    public void join( Sequence<E> other ) {

        if ( ! other.isEmpty() ) {
            if ( isEmpty() ) {
                first = other.first;
                last = other.last;
            } else {
                last.next = other.first ;
                last = other.last ;
            }
            other.first = null; // other becomes empty
            other.last  = null;
        }
    }

    //  ----------------------------------------------------------
    //  Other instance methods
    //  ----------------------------------------------------------

    public String toString() {
        StringBuffer answer = new StringBuffer( "[" );
        Node p = first;
        while ( p != null ) {
            if ( p != first ) {
                answer.append( "," );
            }
            answer.append( p.value );
            p = p.next;
        }
        answer.append( "]" );
        return answer.toString();
    }
}