Appendix D. Answers to Exercises

The solutions provided in this appendix are sample answers. Not every chapter had exercises at the end, but it is hoped that the ones provided will give you ample opportunity to put what you've learned into practice. We encourage you to experiment with each chapter's concepts.

Exercises

  1. Create an iterator that only returns the value of every nth element, where n is any integer greater than zero.

  2. Create a predicate that performs a Boolean AND (&&) of two other predicates.

  3. Re-implement PowerCalculator using recursion instead of iteration.

  4. Replace the use of arrays with iterators in the recursive directory tree printer.

  5. Create an iterator that holds only a single value.

  6. Create an empty iterator that is always done.

Exercise 1 Solution

package com.wrox.algorithms.iteration;

public class SkipIterator implements Iterator {
    private final Iterator _iterator;
    private final int _skip;

    public SkipIterator(Iterator iterator, int skip) {
        assert iterator != null : "iterator can't be null";
        assert skip > 0 : "skip can't be < 1";
        _iterator = iterator;
        _skip = skip;
    }

    public void first() {
        _iterator.first();
skipForwards();
    }

    public void last() {
        _iterator.last();
        skipBackwards();
    }

    public boolean isDone() {
        return _iterator.isDone();
    }

    public void next() {
        _iterator.next();
        skipForwards();
    }

    public void previous() {
        _iterator.previous();
        skipBackwards();
    }

    public Object current() throws IteratorOutOfBoundsException {
        return _iterator.current();
    }

    private void skipForwards() {
        for (int i = 0; i < _skip && !_iterator.isDone(); _iterator.next());
    }

    private void skipBackwards() {
        for (int i = 0; i < _skip && !_iterator.isDone(); _iterator.previous());
    }
}

Exercise 2 Solution

package com.wrox.algorithms.iteration;

public final class AndPredicate implements Predicate {
    private final Predicate _left;
    private final Predicate _right;

    public AndPredicate(Predicate left, Predicate right) {
        assert left != null : "left can't be null";
        assert right != null : "right can't be null";

        _left = left;
        _right = right;
    }

    public boolean evaluate(Object object) {
        return _left.evaluate(object) && _right.evaluate(object);
    }
}

Exercise 3 Solution

package com.wrox.algorithms.iteration;

public final class RecursivePowerCalculator implements PowerCalculator {
    public static final PowerCalculator INSTANCE = new PowerCalculator();

    private RecursivePowerCalculator() {
    }

    public int calculate(int base, int exponent) {
        assert exponent >= 0 : "exponent can't be < 0";

        return exponent > 0 ? base * calculate(base, exponent − 1) : 1;
    }
}

Exercise 4 Solution

package com.wrox.algorithms.iteration;

import java.io.File;

public final class RecursiveDirectoryTreePrinter {
    private static final String SPACES = "  ";

    public static void main(String[] args) {
        assert args != null : "args can't be null";

        if (args.length != 1) {
            System.err.println("Usage: RecursiveDirectoryTreePrinter <dir>");
            System.exit(4);
        }

        System.out.println("Recursively printing directory tree for: " + args[0]);
        print(new File(args[0]), "");
    }

    private static void print(Iterator files, String indent) {
        assert files != null : "files can't be null";

        for (files.first(); !files.isDone(); files.next()) {
            print((File) files.current(), indent);
        }
    }

    private static void print(File file, String indent) {
        assert file != null : "file can't be null";
        assert indent != null : "indent can't be null";

        System.out.print(indent);
        System.out.println(file.getName());

        if (file.isDirectory()) {
print(new ArrayIterator(file.listFiles()), indent + SPACES);
        }
    }
}

Exercise 5 Solution

package com.wrox.algorithms.iteration;

public class SingletonIterator implements Iterator {
    private final Object _value;
    private boolean _done;

    public SingletonIterator(Object value) {
        assert value != null : "value can't be null";
        _value = value;
    }

    public void first() {
        _done = false;
    }

    public void last() {
        _done = false;
    }

    public boolean isDone() {
        return _done;
    }

    public void next() {
        _done = true;
    }

    public void previous() {
        _done = true;
    }

    public Object current() throws IteratorOutOfBoundsException {
        if (isDone()) {
            throw new IteratorOutOfBoundsException();
        }
        return _value;
    }
}

Exercise 6 Solution

package com.wrox.algorithms.iteration;

public final class EmptyIterator implements Iterator {
    public static final EmptyIterator INSTANCE = new EmptyIterator();

    private EmptyIterator() {
// Nothing to do
    }

    public void first() {
        // Nothing to do
    }

    public void last() {
        // Nothing to do
    }

    public boolean isDone() {
        // We're always done!
        return true;
    }

    public void next() {
        // Nothing to do
    }

    public void previous() {
        // Nothing to do
    }

    public Object current() throws IteratorOutOfBoundsException {
        throw new IteratorOutOfBoundsException();
    }
}

Exercises

  1. Write a constructor for ArrayList that accepts a standard Java array to initially populate the List.

  2. Write an equals() method that will work for any List implementation.

  3. Write a toString() method that will work for any List implementation that prints the contents as a single line with values surrounded by square brackets and separated by commas. For example, "[A, B, C]" or "[]" for an empty List.

  4. Create an Iterator that will work for any List implementation. What are the performance implications?

  5. Update LinkedList to traverse backwards if, when inserting and deleting, the desired index is more than halfway along the list.

  6. Rewrite indexOf() so that it will work for any List.

  7. Create a List implementation that is always empty and throws UnsupportedOperationException if an attempt is made to modify it.

Exercise 1 Solution

public ArrayList(Object[] array) {
        assert array != null : "array can't be null";

        _initialCapacity = array.length;
        clear();

        System.arraycopy(array, 0, _array, 0, array.length);
        _size = array.length;
    }

Exercise 2 Solution

public boolean equals(Object object) {
        return object instanceof List ? equals((List) object) : false;
    }

    public boolean equals(List other) {
        if (other == null || size() != other.size()) {
            return false;
        }

        Iterator i = iterator();
        Iterator j = other.iterator();

        for (i.first(), j.first();
            !i.isDone() && !j.isDone(); i.next(),
            j.next()) {

            if (!i.current().equals(j.current())) {
                break;
            }
        }

        return i.isDone() && j.isDone();
    }

Exercise 3 Solution

public String toString() {
        StringBuffer buffer = new StringBuffer();

        buffer.append('[');

        if (!isEmpty()) {
            Iterator i = iterator();
            for (i.first(); !i.isDone(); i.next()) {
                buffer.append(i.current()).append(", ");
            }

            buffer.setLength(buffer.length() - 2);
}

        buffer.append(']');

        return buffer.toString();
    }

