public class Table implements ITable { /** * Dies solle die erstmalige Größe von data sein! */ private static final int DEFAULT_INITIAL_SIZE = 4; /** * Fertige Hilfsklasse für einzelne Einträge. */ private static class Entry { private final Object key; private Object value; /** * Konstruktor. * @param key Schlüsselbegriff. * @param value eigentlicher Inhalt. */ public Entry(Object key, Object value) { this.key = key; this.value = value; } /** * Gibt den Schlüsselbegriff des Eintrags zurück. * @return Schlüssel. */ public Object getKey() { return key; } /** * Gibt den Inhalt des Eintrags zurück. * @return Inhalt. */ public Object getValue() { return value; } /** * Verändert den Inhalt des Eintrags. * @param value neuer Inhalt. * @return vorhergehender Inhalt. */ public Object setValue(Object value) { Object oldValue = this.value; this.value = value; return oldValue; } } private int size; // Anzahl der gespeicherten Adressen. private Entry[] data; // Feld mit den Daten. public Table() { this.data = new Entry[DEFAULT_INITIAL_SIZE]; this.size = 0; } /* (non-Javadoc) * @see ITable#size() */ public int size() { return (size); } /* (non-Javadoc) * @see ITable#put(java.lang.Object, java.lang.Object) */ public Object put(Object key, Object value)throws NullPointerException { if (key ==null) throw new NullPointerException(null); else{ int messageid = getArrayIndex(key); // falls eintrag noch nicht existiert neuen anlegen if (messageid < 0){ try { data[size++] = new Entry(key, value); return null; } catch(ArrayIndexOutOfBoundsException e){ // neuen array anlegen, der doppelte groesse hat this.data = new Entry[DEFAULT_INITIAL_SIZE*2]; Entry [] puffer = new Entry[size*2]; // alte werte "umreferenzieren" for (int x=0; x<size; x++){ puffer[x] = data[x]; } // array referenz auf neuen array legen data = puffer; // nun element hinzufuegen data[size] = new Entry(key, value); return null; } catch (NullPointerException e) { throw new NullPointerException (null); } } else data[messageid].value = value; return data[messageid].value; } } private int getArrayIndex(Object key){ for (int y=0; y<size; y++) if (data[y].key.equals(key)) return y; return -1; } /* (non-Javadoc) * @see ITable#get(java.lang.Object) */ public Object get(Object key)throws NullPointerException { if (key==null)throw new NullPointerException("Key ist null"); else{ for (int i=0; i<size; i++) if (data[i].key.equals(key)) return data[i].value; return null; } } /* (non-Javadoc) * @see ITable#containsKey(java.lang.Object) */ public boolean containsKey(Object key)throws NullPointerException { if (key==null)throw new NullPointerException("Key ist null"); else{ for (int x=0; x<size; x++) if (data[x].key.equals(key)) { return true; } } return false; } /* (non-Javadoc) * @see ITable#remove(java.lang.Object) */ public Object remove(Object key){ if (key == null)throw new NullPointerException("key must not be null"); int i = 0; while (i < size && !data[i].key.equals(key)) i++; int index=(i == size) ? -1 : i; Object result = null; if (index >= 0) { result = data[index].value; int toMove = size - index - 1; if (toMove > 0) System.arraycopy(data, index+1, data, index, toMove); data[--size] = null; } return result; } /* (non-Javadoc) * @see ITable#keys() */ public Object[] keys() { Object[] returnArray = new Object[size]; for (int i=0; i<size; i++) { returnArray[i] = data[i]; } return returnArray; } }
public interface ITable { /** * Gibt die Anzahl der gespeicherten Eintragungen zurück. * * @return Anzahl der eingetragenen Datensätze. */ public int size(); /** * Trägt ein Objekt unter einem Suchbegriff ein. * Wenn der Suchbegriff bereits vorhanden, wird die zugehörige * Objektreferenz überschrieben und das vorher dort gespeicherte * Objekt wird zurückgegeben. Wenn bisher unter dem Schlüssel kein * Objekt gespeichert war, wird <code>null</code> zurückgegeben. * * @param key Suchschlüssel. * @param value Inhaltsobjekt. * @return vorheriger Eintrag oder <code>null</code>. * @throws NullPointerException wenn <code>key == null</code>. */ public Object put(Object key, Object value); /** * Gibt das unter einem Suchbegriff gespeicherte Objekt zurück. * * @param key Suchschlüssel. * @return gefundenes Objekt oder <code>null</code>. * @throws NullPointerException wenn <code>key == null</code>. */ public Object get(Object key); /** * Stellt fest, ob der Suchschlüssel in der Tabelle eingetragen ist. * * @param key Suchschlüssel. * @return <code>true</code> wenn vorhanden. * @throws NullPointerException wenn <code>key == null</code>. */ public boolean containsKey(Object key); /** * Entfernt den Eintrag zu dem angegebenen Suchschlüssel. * Wenn kein Eintrag zu dem Schlüssel gefunden wird, wird * <code>null</code> zurückgegeben. * * @param key Suchschlüssel. * @return bisher gespeichertes Objekt oder <code>null</code>. * @throws NullPointerException wenn <code>key == null</code>. */ public Object remove(Object key); /** * Gibt ein Feld mit allen Suchschlüsseln zurück. * * @return Feld aller Schlüssel. */ public Object[] keys();}
import java.util.Arrays;import junit.framework.Test;import junit.framework.TestCase;import junit.framework.TestSuite;public class TableTest extends TestCase { /* * ACCEPTS_NULL = true: null ist als key erlaubt. * = false: null-keys erzeugen NullPointerException. */ private static final boolean ACCEPTS_NULL = false; /** * Diese Methode legt fest, welche Tests durchgeführt werden. * Wenn man einzelne Tests abschalten will, muss man nur die * entsprechende Zeile auskommentieren. * <p> * Wenn man immer die vollständige Ausführung aller Tests haben * will, sollte man die Methode suite komplett entfernen. */ public static Test suite() { TestSuite t = new TestSuite(); t.addTest(new TableTest("testConstructor")); t.addTest(new TableTest("testOnePutGet")); t.addTest(new TableTest("testOverwriting")); t.addTest(new TableTest("testRemove")); t.addTest(new TableTest("testNullKey")); t.addTest(new TableTest("testNullValue")); t.addTest(new TableTest("testKeys")); t.addTest(new TableTest("testRandomly")); return t; } /** * Konstructor. * Der Konsttruktor wird nur wegen der vorangehenden Methode * <code>suite</code> genötigt. * * @param sName der auszuführenden Testmethode. */ public TableTest(String testMethod) { super(testMethod); } /* * Hiermit wird der Belastungstest gesteuert. Die Zahl 1000 ist keine * feste Größe, die im Programm berücksichtigt werden darf! Sie könnte * z.B. auch 10 Millionen betragen. */ protected static final int RANDOM_TESTS = 1000; /* * Ein paar Hilfsobjekte. */ protected static final TestKey K1 = new TestKey(177); protected static final TestKey K2 = new TestKey(233); protected static final TestKey K3 = new TestKey(1235); /* * Variable für das Testobjekt. */ protected ITable t; /** * Vorbereitungsarbeiten. */ public void setUp() { t = new Table(); TestKey.clearTotalCompares(); K1.clearCompares(); K2.clearCompares(); K3.clearCompares(); } /** * Verlangt, dass ein gerade konstruiertes Objekt, leer ist. * Es dürfen keine Daten gefunden werden. */ public void testConstructor() { assertEquals("Tabelle muss leer sein", 0, t.size()); assertFalse("bei leerer Tabelle darf containsKey nichts finden", t.containsKey(K1)); } /** * Verlangt, dass sich ein einzelnes Schlüssel-Wert-Paar * eintragen und wiederfinden lässt. Zusätzlich wird * verlangt, dass nicht unnötig viele Vergleiche * stattfinden. */ public void testOnePutGet() { t.put(K1, K2); assertEquals("size() muss nach einem put gleich 1 sein,", 1, t.size()); assertTrue("containsKey findet das eingetragene Objekt nicht", t.containsKey(K1)); assertSame("es wird ein falsches Objekt zurückgegeben", K2, t.get(K1)); assertFalse("contains findet einen nicht vorhandenen Schlüssel", t.containsKey(K2)); assertNull("wenn nichts gefunden, muss get null zurückgeben", t.get(K2)); int compares = TestKey.getTotalCompares(); assertTrue("Es wurden 4 Vergleiche erwartet, aber "+ compares + " gezählt", 4 >= compares); } /** * Verlangt, dass ein bereits vorhandener Eintrag mit * einem neuen Wert überschrieben wird. */ public void testOverwriting() { t.put(K1, K2); assertSame("das eingetragene Objekt kommt nicht wieder zurück", K2, t.get(K1)); t.put(K1, K3); assertSame("beim Überschreiben darf kein neues Objekt angelegt werden", K3, t.get(K1)); assertTrue("zuviele Vergleiche!", 3 >= K1.getCompares()); assertEquals("Überschreiben darf nicht die Anzahl erhöhen", 1, t.size()); } /** * Verlangt, dass Elemente richtig entfernt werden. * Bei dem Aufruf muss der vorhergehende Wert oder * <code>null</code> zurückgegeben werden. * Es ist kein Fehler, ein nicht vorhandens Element zu * entfernen. */ public void testRemove() { assertNull("es muss null zurückgegeben werden", t.remove(K1)); t.put(K1, "x"); t.put(K2, "a"); t.put(K3, K1); assertEquals("der alte Wert war a", "a", t.remove(K2)); assertNull("der Schlüssel wurde wohl nicht entfernt", t.remove(K2)); assertEquals("die Anzahl wurde nicht auf 2 erniedrigt", 2, t.size()); assertTrue("andere Werte wurden mitgelöscht", t.containsKey(K1)); assertFalse("der Wert wurde nicht richtig entfernt", t.containsKey(K2)); assertTrue("andere Werte wurden mitgelöscht", t.containsKey(K3)); t.put(K2, "x"); assertEquals("es wird nicht mehr der richtige Wert gefunden", "x", t.remove(K1)); assertEquals("es wird nicht mehr der richtige Wert gefunden", "x", t.remove(K2)); assertSame("es wird nicht mehr der richtige Wert gefunden", K1, t.remove(K3)); assertEquals("die Tabelle müsste leer sein", 0, t.size()); } /** * Verlangt, dass die Tabelle mit <code>null</code> Argumenten für * Key und Value richtig umgeht. <code>null</code> wird hierbei * als gültiger und eindeutiger Schlüssel angesehen. */ public void testNullKey() { if (ACCEPTS_NULL) { t.put(null, ""); assertEquals("ein null-Key soll einen Eintrag erlauben", 1, t.size()); assertTrue("der null-Key wird nicht gefunden", t.containsKey(null)); assertEquals("es wird der falsche Inhalt zu null zurückgegeben", "", t.get(null)); assertEquals("es wird ein falscher Vorgängerwert zurückgegeben", "", t.put(null, "x")); assertEquals("Löschen von null funktioniert nicht", "x", t.remove(null)); assertEquals("Löschen von null funktioniert nicht", 0, t.size()); } else { String message = "null müsste NullPointerException erzeugen"; try { t.put(null, ""); fail(message); } catch (NullPointerException expected) { /* this shall happen */ } try { t.get(null); fail(message); } catch (NullPointerException expected) { /* this shall happen */ } try { t.containsKey(null); fail(message); } catch (NullPointerException expected) { /* this shall happen */ } try { t.remove(null); fail(message); } catch (NullPointerException expected) { /* this shall happen */ } } } /** * Verlangt, dass die Tabelle mit <code>null</code> Argumenten für * Value richtig umgeht. */ public void testNullValue() { t.put("", null); assertEquals("ein leerer String mit null-Wert wird falsch behandelt", 1, t.size()); assertTrue("contains-Test funktioniert nicht mit null-Wert", t.containsKey("")); assertNull("die Rückgabe müsste null sein", t.get("")); } /** * Testet ob die Rückgabe von keys() wirklich ein * Feld mit genau allen Schlüsseln ist. */ public void testKeys() { t.put(K1, "x"); t.put(K2, "a"); t.put(K3, K1); t.put("a", ""); t.put("b", ""); Object[] keys = t.keys(); int nKeys = keys.length; assertEquals("keys enthält zu wenig Schlüssel: "+ nKeys +" anstelle von 5", 5, nKeys); int count = 0; for (int i = 0; i < t.size(); i++) { // assertTrue("keys gibt nicht vorhandenen Schlüssel zurück", // t.containsKey(keys[i])); if (keys[i].equals(K1)) count++; if (keys[i].equals(K2)) count++; if (keys[i].equals(K3)) count++; if (keys[i].equals("a")) count++; if (keys[i].equals("b")) count++; } assertEquals("es wurden nicht alle Schlüssel kopiert", 5, count); } /** * Testet eine großer Anzahl von Operationen. * Damit soll vor allem die Speicherverwaltung * getestet werden. */ public void testRandomly() { int putCount = 0; Double keys[] = new Double[RANDOM_TESTS]; for (int i = 0; i < RANDOM_TESTS; i++) { Double key = new Double(Math.random()); Object oldValue = t.put(key, new Integer(i)); if (oldValue == null) keys[putCount++] = key; } assertEquals(putCount, t.size()); Object[] tKeys = t.keys(); assertEquals(putCount, tKeys.length); Arrays.sort(keys); Arrays.sort(tKeys); assertTrue(Arrays.equals(keys, tKeys)); for (int i = 0; i < putCount; i++) { assertTrue(t.containsKey(keys[i])); t.remove(keys[i]); } assertEquals(0, t.size()); assertEquals(0, t.keys().length); }}
LOGIN
SUCHEStatus
