1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

 

#light

namespace Common 

//---------------------------------------------------------------
// LIBRARIES
//---------------------------------------------------------------  

open System


//---------------------------------------------------------------
// BITARRAY
//---------------------------------------------------------------  

[<Sealed>]
type Bitarray = 
  //The fields are not private in the implementation file so that 
  //only the functions from this module can access them.
  with 
    static member ( ~~~ ) : ba:Bitarray -> Bitarray
    static member ( ^^^ ) : ba:Bitarray * ba':Bitarray -> Bitarray
    static member ( ||| ) : ba:Bitarray * ba':Bitarray -> Bitarray
    static member ( &&& ) : ba:Bitarray * ba':Bitarray -> Bitarray
    
    static member ( + ) : ba:Bitarray * ba':Bitarray -> Bitarray
    static member ( - ) : ba:Bitarray * ba':Bitarray -> Bitarray

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Bitarray =
  ///[Create n] returns a [Bitarray] of [n] bits.
  val Create : int -> Bitarray
  
  ///[Copy barr] returns a fresh copy of [barr].
  val Copy : Bitarray -> Bitarray
  
  ///[Length barr] returns the number of bits of [barr].
  val Length : Bitarray -> int
  
  ///[IsSet nth barr] returns true if the [nth] bit of [barr] is set.
  val IsSet : pos:int -> Bitarray -> bool
  
  ///[Put nth flag barr] puts [flag] at the [nth] bit of [barr].
  val Put : int -> bool -> Bitarray -> unit
  
  ///[Init n f] returns a new [Bitarray] of [n] bits where the
  ///[n]th bit is computed as [f i].
  val Init : n:int -> f:(int -> bool) -> Bitarray
  
  ///[Set nth barr] puts [true] at the [nth] bit of [barr].
  val Set : int -> Bitarray -> unit
  
  ///[SetAll barr] puts [true] at all bits of [barr].
  val SetAll : Bitarray -> unit
  
  ///[Unset nth barr] puts [false] at the [nth] bit of [barr].
  val Unset : int -> Bitarray -> unit
  
  ///[UnsetAll barr] puts [false] at all bits of [barr].
  val UnsetAll : Bitarray -> unit
  
  ///[Inter a b] returns a [Bitarray] where the bits are set at the positions where
  ///they are set both in [a] and [b].
  val Inter : Bitarray -> Bitarray -> Bitarray
  
  ///[Inter a b] returns a [Bitarray] where the bits are set at the positions where
  ///they are set in [a] and / or in [b].
  val Union : Bitarray -> Bitarray -> Bitarray
  
  ///[Diff negged base] returns a [Bitarray] where the bits are set at the positions where
  ///they are set in [base] but not in [negged].
  val Diff : negged:Bitarray -> baseBitarray:Bitarray -> Bitarray
  
  ///[Iter f barr] applies [f bit] to every bit of [barr] where each bit is represented by a boolean value.
  val Iter : (bool -> unit) -> Bitarray -> unit
  
  ///[Iteri f barr] applies [f n bit] to every bit of [barr] where each bit is represented by a boolean value.
  ///[f] varies with the position of the bit. That is, [f i] is applied to the [ n ]th bit.
  val Iteri : (int -> bool -> unit) -> Bitarray -> unit
  
  ///[Map f barr] returns a new [Bitarray] by applying [f] to every bit of [barr] 
  ///where each bit is represented by a boolean value.
  val Map : (bool -> bool) -> Bitarray -> Bitarray
  
  ///[Mapi f barr] returns a new [Bitarray] by applying [f i] to the [ n ]th bit of [barr] 
  ///for [ n ] in [0 .. Length barr]. Each bit is represented by a boolean value.
  val Mapi : (int -> bool -> bool) -> Bitarray -> Bitarray
  
  ///[SetBits barr] returns the indexes of the set bits of [barr].
  val SetBits : Bitarray -> list<int>
  
  ///[UnsetBits barr] returns the indexes of the set bits of [barr].
  val UnsetBits : Bitarray -> list<int>
  
  ///[ToBool barr] returns an array of boolean values where the [ n ]th value is true
  ///if the [ n ]th bit of [barr] is set.
  val ToBool : Bitarray -> bool[]
  
  ///[FromBool boolarr] returns a [Bitarray] where the [ n ]th bit is set
  ///if the [ n ]th boolean of [boolarr] is true.
  val FromBool : bool array -> Bitarray
  
  ///[ToBytes barr] returns a byte[] where [true; false; ... false] translates to [1uy].
  val ToBytes : Bitarray -> byte[]
  
  ///[FromBytes barr] returns a [Bitarray] where [1uy] translates to [true; false; ... false].
  val FromBytes : byte [] -> Bitarray
    
  ///[AreAllSet barr] returns true if all bits of [barr] are unset.
  val AreAllUnset : Bitarray -> bool
  
  ///[AreAllSet barr] returns true if all bits of [barr] are set.
  val AreAllSet : Bitarray -> bool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

 

#light

//reminder : bits_per_byte = 8

namespace Common 

//---------------------------------------------------------------
// LIBRARIES
//---------------------------------------------------------------  

open System


//---------------------------------------------------------------
// IMPLEMENTATION
//---------------------------------------------------------------  