Exercise 4 Solution

package com.wrox.algorithms.lists;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.iteration.IteratorOutOfBoundsException;

public class GenericListIterator implements Iterator {
    private final List _list;
    private int _current;

    public GenericListIterator(List list) {
        assert list != null : "list can't be null";
        _list = list;
    }

    public void first() {
        _current = 0;
    }

    public void last() {
        _current = _list.size() − 1;
    }

    public boolean isDone() {
        return _current < 0 || _current >= _list.size();
    }

    public void next() {
        ++_current;
    }

    public void previous() {
        −−_current;
    }

    public Object current() throws IteratorOutOfBoundsException {
        if (isDone()) {
            throw new IteratorOutOfBoundsException();
        }
        return _list.get(_current);
    }
}

Exercise 5 Solution

private Element getElement(int index) {
        if (index < _size / 2) {
            return getElementForwards(index);
        } else {
            return getElementBackwards(index);
        }
    }

    private Element getElementForwards(int index) {
        Element element = _headAndTail.getNext();

        for (int i = index; i > 0; −−i) {
            element = element.getNext();
        }

        return element;
    }

    private Element getElementBackwards(int index) {
        Element element = _headAndTail;

        for (int i = _size - index; i > 0; −−i) {
            element = element.getPrevious();
        }

        return element;
    }

Exercise 6 Solution

public int indexOf(Object value) {
        assert value != null : "value can't be null";

        int index = 0;
        Iterator i = iterator();

        for (i.first(); !i.isDone(); i.next()) {
            if (value.equals(i.current())) {
                return index;
            }

            ++index;
        }

        return −1;
    }

Exercise 7 Solution

package com.wrox.algorithms.lists;

import com.wrox.algorithms.iteration.EmptyIterator;
import com.wrox.algorithms.iteration.Iterator;

public final class EmptyList implements List {
public static final EmptyList INSTANCE = new EmptyList();

    private EmptyList() {
    }

    public void insert(int index, Object value)
            throws IndexOutOfBoundsException {
        throw new UnsupportedOperationException();
    }

    public void add(Object value) {
        throw new UnsupportedOperationException();
    }

    public Object delete(int index) throws IndexOutOfBoundsException {
        throw new UnsupportedOperationException();
    }

    public boolean delete(Object value) {
        throw new UnsupportedOperationException();
    }

    public void clear() {
    }

    public Object set(int index, Object value)
            throws IndexOutOfBoundsException {
        throw new UnsupportedOperationException();
    }

    public Object get(int index) throws IndexOutOfBoundsException {
        throw new UnsupportedOperationException();
    }

    public int indexOf(Object value) {
        return −1;
    }

    public boolean contains(Object value) {
        return false;
    }

    public int size() {
        return 0;
    }

    public boolean isEmpty() {
        return true;
    }

    public Iterator iterator() {
        return EmptyIterator.INSTANCE;
    }
}

Exercises

  1. Implement a thread-safe queue that performs no waiting. Sometimes all you need is a queue that will work in a multi-threaded environment without the blocking.

  2. Implement a queue that retrieves values in random order. This could be used for dealing cards from a deck or any other random selection process.

Exercise 1 Solution

package com.wrox.algorithms.queues;

public class SynchronizedQueue implements Queue {
    private final Object _mutex = new Object();
    private final Queue _queue;

    public SynchronizedQueue(Queue queue) {
        assert queue != null : "queue can't be null";
        _queue = queue;
    }

    public void enqueue(Object value) {
        synchronized (_mutex) {
            _queue.enqueue(value);
        }
    }

    public Object dequeue() throws EmptyQueueException {
        synchronized (_mutex) {
            return _queue.dequeue();
        }
    }

    public void clear() {
        synchronized (_mutex) {
            _queue.clear();
        }
    }

    public int size() {
        synchronized (_mutex) {
            return _queue.size();
        }
    }

    public boolean isEmpty() {
        synchronized (_mutex) {
            return _queue.isEmpty();
        }
    }
}

Exercise 2 Solution

package com.wrox.algorithms.queues;

import com.wrox.algorithms.lists.LinkedList;
import com.wrox.algorithms.lists.List;

public class RandomListQueue implements Queue {
    private final List _list;

    public RandomListQueue() {
        this(new LinkedList());
    }

    public RandomListQueue(List list) {
        assert list != null : "list can't be null";
        _list = list;
    }

    public void enqueue(Object value) {
        _list.add(value);
    }

    public Object dequeue() throws EmptyQueueException {
        if (isEmpty()) {
            throw new EmptyQueueException();
        }
        return _list.delete((int) (Math.random() * size()));
    }

    public void clear() {
        _list.clear();
    }

    public int size() {
        return _list.size();
    }

    public boolean isEmpty() {
        return _list.isEmpty();
    }
}

Exercises

  1. Write a test to prove that each of the algorithms can sort a randomly generated list of double objects.

  2. Write a test to prove that the bubble sort and insertion sort algorithms from this chapter are stable.

  3. Write a comparator that can order strings in dictionary order, with uppercase and lowercase letters considered equivalent.

  4. Write a driver program to determine how many objects are moved by each algorithm during a sort operation.

Exercise 1 Solution

public class ListSorterRandomDoublesTest extends TestCase {
private static final int TEST_SIZE = 1000;

    private final List _randomList = new ArrayList(TEST_SIZE);
    private final NaturalComparator _comparator = NaturalComparator.INSTANCE;

    protected void setUp() throws Exception {
        super.setUp();

        for (int i = 1; i < TEST_SIZE; ++i) {
            _randomList.add(new Double((TEST_SIZE * Math.random())));
        }
    }

    public void testsortingRandomDoublesWithBubblesort() {
        ListSorter listSorter = new BubblesortListSorter(_comparator);
        List result = listSorter.sort(_randomList);
        assertSorted(result);
    }

    public void testsortingRandomDoublesWithSelectionsort() {
        ListSorter listSorter = new SelectionSortListSorter(_comparator);
        List result = listSorter.sort(_randomList);
        assertSorted(result);
    }

    public void testsortingRandomDoublesWithInsertionsort() {
        ListSorter listSorter = new InsertionSortListSorter(_comparator);
        List result = listSorter.sort(_randomList);
        assertSorted(result);
    }

    private void assertSorted(List list) {
        for (int i = 1; i < list.size(); i++) {
            Object o = list.get(i);
            assertTrue(_comparator.compare(list.get(i − 1), list.get(i)) <= 0);
        }
    }
}

Exercise 2 Solution

