//                              -*- Mode: Java -*- 
// BitList.java --- data structure to store a sequence of bits (ints)
// Author          : Marcel Turcotte
// Created On      : Fri Apr  9 09:00:27 2004
// Last Modified By: Marcel Turcotte
// Last Modified On: Tue Apr  4 10:06:56 2006

// Unlike the list of the current assignment, this one 1) does not
// detect concurrent modifications and 2) does not start with a dummmy
// node.

import java.util.NoSuchElementException;

// Stores the bits in reverse order!

public class BitList {

    // useful constants

    public static final int ZERO = 0;
    public static final int ONE = 1;

    // instance variables

    private Node first;

    // constructors

    public BitList() {  
        first = null;
    }

    public BitList( String s ) {

        // pre-condition

        if ( s == null ) {
            throw new IllegalArgumentException( "null" );
        }

        for ( int i=0; i < s.length() ; i++ ) {
            int bit = s.charAt(i) - '0';
            if ( ( bit != ZERO ) && ( bit != ONE ) ) {
                throw new IllegalArgumentException( s );
            }
            addFirst( bit ); // reverses the order!
        }
    }

    public void addFirst( int bit ) {

        if ( ( bit != ZERO ) && ( bit != ONE ) ) {
            throw new IllegalArgumentException( Integer.toString( bit ) );
        }

        first = new Node( bit, first );
    }

    public int removeFirst() {

        if ( first == null ) {
            throw new NoSuchElementException();
        }

        int saved = first.bit;

        first = first.next;

        return saved;
    }

    public void complement() {
        if ( first == null ) {
            addFirst( ONE );
        } else {
            complement( first );
        }
    }

    private static void complement( Node p ) {

        // base case

        if ( p == null ) {
            return;
        }

        // pre-processing (could be post as well)

        if ( p.bit == ONE ) {
            p.bit = ZERO;
        } else {
            p.bit = ONE;
        }

        // recursion

        complement( p.next );
    }

//    private void complement( Node p ) {
//
//      if ( p.bit == ONE ) {
//          p.bit = ZERO;
//      } else {
//          p.bit = ONE;
//      }
//      if ( p.next != null ) {
//         complement( p.next );
//      }
//    }

    public BitList or( BitList other ) {

        if ( first == null ) {
            throw new IllegalArgumentException( "this list is empty" );
        }

        if ( other.first == null ) {
            throw new IllegalArgumentException( "other is empty" );
        }

        BitList result;
        result = new BitList();

        or( result, first, other.first );

        return result;
    }

    private static void or( BitList result, Node p, Node q ) {

        // pre-conditions

        if ( p == null && q != null ) {
            throw new IllegalArgumentException( "this list is shorter" );
        }
        if ( p != null && q == null ) {
            throw new IllegalArgumentException( "this list is longer" );
        }
        // base case

        if ( p == null && q == null ) {
            return;
        }
        // recursion

        or( result, p.next, q.next );

        // post-processing

        if ( p.bit == ONE || q.bit == ONE ) {
            result.addFirst( ONE );
        } else {
            result.addFirst( ZERO );
        }
    }

    // alternative implementation

    public BitList or2( BitList other ) {

        if ( first == null ) {
            throw new IllegalArgumentException( "this list is empty" );
        }
        if ( other.first == null ) {
            throw new IllegalArgumentException( "other is empty" );
        }
        BitList result;
        result = new BitList();

        result.first = or2( first, other.first );

        return result;
    }

    private static Node or2( Node p, Node q ) {

        // pre-conditions

        if ( p == null && q != null ) {
            throw new IllegalArgumentException( "this list is shorter" );
        }
        if ( p != null && q == null ) {
            throw new IllegalArgumentException( "this list is longer" );
        }
        // base case

        if ( p == null && q == null ) {
            return null;
        }
        // recursion

        Node res = or2( p.next, q.next );

        // post-processing
        
        int bit;

        if ( p.bit == ONE || q.bit == ONE ) {
            bit = ONE;
        } else {
            bit = ZERO;
        }

        return new Node( bit, res );
    }


    public boolean equals( Object other ) {

        if ( ! ( other instanceof BitList ) ) {
            return false;
        }

        return equals( first, ( (BitList) other ).first );

    }

    private static boolean equals( Node p, Node q ) {

        // Base cases (stopping recursion)

        // Same length?
        if ( p == null && q != null ) {
            return false;
        }
        if ( p != null && q == null ) {
            return false;
        }

        // Reached the end of both lists?
        if ( p == null && q == null ) {
            return true;
        }

        // Found a mismatch?
        if ( p.bit != q.bit ) {
            return false;
        }

        // General case

        return equals( p.next, q.next );
    }

    public Iterator iterator() {
        return new BitListIterator();
    }

    public String toString() {

        String str = "";

        if ( first == null ) {

            str += ZERO;

        } else {

            Node p = first;

            while (p!=null) {
                str = p.bit + str; // reverses the order
                p = p.next;
            }

        }
        return str;
    }

    // The implementation of the nodes (static nested class)

    private static class Node {

        private int bit; // <- NEW
        private Node next;

        private Node( int bit, Node next ) { // <- ACCORDINGLY ...
            this.bit = bit;
            this.next  = next;
        }
    }

    // The implementation of the iterators (inner class)

    private class BitListIterator implements Iterator {

        private Node current = null;

        private BitListIterator() {
            current = null;
        }

        public boolean hasNext() {
            return ( ( current == null && first != null )   ||
                     ( current != null && current.next != null ) );
        }

        public int next() {

            if ( current == null ) {
                current = first ;
            } else {
                current = current.next ; // move the cursor forward
            }
            if ( current == null ) {
                throw new NoSuchElementException() ;
            }
            return current.bit ;
        }

        public void add( int bit ) {

            if ( ( bit != ZERO ) && ( bit != ONE ) ) {
                throw new IllegalArgumentException( Integer.toString( bit ) );
            }

            Node newNode;

            if ( current == null ) {
                first = new Node( bit, first );
                current = first;
            } else {
                current.next = new Node( bit, current.next );
                current = current.next;
            }

        }
    }
}