Commits

Anonymous committed 7eef442

BitArray: on internal representation and comparison using ( = )

Comments (0)

Files changed (2)

src/cd_BitArray.ml

  :
   sig
 
+    (* values of type [t] can be compared on equality with [ ( = ) ]. *)
     type t;
 
     value make : int -> bool -> t;
     value all_equal_to : bool -> t -> bool;
     value fill_all : bool -> t -> unit;
 
+    (* bitarrays with equal elements have equal string representation. *)
     value to_repr : t -> string;
     value of_repr_unsafe : string -> t;
 
 
     (* layout: ['bits0..7' .. 'bitsN..N+(1..7)' len_sub]
        where length of bitarray = 8 * (String.length string) - len_sub.
+       unused bits of last data byte are 0.
      *)
 
     type t = string
 
     (* todo: Char/String.unsafe_* when time will prove that code is correct *)
 
-    (* todo: fill unused bits with 0 to make bitarrays comparable with (=) *)
-
     value byte_of_bool = fun [ True -> '\xFF' | False -> '\x00' ]
     ;
 
            *)
         in
         let len_sub = (strlen lsl 3) - len in
-        let r = String.make strlen (byte_of_bool init) in
+        let byte = byte_of_bool init in
+        let r = String.make strlen byte in
         ( assert (len_sub >= 8 && len_sub <= 15)
         ; r.[strlen - 1] := Char.chr len_sub
+        ; if len = 0
+          then ()
+          else
+            r.[strlen - 2] := Char.chr
+              ((Char.code byte) land ((1 lsl (8 - ((-len) land 7))) - 1))
         ; r
         )
     ;
     (fun init ->
        for len = 0 to 25 do
          (let a = Array.make len init
-          and b = BitArray.make len init in
+          and b = BitArray.make len init
+          and b' = BitArray.make len (not init) in
+          let () = for i = 0 to len - 1 do BitArray.set b' i init done in
           let () = midcheck len a b in
           if len = 0
           then
                  and v = Random.bool () in
                  ( a.(k) := v
                  ; BitArray.set b k v
+                 ; BitArray.set b' k v
                  ; assert_equal v (BitArray.get b k)
+                 ; assert_equal v (BitArray.get b' k)
                  ; midcheck len a b
                  )
                 )
               done
+            ; assert_equal (BitArray.to_repr b) (BitArray.to_repr b')
+            ; assert_equal b b'
             ; let x = Random.bool () in
               ( Array.fill a 0 len x
               ; BitArray.fill_all x b