Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Dateiinhalt

/**
 * Implementiert den abtrakten Datentyp sortierte doppelt verkettete Liste
 */
public class SortedList implements LinkedList {
  
  // der erste Knoten und der letzte Knoten der sortierten Liste
  public ListNode first;
  public ListNode last; 
  
  /**
   * Die sortierte Liste enhält immer mindestens zwei Knoten.
   * Der first-Knoten wird mit -unendlich und 
   * der last-Knoten mit +unendlich initialisiert.
   */
  public SortedList() {
    this.first = new ListNode(Integer.MIN_VALUE);    
    this.last = new ListNode(Integer.MAX_VALUE);
    this.last.prev = first;
    this.first.next = last;
  }
  
  public void checkInput(int value) throws IllegalArgumentException {
    if (value == first.value || value == last.value) {
      throw new IllegalArgumentException(
          "Die Eingabe reservierter Werte wie '" + value + "' ist nicht erlaubt.");
    }
  }
  
  @Override
  public ListNode search(int v) {
    checkInput(v);
    return first.search(v);
  }
  
  @Override
  public ListNode insert(int v) {
    checkInput(v);
    return this.first.insert(v);   
  }
  
  public void delete(int v) {
    checkInput(v);
    this.first.delete(v);
  }
    
  public void print() {
    this.first.print();
  }
    
  public boolean checkReferences() {
    return this.first.checkReferences();
  }
  
  /**
   * Testläufe
   */
  public static void main(String[] argv) {
    SortedList s = new SortedList();
    
    System.out.println("Einfügen mit insertAfter");
    ListNode first = s.first;
    for (int i = 1; i <= 5; i++) {
      if (first != null) {
        first = first.insertAfter(i);
        s.print();
        checkAndPrint("Verlinkung ok? ", s.checkReferences());      
        checkAndPrint("Knoten vorhanden? ", s.search(i) != null && s.search(i).value == i);
      }
    }
    
    System.out.println("\nDie Ausgabe sollte so aussehen:");
    System.out.println("First <-->  1 <-->  2 <--> 3 <-->  4 <--> 5 <--> Last");

    System.out.println("\nSuche ausgehend von First (nach Rechts)");
    for (int i = 1; i < 4; i++) {
      ListNode node = s.search(i);
      System.out.println("Knoten " + i + " gefunden? " + ((node!=null&&node.value == i) ? "Ja" : "Nein"));
      assert(node != null && node.value == i);
    }
    
    System.out.println("\nSuche ausgehend vom Knoten 4 (nach Links)");
    ListNode node = s.search(4);
    if (node != null && node.value == 4) {
      for (int i = 1; i < 3; i++) {
        ListNode leftNode = node.search(i);
        System.out.println("Knoten " + i + " gefunden? " + ((leftNode!=null&&leftNode.value == i) ? "Ja" : "Nein"));
        assert(leftNode != null && leftNode.value == i);
      }
    }
    else {
      System.out.println("Knoten 4 nicht gefunden");
    }
    
    System.out.println("\nSortiert einfügen (insert)");
    for (int i = 10; i >= 6; i--) {
      s.insert(i);      
      s.print();
      checkAndPrint("Verlinkung ok? ", s.checkReferences());      
      checkAndPrint("Knoten vorhanden? ", s.search(i) != null && s.search(i).value == i);
    }
    
    System.out.println("\nDie Ausgabe sollte so aussehen:");
    System.out.println("First <-->  1 <-->  2 <-->  3 <-->  4 <-->  5 <-->  6 <-->  7 <-->  8 <-->  9 <--> 10 <--> Last");
    
    System.out.println("\nLöschen");
    for (int i = 5; i < 10; i++) {
      boolean vorhanden = s.search(i) != null && s.search(i).value == i;
      s.delete(i);      
      s.print();
      checkAndPrint("Verlinkung ok? ", s.checkReferences());
      checkAndPrint("Knoten gelöscht? ", vorhanden && (s.search(i) == null || s.search(i).value != i));
    }

    System.out.println("\nDie Ausgabe sollte so aussehen:");
    System.out.println("First <-->  1 <-->  2 <-->  3 <-->  4 <--> 10 <--> Last");

  }
  
  public static void checkAndPrint(String message, boolean correct) {
    if (!correct) {
      System.out.println(message + "NEIN");
    } 
    assert(correct);
  }
}