import com.wrox.algorithms.lists.ArrayList;
import com.wrox.algorithms.lists.List;
import junit.framework.TestCase;

public class ListSorterStabilityTest extends TestCase {
private static final int TEST_SIZE = 1000;

    private final List _list = new ArrayList(TEST_SIZE);
    private final Comparator _comparator = new FractionComparator();

    protected void setUp() throws Exception {
        super.setUp();

        for (int i = 1; i < TEST_SIZE; ++i) {
            _list.add(new Fraction(i % 20, i));
        }
    }

    public void testStabilityOfBubblesort() {
        ListSorter listSorter = new BubblesortListSorter(_comparator);
        List result = listSorter.sort(_list);
        assertStableSorted(result);
    }

    public void testStabilityOfInsertionsort() {
        ListSorter listSorter = new InsertionSortListSorter(_comparator);
        List result = listSorter.sort(_list);
        assertStableSorted(result);
    }

    private void assertStableSorted(List list) {
        for (int i = 1; i < list.size(); i++) {
            Fraction f1 = (Fraction) list.get(i − 1);
            Fraction f2 = (Fraction) list.get(i);
            if(!(f1.getNumerator() < f2.getNumerator()
                    || f1.getDenominator() < f2.getDenominator())) {
                fail("what?!");
            }
        }
    }

    private static class Fraction {
        private final int _numerator;
        private final int _denominator;

        public Fraction(int numerator, int denominator) {
            _numerator = numerator;
            _denominator = denominator;
        }

        public int getNumerator() {
            return _numerator;
        }

        public int getDenominator() {
            return _denominator;
        }
    }

    private static class FractionComparator implements Comparator {
public int compare(Object left, Object right) throws ClassCastException {
            return compare((Fraction) left, (Fraction) right);
        }

        private int compare(Fraction l, Fraction r) throws ClassCastException {
            return l.getNumerator() - r.getNumerator();
        }
    }
}

Exercise 3 Solution

public final class CaseInsensitiveStringComparator implements Comparator {
    public int compare(Object left, Object right) throws ClassCastException {
        assert left != null : "left can't be null";
        assert right != null : "right can't be null";

        String leftLower = ((String) left).toLowerCase();
        String rightLower = ((String) right).toLowerCase();
        return leftLower.compareTo(rightLower);
    }
}

Exercise 4 Solution

public class ListSorterCallCountingListTest extends TestCase {
    private static final int TEST_SIZE = 1000;

    private final List _sortedArrayList = new ArrayList(TEST_SIZE);
    private final List _reverseArrayList = new ArrayList(TEST_SIZE);
    private final List _randomArrayList = new ArrayList(TEST_SIZE);

    private Comparator _comparator = NaturalComparator.INSTANCE;

    protected void setUp() throws Exception {
        super.setUp();

        for (int i = 1; i < TEST_SIZE; ++i) {
            _sortedArrayList.add(new Integer(i));
        }

        for (int i = TEST_SIZE; i > 0; −−i) {
            _reverseArrayList.add(new Integer(i));
        }

        for (int i = 1; i < TEST_SIZE; ++i) {
            _randomArrayList.add(new Integer((int)(TEST_SIZE * Math.random())));
        }
    }

    public void testWorstCaseBubblesort() {
        List list = new CallCountingList(_reverseArrayList);
        new BubblesortListSorter(_comparator).sort(list);
        reportCalls(list);
}

