open Base;;

type ring = {
  buf: char Array.t;  (* array serving as data store *)
  mutable len: int;  (* amount of characters currently retained *)
  mutable pos: int;  (* position in buffer of last character written *)
};;

let create size = {
  buf = Array.create size '\x00';
  len = 0;
  pos = -1;
};;

let length r = r.len;;

let clear r = 
  r.len <- 0;
  r.pos <- -1;
;;

let add_char r ch =
  if r.len < Array.length r.buf then (
    r.pos <- r.pos + 1;
    Array.set r.buf r.pos ch;
    r.len <- r.pos + 1;
    None
  ) else (
    r.pos <- (r.pos + 1) % (Array.length r.buf);
    let prev_ch = Array.get r.buf r.pos in
    Array.set r.buf r.pos ch;
    Some prev_ch
  )
;;

let rev_str s = Sequence.unfold_step ~init:(String.length s - 1) ~f:(
  function n -> 
    if n < 0
      then Sequence.Step.Done
      else Sequence.Step.Yield (String.get s n, n - 1)
  )
;;

let rev r = Sequence.unfold_step ~init:(r.len, r.pos) ~f:(
  function (remaining, pos) -> 
    if remaining <= 0
    then Sequence.Step.Done
    else Sequence.Step.Yield (
      Array.get r.buf pos,
      (remaining - 1, (pos - 1) % (Array.length r.buf))
    )
  )
;;

let fwd r =
  Sequence.unfold_step
  ~init:(
    r.len,
    if r.len < (Array.length r.buf) then 0 else (r.pos + 1) % (Array.length r.buf)
  )
  ~f:(function (remaining, pos) ->
    if remaining <= 0
    then Sequence.Step.Done
    else Sequence.Step.Yield (
      Array.get r.buf pos,
      (remaining - 1, (pos + 1) % (Array.length r.buf))
    )
  )
;;

let compare (r:ring) (s:string) =
  let size_diff = r.len - (String.length s) in
  if size_diff = 0 then (
    Sequence.compare Char.compare (rev r) (rev_str s)
  ) else if size_diff < 0 then -1 else 1
;;