Thomas Kramer

IT-COW | All posts tagged 'Rabin-Karp-Algorithmus'

Mehrfach-Mustersuche mit dem RK-Algorithmus

By Administrator at Dezember 14, 2011 16:51
Filed Under: Algorithmen, Java, Programmierung allgemein, Studium

Der Rabin-Karp-Algorithmus ist in der Einzel-Mustersuche anderen String-Matching-Algorithmen wie KMP unterlegen, hat aber den Vorteil beliebig viele Zeichenketten in einem Durchlauf im Durchschnitt in O(n) zu finden.

 

Er ist daher dafür prädestiniert alle Vorkommen von verschiedenen Mustern gleicher Länge zu finden - z. B. bei der Suche nach Plagiaten. Deswegen habe ich meine Implementierung einmal dahingehend angepasst. Bei dieser Variante wird die Position des ersten Fundes zusammen mit der Anzahl der Funde direkt ausgegeben und alle Positionen auf der Konsole.

 

Die Muster müssen mit einem Komma separiert eingegeben werden. Das Verfahren funktioniert nur wenn alle Muster gleich lang sind, weil der rollende RK-Algorithmus einen Verschiebefaktor benutzt der von der Musterlänge abhängig ist. Wenn sich die Längen unterscheiden wird eine Fehlermeldung mittels JOptionPane ausgegeben.

 

Damit habe ich das Thema String-Matching nun einigermaßen umfassend abgehandelt. Es gibt noch weitere Such-Algorithmen, aber bei den heutigen PC-Geschwindigkeiten werden andere Verfahren zunehmend irrelevant. Interessanter wäre eher noch eine Implementierung zur unscharfen Suche, dem approximativen String-Matching. Übrigens lassen sich nun alle meine Blog-Einträge, die sich mit dem Thema String-Matching befassen, über selbiges Tagging-Stichwort und einer einzelnen Suche auffinden.

 

Allgemeines noch zu Encodings: Die Kodierung einer Datei lässt sich z. B. mit dem GNU-File-Befehl herausfinden - auch die Art des verwendeten Zeilenumbruchs wird dabei herausgegeben. In Unicode-Dateien gibt es mit dem Byte Order Mark eine spezielle Kennzeichnung, in XML-Dateien wird die Kodierung am Dateianfang sogar explizit im Klartext angegeben. Eine hundertprozentig zuverlässige Methode die Kodierung herauszufinden (wenn sie nicht angegeben ist) existiert jedoch nicht.

 

Außerdem wollte ich mir die Links von wsoftware.de bezüglich Verwendung von Character-Sets und der Angabe des Encodings bei StreamReadern in Java vermerken. Vielleicht ist auch diese generelle Übersicht über Encodings hilfreich. Zeichensatzkonvertierungen kann man unter Linux übrigens mit dem iconv-Befehl durchführen.

 

Ergänzung 16.12.2011: Eventuell doch besser eine höhere Zahl für q wählen, mit 1024 gab es immer Kollisionen. Außer einer niedrigeren Geschwindigkeit haben Kollisionen aber keine weiteren Folgen, da bei einem Match auch immer ein Stringvergleich stattfindet.

 

Da ich hier immer bitweise Modulo berechne muss für q eine Zweierpotenz gewählt werden.

 

Ergänzung 21.12.2011: File scheint LF-Zeilenumbrüche nicht für erwähnenswert zu halten, nur bei CRLF erfolgt ein Hinweis. Die Typerkennung funktioniert auch nicht immer zuverlässig, jedoch kann sie mit einer Magic-Datei als Typ-Datenbank verbessert werden.

 

Die Diplomarbeit von Gausi.de listet übrigens zur mehrfachen Mustersuche folgende weitere Algorithmen auf:

 

  • Naive Triesuche
  • Aho-Corasick
  • Advanced Aho-Corasick
  • Commentz-Walter
  • Set Horspool
  • Wu-Manber
  • Set-Backward-Oracle-Matching
  • Multiple Shift-And

 