    public void testWorstCaseSelectionSort() {
        List list = new CallCountingList(_reverseArrayList);
        new SelectionSortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testWorstCaseInsertionSort() {
        List list = _reverseArrayList;
        List result = new CallCountingList(new ArrayList());
        new InsertionSortListSorter(_comparator).sort(list, result);
        reportCalls(result);
    }

    public void testBestCaseBubblesort() {
        List list = new CallCountingList(_sortedArrayList);
        new BubblesortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testBestCaseSelectionSort() {
        List list = new CallCountingList(_sortedArrayList);
        new SelectionSortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testBestCaseInsertionSort() {
        List list = _sortedArrayList;
        List result = new CallCountingList(new ArrayList());
        new InsertionSortListSorter(_comparator).sort(list, result);
        reportCalls(result);
    }

    public void testAverageCaseBubblesort() {
        List list = new CallCountingList(_randomArrayList);
        new BubblesortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testAverageCaseSelectionSort() {
        List list = new CallCountingList(_randomArrayList);
        new SelectionSortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testAverageCaseInsertionSort() {
        List list = _randomArrayList;
        List result = new CallCountingList(new ArrayList());
        new InsertionSortListSorter(_comparator).sort(list, result);
        reportCalls(result);
    }

    private void reportCalls(List list) {
System.out.println(getName() + ": " + list);
    }
}

Exercises

  1. Implement mergesort iteratively, rather than recursively.

  2. Implement quicksort iteratively, rather than recursively.

  3. Count the number of list manipulations (for example, set(), add(), insert()) during quicksort and shellsort.

  4. Implement an in-place version of insertion sort.

  5. Create a version of quicksort that uses insertion sort for sublists smaller than five items.

Exercise 1 Solution

public class IterativeMergesortListSorter implements ListSorter {
    private final Comparator _comparator;

    public IterativeMergesortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }

    public List sort(List list) {
        assert list != null : "list cannot be null";

        return mergeSublists(createSublists(list));
    }

    private List mergeSublists(List sublists) {
        List remaining = sublists;
        while (remaining.size() > 1) {
            remaining = mergeSublistPairs(remaining);

        }
        return (List) remaining.get(0);
    }

    private List mergeSublistPairs(List remaining) {
        List result = new ArrayList(remaining.size() / 2 + 1);

        Iterator i = remaining.iterator();
        i.first();
        while (!i.isDone()) {
            List left = (List) i.current();
            i.next();
            if (i.isDone()) {
result.add(left);
            } else {
                List right = (List) i.current();
                i.next();
                result.add(merge(left, right));
            }
        }

        return result;
    }

    private List createSublists(List list) {
        List result = new ArrayList(list.size());

        Iterator i = list.iterator();
        i.first();
        while (!i.isDone()) {
            List singletonList = new ArrayList(1);
            singletonList.add(i.current());
            result.add(singletonList);
            i.next();
        }

        return  result;
    }

    private List merge(List left, List right) {
        List result = new ArrayList();

        Iterator l = left.iterator();
        Iterator r = right.iterator();

        l.first();
        r.first();

        while (!(l.isDone() && r.isDone())) {
            if (l.isDone()) {
                result.add(r.current());
                r.next();
            } else if (r.isDone()) {
                result.add(l.current());
                l.next();
            } else if (_comparator.compare(l.current(), r.current()) <= 0) {
                result.add(l.current());
                l.next();
            } else {
                result.add(r.current());
                r.next();
            }
        }

        return result;
    }
}

Exercise 2 Solution

public class IterativeQuicksortListSorter implements ListSorter {
    private final Comparator _comparator;

    public IterativeQuicksortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }

    public List sort(List list) {
        assert list != null : "list cannot be null";

        quicksort(list);

        return list;
    }

    private void quicksort(List list) {
        Stack jobStack = new ListStack();

        jobStack.push(new Range(0, list.size() − 1));

        while (!jobStack.isEmpty()) {
            Range range = (Range) jobStack.pop();
            if (range.size() <= 1) {
                continue;
            }

            int startIndex = range.getStartIndex();
            int endIndex = range.getEndIndex();

            Object value = list.get(endIndex);

            int partition = partition(list, value, startIndex, endIndex − 1);
            if (_comparator.compare(list.get(partition), value) < 0) {
                ++partition;
            }

            swap(list, partition, endIndex);

            jobStack.push(new Range(startIndex, partition − 1));
            jobStack.push(new Range(partition + 1, endIndex));
        }
    }

    private int partition(List list, Object value, int leftIndex, int rightIndex) {
        int left = leftIndex;
        int right = rightIndex;

        while (left < right) {
            if (_comparator.compare(list.get(left), value) < 0) {
                ++left;
                continue;
            }

            if (_comparator.compare(list.get(right), value) >= 0) {
−−right;
                continue;
            }

            swap(list, left, right);
            ++left;
        }

        return left;
    }

    private void swap(List list, int left, int right) {
        if (left == right) {
            return;
        }
        Object temp = list.get(left);
        list.set(left, list.get(right));
        list.set(right, temp);
    }

    private static final class Range {
        private final int _startIndex;
        private final int _endIndex;

        public Range(int startIndex, int endIndex) {
            _startIndex = startIndex;
            _endIndex = endIndex;
        }

        public int size() {
            return _endIndex - _startIndex + 1;
        }

        public int getStartIndex() {
            return _startIndex;
        }

        public int getEndIndex() {
            return _endIndex;
        }
    }
}

Exercise 3 Solution

public class AdvancedListSorterCallCountingListTest extends TestCase {
    private static final int TEST_SIZE = 1000;

    private final List _sortedArrayList = new ArrayList(TEST_SIZE);
    private final List _reverseArrayList = new ArrayList(TEST_SIZE);
    private final List _randomArrayList = new ArrayList(TEST_SIZE);

    private Comparator _comparator = NaturalComparator.INSTANCE;

    protected void setUp() throws Exception {
super.setUp();

        for (int i = 1; i < TEST_SIZE; ++i) {
            _sortedArrayList.add(new Integer(i));
        }

        for (int i = TEST_SIZE; i > 0; −−i) {
            _reverseArrayList.add(new Integer(i));
        }

        for (int i = 1; i < TEST_SIZE; ++i) {
            _randomArrayList.add(new Integer((int)(TEST_SIZE * Math.random())));
        }
    }

    public void testWorstCaseQuicksort() {
        List list = new CallCountingList(_reverseArrayList);
        new QuicksortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testWorstCaseShellSort() {
        List list = new CallCountingList(_reverseArrayList);
        new ShellsortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testBestCaseQuicksort() {
        List list = new CallCountingList(_sortedArrayList);
        new QuicksortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testBestCaseShellSort() {
        List list = new CallCountingList(_sortedArrayList);
        new ShellsortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testAverageCaseQuicksort() {
        List list = new CallCountingList(_randomArrayList);
        new QuicksortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    public void testAverageCaseShellSort() {
        List list = new CallCountingList(_randomArrayList);
        new ShellsortListSorter(_comparator).sort(list);
        reportCalls(list);
    }

    private void reportCalls(List list) {
        System.out.println(getName() + ": " + list);
    }
}

public class CallCountingList implements List {
    private final List _list;

    private int _insertCount;
    private int _addCount;
    private int _deleteCount;
    private int _getCount;
    private int _setCount;

    public CallCountingList(List list) {
        assert list != null : "list can't be null";
        _list = list;
    }

    public void insert(int index, Object value) throws IndexOutOfBoundsException {
        _list.insert(index, value);
        ++_insertCount;
    }

    public void add(Object value) {
        _list.add(value);
        ++_addCount;
    }

    public Object delete(int index) throws IndexOutOfBoundsException {
        ++_deleteCount;
        return _list.delete(index);
    }

    public Object delete(Object value) {
        ++_deleteCount;
        return _list.delete(value);
    }

    public Object get(int index) throws IndexOutOfBoundsException {
        ++_getCount;
        return _list.get(index);
    }

    public Object set(int index, Object value) throws IndexOutOfBoundsException {
        ++_setCount;
        return _list.set(index, value);
    }


    public void clear() {
        _list.clear();
    }

    public int indexOf(Object value) {
        return _list.indexOf(value);
    }

    public boolean contains(Object value) {
return _list.contains(value);
    }

    public boolean isEmpty() {
        return _list.isEmpty();
    }

    public Iterator iterator() {
        return _list.iterator();
    }

    public int size() {
        return _list.size();
    }

    public String toString() {
        return new StringBuffer("Call-counting List: ")
                .append("add: " + _addCount)
                .append(" insert: " + _insertCount)
                .append(" delete: " + _deleteCount)
                .append(" set: " + _setCount)
                .append(" get: " + _getCount).toString();
    }
}

Exercise 4 Solution

public class InPlaceInsertionSortListSorter implements ListSorter {
    private final Comparator _comparator;

    public InPlaceInsertionSortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }

    public List sort(List list) {
        assert list != null : "list cannot be null";

        for (int i = 1; i < list.size(); ++i) {
            Object value = list.get(i);
            int j;
            for (j = i; j > 0; −−j) {
                Object previousValue = list.get(j − 1);
                if (_comparator.compare(value, previousValue) >= 0) {
                    break;
                }
                list.set(j, previousValue);
            }
            list.set(j, value);
        }

        return list;
    }
}

Exercise 5 Solution

public class HybridQuicksortListSorter implements ListSorter {
    private final Comparator _comparator;

    public HybridQuicksortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }

    public List sort(List list) {
        assert list != null : "list cannot be null";

        quicksort(list, 0, list.size() − 1);

        return list;
    }

    private void quicksort(List list, int startIndex, int endIndex) {
        if (startIndex < 0 || endIndex >= list.size()) {
            return;
        }
        if (endIndex <= startIndex) {
            return;
        }

        if (endIndex - startIndex < 5) {
            doInsertionSort(list, startIndex, endIndex);
        } else {
            doQuicksort(list, startIndex, endIndex);
        }
    }

    private void doInsertionSort(List list, int startIndex, int endIndex) {
        for (int i = startIndex + 1; i <= endIndex; ++i) {
            Object value = list.get(i);
            int j;
            for (j = i; j > startIndex; −−j) {
                Object previousValue = list.get(j − 1);
                if (_comparator.compare(value, previousValue) >= 0) {
                    break;
                }
                list.set(j, previousValue);
            }
            list.set(j, value);
        }
    }

    private void doQuicksort(List list, int startIndex, int endIndex) {
        Object value = list.get(endIndex);

        int partition = partition(list, value, startIndex, endIndex − 1);
        if (_comparator.compare(list.get(partition), value) < 0) {
            ++partition;
}

        swap(list, partition, endIndex);

        quicksort(list, startIndex, partition − 1);
        quicksort(list, partition + 1, endIndex);
    }

    private int partition(List list, Object value, int leftIndex, int rightIndex) {
        int left = leftIndex;
        int right = rightIndex;

        while (left < right) {
            if (_comparator.compare(list.get(left), value) < 0) {
                ++left;
                continue;
            }

            if (_comparator.compare(list.get(right), value) >= 0) {
                −−right;
                continue;
            }

            swap(list, left, right);
            ++left;
        }

        return left;
    }

    private void swap(List list, int left, int right) {
        if (left == right) {
            return;
        }
        Object temp = list.get(left);
        list.set(left, list.get(right));
        list.set(right, temp);
    }
}

Exercises

  1. Use a priority queue to implement a Stack.

  2. Use a priority queue to implement a FIFO Queue.

  3. Use a priority queue to implement a ListSorter.

  4. Write a priority queue that provides access to the smallest item, rather than the largest.

Exercise 1 Solution

package com.wrox.algorithms.stacks;

import com.wrox.algorithms.queues.EmptyQueueException;
import com.wrox.algorithms.queues.HeapOrderedListPriorityQueue;
import com.wrox.algorithms.sorting.Comparator;

public class PriorityQueueStack extends HeapOrderedListPriorityQueue
                                implements Stack {
    private final static Comparator COMPARATOR = new StackItemComparator();
    private long _count = 0;

    public PriorityQueueStack() {
        super(COMPARATOR);
    }

    public void enqueue(Object value) {
        super.enqueue(new StackItem(++_count, value));
    }

    public Object dequeue() throws EmptyQueueException {
        return ((StackItem) super.dequeue()).getValue();
    }

    public void push(Object value) {
        enqueue(value);
    }

    public Object pop() throws EmptyStackException {
        try {
            return dequeue();
        } catch (EmptyQueueException e) {
            throw new EmptyStackException();
        }
    }

    public Object peek() throws EmptyStackException {
        Object result = pop();
        push(result);
        return result;
    }

    private static final class StackItem {
        private final long _key;
        private final Object _value;

        public StackItem(long key, Object value) {
            _key = key;
            _value = value;
        }

        public long getKey() {
            return _key;
        }

        public Object getValue() {
return _value;
        }
    }

    private static final class StackItemComparator implements Comparator {
        public int compare(Object left, Object right) throws ClassCastException {
            StackItem si1 = (StackItem) left;
            StackItem si2 = (StackItem) right;

            return (int) (si1.getKey() - si2.getKey());
        }
    }
}

Exercise 2 Solution

package com.wrox.algorithms.queues;

import com.wrox.algorithms.sorting.Comparator;

public class PriorityQueueFifoQueue extends HeapOrderedListPriorityQueue {
    private static final Comparator COMPARATOR = new QueueItemComparator();
    private long _count = Long.MAX_VALUE;

    public PriorityQueueFifoQueue() {
        super(COMPARATOR);
    }

    public void enqueue(Object value) {
        super.enqueue(new QueueItem(−−_count, value));
    }

    public Object dequeue() throws EmptyQueueException {
        return ((QueueItem) super.dequeue()).getValue();
    }

    private static final class QueueItem {
        private final long _key;
        private final Object _value;

        public QueueItem(long key, Object value) {
            _key = key;
            _value = value;
        }

        public long getKey() {
            return _key;
        }

        public Object getValue() {
            return _value;
}
    }

    private static final class QueueItemComparator implements Comparator {
        public int compare(Object left, Object right) throws ClassCastException {
            QueueItem si1 = (QueueItem) left;
            QueueItem si2 = (QueueItem) right;

            return (int) (si1.getKey() - si2.getKey());
        }
    }
}

Exercise 3 Solution

public class PriorityQueueListSorter implements ListSorter {
    private final Comparator _comparator;

    public PriorityQueueListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }

    public List sort(List list) {
        assert list != null : "list cannot be null";

        Queue queue = createPriorityQueue(list);

        List result = new ArrayList(list.size());

        while (!queue.isEmpty()) {
            result.add(queue.dequeue());
        }

        return result;
    }

    private Queue createPriorityQueue(List list) {
        Comparator comparator = new ReverseComparator(_comparator);
        Queue queue = new HeapOrderedListPriorityQueue(comparator);

        Iterator i = list.iterator();
        i.first();
        while (!i.isDone()) {
            queue.enqueue(i.current());
            i.next();
        }

        return queue;
    }
}

Exercise 4 Solution

public class MinimumOrientedHeapOrderedListPriorityQueue
        extends HeapOrderedListPriorityQueue {
    public MinimumOrientedHeapOrderedListPriorityQueue(Comparator comparator) {
        super(new ReverseComparator(comparator));
    }
}

Exercises

  1. Write a recursive form of minimum().

  2. Write a recursive form of search().

  3. Write a method that takes a root node and recursively prints all the values of the tree in order.

  4. Write a method that takes a root node and iteratively prints all the values of the tree in order.

  5. Write a method that takes a root node and recursively prints all the values of the tree pre-order.

  6. Write a method that takes a root node and recursively prints all the values of the tree post-order.

  7. Write a method(s) that inserts values from a sorted list into a binary search tree in such a way as to maintain balance yet require no explicit balancing.

  8. Add method(s) to Node to recursively calculate its size.

  9. Add method(s) to Node to recursively calculate its height.

Exercise 1 Solution

public Node minimum() {
        return getSmaller() != null ? GetSmaller() : this;
    }

Exercise 2 Solution

public Node search(Object value) {
        return search(value, _root);
    }

    private Node search(Object value, Node node) {
        if (node == null) {
            return null;
        }

        int cmp = _comparator.compare(value, node.getValue());
        if (cmp == 0) {
            return node;
        }

        return search(value, cmp < 0 ? node.getSmaller() : node.getLarger());
    }

Exercise 3 Solution

public void inOrderPrint(Node node) {
        if (node == null) {
            return;
        }

        inOrderPrint(node.getSmaller());
        System.out.println(node.getValue());
        inOrderPrint(node.getLarger()));
    }

Exercise 4 Solution

public void inOrderPrint(Node root) {
        for (Node node = root.minimum(); node != null; node = node.successor()) {
            System.out.println(node.getValue());
        }
    }

Exercise 5 Solution

public void preOrderPrint(Node node) {
        if (node == null) {
            return;
        }

        System.out.println(node.getValue());
        preOrderPrint(node.getSmaller());
        preOrderPrint(node.getLarger()));
    }

Exercise 6 Solution

public void postOrderPrint(Node node) {
        if (node == null) {
            return;
        }

        postOrderPrint(node.getSmaller());
        postOrderPrint(node.getLarger()));
        System.out.println(node.getValue());
    }

Exercise 7 Solution

public void preOrderInsert(BinarySearchTree tree, List list) {
        preOrderInsert(tree, list, 0, list.size() − 1);
    }

    private void preOrderInsert(BinarySearchTree tree, List list,
                                int lowerIndex,int upperIndex) {
        if (lowerIndex > upperIndex) {
return;
        }

        int index = lowerIndex + (upperIndex - lowerIndex) / 2;

        tree.insert(list.get(index));
        preOrderInsert(tree, list, lowerIndex, index − 1);
        preOrderInsert(tree, list, index + 1, upperIndex);
    }

Exercise 8 Solution

public int size() {
        return size(this);
    }

    private int size(Node node) {
        if (node == null) {
            return 0;
        }

        return 1 + size(node.getSmaller()) + size(node.getLarger());
    }

Exercise 9 Solution

public int height() {
        return height(this) − 1;
    }

    private int height(Node node) {
        if (node == null) {
            return 0;
        }

        return 1 + Math.max(height(node.getSmaller()), height(node.getLarger()));
    }

Exercises

  1. Modify BucketingHashtable to always use a prime number of buckets. What effect (if any) does this have on performance?

  2. Modify LinearProbingHashtable to maintain the number of values in the table, rather than calculate it every time.

  3. Modify BucketingHashtable to maintain the number of values in the table, rather than calculate it every time.

  4. Create an iterator that provides access to all of the entries in a BucketingHashtable.

Exercise 1 Solution

package com.wrox.algorithms.hashing;

public final class SimplePrimeNumberGenerator {
    public static final SimplePrimeNumberGenerator INSTANCE =
                                                  new SimplePrimeNumberGenerator();

    private SimplePrimeNumberGenerator() {
    }

    public int generate(int candidate) {
        int prime = candidate;

        while (!isPrime(prime)) {
            ++prime;
        }

        return prime;
    }

    private boolean isPrime(int candidate) {
        for (int i = candidate / 2; i >= 2; −−i) {
            if (candidate % i == 0) {
                return false;
            }
        }
        return true;
    }
}
package com.wrox.algorithms.hashing;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.lists.LinkedList;
import com.wrox.algorithms.lists.List;

public class BucketingHashtable implements Hashtable {
    ...

    public BucketingHashtable(int initialCapacity, float loadFactor) {
        assert initialCapacity > 0 : "initialCapacity can't be < 1";
        assert loadFactor > 0 : "loadFactor can't be <= 0";

        _loadFactor = loadFactor;
        _buckets = new Bucket[
                SimplePrimeNumberGenerator.INSTANCE.generate(initialCapacity)];
    }

    ...
}

Exercise 2 Solution

package com.wrox.algorithms.hashing;

public class LinearProbingHashtable implements Hashtable {
    ...

    private int _size;

    public void add(Object value) {
        ensureCapacityForOneMore();

        int index = indexFor(value);

        if (_values[index] == null) {
            _values[index] = value;
            ++_size;
        }
    }

    public int size() {
        return _size;
    }
}

Exercise 3 Solution

package com.wrox.algorithms.hashing;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.lists.LinkedList;
import com.wrox.algorithms.lists.List;

public class BucketingHashtable implements Hashtable {
    ...

    private int _size;

    public void add(Object value) {
        List bucket = bucketFor(value);

        if (!bucket.contains(value)) {
            bucket.add(value);
            ++_size;
            maintainLoad();
        }
    }

    public int size() {
        return _size;
    }
}

Exercise 4 Solution

package com.wrox.algorithms.hashing;

import com.wrox.algorithms.iteration.EmptyIterator;
import com.wrox.algorithms.iteration.Iterable;
import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.iteration.IteratorOutOfBoundsException;

public class HashtableIterator implements Iterator {
    private final Iterator _buckets;
    private Iterator _values = EmptyIterator.INSTANCE;

    public HashtableIterator(Iterator buckets) {
        assert buckets != null : "buckets can't be null";
        _buckets = buckets;
    }

    public void first() {
        _buckets.first();
        _values = EmptyIterator.INSTANCE;
        next();
    }

    public void last() {
        _buckets.last();
        _values = EmptyIterator.INSTANCE;
        previous();
    }

    public boolean isDone() {
        return _values.isDone() && _buckets.isDone();
    }

    public void next() {
        for (_values.next();
             _values.isDone() && !_buckets.isDone();
             _buckets.next()) {
            Iterable bucket = (Iterable) _buckets.current();
            if (bucket != null) {
                _values = bucket.iterator();
                _values.first();
            }
        }
    }

    public void previous() {
        for (_values.previous();
             _values.isDone() && !_buckets.isDone();
             _buckets.previous()) {
            Iterable bucket = (Iterable) _buckets.current();
            if (bucket != null) {
                _values = bucket.iterator();
                _values.last();
            }
}
    }

    public Object current() throws IteratorOutOfBoundsException {
        if (isDone()) {
            throw new IteratorOutOfBoundsException();
        }
        return _values.current();
    }
}

Exercises

  1. Write a method that takes two sets and determines whether they are equal.

  2. Write a method that takes two sets and produces a third set containing the union of the first two.

  3. Write a method that takes two sets and produces a third set containing the intersection of the first two.

  4. Write a method that takes two sets and produces a third set containing the difference between the first two.

  5. Update the delete() method in HashSet to free the bucket if it's empty.

  6. Create a set implementation that uses a sorted list.

  7. Create a set implementation that is always empty and throws UnsupportedOperationException whenever an attempt is made to modify it.

Exercise 1 Solution

public boolean equals(Set a, Set b) {
        assert a != null : "a can't be null";
        assert b != null : "b can't be null";

        Iterator i = a.iterator();
        for (i.first(); !i.isDone(); i.next()) {
            if (!b.contains(i.current())) {
                return false;
            }
        }

        return a.size() == b.size();
    }
}

Exercise 2 Solution

public Set union(Set a, Set b) {
        assert a != null : "a can't be null";
assert b != null : "b can't be null";

        Set result = new HashSet();

        Iterator i = a.iterator();
        for (i.first(); !i.isDone(); i.next()) {
            result.add(i.current());
        }

        Iterator j = b.iterator();
        for (j.first(); !j.isDone(); j.next()) {
            result.add(j.current());
        }

        return result;
    }

Exercise 3 Solution

public Set intersection(Set a, Set b) {
        assert a != null : "a can't be null";
        assert b != null : "b can't be null";

        Set result = new HashSet();

        Iterator i = a.iterator();
        for (i.first(); !i.isDone(); i.next()) {
            if (b.contains(i.current())) {
                result.add(i.current());
            }
        }

        return result;
    }

Exercise 4 Solution

public Set difference(Set a, Set b) {
        assert a != null : "a can't be null";
        assert b != null : "b can't be null";

        Set result = new HashSet();

        Iterator i = a.iterator();
        for (i.first(); !i.isDone(); i.next()) {
            if (!b.contains(i.current())) {
                result.add(i.current());
            }
        }

        return result;
    }

Exercise 5 Solution

public boolean delete(Object value) {
        int bucketIndex = bucketIndexFor(value);
        ListSet bucket = _buckets[bucketIndex];
        if (bucket != null && bucket.delete(value)) {
            −−_size;
            if (bucket.isEmpty()) {
                _buckets[bucketIndex] = null;
            }
            return true;
        }

        return false;
    }

Exercise 6 Solution

package com.wrox.algorithms.sets;

import com.wrox.algorithms.bsearch.IterativeBinaryListSearcher;
import com.wrox.algorithms.bsearch.ListSearcher;
import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.lists.ArrayList;
import com.wrox.algorithms.lists.List;
import com.wrox.algorithms.sorting.Comparator;
import com.wrox.algorithms.sorting.NaturalComparator;

public class SortedListSet implements Set {
    private final List _values = new ArrayList();
    private final ListSearcher _searcher;

