ITI 1121. Introduction to Computer Science II

Laboratory 12

Winter 2014


Part I

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:

-> 0 -> 1 -> 0 -> 1 -> 1

Complete the implementation of the class BitList.

  1. public BitList( String s ); creates a list of bits representing the input string s.

    The given string, s, must be a string of 0s and 1s, otherwise the constructor must throw an exception of type IllegalArgumentException.

    This constructor initializes the new BitList instance to represent the value in the string. Each character in the string represents one bit of the list, with the rightmost character in the string being the low order bit.

    For example, given the string “1010111” the constructor should initialize the new BitList to include this list of bits:

    -> 1 -> 1 -> 1 -> 0 -> 1 -> 0 -> 1

    If given the empty string, the constructor should create an empty list — null is a not a valid argument.

    The constructor must not remove the leading zeroes. For example, given “0001” the constructor must create a list of size 4:

    -> 1 -> 0 -> 0 -> 0

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.

a = 10001  
b = 00011  
a or b = 10011

Part II

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(); 

Complete the implementation of the class CircularQueue.

The template below provides hints for your implementation.

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; 
        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

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().

Hint: draw detailed memory diagrams.

Part IV

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( );  
        System.out.println( a );  
        System.out.println( b );  

What is the result of the execution of the above Java program?

  1. charlie, tango, bravo, alpha
    charlie, tango, bravo, alpha
  2. alpha, bravo, tango, charlie
    alpha, bravo, tango, charlie
  3. charlie, tango, bravo, alpha
    alpha, bravo, tango, charlie
  4. alpha, bravo, tango, charlie
    charlie, tango, bravo, alpha
  5. Runs into an infinite loop

Last Modified: March 26, 2014