# BitArray and BitSet API Review

Hey everyone! This is an overview of the API for the `BitArray`

and `BitSet`

data structures for the Swift Collections package. This project was done as a GSoC (Google Summer of Code) project for which you can find the original Swift Forums post here. This is the resulting API of the project. Please have a look! I'll appreciate any feedback you have!

## Introduction

The `BitArrayModule`

contains two data structures in its initial release, the `BitArray`

and the `BitSet`

, that allow for boolean values to be stored using less memory while also allowing for certain faster operations.

## Motivation

Since a `Bool`

has two values (`true`

and `false`

) in its domain, it only needs one bit of memory to represent its value. However, as a variable cannot be stored in a space smaller than one byte in memory, a `Bool`

ends up using 8 times more memory than it would need. For a single value, this is hardly an issue, but for a larger `Array<Bool>`

, this makes room for memory optimization. Additionally, if `Bool`

s were stored as bits, this could result in faster operations like that of bitwise AND, as chunks of values could likely be manipulated at once instead of iterating and operating over every single one.

Hence, creating a data structure that makes more efficient use of memory could also result in optimized performance.

## Proposed Solution

As it isn't exactly feasible to create a variable that gets stored into a bit, the primary solution would be to have the `Bool`

s represented as the bits of an unsigned integer in a data structure called a `BitArray`

For example, the number `182`

in binary is `10110110`

. Each `1`

and `0`

in the binary representation can represent a `true`

and `false`

value respectively. This allows us to store the values into an `Array<UInt>`

as opposed to an `Array<Bool>`

, making use of all of the bits, requiring up to 8 times less memory, but whose API would function much like an `Array<BooL>`

.

Additionally, since every element in the storage is technically holding 8 or more boolean values, performance on common operations such as bitwise AND are much faster, as multiple boolean values can be manipulated by manipulating a single integer value in the array.

Such a data structure would also be a great storage solution to the `Set<Int>`

version of a `BitArray`

, whose integer values are to represent the indices of the `true`

values in an `Array<Bool>`

, called a ** BitSet**. This set representation utilizing the

`BitArray`

would allow for the memory and speed optimization, but with an API functioning as a `Set<Int>`

.```
let bitArray: BitArray = [true, true, false, true, true] // a BitArray implementation that functions like an Array<Bool>
let bitSet: BitSet = [0, 1, 3, 4] // an equivalent set version of the BitArray, functioning as a Set<Int>
```

## Detailed Design

###
**BitArray**

The `BitArray`

mimics the API of an `Array<Bool>`

, but maintains the `Bool`

s within the bits of an unsigned integer with its own unique bitwise operations.

```
var bitArray: BitArray = [true, false, true, false] // stored little-endian within an integer as 00000101, or 5
let secondBitArray: BitArray = [true, false, false, false]
// works much like an Array<Bool>
bitArray.removeLast()
bitArray.reversed()
let isEqual: Bool = (bitArray == secondBitArray) // false
bitArray.append(isEqual)
print(Array(bitArray)) // prints "[true, false, true, false, false]"
// also has its own unique bitwise operations
bitArray.formBitwiseAnd(secondBitArray)
bitArray ^= secondBitArray
let invertedBitArray = ~bitArray
```

### Definition

```
struct BitArray: ExpressibleByArrayLiteral, RandomAccessCollection, MutableCollection, Equatable, Codable {
subscript(position: Int) -> Bool
}
```

### BitArray-specific initializer APIs

`BitArray`

, like an `Array<Bool>`

, is a `RandomAccessCollection`

with integer indices. However, `BitArray`

does not conform to `RangeReplaceableCollection`

because there didn't seem to be any use cases. However, some relevant parts of `RangeReplaceableCollection`

were implemented without conforming.

```
/// Creates a new collection containing the specified number of a single, repeated `Bool`
///
/// The following example creates a BitArray initialized with 5 true values
///
/// let fiveTrues = BitArray(repeating: true, count: 5)
/// print(fiveTrues)
/// // Prints "BitArray(storage: [31], excess: 5)"
/// print(Array(fiveTrues))
/// // Prints "[true, true, true, true, true]"
///
/// - Parameters:
/// - repeatedValue: The `Bool` to repeat.
/// - count: The number of times to repeat the value passed in the
/// `repeating` parameter. `count` must be zero or greater.
public init(repeating repeatedValue: Bool, count: Int)
```

