среда, 1 августа 2012 г.

core-labs: collections


Java Collection API

    equals(..)/hashCode()/toString()
    - collections.eq+hash+toStr.EntityA (обязательно)
    - collections.eq+hash+toStr.EntityB (обязательно)
    - collections.eq+hash+toStr.EntityC

    List/Set/Map
    - collections.impl.ArrayList (обязательно)
    - collections.impl.LinkedList (обязательно)
    - collections.impl.HashMap
    - collections.impl.TreeMap
    - collections.impl.HashSet
    - collections.impl.TreeSet

    equals(..)/hashCode()/toString()

    collections.eq+hash+toStr.EntityA    
    Дан класс, представляющий собой некоторую бизнес-сущность (entity), объект предметной области (domain object). Необходимо для него корректно определить методы equals(..), hashCode() и toString().
public class EntityA {
    private int age;
    private int height;
    private String name;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean equals(Object obj) {
        throw new UnsupportedOperationException();
    }

    @Override
    public String toString() {
        throw new UnsupportedOperationException();
    }
}

    collections.eq+hash+toStr.EntityB    
    Дан класс, представляющий собой некоторую бизнес-сущность (entity), объект предметной области (domain object). Необходимо для него корректно определить методы equals(..), hashCode() и toString().
public class EntityB {
    private final String[][] stringArr;
    private final double[] doubleArr;

    public EntityB(String[][] stringArr, double[] doubleArr) {
        this.stringArr = stringArr;
        this.doubleArr = doubleArr;
    }

    public String[][] getStringArr() {
        return stringArr;
    }

    public double[] getDoubleArr() {
        return doubleArr;
    }

    @Override
    public int hashCode() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean equals(Object obj) {
        throw new UnsupportedOperationException();
    }

    @Override
    public String toString() {
        throw new UnsupportedOperationException();
    }
}


    collections.eq+hash+toStr.EntityC    
    Дан класс, представляющий собой некоторую бизнес-сущность (entity), объект предметной области (domain object). Необходимо для него корректно определить методы equals(..), hashCode() и toString().
    Предполагается, что методы equals(..), hashCode() и toString() для EntityA и EntityB уже корректно определены.
import java.util.List;
import java.util.Map;
import java.util.Set;

public class EntityC {
    private final EntityA entity;
    private final List<EntityB> list;
    private final Map<Set<EntityA>, List<EntityB[]>> map;

    public EntityC(EntityA entity, List<EntityB> list, Map<Set<EntityA>, List<EntityB[]>> map) {
        this.entity = entity;
        this.list = list;
        this.map = map;
    }

    public EntityA getEntity() {
        return entity;
    }

    public List<EntityB> getList() {
        return list;
    }

    public Map<Set<EntityA>, List<EntityB[]>> getMap() {
        return map;
    }

    @Override
    public int hashCode() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean equals(Object obj) {
        throw new UnsupportedOperationException();
    }

    @Override
    public String toString() {
        throw new UnsupportedOperationException();
    }
}


    List / ArrayList/LinkedList

    Интерфейс SimpleList представляет собой упрощенную версию интерфейса java.util.List. В ней меньше методов, но все контракты остались прежними:
public interface SimpleList<T> {

    // *** *** *** ADD *** *** ***
    public boolean add(T newElement);

    public void add(int index, T element);

    // *** *** *** READ *** *** ***
    public T get(int index);

    public Iterator<T> iterator();

    // *** *** *** CHECK *** *** ***
    public boolean contains(Object hasElement);

    public int size();

    public boolean isEmpty();

    // *** *** *** MUTATE *** *** ***
    public T set(int index, T newElement);

    // *** *** *** REMOVE *** *** ***
    public boolean remove(Object o);

    public T remove(int index);
}


    collections.impl.SimpleArrayList
    В классе SimpleArrayList реализовать методы:
1) remove(Object value)
2) iterator()
3) toString()
4) equals(Object other)
5) hashCode()
Они должны вести себя так же, как и соответствующие методы java.util.ArrayList.    
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

import static java.lang.Math.max;

public class SimpleArrayList_q<E> implements SimpleList<E> {
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    private E[] data;
    private int size = 0;

    public SimpleArrayList_q() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    public SimpleArrayList_q(int initialCapacity) {
        this.data = (E[]) new Object[initialCapacity];
    }

