Övning 5

Skriv en generisk klass som implementerar följande interface för mängder:

public interface Set<E> {
    void add(E e);
    void remove(E e);
    boolean contains(E e);
    int size();
}

add ska lägga till elementet i mängden om det inte redan finns ett likadant (equals). remove ska ta bort ett element som är likadant (equals) om ett sådant finns. contains ska avgöra om ett likadant element finns i mängden. size ska tala om hur många element som finns i mängden. Implementationen ska kräva att den generiska typen implementerar Comparable. Den ska använda en sorterad (enligt compareTo) array för att lagra elementen och binärsökning för att hitta dem. Du kan använda java.util.ArrayList istället för en primitiv Java-array. Då blir det enkelt att skjuta in och ta bort element. Du måste inte implementera binärsökning själv utan kan använda metoden Collections.binarySearch.

Ändra följande klass så att den implementerar Comparable enligt beskrivningen nedan.

public class Entry {
    public int n;
    public String s;

    public Entry(int n, String s) {
        this.n = n;
        this.s = s;
    }
}

Om första (mest signifikanta) siffran i decimalrepresentationen av variabeln n i en instans e1 är mindre/större än motsvarande siffra i en instans e2 så ska e1 vara mindre/större än e2. Om första siffrorna är lika så ska e1 vara mindre än e2 om e1:s variabel s innehåller fler tecken än e2:s s. Om den innehåller färre teckan ska e1 anses vara större. Om s i e1 och e2 innehåller lika många tecken ska instanserna vara lika.

Exempel:

    Entry e1 = new Entry(23455, "1");
    Entry e2 = new Entry(7255, "22");
    Entry e3 = new Entry(71, "vv");
    Entry e4 = new Entry(224544, "333");

För dessa instanser ska följande gälla:

e4 < e1 < e2 = e3

T.ex. så ska e1.compareTo(e2) returnera ett tal som är mindre än 0.

Följande klass används för att representera personer i ett släktforskningsprogram:

public class Person {
    public final String name;
    public final Person mother, father;
      // null indicates no known mother/father

    public Person(String name, Person mother, Person father) {
            this.name = name;
            this.mother = mother;
            this.father = father;
    }
}

Varje person har ett namn, en mor och en far. Om mor eller far är okänd så sätts respektive variabel till null.

Lägg till en metod

public boolean isDescendantOf(Person p)

som avgör om aktuell person är en ättling (enligt det som modeller känner till) till p, d.v.s. barn eller barnbarn eller ...

När du avgör om två personer är samma så använd identitetslikhet, d.v.s. ==, ej t.ex. personernas namn.

Test:

    Person p1 = new Person("Asta", null, null);
    Person p2 = new Person("Ingolf", null, null);
    Person p3 = new Person("Kerstin", p1, p2);
    Person p4 = new Person("Börje", p1, p2);
    Person p5 = new Person("Svampbob#", null, null);
    Person p6 = new Person("Tindra", p3, p5);

    System.out.println(p6.isDescendantOf(p3));  --> true
    System.out.println(p6.isDescendantOf(p4));  --> false
    System.out.println(p6.isDescendantOf(p2));  --> true
    System.out.println(p1.isDescendantOf(p6));  --> false
    System.out.println(p4.isDescendantOf(p4));  --> false

Skriv en klass som implementerar avbildningar med följande interface

import java.util.Iterator;

public interface Map<K, V> {
    V get(K key);
    void put(K key, V value);
    void remove(K key);
    int size();
    Iterator<K> keysIterator();
}

get ska returnera värdet som key är associerad med i avbildningen, eller null om key inte är associerad till något värde. put ska associera nyckeln key med värdet value. Om key redan var associerad med ett värde så ska denna associering tas bort. remove ska ta bort associeringen för key om en sådan finns. size ska returnera antal nyckel-värde-par i avbildningen. keysIterator ska returnera en iterator som går igenom alla nycklar i avbildningen.

Du kan implementera klassen på enklast möjliga sätt förutom att använda någon implementering av java.util.Map i API:t. Använd t.ex. en ArrayList och lägg in objekt som var och ett innehåller en nyckel och ett värde. Du kan definiera en lokal klass för sådana objekt, t.ex.:

private class Entry {
        public K k;
        public V v;
        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
}

Du kan då alltså ha en variabel av typen ArrayList<Entry> i din klass. Du kan lägga nyckel-värde-par i denna i godtycklig ordning. När du letar efter en nyckel kan du söka igenom listan linjärt.