wdiff/wdiff.d

   1 // simple and free spellchecker
   2 // simple word difference algorithm (found somewhere in teh internets, dunno whose it is)
   3 module wdiff /*is aliced*/;
   4 import iv.alice;
   5
   6
   7 struct DiffEngine {
   8   int[] dmat;
   9   int d0, d1; // "virtual dimensions"
  10
  11   int opIndex (int x, int y) {
  12     pragma(inline, true);
  13     return (x >= 0 && y >= 0 && x < d0 && y < d1 ? dmat[y*d0+x] : 0);
  14   }
  15
  16   void opIndexAssign (int v, int x, int y) {
  17     pragma(inline, true);
  18     if (x >= 0 && y >= 0 && x < d0 && y < d1) dmat[y*d0+x] = v;
  19   }
  20
  21   // ad0 and ad1: maximum string lengthes
  22   void setup (int ad0, int ad1) {
  23     assert(ad0 > 0 && ad1 > 0);
  24     ++ad0;
  25     ++ad1;
  26     if (dmat.length < ad0*ad1) dmat.length = ad0*ad1;
  27     d0 = ad0;
  28     d1 = ad1;
  29     foreach (int n; 0..ad0) this[n, 0] = n;
  30     foreach (int n; 0..ad1) this[0, n] = n;
  31   }
  32
  33   // compare str0 and str1, return "difference count"
  34   int diffCount (const(char)[] str0, const(char)[] str1) {
  35     int l0 = cast(int)str0.length;
  36     int l1 = cast(int)str1.length;
  37     setup(l0, l1);
  38     foreach (int i1; 1..l0+1) {
  39       foreach (int i2; 1..l1+1) {
  40         if (str0.ptr[i1-1] == str1.ptr[i2-1]) {
  41           this[i1, i2] = this[i1-1, i2-1];
  42         } else {
  43           import std.algorithm : min;
  44           this[i1, i2] = min(this[i1-1, i2], this[i1, i2-1], this[i1-1, i2-1])+1;
  45         }
  46       }
  47     }
  48     return this[l0, l1];
  49   }
  50 }
  51
  52
  53 void main () {
  54   import std.stdio;
  55   DiffEngine de;
  56   writeln(de.diffCount(n"ÈÕÊ", n"ÈÏÊ"));
  57   writeln(de.diffCount(n"ÁÂÂÁÔ", n"ÐÉÚÄÀË"));
  58   writeln(de.diffCount(n"ÅÂÁÌÁ", n"ÅÂÁÌÁÊËÁ"));
  59   writeln(de.diffCount(n"ÐÏÃ", n"ÐÏÃÙ"));
  60   writeln(de.diffCount(n"ÐÏÃ", n"ÐÃÏÙ"));
  61 }