It also has an initializer that initializes from the `BitSet`

```
/// Creates a new BitArray using a BitSet, where the indices in the BitSet become the true values in the BitArray. The resulting BitArray often contains many padded false values at the end from empty bits that fill up the word
///
/// The following example creates a BitArray initialized by a BitSet
/// let bitSet: BitSet = [0, 1, 3, 5]
/// let bitArray = BitArray(bitSet)
/// print(bitArray)
/// // Prints "BitArray(storage: [43], excess: 0)"
/// print(Array(bitArray))
/// // Prints "[true, true, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false]"
///
/// - Parameters:
/// - bitSet: An initialized BitSet
public init(_ bitSet: BitSet)
```

### BitArray bitwise Operation APIs

The `BitArray`

offers bitwise operation methods, both mutating and non-mutating, and both in the form of overloaded operators and function calls.

###
*Bitwise OR operation*

The bitwise or operation can either be mutating, non-mutating, with a function call, or by using an overloaded operator.

```
/// mutates self by setting the value in each index to true if either self or the passed in BitArray -- or both -- have a true value in that respective index.
///
/// The following example mutates a BitArray to be OR'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray.formBitwiseOr(secondBitArray)
/// print(Array(bitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
mutating func formBitwiseOr(_ other: BitArray)
/// overloaded operator that mutates the lhs BitArray by setting the value in each index to true if either the lhs BitArray or the rhs BitArray -- or both -- have a true value in that respective index.
///
/// The following example mutates the lhs to be OR'd with the rhs
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray |= secondBitArray
/// print(Array(bitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
static func |= (lhs: inout BitArray, rhs: BitArray)
/// creates and returns a new BitArray by setting the value in each index of the new BitArray to true if either self or the passed in BitArray -- or both -- have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the OR'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray.bitwiseOr(secondBitArray)
/// print(Array(newBitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
/// - Returns: The BitArray that is the XOR'd result of `self` and `other`
func bitwiseOr(_ other: BitArray) -> BitArray
/// overloaded operator that creates and returns a new BitArray by setting the value in each index to true if either the lhs BitArray or the rhs BitArray -- or both -- have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the OR'd result of the lhs and rhs
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray | secondBitArray
/// print(Array(newBitArray))
/// Prints "[true, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
/// - Returns: The BitArray that is the XOR'd result of the lhs and rhs
static func | (lhs: BitArray, rhs: BitArray) -> BitArray
```

###
*Bitwise AND operation*

The bitwise AND operation can either be mutating, non-mutating, with a function call, or by using an overloaded operator.

```
/// mutates self by setting the value in each index to true if both self and the passed in BitArray have a true value in that respective index.
///
/// The following example mutates a BitArray to be AND'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray.formBitwiseAnd(secondBitArray)
/// print(Array(bitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
mutating func formBitwiseAnd(_ other: BitArray)
/// overloaded operator that mutates the lhs BitArray by setting the value in each index to true if both the lhs BitArray and the rhs BitArray have a true value in that respective index.
///
/// The following example mutates the lhs to be AND'd with the rhs
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray &= secondBitArray
/// print(Array(bitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
static func &= (lhs: inout BitArray, rhs: BitArray)
/// creates and returns a new BitArray by setting the value in each index of the new BitArray to true if both self and the passed in BitArray have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the AND'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray.bitwiseAnd(secondBitArray)
/// print(Array(newBitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
/// - Returns: The BitArray that is the AND'd result of `self` and `other`
func bitwiseAnd(_ other: BitArray) -> BitArray
/// overloaded operator that creates and returns a new BitArray by setting the value in each index of the new BitArray to true if both the lhs BitArray and the rhs BitArray have a true value in that respective index.
///
/// The following example creates and returns a BitArray that is the AND'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray & secondBitArray
/// print(Array(newBitArray))
/// Prints "[true, false, false, false]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
/// - Returns: The BitArray that is the AND'd result of the lhs and rhs
static func & (lhs: BitArray, rhs: BitArray) -> BitArray
```

