WDL/diffcalc.h

   1 #ifndef _WDL_DIFFCALC_H_
   2 #define _WDL_DIFFCALC_H_
   3
   4 #include "assocarray.h"
   5
   6
   7
   8 // Based on "An O(ND) Difference Algorithm and Its Variations", Myers
   9 // http://xmailserver.org/diff2.pdf
  10
  11
  12 template <class T> class WDL_DiffCalc
  13 {
  14 public:
  15   WDL_DiffCalc() {}
  16   virtual ~WDL_DiffCalc() {}
  17
  18   // cmp() returns 0 if the elements are equal.
  19   // returns the length of the merged list and populates m_rx, m_ry.
  20   int Diff(const T* x, const T* y, int nx, int ny, int (*cmp)(const T*, const T*))
  21   {
  22     m_rx.Resize(0, false);
  23     m_ry.Resize(0, false);
  24     ClearV();
  25
  26     if (!nx && !ny) return 0;
  27     if (!nx || !ny)
  28     {
  29       int i, n=max(nx, ny);
  30       for (i=0; i < n; ++i)
  31       {
  32         m_rx.Add(nx ? i : -1);
  33         m_ry.Add(ny ? i : -1);
  34       }
  35       return n;
  36     }
  37
  38     if (!cmp(x, y)) // special case
  39     {
  40       int i, n;
  41       for (n=1; n < min(nx, ny); ++n)
  42       {
  43         if (cmp(x+n, y+n)) break;
  44       }
  45       int len=Diff(x+n, y+n, nx-n, ny-n, cmp);
  46       int *rx=m_rx.Get(), *ry=m_ry.Get();
  47       for (i=0; i < len; ++i)
  48       {
  49         if (rx[i] >= 0) rx[i] += n;
  50         if (ry[i] >= 0) ry[i] += n;
  51       }
  52       len += n;
  53       while (n--)
  54       {
  55         m_rx.Insert(n, 0);
  56         m_ry.Insert(n, 0);
  57       }
  58       return len;
  59     }
  60
  61     SetV(0, 1, 0);
  62     int d, k, xi, yi;
  63     for (d=0; d <= nx+ny; ++d)
  64     {
  65       for (k=-d; k <= d ; k += 2)
  66       {
  67         if (k == -d || (k != d && GetV(d, k-1) < GetV(d, k+1)))
  68         {
  69           xi=GetV(d, k+1);
  70         }
  71         else
  72         {
  73           xi=GetV(d, k-1)+1;
  74         }
  75         yi=xi-k;
  76         while (xi < nx && yi < ny && !cmp(x+xi, y+yi))
  77         {
  78           ++xi;
  79           ++yi;
  80         }
  81         SetV(d+1, k, xi);
  82         if (xi >= nx && yi >= ny) break;
  83       }
  84       if (xi >= nx && yi >= ny) break;
  85     }
  86
  87     int len=(nx+ny+d)/2;
  88     int *rx=m_rx.Resize(len);
  89     int *ry=m_ry.Resize(len);
  90     int pos=len;
  91
  92     while (d)
  93     {
  94       while (xi > 0 && yi > 0 && !cmp(x+xi-1, y+yi-1))
  95       {
  96         --pos;
  97         rx[pos]=--xi;
  98         ry[pos]=--yi;
  99       }
 100       --pos;
 101       if (k == -d || (k != d && GetV(d, k-1) < GetV(d, k+1)))
 102       {
 103         ++k;
 104         rx[pos]=-1;
 105         ry[pos]=--yi;
 106       }
 107       else
 108       {
 109         --k;
 110         rx[pos]=--xi;
 111         ry[pos]=-1;
 112       }
 113       --d;
 114     }
 115
 116     return len;
 117   }
 118
 119   // m_rx, m_ry hold the index of each merged list element in x and y,
 120   // or -1 if the merged list element is not an element in that source list.
 121   // example: X="ABCABBA", Y="CBABAC"
 122   //             0123456      012345
 123   // WDL_Merge() returns "ABCBABBAC"
 124   //                      012 3456
 125   //                        0123 45
 126   // m_rx={ 0,  1,  2, -1,  3,  4,  5,  6, -1}
 127   // m_ry={-1, -1,  0,  1,  2,  3, -1,  4,  5}
 128    WDL_TypedBuf<int> m_rx, m_ry;
 129
 130 private:
 131
 132   WDL_IntKeyedArray<int> m_v; // x coord of d-contour on row k
 133   void ClearV()
 134   {
 135     m_v.DeleteAll();
 136   }
 137   void SetV(int d, int k, int xi)
 138   {
 139     m_v.Insert(_key(d, k), xi);
 140   }
 141   int GetV(int d, int k)
 142   {
 143     return m_v.Get(_key(d, k));
 144   }
 145   static int _key(int d, int k) { return (d<<16)|(k+(1<<15)); }
 146 };
 147
 148
 149 // this is a separate function from WDL_DiffCalc only because it requires T::operator=
 150 template <class T> int WDL_Merge(const T* x, const T* y, int nx, int ny,
 151   int (*cmp)(const T*, const T*), T* list)
 152 {
 153   WDL_DiffCalc<T> dc;
 154   int i, n=dc.Diff(x, y, nx, ny, cmp);
 155   int *rx=dc.m_rx.Get(), *ry=dc.m_ry.Get();
 156   for (i=0; i < n; ++i)
 157   {
 158     if (list) list[i]=(rx[i] >= 0 ? x[rx[i]] : y[ry[i]]);
 159   }
 160   return n;
 161 }
 162
 163 #endif