    public SortedListSet() {
        this(NaturalComparator.INSTANCE);
    }

    public SortedListSet(Comparator comparator) {
        _searcher = new IterativeBinaryListSearcher(comparator);
    }

    public boolean contains(Object value) {
        return indexOf(value) >= 0;
    }

    public boolean add(Object value) {
        int index = indexOf(value);
        if (index < 0) {
            _values.insert(-(index + 1), value);
            return true;
        }

        _values.set(index, value);
        return false;
    }

    public boolean delete(Object value) {
int index = indexOf(value);
        if (index >= 0) {
            _values.delete(index);
            return true;
        }

        return false;
    }

    public Iterator iterator() {
        return _values.iterator();
    }

    public void clear() {
        _values.clear();
    }

    public int size() {
        return _values.size();
    }

    public boolean isEmpty() {
        return _values.isEmpty();
    }

    private int indexOf(Object value) {
        return _searcher.search(_values, value);
    }
}

Exercise 7 Solution

package com.wrox.algorithms.sets;

import com.wrox.algorithms.iteration.EmptyIterator;
import com.wrox.algorithms.iteration.Iterator;

public final class EmptySet implements Set {
    public static final EmptySet INSTANCE = new EmptySet();

    private EmptySet() {
    }

    public boolean contains(Object value) {
        return false;
    }