    // *** *** *** ADD *** *** ***
    @Override
    public boolean add(E newElement) {
        ensureCapacity(size + 1);
        data[size] = newElement;
        size++;
        return true;
    }

    @Override
    public void add(int index, E element) {
        rangeCheck(index);
        System.arraycopy(data, index, data, index + 1, size - index);
        data[index] = element;
        size++;
    }

    // *** *** *** READ *** *** ***
    @Override
    public E get(int index) {
        rangeCheck(index);
        return data[index];
    }

    @Override
    public Iterator<E> iterator() {
        throw new UnsupportedOperationException(); 
    }

    // *** *** *** CHECK *** *** ***
    @Override
    public boolean contains(Object element) {
        if (element == null) { // look for null
            for (int k = 0; k < size; k++) {
                if (null == data[k]) {
                    return true;
                }
            }
        } else { // look for !null
            for (int k = 0; k < size; k++) {
                if (element.equals(data[k])) {
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public int size() {
        return size;
    }

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

    // *** *** *** MUTATE *** *** ***
    @Override
    public E set(int index, E newElement) {
        rangeCheck(index);
        E oldElement = data[index];
        data[index] = newElement;
        return oldElement;
    }

    // *** *** *** REMOVE *** *** ***
    @Override
    public boolean remove(Object element) {
        throw new UnsupportedOperationException();
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        E oldValue = data[index];
        int numMoved = size - index - 1;
        System.arraycopy(data, index + 1, data, index, numMoved);
        data[--size] = null;
        return oldValue;
    }

    // *** *** *** OBJECT METHODS *** *** ***
    @Override
    public boolean equals(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public int hashCode() {
        throw new UnsupportedOperationException();
    }

    @Override
    public String toString() {
        throw new UnsupportedOperationException();
    }

    // ---------- internals ----------
    private void rangeCheck(int index) {
        if (index < 0 || size < index) {
            throw new ArrayIndexOutOfBoundsException();
        }
    }

    private void ensureCapacity(int minCapacity) {
        if (minCapacity > data.length) {
            int newCapacity = max(minCapacity, data.length + (data.length >> 1));
            E[] newData = (E[]) new Object[newCapacity];
            System.arraycopy(data, 0, newData, 0, data.length);
            this.data = newData;
        }
    }
}



    collections.impl.SimpleLinkedList


    В классе SimpleдLinkedList реализовать методы:
1) remove(Object value)
2) iterator()
3) toString()
4) equals(Object other)
5) hashCode()
Они должны вести себя так же, как и соответствующие методы java.util.LinkedList. 


import java.util.Iterator;

public class SimpleLinkedList_q<E> implements SimpleList<E> {
    private Node<E> first = null; // head
    private Node<E> last = null; // tail
    private int size = 0;

    // *** *** *** ADD *** *** ***
    public boolean add(E newElement) {
        final Node<E> tmp = last;
        final Node<E> newNode = new Node<>(tmp, newElement, null);
        last = newNode;
        if (tmp == null) {
            first = newNode;
        } else {
            tmp.next = newNode;
        }
        size++;
        return true;
    }

    public void add(int index, E element) {
        checkIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    // *** *** *** READ *** *** ***
    public E get(int index) {
        checkIndex(index);
        return node(index).item;
    }

    public Iterator<E> iterator() {
        throw new UnsupportedOperationException();
    }

    // *** *** *** CHECK *** *** ***
    public boolean contains(Object hasElement) {
        return indexOf(hasElement) != -1;
    }

    public int size() {
        return size;
    }

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

    // *** *** *** MUTATE *** *** ***
    public E set(int index, E newElement) {
        checkIndex(index);
        Node<E> foundNode = node(index);
        E oldVal = foundNode.item;
        foundNode.item = newElement;
        return oldVal;
    }

    // *** *** *** REMOVE *** *** ***
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }

    public E remove(int index) {
        checkIndex(index);
        return unlink(node(index));
    }