###
*Bitwise XOR operation*

The bitwise xor operation can either be mutating, non-mutating, with a function call, or by using an overloaded operator.

```
/// mutates self by setting the value in each index to true if either self or the passed in BitArray -- but not both -- have a true value in that respective index.
///
/// The following example mutates self to be XOR'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray.formBitwiseXor(secondBitArray)
/// print(Array(bitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
mutating func formBitwiseXor(_ other: BitArray)
/// overloaded operator that mutates the lhs BitArray by setting the value in each index to true if either the lhs BitArray or the rhs BitArray -- but not both -- have a true value in that respective index.
///
/// The following example mutates a BitArray to be XOR'd with another BitArray
/// var bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// bitArray ^= secondBitArray
/// print(Array(bitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
static func ^= (lhs: inout BitArray, rhs: BitArray)
/// creates a new BitArray by setting the value in each index of the new BitArray to true if either self or the passed in BitArray -- but not both -- have a true value in that respective index.
///
/// The following example creates a new a BitArray that is the XOR'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray.bitwiseOr(secondBitArray)
/// print(Array(newBitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - other: An initialized BitArray. `other` must have the same count as `self`
/// - Returns: The BitArray that is the XOR'd result of `self` and `other`
func bitwiseXor(_ other: BitArray) -> BitArray
/// creates a new BitArray by setting the value in each index of the new BitArray to true if either lhs BitArray or the rhs BitArray -- but not both -- have a true value in that respective index.
///
/// The following example creates a new a BitArray that is the XOR'd result of self and another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let secondBitArray = [true, false, false, true]
/// let newBitArray = bitArray ^ secondBitArray
/// print(Array(newBitArray))
/// Prints "[false, false, true, true]"
///
/// - Parameters:
/// - lhs: An initialized BitArray
/// - rhs: An initialized BitArray. `rhs` must have same count as `lhs`
/// - Returns: The BitArray that is the XOR'd result of the lhs and rhs
static func ^ (lhs: BitArray, rhs: BitArray) -> BitArray
```

###
*Bitwise NOT operation*

The bitwise not operation is non-mutating and can be done with a function call or by using an overloaded operator.

```
/// creates a new BitArray by setting each value in the new BitArray to the opposite value of that in self
///
/// The following example creates a new a BitArray that is the inverse of self
/// let bitArray: BitArray = [true, false, true, false]
/// let newBitArray = bitArray.bitwiseNot()
/// print(Array(newBitArray))
/// Prints "[false, true, false, true]"
///
/// - Returns: The BitArray that contains the inverse or opposite values of that in self
func bitwiseNot() -> BitArray
/// The bitwise NOT operator (`~`) is a prefix operator that returns a value in which all the Bools of its argument are flipped
///
/// The following example creates a new a BitArray to be NOT'd with another BitArray
/// let bitArray: BitArray = [true, false, true, false]
/// let newBitArray = ~bitArray
/// print(Array(newBitArray))
/// Prints "[false, true, false, true]"
///
/// - Returns: The `BitArray` that contains the inverse or opposite values of that in `self`
static prefix func ~ (_ bitArray: BitArray) -> BitArray
```

### BitArray-specific function APIs

There are two functions that `RangeReplaceableCollection`

s have that `BitArray`

has as well, even though it does not conform to the `RangeReplaceableCollection`

protocol.

They are the `removeFirst(...)`

and `removeLast(...)`

functions that remove a range of values.

```
/// Removes the first several values in the beginning of the BitArray
/// self must not be empty
///
/// The following example removes the first 3 elements of a BitArray
/// var bitArray: BitArray = [true, false, true, false, true]
/// bitArray.removeFirst(3)
/// print(Array(bitArray))
/// Prints "[false, true]"
///
/// - Parameters:
/// - k: an integer that represents the number of values desired to be removed from the beginning.
///`k` must be a positive number, and less than the `count` value of `self`
mutating func removeFirst(_ k: Int)
/// Removes the last several values in the end of the BitArray
///
/// The following example removes the last 3 elements of a BitArray
/// var bitArray: BitArray = [true, false, true, false, false, true]
/// bitArray.removeLast(3)
/// print(Array(bitArray))
/// Prints "[true, false, true]"
///
/// - Parameters:
/// - k: an integer that represents the number of values desired to be removed from the beginning.
///`k` must be a positive number, and less than the `count` value of self
mutating func removeLast(_ k: Int)
```