    public boolean add(Object value) {
        throw new UnsupportedOperationException();
    }

    public boolean delete(Object value) {
        throw new UnsupportedOperationException();
    }

    public void clear() {
}

    public int size() {
        return 0;
    }

    public boolean isEmpty() {
        return true;
    }

    public Iterator iterator() {
        return EmptyIterator.INSTANCE;
    }

Exercises

  1. Create an iterator that returns only the keys contained within a map.

  2. Create an iterator that returns only the values contained within a map.

  3. Create a set implementation that uses a map as the underlying storage mechanism for the values.

  4. Create an empty map that throws UnsupportedOperationException anytime an attempt is made to modify it.

Exercise 1 Solution

package com.wrox.algorithms.maps;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.iteration.IteratorOutOfBoundsException;

public class MapKeyIterator implements Iterator {
    private final Iterator _entries;

    public MapKeyIterator(Iterator entries) {
        assert entries != null : "entries can't be null";
        _entries = entries;
    }

    public void first() {
        _entries.first();
    }

    public void last() {
        _entries.last();
    }

    public boolean isDone() {
        return _entries.isDone();
}

    public void next() {
        _entries.next();
    }

    public void previous() {
        _entries.previous();
    }

    public Object current() throws IteratorOutOfBoundsException {
        return ((Map.Entry) _entries.current()).getKey();
    }
}

Exercise 2 Solution

package com.wrox.algorithms.maps;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.iteration.IteratorOutOfBoundsException;

public class MapValueIterator implements Iterator {
    private final Iterator _entries;