Ergänzung 22.12.2011: In dieser Schrift der technischen Universität München wurde auf Seite 77 der Beweis geführt dass q größer als n*m sein sollte, um Kollisionen zu vermeiden.

 

Update 06.03.2012: Ich verwende nun den überladenen append-Befehl des StringBuilders mit drei Parametern, wodurch das Einlesen weniger Quellcodezeilen benötigt.

 

Außerdem habe ich die Zeilen mit der Muster-Vorverarbeitung aus der Rabin-Karp-Routine nun in die Präprozessing-Routine verfrachtet, weil eine Routine mit dem Namen des Algorithmus imho NUR den Algorithmus beherbergen sollte.

 

Vorher hatte ich außerdem als Ergebnisklasse für die Suchergebnisse eine generische Array-Liste vom Typ String verwendet, in der sowohl die Suchpatterns als auch die gefundenen Suchpostionen gemeinsam in einem einzelnen String gespeichert waren. Das war natürlich nicht ganz optimal, aber für generische Typen kann man leider nur einen Typ als Input verwenden - ArrayList<String, Integer> funktioniert leider nicht.

 

Daher habe ich das nun anders gemacht und eine eigene Klasse als Input-Typ für die ArrayList deklariert - ArrayList<SearchResults> - es sollte aber klar sein das die java.util.Collections.sort-Methode dann nicht mehr funktioniert und die Ergebnisse auf der Konsole nur noch nach der Suchposition sortiert sind.

 

Ergänzung 21.03.2012: Unten habe ich zweimal die get()-Funktion auf das Hashtable angewandt - auch wenn eine Hashtabelle im Regelfall einen Zugriff in O(1) erlaubt wäre ein Zwischenspeichern in einem String sinnvoller um nur einen get()-Aufruf zu haben.

 

Ergänzung 27.03.2012: In diesem Script ("Algorithmen auf Sequenzen") der Universität Dortmund sind ebenfalls einige Pattern-Matching-Algorithmen für die Mehrfachsuche erklärt worden.

 

/* Mehrfachmustersuche mit dem Rabin-Karp-Algorithmus (32-Bit) von Thomas Kramer
   Version 1.30 vom 06.03.2012 */


/* Konfiguration */
   /* Basis-Wert: 10 für Zahlensuche verwenden
      (Anzahl Buchstaben des Alphabets) */

   int base = 257;   
   /* Modulo-Wert für die Hash-Funktion */
   int q = 1024;    
  
   /* Modus bestimmen; true für Textsuche, false für Zahlensuche */
   boolean textSearch = true;     
   /* Patterndatei verwenden für längere Suchmuster, auf "" setzen wenn Eingabe
      von Hand gewünscht. Forwardslash / verwenden, gemäß
      http://docs.oracle.com/javase/tutorial/essential/environment/sysprop.html
      wird in Java plattformspezifisch eh automatisch umgewandelt */

//   String patternFile = "C:/Users/thomas/Downloads/m1.TXT";
   String patternFile="";     
  
   color buttoncolor = color(102);
   color highlight = color(51);
   color c1 = color(0, 0, 0);
   color c2 = color(255, 255, 255);   
   color c3 = color(193, 185, 185);
/* Konfiguration-Ende */

color currentcolor;
RectButton rect1,rect2,rect3;
boolean locked = false;
String loadPath="";
StringBuilder completeString=new StringBuilder(0);
String searchString = "";
SearchPatterns searchPatterns;
ArrayList<SearchResults> searchResults;
String searchedString="";
boolean fileSelected=false;
int shiftFactor=0;
int searchPosition=0;
String timeString="";
/* fm = false matches, Kollisionen */
int fm = 0; 
/* wenn bitweise Modulo gerechnet werden soll muss q-1 nicht jedes Mal
   neu berechnet werden */

int reducedQ = q - 1;

import java.lang.Math;
import java.util.concurrent.TimeUnit;
import javax.swing.JOptionPane;