Additionally, there are two functions that indicate where the first and last true values are located in the BitArray

```
/// Returns the index of the first true value in the BitArray.
/// If there are no true values in the BitArray, the function returns nil
///
/// Examples:
/// let bitArray: BitArray = [false, true, false, true]
/// let firstTrue: Int? = bitArray.firstTrue()
/// print(firstTrue)
/// Prints "2"
///
/// let allFalseBitArray: BitArray = [false, false, false]
/// let firstTrue: Int? = allFalseBitArray.firstTrue()
/// print(firstTrue)
/// Prints "nil"
///
/// - Returns: An optional integer value of the index where the first true was found.
/// If there are no true values in the BitArray, the function returns `nil`
func firstTrue() -> Int?
/// Returns the index of the last true value in the BitArray.
/// If there are no true values in the BitArray, the function returns nil
///
/// Examples:
/// let bitArray: BitArray = [false, true, false, true]
/// let lastTrue: Int? = bitArray.lastTrue()
/// print(lastTrue)
/// Prints "2"
///
/// let allFalseBitArray: BitArray = [false, false, false]
/// let lastTrue: Int? = allFalseBitArray.lastTrue()
/// print(lastTrue)
/// Prints "nil"
///
/// - Returns: An optional integer value of the index where the last true was found
/// If there are no true values in the BitArray, the function returns `nil`
func lastTrue() -> Int?
```

###
**BitSet**

`BitSet`

is like `BitArray`

, except a true value in its underlying storage represents an integer at the respective offset (a false value represents the absence of an integer at the respective offset). In fact, its storage *is* a `BitArray`

. The API, however, works much like a `Set<Int>`

, although `BitSet`

does not actually conform to any `Set<Int>`

protocols.

```
var bitSet: BitSet= [0, 5, 8, 6]
// Some set operations that work on BitSet
bitSet.formUnion(BitSet([2, 4, 6]))
bitSet.insert(3)
```

### Definition

```
struct BitSet: ExpressibleByArrayLiteral, BidirectionalCollection, {
struct Index: Comparable, Hashable {...}
subscript(position: Index) -> Int
}
```

`BitSet`

has an opaque (non-integer) index. Advancing the index forward (or backward) is O(n) because `BitSet`

searches the underlying storage for the next (or previous) true bit.

### BitSet's Set-Like APIs

Although `BitSet`

doesn't conform to `SetAlgebra`

, it makes use of many of the same functions. `BitSet`

doesn't directly conform mainly because there are some unnecessary features and functions that come with `SetAlgebra`

that `BitSet`

does better off without.

###
*Insert*

```
/// Inserts a new member into the set
/// The following examples insert a 2 into a set that already has a 2 and a set that doesn't, respectively
/// var bitSetWithTwo: BitSet = [0, 2, 4, 5]
/// var didInsert: Bool = bitSetWithTwo.insert(2)
/// print(didInsert)
/// // Prints "false"
/// print(Array(bitSetWithTwo))
/// // Prints "[0, 2, 4, 5]"
///
/// var bitSetWithoutTwo: BitSet = [0, 3, 4, 6]
/// didInsert = bitSetWithoutTwo.insert(2)
/// print(didInsert)
/// // Prints "true"
/// print(Array(bitSetWithoutTwo))
/// // Prints "[0, 2, 3, 4, 6]"
///
/// - Parameter newMember: An element to insert into the set
/// - Returns: `true` if `newMember` was not contained in the
/// set. If an element equal to `newMember` was already contained in the
/// set, the method returns `false`. Returned value is discarded without giving a warning if unused
@discardableResult
mutating func insert(_ newMember: Int) -> Bool
```

###
*Remove*