(** Notes

8 bits per byte
4 bytes to represent a signed integer

0xf = 15 * (2. ** 4.) = 16 ^- 1
0xff = 15 * (2. ** 4.) + 15 = 16 ^ 2 - 1
...
0xffff = 16 ^ 4 - 1
...
0xffffffff = 16 ^ 8 - 1


n <<< i = b * (2 ^ i)

n >>> i = b / (2 ^ i) as an integer division, i.e. 17 / 2 = 8

n &&& -b returns the value of the first bit Set to 1 in n, 
i.e. [2 ^ pos] where [pos] is the index of the minimum Set bit.

b &&& i =  0 if the ith bit is not Set in n, ith's value otherwise
*)


type Bitarray = 
  { Data : byte[]
    Length : int
  }
  with         
    static member (~~~) ba =
      { ba with Data = Array.map (fun e -> ~~~e) ba.Data }
      
    static member (^^^) (ba, ba') =
      if ba.Length <> ba'.Length then invalid_arg "Bitarray (^^^) operator"
      { ba with Data = Array.map2 (fun e e' -> e ^^^ e') ba.Data ba'.Data }
      
    static member (|||) (ba, ba') =
      if ba.Length <> ba'.Length then invalid_arg "Bitarray (|||) operator"
      { ba with Data = Array.map2 (fun e e' -> e ||| e') ba.Data ba'.Data }
      
    static member (&&&) (ba, ba') =
      if ba.Length <> ba'.Length then invalid_arg "Bitarray (&&&) operator"
      { ba with Data = Array.map2 (fun e e' -> e &&& e') ba.Data ba'.Data }
      
    static member (+) (b:Bitarray, b') = b ||| b'
      
    static member (-) (b:Bitarray, b') = b &&& ~~~b'


[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Bitarray =

  let private bitToByteShift nbits = nbits >>> 3
  let private staticBits = [|for i in 0 .. 7 -> 1 <<< i |> byte|] 
  
  let bits ba = ba.Data
  
  let Length ba = ba.Length
  
  let Create nbits =
    if nbits < 0 then invalid_arg "Cannot Create a Bitarray with less than 0 element"
    { Data = (nbits + 7) |> bitToByteShift |> Array.zero_create
      Length = nbits
    }
  
  let Copy ba =
    {ba with Data = Array.copy ba.Data}
      
  let IsSet pos ba =
    if pos < 0 || pos >= ba.Length then raise <| IndexOutOfRangeException()
    ba.Data.[bitToByteShift pos] &&& staticBits.[pos &&& 7] <> 0uy
    
  let Put pos flag ba =
    if IsSet pos ba <> flag then
      if flag then
        ba.Data.[bitToByteShift pos] <- ba.Data.[bitToByteShift pos] ||| staticBits.[pos &&& 7]
      else
        ba.Data.[bitToByteShift pos] <- ba.Data.[bitToByteShift pos] ^^^ staticBits.[pos &&& 7]   
  
  let Init nbits f =
    let res = Create nbits
    for i in 0 .. nbits - 1 do
      Put i (f i) res
    res
      
  let Set pos ba = Put pos true ba
  
  let SetAll ba =
    ba.Data |> Array.iteri (fun n _ -> ba.Data.[ n ] <- 255uy)
  
  let Unset pos ba = Put pos false ba
  
  let UnsetAll ba =
    ba.Data |> Array.iteri (fun n _ -> ba.Data.[ n ] <- 0uy)
  
  let Inter (b:Bitarray) b' = b &&& b'
  
  let Union (b:Bitarray) b' = b ||| b'

  let Diff (negged:Bitarray) baseBitarray = baseBitarray ^^^ negged

  let Iter f ba =
    let res = Create (Length ba)
    for n in 0 .. (Length ba) - 1 do
      f <| IsSet n ba   
  
  let Iteri f ba =
    let res = Create (Length ba)
    for n in 0 .. (Length ba) - 1 do
      f n <| IsSet n ba      

  let Mapi f ba =
    let res = Create (Length ba)
    for n in 0 .. Length ba - 1 do
      Put n (f n (IsSet n ba)) res
    res     

  let Map f ba =
    let res = Create (Length ba)
    for n in 0 .. Length ba - 1 do
      Put n (f (IsSet n ba)) res
    res  
        
  let SetBits ba =
    [ for n in 0 .. Length ba - 1 do if IsSet n ba then yield n ]
    
  let UnsetBits ba =
    [ for n in 0 .. Length ba - 1 do if not <| IsSet n ba then yield n ]
  
  let ToBool ba =
    [|for n in 0 .. Length ba - 1 -> IsSet n ba |]
  
  let FromBool xs =
    Init (Array.length xs) (fun n -> xs.[ n ])    
  
  let ToBytes ba =
    Array.copy ba.Data
    
  let FromBytes xs =
    { Data = Array.copy xs
      Length = Array.length xs * 8
    }
    
  let areAll n ba =
    let nFull = ba.Length / 8
    let n = ref 0 
    let ok = ref true 
    while !i < nFull && !ok do
      if ba.Data.[!i] <> n then ok := false
      incr i
    if !ok then
      n := nFull * 8
      while !i < ba.Length && !ok do
        if not <| IsSet !i ba then ok := false
        incr n      
    !ok
  
  let AreAllSet ba = areAll 255uy ba
    
  let AreAllUnset ba = areAll 0uy ba

1

System.Collections.IEnumerable

1

System.Collections.Generic.IEnumerable<T>

1

System.Linq.Enumerable.Cast<T>