type t = { length : int;
           bits : string; }

let create ?(init=false) size =
  let i = if init then '\xff' else '\x00' in
  { length = size;
    bits = String.make (1 + size / 8) i
  }

let alloc size =
  { length = size;
    bits = String.create (1 + size / 8);
  }

let length v = v.length

let unsafe_get v n =
  let i = n / 8
  and j = n mod 8 in
  (((Char.code (String.unsafe_get v.bits i)) lsr j) land 1) == 1

let union v1 v2 =
  assert ( v1.length == v2.length );
  let res = alloc v1.length in
 (* Format.printf "size %d@." (String.length res.bits);*)
  for i = 0 to String.length v1.bits - 1 do
      res.bits.[i] <- Char.chr ((Char.code v1.bits.[i]) lor (Char.code v2.bits.[i]))
  done;
  res

let inter v1 v2 =
   assert ( v1.length == v2.length );
  let res = alloc v1.length in
  for i = 0 to String.length v1.bits - 1 do
    res.bits.[i] <- Char.chr ((Char.code v1.bits.[i]) land (Char.code v2.bits.[i]))
  done;
  res

let diff v1 v2 =
  assert ( v1.length == v2.length );
  let res = alloc v1.length in
  for i = 0 to String.length v1.bits - 1 do
    res.bits.[i] <- Char.chr ((Char.code v1.bits.[i]) land (lnot (Char.code v2.bits.[i])))
  done;
  res


 
let unsafe_set v n (b:bool) =
  let x : int = Obj.magic b in
  let i = n / 8
  and j = n mod 8 in
  let m = 1 lsl j in
  let w = Char.code (String.unsafe_get v.bits i) in
  let w = (w land lnot m) lor (~-x land m) in
  String.unsafe_set v.bits i (Char.unsafe_chr (w land 0xff))
;;

let get v n =
  if n < 0 || n >= v.length then failwith "Bitvector.get"
  else unsafe_get v n
;;

let set v n b =
  if n < 0 || n >= v.length then failwith "Bitvector.set"
  else unsafe_set v n b
;;