```
/// Removes a member from the set
/// The following examples remove a 2 from a set that has a 2 and a set that doesn't, respectively
/// var bitSetWithTwo: BitSet = [0, 2, 4, 5]
/// var didRemove: Bool = bitSetWithTwo.remove(2)
/// print(didRemove)
/// // Prints "true"
/// print(Array(bitSetWithTwo))
/// // Prints "[0, 4, 5]"
///
/// var bitSetWithoutTwo: BitSet = [0, 3, 4, 6]
/// didRemove = bitSetWithoutTwo.remove(2)
/// print(didRemove)
/// // Prints "false"
/// print(Array(bitSetWithoutTwo))
/// // Prints "[0, 3, 4, 6]"
///
/// - Parameter member: An element to remove from the set.
/// - Returns: `true` if `member` was contained in the
/// set. If an element equal to `member` was not already contained in the
/// set, the method returns `false`. Returned value is discarded without giving a warning if unused
@discardableResult
mutating func remove(_ member: Int) -> Bool
```

###
*Contains*

```
/// Checks whether the set contains a value or not
///
/// Example:
/// let bitSet: BitSet = [0, 2, 5, 6, 7]
/// let doesContain: Bool = bitSet.contains(0)
/// print(doesContain) // prints "true"
/// doesContain = bitSet.contains(8)
/// print(doesContain) // prints "false"
///
/// - Parameter member: An element to look for in the set.
/// - Returns: `true` if `member` exists in the set; otherwise returns `false`.
func contains(_ member: Int) -> Bool
```

###
*Union*

```
/// mutates self to be the resulting union of itself and another set
/// The union is the set of values that exist in either or both sets
///
/// The following example takes a set and transforms it into the union of itself and another set
/// var firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// firstBitSet.formUnion(secondBitSet)
/// print(Array(firstBitSet)) // prints "[0, 2, 3, 4, 5, 6]"
///
/// - Parameter other: Another BitSet. `other` must be finite
mutating func formUnion(_ other: BitSet)
/// creates a new BitSet that is the resulting union of itself and another set
/// The union is the set of values that exist in either or both sets
///
/// The following example creates a set that is the union of two sets
/// let firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// let resultSet = firstBitSet.union(secondBitSet)
/// print(Array(resultSet)) // prints "[0, 2, 3, 4, 5, 6]"
///
/// - Parameter other: Another BitSet
/// - Returns: A new BitSet with the elements that are in this set or `other` or both.
func union(_ other: BitSet) -> BitSet
```

###
*Intersection*

```
/// mutates self to be the resulting intersection of itself and another set
/// The intersection is the set of values that exist both sets
///
/// The following example takes a set and transforms it into the intersection of itself and another set
/// var firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// firstBitSet.formIntersection(secondBitSet)
/// print(Array(firstBitSet)) // prints "[2, 5]"
///
/// - Parameter other: Another BitSet
mutating func formIntersection(_ other: BitSet)
/// creates a new BitSet that is the resulting intersection of itself and another set
/// The intersection is the set of values that exist both sets
///
/// The following example creates a set that is the union of two sets
/// let firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// let resultSet = firstBitSet.intersection(secondBitSet)
/// print(Array(resultSet)) // prints "[2, 5]"
///
/// - Parameter other: Another BitSet
/// - Returns: A new BitSet with the elements that are both in this set and `other`.
func intersection(_ other: BitSet) -> BitSet
```

###
*Symmetric Difference*

```
/// mutates self to be the resulting symmetric difference of itself and another set
/// The symmetric difference is the set of values that exist one set or the other, but not both
///
/// The following example takes a set and mutates it into the symmetric difference between itself and another set
/// var firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// firstBitSet.formSymmetricDifference(secondBitSet)
/// print(Array(firstBitSet)) // prints "[0, 3, 4, 6]"
///
/// - Parameter other: Another BitSet
mutating func formSymmetricDifference(_ other: BitSet)
/// creates a new BitSet that is the resulting symmetric difference of itself and another set
/// The symmetric difference is the set of values that exist one set or the other, but not both
///
/// The following example creates a set that is the symmetric difference of two sets
/// let firstBitSet: BitSet = [0, 2, 3, 5]
/// let secondBitSet: BitSet = [2, 4, 5, 6]
/// let resultSet = firstBitSet.symmetricDifference(secondBitSet)
/// print(Array(resultSet)) // prints "[0, 3, 4, 6]"
///
/// - Parameter other: Another BitSet
/// - Returns: A new BitSet with the elements that are in either this set or the other set, but not both
func symmetricDifference(_ other: BitSet) -> BitSet
```