/* Suchmuster-Klasse */
public class SearchPatterns
{
  public Hashtable<Integer, String> patterns; 
  public int minLength = 0;
  public int maxLength = 0;
  public int diffLength = 0; 
  private int randomHashLength = 0;
 
  /* Konstruktor */
  public SearchPatterns()
  {
     patterns = new Hashtable<Integer, String>();       
  }
 
  /* Hash hinzufügen */
  public void addPattern(Integer hash, String hashtext)
  {
    if (hash == 0 || trim(hashtext) == "")
      return;
     
    patterns.put(hash, hashtext);
    randomHashLength = hashtext.length();
  }   
 
  /* minimale und maximale Größe der Muster berechnen */
  public void setLengths()
  {
    if (patterns.size() == 0)
      return;
     
    /* Initialisierungswerte für Vergleiche setzen */
    minLength = randomHashLength;
    maxLength = 0;
    for (String value: patterns.values())
    {
       /* Minimum finden */
       minLength = min(minLength, value.length());
        
       /* Maximum finden */
       maxLength = max(maxLength, value.length()); 
    }
    diffLength = maxLength - minLength;       
  }
}

/* Results-Klasse der gefundenen Muster */
public class SearchResults
{
  public String  searchPattern = null;
  public Integer searchResult  = null;

  /* Konstruktor */
  public SearchResults()
  {
     searchPattern = "";
     searchResult  = 0;
  } 
 
  public void addResult(String pattern, Integer result)
  {
    searchPattern = pattern;
    searchResult  = result;   
  } 
}

/*-----------------------------------------------------------------------------
 *  Initialisierungen
 *-----------------------------------------------------------------------------*/

void setup()
{   
  /* Test der Hashfunktionen selbst */
  testHashFunction();
 
   /* Größe des Screens setzen */
  size(screen.width-400, 300);
 
  /* Bildschirm löschen */
  background(c3);
 
  /* Buttons instanziieren */
  rect1 = new RectButton(((screen.width)/2)-400, 130, 50, 20, buttoncolor, highlight); 
  rect2 = new RectButton(((screen.width)/2)-400, 152, 380, 20, buttoncolor, highlight);   
  rect3 = new RectButton(((screen.width)/2)-400, 175, 50, 20, buttoncolor, highlight);     
 
  /*-----------------------------------------------------------------------------
   *  Patternfile laden
   *-----------------------------------------------------------------------------*/
 
  patternFile = trim(patternFile);
  if (patternFile != "")
  {
    File f = new File(patternFile);
    if (!f.exists())
      throw new IllegalArgumentException("Fehler, Patterndatei ist angegeben und existiert nicht!");
     
    searchString = loadFile(patternFile).toString();
  }
}

/*-----------------------------------------------------------------------------
 *  Datei laden
 *-----------------------------------------------------------------------------*/

StringBuilder loadFile(String fileName)
{       
  File file = new File(fileName);
  int fileLength = (int) file.length();  
  file = null;
 
  BufferedReader br = null;
  StringBuilder result = new StringBuilder(fileLength);            
  try
  {
    char[] ioBuf = new char[1000];     
    /* buffer liefert Anzahl gelesener Zeichen zurück, siehe auch
       http://www.dpunkt.de/java/Referenz/Das_Paket_java.io/4.html#read%28%29 */
 
    int buffer = 0;   
   
    br = new BufferedReader(new FileReader(fileName));     
    while ((buffer = br.read(ioBuf,0,1000)) != -1)      
    {
      /* eingelesene Zeile anhängen */
      result.append(ioBuf,0,buffer);          
    }
  } catch (IOException e)
  {
    println("Datei konnte nicht (vollständig) eingelesen werden!");
  } finally
  {
    try
    {
      if (br != null)
        br.close();
    } catch (IOException e) {}  
  }   
 
  return result;
}

