/* ------------------------------------------------------------------------- */
/*   Shift-Or exact string matching algorithm                                */
/*                                                                           */
/*   See ESMAJ: http://www-igm.univ-mlv.fr/~lecroq/string/node6.html         */
/* ------------------------------------------------------------------------- */

/* NOTE: there's a bug in this program but I was too lazy to fix it ;) (P.)  */

using Nemerle.IO;
using System;
using System.Collections;

class ShiftOr
{
  private mutable _pattern : array [char];
  private mutable _pattern_length : int;
  private mutable _R : BitArray;
  private mutable _S : array [BitArray];
  private mutable _L : BitArray;

  private shift_left (mask : BitArray) : void 
  {  
    def shift (index) {
      when (index >= 0) {
        mask.Set (index + 1, mask.Get (index));
        mask.Set (index, false);
      
        shift (index - 1)
      }
    };
    
    shift (mask.Length - 2)
  }
  
  private shift_right (mask : BitArray) : void 
  {  
    def shift (index : int) : void {    
      when (index < mask.Length) {      
        mask.Set (index - 1, mask.Get (index));
        mask.Set (index, false);
      
        shift (index + 1)
      }
    };
    
    shift (1)
  }
    
  private init_S (index : int) : void
  {
    when (index < 256)
    {
      _S [index] = BitArray (_pattern_length, true);
    
      init_S (index + 1)
    }
  }
    
  private build_S (index : int) : void
  {
    when (index < _pattern_length)
    {
      assert ((_pattern [index] :> int) < 256, 
              "only 8-bit wide characters are allowed for simplicity");
      
      mutable mask = BitArray (_pattern_length, true);
      mask.Set (index, false);
      def current_char = (_pattern [ index ] :> int); 
      def s = _S [ current_char ];
      _S [ current_char ] = s.And (mask);

      mask = mask.Not ();      
      _L = _L.Or (mask);
                      
      build_S (index + 1)
    }
  }

#if DEBUG  
  private static dump (title : string, mask : BitArray) : void 
  {
    printf ("(%s):%d: ", title, mask.Length);
    
    def loop (index : int) : void {      
      when (index >= 0) {
        printf ("%s", if (mask.Get (index)) "!" else ".");
        loop (index - 1);
      }
    };
    
    loop (mask.Length - 1);
    
    printf ("\n")
  }
#endif
  
  public this (pattern : string) 
  {
    _pattern = pattern.ToCharArray ();  
    _pattern_length = pattern.Length;
    
    _L = BitArray (_pattern_length, false);
        
    _S = array (256);
    
    init_S (0);
    build_S (0);
    
    shift_right (_L);    

    _L = _L.Not ()
  }
  
  public Search (text : string) : option [int]
  {
    _R = BitArray (_pattern_length, true);

    def text = text.ToCharArray ();
    
    def le (index : int, l : BitArray, r : BitArray) : bool
    {
      if (index > 0) {      
        if (l.Get (index) == false && r.Get (index) == true)
          true
        else      
          le (index - 1, l, r)
      }
      else false
    };
    
    def loop (index)
    {    
      if (index < text.Length) {              
        shift_left (_R);
        def t = _S [ (text [ index ] :> int) ];
        _R = _R.Or (t);

        if (le (_R.Length - 1, _R, _L))
          Some (index)
        else
          loop (index + 1)      
      }
      else None ();
    };
      
    loop (0)
  }
  
  public static Main () : void 
  { 
    def r = ShiftOr ("coca");
    
    match (r.Search ("Trink coca cola!")) {
      | Some (i) => printf ("Found, ending at index %d\n", i + 1)
      | None => printf ("Not found\n")
    }
  }
}

/*
BEGIN-OUTPUT
Found, ending at index 10
END-OUTPUT
*/