    public MapValueIterator(Iterator entries) {
        assert entries != null : "entries can't be null";
        _entries = entries;
    }

    public void first() {
        _entries.first();
    }

    public void last() {
        _entries.last();
    }

    public boolean isDone() {
        return _entries.isDone();
    }

    public void next() {
        _entries.next();
    }

    public void previous() {
        _entries.previous();
    }

    public Object current() throws IteratorOutOfBoundsException {
        return ((Map.Entry) _entries.current()).getValue();
    }
}

Exercise 3 Solution

package com.wrox.algorithms.maps;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.sets.Set;

public class MapSet implements Set {
    private static final Object PRESENT = new Object();

    private final Map _map;

    public MapSet(Map map) {
        assert map != null : "map can't be null";
        _map = map;
    }

    public boolean contains(Object value) {
        return _map.contains(value);
    }

    public boolean add(Object value) {
        return _map.set(value, PRESENT) == null;
    }

    public boolean delete(Object value) {
        return _map.delete(value) == PRESENT;
    }

    public Iterator iterator() {
        return new MapKeyIterator(_map.iterator());
    }

    public void clear() {
        _map.clear();
    }

    public int size() {
        return _map.size();
    }

    public boolean isEmpty() {
        return _map.isEmpty();
    }
}

Exercise 4 Solution

package com.wrox.algorithms.maps;

import com.wrox.algorithms.iteration.EmptyIterator;
import com.wrox.algorithms.iteration.Iterator;

public final class EmptyMap implements Map {
public static final EmptyMap INSTANCE = new EmptyMap();

