Date: Wed, 23 Apr 2003 11:01:25 +0300
From: Kai-Peter Bäckman <kpbackma@cs.helsinki.fi>

------------------------------------------------------
Tietorakenteet, 1. kursikoe 28.2.2003/AW

Korjauskertomus tehtävä 1

Arvostelu:
Osa a    4p
Osa b    4p
       ---
Yhteensä 8p


 Oleellista arvostelussa oli kaikkien vaatimusten
täyttäminen. Tehtävässä a taulukon piti kasvaa ilman mitään
rajoituksia ja indeksien muuttua oikein poistotapauksessa. Tehtävässä
b listan rakenteen ylläpitäminen ja oikean solmun löytäminen oli
tärkeintä.

Alla seuraavat esimerkkitoteutukset VectorArray ja VectorList.


// Tietorakenteet, 1. kursikoe 28.2.2003/AW
//
// Tehtävä 1 a
// Kai-Peter Bäckman Huhtikuu/2003
//

// Selitettävät metodit:

// public boolean isEmpty()
//  Tarkistaa jos koko on 0

// public Object set(int index, Object element)
//  Korvaa taulukossa elementin uudella.

// public boolean remove(Object element)
//  Hakee alusta oikean kohdan ja siirtää kuten remove(int index)

// public void add(int index, Object newElement)
//  Kasvattaa kokoa kuten add(Object newElement), siirtää häntää eteenpäin.

class VectorArray
{
    private static final int INITIAL_MAXIMUM_SIZE = 100;

    private int maximumSize;
    private int currentSize;
    private Object[] storage;

    public VectorArray()
    {
        maximumSize = INITIAL_MAXIMUM_SIZE;
        currentSize = 0;
        storage = new Object[maximumSize];
    }

    public int size()
    {
        return currentSize;
    }

    // Tärkeätä: Aloitetaan haku loppupäästä
    public int lastIndexOf(Object element)
    {
        for(int indexOfCandidate = currentSize - 1; indexOfCandidate >= 0;
            indexOfCandidate--) {

            Object candidate = storage[indexOfCandidate];

            if(element != null) {
                if(element.equals(candidate)) {
                    return indexOfCandidate;
                }
            }
            else if(candidate == null) {
                return indexOfCandidate;
            }
        }

        return -1;
    }

    public Object get(int index)
    {
        if(index > currentSize || index < 0) 
           throw new RuntimeException("Index out of bounds");
        return storage[index];
    }

    // Tärkeätä: Tallennustilan kasvattaminen jos tila loppuu
    public boolean add(Object newElement)
    {
        if(currentSize == maximumSize) {
            Object[] oldStorage = storage;
            maximumSize = maximumSize * 2;
            storage = new Object[maximumSize];
            for(int objectToMove = 0; objectToMove < currentSize; 
                objectToMove++) {
                storage[objectToMove] = oldStorage[objectToMove];
            }
        }
        storage[currentSize] = newElement;
        currentSize++;
        return true;
    }


    // Tärkeätä: Elementtien siirtäminen
    public Object remove(int index)
    {
        if(index > currentSize || index < 0)
           throw new RuntimeException("Index out of bounds");
        Object removedObject = storage[index];
        for(int shiftedIndex = index + 1; shiftedIndex < currentSize;
            shiftedIndex++) {
            storage[shiftedIndex - 1] = storage[shiftedIndex];
        }
        currentSize--;

        return removedObject;
    }
}

// Tietorakenteet, 1. kursikoe 28.2.2003/AW
//
// Tehtävä 1 b
// Kai-Peter Bäckman Huhtikuu/2003
//

// Selitettävät tehtävät:

// public lastIndexOf(Object element)
//  Hakee samoin kuin indexOf(Object element) paitsi taaksepäin

// public Object get(int index)
//  Hakee kuten set(int index) paitsi että palauttaa arvon

// public boolean add(Object newElement)
//  Lisää elementin loppuun käyttäen tunnussolmun previous kenttää

// public Object remove(int index)
//  Toimii samoun kuin remove(Object) paitsi että kohta haetaan hyppimällä


class VectorList
{
    private class Node
    {
        Node previous;
        Node next;
        Object element;
    }

    private int currentSize;
    private Node header;

    public VectorList()
    {
        currentSize = 0;
        header = new Node;
        header.next = header;
        header.previous = header;
    }

    public int size()
    {
        return currentSize;
    }

    public int indexOf(Object targetElement)
    {
        int currentIndex = 0;
        Node iterator = header.next;
        while(iterator != header) {
            if(areElementEquals(targetElement, iterator.element))
                return currentIndex;
            iterator = iterator.next;
            currentIndex++;
        }
        return -1;
    }


    public Object set(int index, Object newElement)
    {
        if(index >= currentSize || index < 0)
           throw new RuntimeException("Index out of bounds");

        Node iterator = header.next;
        for(int skipCount = 0; skipCount < index; skipCount++) {
            iterator = iterator.next;
        }

        Object oldElement = iterator.element;
        iterator.element = newElement;
        return oldElement;
    }

    public boolean remove(Object targetElement)
    {
        Node iterator = header.next;
        while(iterator != header) {
            if(areElementEqual(targetElement, iterator.element)) {
                Node predecessor = iterator.previous;
                Node successor = iterator.next;

                predecessor.next = successor;
                successor.previous = predecessor;

                currentSize--;
                return true;
            }
            iterator = iterator.next;
        }
        return false;
    }

    // Tärkeätä: Erikoistilanne jos lisätään uusi elementti viimeiseksi
    public void add(int index, Object newElement)
    {
        if(index > currentSize || index < 0)
           throw new RuntimeException("Index out of bounds");

        Node predecessor = header;
        for(int skipCount = 0; skipCount < index; skipCount++) {
            predecessor = iterator.next;
        }
        Node successor = predecessor.next;
        Node newNode = new Node;

        newNode.previous = predecessor;
        newNode.next = successor;
        predecessor.next = newNode;
        successor.previous = newNode;

        newNode.element = newElement;

        currentSize++;
    }


    private bool areElementsEqual(Object element1, Object element2)
    {
        if(element1 == null) {
            if(element2 == null) {
                    return true;
            }
        }
        else if(element1.equals(element2)) {
                return true;
        }
        return false;
    }

}