### BitSet initializer from BitArray

A `BitSet`

can conveniently be initialized from a `BitArray`

. The `BitArray`

simply becomes it's storage. If there are excessive false values at the end of the `BitArray`

storage, they are removed as `BitSet`

does not keep track of false values.

```
// Initializes a BitSet from a BitArray
init(_ bitArray: BitArray)
```

## Considerations

### Computed startIndex Property

The `startIndex`

for the `BitArray`

is traditionally a stored property of constant time. However, for the `BitSet`

, as it needs to traverse and find the first true value in its `BitArray`

storage type, is a computed property. Although this might not be ideal, when benchmarked, the operation is hardly slow at all. Consider this linear view of a benchmark comparing the `BitSet`

's `startIndex`

lookup compared to that of the `Set<Int>`

:

Their runtimes hardly differ, and oftentimes the `BitSet`

performs better than the `Set<Int>`

. There may be a few worse-case scenarios where the `BitSet`

's `startIndex`

lookup is worse, but I felt it wasn't significant enough to go for the more complicated approach.

## Lack of Conformance to RangeReplaceableCollection

Even though `Array<Bool>`

conforms to `RangeReplaceableCollection`

, I choose not to conform to it for `BitArray`

. This is because use cases for the `replaceSubrange(...)`

method seems to be a rarity (and actually couldn't think of any). Additionally, such a method would likely be costly in performance; as the conformance takes the `replaceSubrange(...)`

implementation and utilizes it for all `RangeReplaceableCollection`

methods, it could potentially make several other methods unnecessarily slow as well. Hence, as a conformance to `RangeReplaceableCollection`

requires an implementation of `replaceSubrange(...)`

, the conformance seemed unnecessary. Instead, I added implementations of certain methods that might be useful.

## Lack of Conformance to SetAlgebra

As `BitSet`

is essentially a `Set<Int>`

in its API. Therefore, not conforming to `SetAlgebra`

is naturally an interesting choice. Instead, useful methods from `SetAlbegra`

were implemented.

For example, for the `insert(...)`

method:

```
// SetAlgebra method
@discardableResult
mutating func insert( _ newMember: __owned Element) -> (inserted: Bool, memberAfterInsert: Element)
// BitSet method
@discardableResult
mutating func insert(_ newMember: Int) -> Bool
```

The insert method in `SetAlgebra`

returns virtually useless information for a BitSet, resulting in the method doing more work than necessary.

Additionally, `SetAlgebra`

requires an implementation of the `update(...)`

method, that, not only returns more information than necessary, but has practically the same purpose as `insert(...)`

, making it practically useless, as well as confusing for an API.

```
mutating func update(with newMember: __owned Element) -> Element?
```

Hence, instead of implementing all of these practically useless or overworking methods, *some* useful methods were cherry picked from `SetAlgebra`

and implemented manually without the conformance.

## Some Neat Performance Benchmarks

As explained in the Proposed Solution section, a primary objective in implementing these data structures was to speed up typical operations (bitwise operations for the `BitArray`

and set operations for the `BitSet`

). As `Array<Bool>`

does not have any bitwise operations, having them for `BitArray`

is already a plus, and there isn't much to compare it to within the realm of Swift. However, for the `BitSet`

, it is possible to test how much faster the `BitSet`

set operations are compared to the `Set<Int>`

. I was very happy to see the performance charts of the `BitSet`

operations compared to that of `Set<Int>`

, and am very excited to share them with you all as well! Check it out!

###
*BitSet Union VS Set<Int> Union*

###
*BitSet Intersection VS Set<Int> Intersection*

###
*BitSet Symmetric Difference VS Set<Int> Symmetric Difference*

Very pleasing to the eye if you ask me

## End Remarks

Thank you for reviewing this API! Please feel free to leave feedback and suggestions! I;m very grateful for the great time I had with the Swift Standard Library on my GSoC project!

A special thanks to my primary mentor @David_Smith, as well as my other great mentors @lorentey and @kylemacomber. Also a special thanks to some Twitter friends who were willing to look over my draft for errors @ ziti and @ nasimuddin01