    // *** *** *** OBJECT METHODS *** *** ***
    @Override
    public boolean equals(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public int hashCode() {
        throw new UnsupportedOperationException();
    }

    @Override
    public String toString() {
        throw new UnsupportedOperationException();
    }    
    
    // ---------- internals ----------
    private void checkIndex(int index) {
        if (index < 0 || size < index) {
            throw new ArrayIndexOutOfBoundsException();
        }
    }

    private Node<E> node(int index) {
        if (index < size / 2) {
            Node<E> tmp = first;
            for (int i = 0; i < index; i++) {
                tmp = tmp.next;
            }
            return tmp;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    private int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    private E unlink(Node<E> x) { //todo:
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        return element;
    }

    private void linkLast(E e) { //todo
        final Node<E> tmp = last;
        final Node<E> newNode = new Node<>(tmp, e, null);
        last = newNode;
        if (tmp == null) {
            first = newNode;
        } else {
            tmp.next = newNode;
        }
        size++;
    }

    private void linkBefore(E e, Node<E> succ) { //todo
        // assert succ != null;
        final Node<E> prev = succ.prev;
        final Node<E> newNode = new Node<>(prev, e, succ);
        succ.prev = newNode;
        if (prev == null) {
            first = newNode;
        } else {
            prev.next = newNode;
        }
        size++;
    }

    private static class Node<T> {
        private Node<T> prev;
        private T item;
        private Node<T> next;

        private Node(Node<T> prev, T item, Node<T> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
}

    Iterable/Iterator

    Дан пример реализации удобной функции interval(int left, int right), возвращающей целые числа большие или равные left и меньшие right.

    В IteratorUtils "хранится" метод interval(...):

public class IteratorUtils {
    public static Iterable<Integer> interval(int left, int right) {
        return new IntervalIterable(left, right);
    }
}
    Который возвращает Iterable<Integer>:


import java.util.Iterator;

public class IntervalIterable implements Iterable<Integer> {
    private final int left;
    private final int right;

    public IntervalIterable(int left, int right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new IntervalIterator(left, right);
    }
}
    Который возвращает Iterator<Integer>:
import java.util.Iterator;

public class IntervalIterator implements Iterator<Integer> {
    private final int max;
    private int current;

    public IntervalIterator(int left, int right) {
        this.max = right;
        this.current = left;
    }

    @Override
    public boolean hasNext() {
        return current < max;
    }

    @Override
    public Integer next() {
        return current++;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}
    Который можно использовать следующим образом:
import static IteratorUtils.*;

public class TestInterval {
    public static void main(String[] args) {
        double[] array = {0.5, 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5};

        for (int index : interval(0, array.length)) {
            System.out.print(" " + index);
        }
        System.out.println();

        for (int index : interval(0, array.length)) {
            System.out.print(" " + array[index]);
        }
        System.out.println();

        for (int index : interval(4, 8)) {
            System.out.print(" " + index);
        }
        System.out.println();

        for (int index : interval(4, 8)) {
            System.out.print(" " + array[index]);
        }
        System.out.println();
    }
}

>> 0 1 2 3 4 5 6 7 8 9

>> 0.5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5

>> 4 5 6 7
>> 4.5 5.5 6.5 7.5


    collections.iterator.square

    "По образу и подобию" дополните IteratorUtils методом square(int left, int right), возвращающим квадраты целых чисел большие или равные left и меньшие right.:
public class IteratorUtils {
    ...
    public static Iterable<Integer> squares(int left, int right) {
        ...
    }
}

    Мы бы его использовали вот так
import static net.golovach._core_3_collection._0_iterable_iterator._lab.IteratorUtils.squares;

public class TestSquares {
    public static void main(String[] args) {
        double[] array={0.5, 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5, 10.5};

        for (int index : squares(0, array.length)) {
            System.out.print(" " + array[index]);
        }
        System.out.println();

        for (int index : squares(3, array.length)) {
            System.out.print(" " + array[index]);
        }
        System.out.println();

        for (int index : squares(5, 8)) {
            System.out.print(" " + array[index]);
        }
        System.out.println();

        for (int index : squares(4, 5)) {
            System.out.print(" " + array[index]);
        }
        System.out.println();
    }
}
>> 0.5 1.5 4.5 9.5
>> 4.5 9.5
>> ... ничего, пустая строка
>> 4.5




    collections.iterator.merge

    Реализуйте IteratorUtils.merge(...)
public class IteratorUtils {
    ...
    public static Iterable<Integer> merge(Iterable<Integer> iter0, Iterable<Integer> iter1) {
        ...
    }
}

    Который получает два Iterable, возвращающие итераторы на сортированные последовательности, и "сливает в" Iterable возвращающий итератор на сортированную последовательность образованную в результате "слияния". 
    Мы бы его использовали вот так:
import static net.golovach._core_3_collection._0_iterable_iterator._lab.IteratorUtils.*;

public class MergeIteratorTest {
    public static void main(String[] args) {
        for (int k : merge(interval(10, 12), interval(10, 12))) {
            System.out.print(" " + k);
        }
        System.out.println();

        for (int k : merge(interval(10, 10), interval(10, 12))) {
            System.out.print(" " + k);
        }
        System.out.println();

        for (int k : merge(interval(10, 12), interval(10, 10))) {
            System.out.print(" " + k);
        }
        System.out.println();

        for (int k : merge(interval(10, 10), interval(10, 10))) {
            System.out.print(" " + k);
        }
        System.out.println();

        for (int k : merge(interval(0, 10), interval(1000, 1002))) {
            System.out.print(" " + k);
        }
        System.out.println();

        for (int k : merge(interval(1000, 1002), interval(0, 10))) {
            System.out.print(" " + k);
        }
        System.out.println();

        for (int k : merge(interval(0, 10), interval(5, 15))) {
            System.out.print(" " + k);
        }
        System.out.println();
    }
}

>>  10 10 11 11

>>  10 11

>>  10 11
>> ... ничего, пустая строка >>  0 1 2 3 4 5 6 7 8 9 1000 1001>>  0 1 2 3 4 5 6 7 8 9 1000 1001>>  0 1 2 3 4 5 5 6 6 7 7 8 8 9 9 10 11 12 13 14



    collections.iterator.is_to_iterator_adapter

    Вот Вам пример чуда инженерной мысли - адаптера Iterator-а к InputStream:

import java.io.IOException;
import java.io.InputStream;
import java.util.Iterator;

public class IteratorToISAdapter extends InputStream {
    private final Iterator<Integer> iterator;

    public IteratorToISAdapter(Iterator<Integer> iterator) {
        this.iterator = iterator;
    }

    @Override
    public int read() throws IOException {
        return (iterator.hasNext()) ? iterator.next() : -1;
    }
}
    Он позволяет использовать идиому вычитывания всех данных из InputStream для вычитывания всех данных из Iterator:
import java.io.IOException;
import java.io.InputStream;

import static net.golovach._core_3_collection._0_iterable_iterator._lab.IteratorUtils.interval;

public class IteratorToISAdapterTest {
    public static void main(String[] args) throws IOException {
        InputStream is 
                = new IteratorToISAdapter(interval(0, 10).iterator());
        int k;
        while ((k = is.read()) != -1) {
            System.out.print(" " + k);
        }
    }
}

    Увековечьте себя реализовав адаптер InputStream к Iterator
import java.io.IOException;
import java.io.InputStream;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ISToIteratorAdapter implements Iterator<Integer> {
    private final InputStream is;
    ...

    public ISToIteratorAdapter(InputStream is) {
        this.is = is;
        ...
    }

    @Override
    public boolean hasNext() {
        ...
    }

    @Override
    public Integer next() {
        ...
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}
    Что бы работало следующее:
import java.io.ByteArrayInputStream;
import java.util.Iterator;

public class ISToIteratorAdapterTest {
    public static void main(String[] args) {
        Iterator<Integer> iter3 
                = new ISToIteratorAdapter(new ByteArrayInputStream(new byte[]{10, 20, 30}));
        while (iter3.hasNext()) {
            System.out.print(" " + iter3.next());
        }
        System.out.println();

        Iterator<Integer> iter0 
                = new ISToIteratorAdapter(new ByteArrayInputStream(new byte[0]));
        while (iter0.hasNext()) {
            System.out.print(" " + iter0.next());
        }
        System.out.println();

        Iterator<Integer> iter1 
                = new ISToIteratorAdapter(new ByteArrayInputStream(new byte[]{10}));
        while (iter1.hasNext()) {
            System.out.print(" " + iter1.next());
        }
        System.out.println();
    }
}
>> 10 20 30
>> ... ничего, пустая строка 
>> 10