(* Copyright (C) 2007 Mauricio Fernandez <mfp@acm.org> http//eigenclass.org
 * See README.txt and LICENSE for the redistribution and modification terms *)

exception Done of int

let memcmp a o1 b o2 len =
  let rec loop a b o1 o2 i =
    if i < len then
      if a.[o1] = b.[o2] then
        loop a b (o1 + 1) (o2 + 1) (i + 1)
      else false
    else true
  in loop a b o1 o2 0

let boyermoore_needlematch needle nlen portion offset =
  let virtual_begin = ref (nlen - offset - portion) in
  let ignore = ref 0 in
    if !virtual_begin < 0 then begin
      ignore := - !virtual_begin;
      virtual_begin := 0
    end;

    if !virtual_begin > 0 &&
       needle.[!virtual_begin - 1] == needle.[nlen - portion - 1] then
      false
    else
      memcmp
        needle (nlen - portion + !ignore)
        needle !virtual_begin
        (portion - !ignore)

let max_i (a : int) (b : int) = if a > b then a else b

type t = {
  skip : int array;
  occ : int array;
  needle : string;
  nlen : int
}

let make needle =
  let nlen = String.length needle in
  let skip = Array.make nlen 0 in
  let occ = Array.make 256 (-1) in

    for a = 0 to nlen - 1 - 1 do
      occ.(Char.code needle.[a]) <- a;
    done;

    for a = 0 to nlen - 1 do
      let value = ref 0 in
        while !value < nlen &&
              not (boyermoore_needlematch needle nlen a !value) do
          incr value
        done;
        skip.(nlen - a - 1) <- !value
    done;

    { skip = skip; occ = occ; needle = needle; nlen = nlen }

let boyermoore_search t haystack start hlen =
  let skip = t.skip and occ = t.occ and needle = t.needle and nlen = t.nlen in
    if nlen > hlen || nlen <= 0 then raise Not_found;
    try
      let hpos = ref start in
      let lim = hlen - nlen in
        while !hpos <= lim do
          let npos = ref (nlen - 1) in
            while needle.[!npos] = haystack.[!npos + !hpos] do
              if !npos = 0 then raise (Done !hpos);
              decr npos
            done;
            hpos := !hpos +
            max_i skip.(!npos)
              (!npos - occ.(Char.code (haystack.[!npos + !hpos])))
        done;
        raise Not_found
    with Done m -> m

let find t haystack start =
  boyermoore_search t haystack start (String.length haystack)

let find_end t haystack start = find t haystack start + t.nlen