/*-----------------------------------------------------------------------------
 *  draw()-Funktion wird aufgerufen wenn der Bildschirm neu gezeichnet wird
 *-----------------------------------------------------------------------------*/

void draw()
{
  /*-----------------------------------------------------------------------------
   *  Hintergrundfarbe setzen, dabei wird auch der gesamte Bildschirm gelöscht
   *-----------------------------------------------------------------------------*/

  background(c3);   
 
  /*-----------------------------------------------------------------------------
   *  Überschriften setzen
   *-----------------------------------------------------------------------------*/

  fill(c2);
  textSize(20);
  text("Der Rabin-Karp-Algorithmus 32-Bit", ((screen.width)/2)-370, 50);
  textSize(15);
  text("von Thomas Kramer", ((screen.width)/2)-270, 80);
  text("(ESC zum Abbrechen)", ((screen.width)/2)-275, 110);
  textSize(13);
 
  /*-----------------------------------------------------------------------------
   *  Buttons setzen und beschriften
   *-----------------------------------------------------------------------------*/
   
  rect1.display();
  if (patternFile == ""
  {
    rect2.display();           
  } else {
    fill(c2);
    text(patternFile, ((screen.width)/2)-398, 167);                   
  }
  rect3.display();                 
  update(mouseX, mouseY);    
  text("FileOpen: ", ((screen.width)/2)-485, 145);
  text("SearchString: ", ((screen.width)/2)-485, 167); 
  text("Start ", ((screen.width)/2)-485, 190);   
 
  /*-----------------------------------------------------------------------------
   *  Eingabetexte, Statusmeldungen etc. setzen
   *-----------------------------------------------------------------------------*/

  /* weiße Schriftfarbe setzen */
  fill(c2); 
  /* anzeigen des Suchstrings */
  if ((patternFile == "") && (searchString.length() > 0))
      text(searchString, ((screen.width)/2)-398, 167);               
  text(searchString.length() + " Bytes Länge", ((screen.width)/2), 167);           

  /* ausgewählte Datei anzeigen */ 
  if (loadPath!=null)
    text(loadPath, ((screen.width)/2)-330, 145);                          

  /* Suchstring anzeigen */ 
  text(searchedString, ((screen.width)/2)-485, 230);  
 
  /* wenn Postion ungleich -1 ist der Algorithmus bereits einmal durchgelaufen */
  if (searchPosition != -1)
  {
    fill(c1);   
   
    /* Suchposition anzeigen */
    text("Pos " + (searchPosition + 1), ((screen.width)/2)-485, 243);             
   
    /* Ergebnis der Zeitmessung anzeigen */
    text(timeString, ((screen.width)/2)-485, 265);
 
  } else {
    text("Pos " + searchPosition + " = nicht gefunden", ((screen.width)/2)-485, 243);                       
  }

}

/*-----------------------------------------------------------------------------
 *  Test-Funktion um Übereinstimmung zwischen initialer und rollender Hash-Funktion
 *  sicherzustellen.
 *-----------------------------------------------------------------------------*/

void testHashFunction()
{
  completeString.setLength(0); 
  searchString="";
  if (textSearch)
  {
    completeString.append("War and Peace von Leo Tolstoi"); 
    searchString = "toi"
  } else {
    completeString.append("2359023141526739921"); 
    searchString = "39921"
  }

  println("Text:   " + "'" + completeString + "'");
  println("Muster: " + "'" + searchString + "'"); 
     
  /* berechne Hashwert der letzten Zeichen mit der initialen Hash-Funktion */
  int hs1   = hashFirst(completeString.substring(completeString.length()-searchString.length()),
                        searchString.length());   
  /* berechne Hashwert der letzten Zeichen mit der rollenden Hash-Funktion,
     ausgehend vom ersten Hashwert der initialen Hash-Funktion */

  int hs2   = hashFirst(completeString.substring(0,searchString.length()),
                        searchString.length()); 
  for (int i=1;i<=(completeString.length()-searchString.length());i++)
    hs2 = hash(hs2,i,searchString.length());
   
  println("initiale Hash-Funktion: " + hs1);       
  println("rollende Hash-Funktion: " + hs2);  
 
  if (hs1 != hs2)
  {
    throw new IllegalArgumentException("Fehler, initiale- und rollende Hashfunktion ergeben unterschiedliche Werte!");
  } else {
    println("Hash-Funktionalität ok!\n");
    searchString = "";
    completeString.setLength(0);
  }
}

/*-----------------------------------------------------------------------------
 *  initiale Hash-Funktion
 *-----------------------------------------------------------------------------*/

int hashFirst(String searchText, int patternLength)
{
  int result=0;
  if (textSearch)
  {
    int reducedBase=1;
    for (int i=(patternLength-1); i>=0; i--)
    {
      if (i != (patternLength-1))
        reducedBase = bitModulo(reducedBase * base); 
        
      result += bitModulo(reducedBase * (int) searchText.charAt(i));
      result = bitModulo(result);    
    }   
    shiftFactor=reducedBase;    
  } else {
    /* für den Zahlensuchmodus wird natürlich eine Basis von 10 benötigt */
   
    /* Verschiebe-Faktor berechnen */
    shiftFactor=1;     
    for (int i=1;i<patternLength;i++)
      shiftFactor=bitModulo(shiftFactor * base);
   
    /* Zahl ausschneiden */
    result = Integer.parseInt(searchText.substring(0,patternLength)); 
  }    
  return bitModulo(result);   
}

/*-----------------------------------------------------------------------------
 *  Diese Modulo-Variante arbeitet bitweise mit dem &-Operator und benötigt daher
 *  als q eine Zweierpotenz
 *-----------------------------------------------------------------------------*/

int bitModulo(int x)
{
   return (x & reducedQ);
}

/*-----------------------------------------------------------------------------
 *  rollende Hash-Funktion
 *-----------------------------------------------------------------------------*/

int hash(int oldHashValue, int startPos, int patternLength)
{
  /* wenn die gesamte Stringlänge kleiner als die des Musters ist, kann das Muster
     nicht vorkommen */

  if (completeString.length() < patternLength)
    return 0;
 
  int result=0;
 
  int intValue;
  int intValue2;
  if (textSearch)
  {
    /* das erste Zeichen von links bestimmen, das wegfällt */
    intValue  = (int) completeString.charAt(startPos-1);
    /* das hinzukommende Zeichen von rechts bestimmen */
    intValue2 = (int) completeString.charAt(startPos+patternLength-1);   
  } else {
    /* das erste Zeichen von links bestimmen, das wegfällt */
    intValue  = Integer.parseInt(completeString.substring(startPos-1,startPos)); 
    /* das hinzukommende Zeichen von rechts bestimmen */
    intValue2 = Integer.parseInt(completeString.substring(startPos+patternLength-1,startPos+patternLength));
  }

//  println(oldHashValue + "-" + intValue + "-" + shiftFactor + "-" + base + "-" + intValue2);   
  result = ((oldHashValue - (intValue * shiftFactor)) * base) + intValue2;
  result = bitModulo(result);
 
  return result; 
}

/*-----------------------------------------------------------------------------
 *  allgemeine Vorarbeiten
 *-----------------------------------------------------------------------------*/

void praeProcessing()
{
  if  (loadPath == "" || searchString.length() == 0)
    return;
       
  String pattern; 
  String[] sPatterns = null;         
  long completeTimeBefore = 0;
  long completeTimeAfter  = 0;
  long completeTimeDiff = 0;
  int i = 0;
 
  /* Muster aufsplitten, nach Kommas - und sortieren */ 
  sPatterns = searchString.toString().split(",");
  for (i = 0; i < sPatterns.length; i++)
     sPatterns[i] = trim(sPatterns[i]);
  java.util.Arrays.sort(sPatterns);
 
  /* in searchPatterns-Klasse einfügen */
  searchPatterns = new SearchPatterns();   
  for (i = 0; i < sPatterns.length; i++)
  {
    pattern = sPatterns[i];
    if (pattern != "")
      searchPatterns.addPattern(hashFirst(pattern, pattern.length()), pattern);    
  }
  searchPatterns.setLengths();
  sPatterns = null
 
  if (searchPatterns.diffLength != 0)
  {
    JOptionPane.showMessageDialog(null,"Patternlängen sind unterschiedlich!","Fehler", JOptionPane.CANCEL_OPTION);
    return;
  } 
 
  searchString = ""
 
  /* Datei laden */
  completeString.setLength(0);
  completeString = loadFile(loadPath); 
 
  /* nimm die Vorher-Zeit für Gesamtdurchlauf */   
  completeTimeBefore = System.currentTimeMillis();   
 
  /* Algorithmus starten */
  searchResults = rabinKarp();
 
  /* nimm die Danach-Zeit für Gesamtdurchlauf und bestimme Differenz */   
  completeTimeAfter = System.currentTimeMillis();     
  completeTimeDiff   = completeTimeAfter - completeTimeBefore;   
   
  /* Ausgabe für Gesamtdurchlauf formatieren */
  timeString = String.format("Gesamtzeit: %02d min, %02d sec, %03d milliseconds - %d Funde",
    TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff),
    TimeUnit.MILLISECONDS.toSeconds(completeTimeDiff) -
      TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff)),
    completeTimeDiff % 1000,
    searchResults.size());
   
  if (searchResults.size() > 0)
  {
    /* sortieren funktioniert so leider nicht mehr */
    /* java.util.Collections.sort(searchResults); */
   
    /* das erste Element nehmen */
    searchPosition = searchResults.get(0).searchResult;
   
    // String test[] = searchResults.toArray()[0].toString().split(" = ");   
    // searchPosition = Integer.valueOf(test[1]).intValue();
  } else {
    /* nichts gefunden */
    searchPosition = -1;
  }   
 
  /* letztes Suchfenster für Anzeige festlegen */
  i = searchPosition;  
  boolean cutted = false
  if (i < 0)
  {
    /* nicht gefunden */
    if (completeString.length()>100)   
    {
      searchedString = completeString.substring(0,100);                             
      cutted = true;
    } else {
      searchedString=completeString.substring(0);               
    }
  } else if ((completeString.length() -i + 1)>100)
  {
    /* ab der gefundenen Position folgen noch mehr als 100 Zeichen */
    searchedString = completeString.substring(i,i+100);                 
    cutted = true;
  } else {
    /* ab der gefundenen Position folgen weniger oder genau 100 Zeichen */
    searchedString=completeString.substring(i);
  }
  /* Zeilenumbrüche entfernen */
  searchedString = searchedString.replace("\r\n"," ");
  searchedString = searchedString.replace("\n"," "); 
  if (cutted)
    searchedString=searchedString + " [..]";                
   
  /* Konsolenausgaben */
  /* die sind deswegen hier drin weil sie in draw() immer wieder aufgerufen werden würden */
  println(fm + " false matches\n");                  
 
  /* Alle Suchergebnisse in Konsole ausgeben */
  println("\n - Alle Suchergebnisse -\n");
  for (int w = 0; w < searchResults.size(); w++)
  {
    println(searchResults.get(w).searchPattern + " = " + searchResults.get(w).searchResult);
  } 
}