    private EmptyMap() {
    }

    public Object get(Object key) {
        return null;
    }

    public Object set(Object key, Object value) {
        throw new UnsupportedOperationException();
    }

    public Object delete(Object key) {
        throw new UnsupportedOperationException();
    }

    public boolean contains(Object key) {
        return false;
    }

    public void clear() {
    }

    public int size() {
        return 0;
    }

    public boolean isEmpty() {
        return true;
    }

    public Iterator iterator() {
        return EmptyIterator.INSTANCE;
    }
}

Exercise

  1. Create an iterative form of search().

Exercise 1 Solution

private Node search(Node node, CharSequence word, int index) {
        assert word != null : "word can't be null";

        while (node != null) {
            char c = word.charAt(index);
            if (c == node.getChar()) {
                if (index + 1 < word.length()) {
                    node = node.getChild();
                } else {
                    break;
}
            } else {
                node = c < node.getChar() ? node.getSmaller() : node.getLarger();
            }
        }

        return node;
    }

Exercises

  1. Re-implement the traverse() method on Node to return the entries in key order.

  2. Re-implement the indexOf() method on Node to perform a binary search instead of a linear search.

Exercise 1 Solution

public void traverse(List list) {
            assert list != null : "list can't be null";

            Iterator children = _children.iterator();
            Iterator entries = _entries.iterator();

            children.first();
            entries.first();

            while (!children.isDone() || !entries.isDone()) {
                if (!children.isDone()) {
                    ((Node) children.current()).inOrderTraversal(list);
                    children.next();
                }

                if (!entries.isDone()) {
                    Entry entry = (Entry) entries.current();
                    if (!entry.isDeleted()) {
                        list.add(entry);
                    }
                    entries.next();
                }
            }
        }

Exercise 2 Solution

private int indexOf(Object key) {
            int lowerIndex = 0;
            int upperIndex = _entries.size() − 1;

            while (lowerIndex <= upperIndex) {
                int index = lowerIndex + (upperIndex - lowerIndex) / 2;

                int cmp = _comparator.compare(key,
(Entry) _entries.get(index)).getKey());

                if (cmp == 0) {
                    return index;
                } else if (cmp < 0) {
                    upperIndex = index − 1;
                } else {
                    lowerIndex = index + 1;
                }
            }

            return -(lowerIndex + 1);
        }

Exercises

  1. Implement a brute-force solution to the closest pair problem.

  2. Optimize the plane sweep algorithm so that points too distant in the vertical direction are ignored.

Exercise 1 Solution

package com.wrox.algorithms.geometry;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.lists.ArrayList;
import com.wrox.algorithms.lists.List;
import com.wrox.algorithms.sets.ListSet;
import com.wrox.algorithms.sets.Set;
import com.wrox.algorithms.bsearch.ListInserter;
import com.wrox.algorithms.bsearch.IterativeBinaryListSearcher;

public final class BruteForceClosestPairFinder implements ClosestPairFinder {
    public static final BruteForceClosestPairFinder INSTANCE = new BruteForceClosestPairFinder();

    private BruteForceClosestPairFinder() {
    }

    public Set findClosestPair(Set points) {
        assert points != null : "points can't be null";

        if (points.size() < 2) {
            return null;
        }

        List list = sortPoints(points);

        Point p = null;
Point q = null;
        double distance = Double.MAX_VALUE;

        for (int i = 0; i < list.size(); i++) {
            Point r = (Point) list.get(i);
            for (int j = 0; j < list.size(); j++) {
                Point s = (Point) list.get(j);
                if (r != s && r.distance(s) < distance) {
                    distance = r.distance(s);
                    p = r;
                    q = s;
                }
            }
        }

        return createPointPair(p, q);
    }

    private static List sortPoints(Set points) {
        assert points != null : "points can't be null";

        List list = new ArrayList(points.size());

        Iterator i = points.iterator();
        for (i.first(); !i.isDone(); i.next()) {
            INSERTER.insert(list, i.current());
        }

        return list;
    }

    private Set createPointPair(Point p, Point q) {
        Set result = new ListSet();
        result.add(p);
        result.add(q);
        return result;
    }
}

Exercise 2 Solution

package com.wrox.algorithms.geometry;

import com.wrox.algorithms.bsearch.IterativeBinaryListSearcher;
import com.wrox.algorithms.bsearch.ListInserter;
import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.lists.ArrayList;
import com.wrox.algorithms.lists.List;
import com.wrox.algorithms.sets.ListSet;
import com.wrox.algorithms.sets.Set;

public final class PlaneSweepOptimizedClosestPairFinder implements ClosestPairFinder {
public static final PlaneSweepOptimizedClosestPairFinder INSTANCE = new PlaneSweepOptimizedClosestPairFinder();

    private static final ListInserter INSERTER = new ListInserter(
            new IterativeBinaryListSearcher(XYPointComparator.INSTANCE));

    private PlaneSweepOptimizedClosestPairFinder() {
    }

    public Set findClosestPair(Set points) {
        assert points != null : "points can't be null";

        if (points.size() < 2) {
            return null;
        }

        List sortedPoints = sortPoints(points);

        Point p = (Point) sortedPoints.get(0);
        Point q = (Point) sortedPoints.get(1);

        return findClosestPair(p, q, sortedPoints);
    }

    private Set findClosestPair(Point p, Point q, List sortedPoints) {
        Set result = createPointPair(p, q);
        double distance = p.distance(q);
        int dragPoint = 0;

        for (int i = 2; i < sortedPoints.size(); ++i) {
            Point r = (Point) sortedPoints.get(i);
            double sweepX = r.getX();
            double dragX = sweepX - distance;

            while (((Point) sortedPoints.get(dragPoint)).getX() < dragX) {
                ++dragPoint;
            }

            for (int j = dragPoint; j < i; ++j) {
                Point test = (Point) sortedPoints.get(j);
                if (Math.abs(r.getY() - test.getY()) > distance) {
                    continue;
                }
                double checkDistance = r.distance(test);
                if (checkDistance < distance) {
                    distance = checkDistance;
                    result = createPointPair(r, test);
                }
            }
        }

        return result;
    }

    private static List sortPoints(Set points) {
assert points != null : "points can't be null";

        List list = new ArrayList(points.size());

        Iterator i = points.iterator();
        for (i.first(); !i.isDone(); i.next()) {
            INSERTER.insert(list, i.current());
        }

        return list;
    }

    private Set createPointPair(Point p, Point q) {
        Set result = new ListSet();
        result.add(p);
        result.add(q);
        return result;
    }
}
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.226.165.247