ITI 1121. Introduction to Computer Science II

For this laboratory there is a class to store an unlimited number of bits: zeros and ones. This class, called BitList, is a linked list to store the bits. Unlike the previous list implementations that we looked at, the values inside the nodes will be ints.

1 BitList

Because most operations on bits work from right to left, your implementation must store the bits in the “right-to-left” order — i.e. with the rightmost bit in the first node of the list.

For example, the bits “11010” must be stored in a list such that the bit 0 is the first, followed by 1, followed by 0, followed by, 1, followed by 1:

2 Iterative

Create a class called Iterative. Implement the methods below. Your solutions must be iterative (i.e. uses iterators).

2.1 static BitList complement( BitList in )

Write a static iterative method that returns a new BitList that is the complement of its input. The complement of 0 is 1, and vice-versa. The complement of a list of bits is a new list such that each bit is the complement of the bit at the same position in the original list. Here are 4 examples.

2.2 static BitList or( BitList a, BitList b )

Write a static iterative method that returns the or of two BitLists. This is a list of the same length as a and b such that each bit is the or of the bits at the equivalent position in the lists a and b. It throws an exception, IllegalArgumentException, if either list is empty or the lists are of different lengths.

Part II
Iterator

3 CircularQueue

This question is about circular queue and iterator. The class CircularQueue uses the implementation technique called “circular array” to implement a fixed-size queue. This class also provides an implementation of an iterator.

public interface Iterator<E> {
    // Returns the next element in the iteration.
    public abstract E next();

    // Returns true if the iteration has more elements.
    public abstract boolean hasNext();
}

public class CircularQueue<E> implements Queue<E> {

    private static final int DEFAULT_CAPACITY = 100;
    private int front, rear, size;
    private E[] elems;

    public CircularQueue( int capacity ) {
            elems = (E[]) new Object[ capacity ];
            front = 0;
            rear = -1;
            size = 0;
    }

    public boolean isEmpty() {
            return ( size == 0 );
    }

    public void enqueue( E value ) {
            rear = ( rear+1 ) % elems.length;
            elems[ rear ] = value;
            size = Math.min( size + 1, elems.length ) ;
    }

    public E dequeue() {
        E savedValue = elems[ front ];
        elems[ front ] = null;
        size--;
        front = ( front+1 ) % elems.length;
        return savedValue;
    }

    private                      CircularQueueIterator implements Iterator<E> {

        private                      current =                     ;

        public E next() {

            if (                                                              ) {
                throw new NoSuchElementException();
            }

            return                                         ;
        }

        public boolean hasNext() {
            boolean result;

            result =                                                                                         ;

            return result;
        }
    } // End of CircularQueueIterator

    public                                iterator() {

        return                                                             ;
    }

} // End of CircularQueue

Part III
LinkedList

4 remove(int from, int to)

Implement the method remove( int from, int to ) for the class LinkedList. This instance method removes all the elements in the specified range from this list and returns a new list that contains all the removed elements, in their original order. The implementation of LinkedList has the following characteristics:

Example: if xs is a reference designating a list containing the following elements [a,b,c,d,e,f], after the method call ys = xs.remove(2,3), the list designated by xs contains [a,b,e,f], and ys designates a list containing [c,d].

You cannot use the methods of the class LinkedList. In particular, you cannot use the methods add() or remove().

Part IV
Quiz

5 Question

For this question, we use the list iterator of Java. This iterator has a method add. Hence, the iterator can add elements to a list.

import java.util.ListIterator;
import java.util.LinkedList;

public class Test {

    public static void main( String[] args ) {

        LinkedList<String> a, b;

        a = new LinkedList<String>();
        b = new LinkedList<String>();

        a.add( "alpha" );
        a.add( "bravo" );
        a.add( "tango" );
        a.add( "charlie" );

        ListIterator<String> i, j;

        i = a.listIterator();
        j = b.listIterator();

        while ( i.hasNext() ) {
            j.add( i.next() );
        }

        System.out.println( a );
        System.out.println( b );

    }
}