home *** CD-ROM | disk | FTP | other *** search
/ Meeting Pearls 3 / Meeting_Pearls_III.iso / Pearls / texmf / source / driver / show / search.c < prev    next >
C/C++ Source or Header  |  1994-07-21  |  4KB  |  177 lines
  1. /* Boyer-Moor Suchalgorithmus nach Algorithmen in C von Robert Sedgewick */
  2.  
  3.  
  4. #include "defines.h"
  5.  
  6. #include <stdio.h>
  7. #include <ctype.h>
  8.  
  9. #include <graphics/gfx.h>
  10.  
  11. #include "commands.h"
  12. #include "globals.h"
  13. #include "globvars.h"
  14.  
  15. #ifdef ANSI
  16. #  include <string.h>
  17. #  include <stdlib.h>
  18. #endif
  19.  
  20. #include "globals.i"
  21. #include "search.i"
  22.  
  23.  
  24. #ifndef min
  25. # define min(a,b)    ((a)<(b) ? (a) : (b))
  26. #endif
  27. #ifndef max
  28. # define max(a,b)    ((a)>(b) ? (a) : (b))
  29. #endif
  30.  
  31.  
  32. static __inline int doBMSearch(void);
  33.  
  34.  
  35.  
  36. /* Boyer-Moore */
  37.  
  38. static unsigned char StrStep[256];        // Array über alle vorkommbaren Zeichen
  39. static char StrBuf[256];            // Puffer, in dem gesucht wird
  40. static int  StrBufPtr;                // Zeiger in dem Suchpuffer
  41.  
  42.        char  SearchPattern[102] = "";        // Such Pattern (Pattern muss kleiner StrBuf sein!)
  43.                                // wird direkt auch schon verwendet/gesetzt
  44. static int   PatternLen;            // Laenge des Patterns
  45.  
  46. static struct Rectangle SRects[256];        // Positionen der Buchstaben (2kB)
  47.  
  48. static struct Rectangle LocalRect;        // da wird das Ergebniss drin gespeichert
  49.  
  50.  
  51.  
  52. /**
  53.  ** Suche in einem fortlaufenden Strom von Buchstaben:
  54.  **
  55.  ** Vor Beginn der eigentlichen Suche muss InitBMSearch() mit dem
  56.  ** zu suchenden Muster aufgerufen werden. Dieses Muster muss 
  57.  ** kuerzer sein, als der StrBuf.
  58.  **
  59.  ** Bei der eigentlichen Suche wird fuer jeden Buchstaben BMSearch
  60.  ** aufgerufen. Dabei wird der eigentliche Suchvorgang nur bei
  61.  ** vollem Buffer, oder aber bei dem '\0' Zeichen aufgerufen.
  62.  ** Am Ende einer Seite muss also die Suche immer noch expliziet mit
  63.  ** einem BMSearch('\0') aufgerufen und damit der Buffer entlehrt
  64.  ** werden.
  65.  **
  66.  ** Wenn BMSearch() etwas gefunden hat, dann wird die globale
  67.  ** Variable SearchRect auf eine Rechteck Struktur gesetzt.
  68.  ** Ansonsten ist SearchRect immer gleich NULL.
  69.  **
  70.  **/
  71.  
  72.  
  73. void InitBMSearch(char * p)
  74. {
  75.   int i;
  76.   int M = strlen(p);
  77.  
  78.   for (i=0; i<256; i++) StrStep[i]    = M;
  79.   for (i=0; i<M; i++)   StrStep[p[i]] = M-i-1;
  80.   
  81.   StrBufPtr = 0;
  82.   StrBuf[sizeof(StrBuf)-1] = '\0';
  83.   
  84.   if (M >= sizeof(SearchPattern)-2) {
  85.     FatalStr(20, "zu langes Suchmuster");
  86.   }
  87.   
  88.   strcpy(SearchPattern, p);
  89.   PatternLen = M;
  90.   
  91.   SearchRect = NULL;
  92. }
  93.  
  94.  
  95. // static FILE * debout = NULL;
  96.  
  97. void BMSearch(char a, int x, int y, int w, int h)
  98. {
  99.   static int count = 0;
  100.  
  101.   int ret = -1;
  102.   int M = PatternLen;
  103.   
  104.   // if (!debout) debout = fopen("ram:debout", "w");
  105.   // if (debout) fprintf(debout, "%d (%d, %d, %d, %d)\n", a, x, y, w, h);
  106.   
  107.   if (StrBufPtr >= sizeof(StrBuf)-1 || a == '\0') {
  108.     ret = doBMSearch();
  109.  
  110.     // wurde was gefunden?
  111.     if (ret == sizeof(StrBuf)-1) ret = -1;
  112.     else {
  113.       LocalRect.MinX = min(SRects[ret+1].MinX, SRects[ret+M].MinX);
  114.       LocalRect.MinY = min(SRects[ret+1].MinY, SRects[ret+M].MinY);
  115.       LocalRect.MaxX = max(SRects[ret+1].MaxX, SRects[ret+M].MaxX);
  116.       LocalRect.MaxY = max(SRects[ret+1].MaxY, SRects[ret+M].MaxY);
  117.       ret += count;
  118.     }
  119.     
  120.     if (a == '\0') {
  121.       // erzwungenes Such-Ende. Puffer komplett leeren.
  122.       count = 0;
  123.       StrBufPtr = 0;
  124.     }
  125.     else {
  126.       // Anzahl gelesener Buchstaben erhoehen (minus rechten Rand)
  127.       count += sizeof(StrBuf)-1 - M;
  128.  
  129.       // rechten Rand nach links kopieren
  130.       for (StrBufPtr=0; StrBufPtr < M-1; StrBufPtr++) {            // kopiere die rechten M Zeichen nach links um neu anzufangen
  131.         StrBuf[StrBufPtr] = StrBuf[sizeof(StrBuf)-1-M+1+StrBufPtr];
  132.         SRects[StrBufPtr] = SRects[sizeof(StrBuf)-1-M+1+StrBufPtr];    // Kopie einer Struktur
  133.       }
  134.     }
  135.   }
  136.  
  137.   if (a) {
  138.     StrBuf[StrBufPtr] = a;
  139.     SRects[StrBufPtr].MinX = x;
  140.     SRects[StrBufPtr].MinY = y;
  141.     SRects[StrBufPtr].MaxX = x+w;
  142.     SRects[StrBufPtr].MaxY = y+h;
  143.     StrBufPtr++;
  144.   }
  145.   
  146.   if (ret != -1) {
  147.     // es wurde was gefunden
  148.     SearchRect = &LocalRect;
  149.   }
  150.   else SearchRect = NULL;
  151. }
  152.  
  153.  
  154.  
  155.  
  156. static __inline int doBMSearch(void)
  157. {
  158.   int i, j, t;
  159.  
  160.   char * a = StrBuf;
  161.   char * p = SearchPattern;
  162.   int    M = PatternLen;
  163.   int    N = strlen(a);
  164.   
  165.   for (i=M-1, j=M-1; j>=0; i--, j--) {
  166.     while (a[i] != p[j]) {
  167.       t = StrStep[a[i]];
  168.       i += (M-j > t) ? M-j : t;
  169.       if (i >= N) return N;
  170.       j = M-1;
  171.     }
  172.   }
  173.   
  174.   return i;
  175. }
  176.  
  177.