/*-----------------------------------------------------------------------------
 *  eigentlicher Suchalgorithmus
 *  - zurückgegeben werden die Suchpositionen der einzelnen Muster
 *-----------------------------------------------------------------------------*/

ArrayList<SearchResults> rabinKarp()
{
  ArrayList<SearchResults> result = new ArrayList<SearchResults>();
  SearchResults searchResults = null;
 
  int hs = 0;
  int i = 0;     
  int n = 0;
  int m = 0;
  int n_m = 0;
  fm = 0;
    
  /* n = Länge des gesamten Textes */
  n=completeString.length();
  m=searchPatterns.minLength;  
  n_m = n - m;
 
  /* hs=hash-Wert der ersten Zeichen des gesamten Textes */
  hs   = hashFirst(completeString.substring(0, m), m);

  /* solange Text noch nicht komplett durchlaufen... */       
  for (i = 0; i <= n_m; i++)
  {       
    /* wenn Hashwert des Musters mit dem Hashwert des Textausschnittes übereinstimmt... */
    if (searchPatterns.patterns.containsKey(hs))
    {
     
      /* ... und die Strings an der Stelle auch übereinstimmen ... */
      if (completeString.substring(i, i + m).equals(searchPatterns.patterns.get(hs))) 
      {  
        /* Übereinstimmung gefunden */
        searchResults = new SearchResults();
        searchResults.addResult(searchPatterns.patterns.get(hs), i);
        result.add(searchResults);
      } else {
        /* Anzahl der False Matches erhöhen */
        fm += 1;
      }
    }
           
    /* Bereichsüberlaufsfehler abfangen */
    if ((i + m + 1) > n)
      break;   
    /* nächsten Hashwert bestimmen */       
    hs = hash(hs, i + 1, m);      
  }       
           
  return result;
}

/*-----------------------------------------------------------------------------
 *  nachfolgend der Code für die Button-Implementierung, denn Buttons gibt es
 *  standardmäßig nicht in Processing
 *-----------------------------------------------------------------------------*/

void update(int x, int y)
{
  if(locked == false) {
    rect1.update();
    rect3.update();
  }
  else {
    locked = false;
  }

  if(mousePressed) {
    if(rect1.pressed()) {
      currentcolor = rect1.basecolor;
      if (!fileSelected)
      {       
        loadPath = selectInput();      
        fileSelected = true;
      }
    }
   
    if (rect3.pressed()) {
      /* Suche starten */
     if ((fileSelected) && (searchString!=""))
      { praeProcessing(); }     
    }
  }
}

class Button
{
  int x, y;
  int i_width,i_height;
  color basecolor, highlightcolor;
  color currentcolor;
  boolean over = false;
  boolean pressed = false;  

  void update()
  {
    if(over()) {
      currentcolor = highlightcolor;
    }
    else {
      currentcolor = basecolor;
    }
  }

  boolean pressed()
  {
    if(over) {
      locked = true;   
      return true;
    }
    else {
      locked = false;           
      return false;
    }   
  }

  boolean over()
  {
    return true;
  }

  boolean overRect(int x, int y, int width, int height)
  {
    if (mouseX >= x && mouseX <= x+width &&
      mouseY >= y && mouseY <= y+height) {
      return true;
    }
    else {
      return false;
    }
  }
}

class RectButton extends Button
{
  RectButton(int ix, int iy, int iwidth, int iheight, color icolor, color ihighlight)
  {
    x = ix;
    y = iy;
    i_width = iwidth;
    i_height = iheight;
    basecolor = icolor;
    highlightcolor = ihighlight;
    currentcolor = basecolor;
  }

  boolean over()
  {
    if( overRect(x, y, i_width, i_height) ) {
      over = true;
      return true;
    }
    else {
      over = false;
      return false;
    }
  }

  void display()
  {
    stroke(255);
    fill(currentcolor);
    rect(x, y, i_width, i_height);
  }
}

void keyPressed()
{
  if (patternFile != "")
    return;
   
  if (key!=CODED)
  {   
    searchedString="";     
    searchPosition=0;   
   
    if (keyCode==DELETE)
    {
      searchString="";
    } else if (keyCode==BACKSPACE)
    {
      if (searchString.length()>0)
        searchString=searchString.substring(0,searchString.length()-1);     
    } else if (keyCode==ENTER)
    {
      /* funktioniert mit JOptionPane nicht!! */
      //praeProcessing();    
    } else {
      searchString+=key;
    }      
  }
}

 

Monats-Liste