All files / utils bit-array.ts

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
 
 
 
 
 
 
 
 
 
 
 
6x
 
 
 
225x
 
 
 
 
 
 
225x
225x
225x
225x
 
 
 
 
 
 
843x
 
 
 
 
 
 
 
2487x
 
 
 
2487x
 
2487x
 
 
 
 
 
 
2487x
1235x
 
 
 
2487x
 
 
 
 
 
 
 
 
225x
2487x
 
 
 
 
 
 
 
 
176751x
 
 
 
176751x
176751x
 
 
 
 
 
 
 
 
172x
 
 
 
172x
172x
2212x
2212x
 
172x
 
 
 
 
 
181450x
 
 
 
 
 
 
181450x
 
 
 
 
182685x
 
 
 
 
181450x
 
 
export type bit = 0 | 1;
type byte = number;
 
interface IBitArray {
  size: number,
  push: (value: bit) => void
  pushAll: (value: Array<bit>) => void
  atIndex: (index: number) => bit
  atIndexRange: (index: number, count: number) => bit[]
}
 
export default class BitArray implements IBitArray {
  private _array: Uint8Array;
  private _size: number;
  private _pointer: number;
  private _bitPerIndex: number = 8;
 
  /**
   * Creates a bitArray
   * @param values The bits to push onto the array
   */
  constructor(values: Array<bit>) {
    this._size = values.length;
    this._array = new Uint8Array(Math.ceil(this._size/this._bitPerIndex));
    this._pointer = 0;
    this.pushAll(values);
  }
  
  /**
   * Gets the size of the array
   */
  public get size() {
    return this._size;
  }
 
  /**
   * Pushes a single bit onto the array
   * @param value The bit to push onto the array
   */
  public push(value: bit) {
    Iif (this._pointer == this._size) {
      throw `Bit array max size reached (${this._size})`;
    }
    // create a mask for current index.
    const mask = this._createMask(this._pointer);
    // compare the array with the mask. A value different than 0 means the target bit is set
    Iif (this._matchesMask(mask, this._array[this._arrayIndex(this._pointer)])) {
      // bit is set in array. Should we toggle it?
      if (value === 0) {
        this._array[this._arrayIndex(this._pointer)] ^= mask;
      }
    } else {
      // bit is unset in array. Sould we toggle it?
      if (value === 1) {
        this._array[this._arrayIndex(this._pointer)] ^= mask;
      }
    }
    // increment pointer for next push
    this._pointer++;
  }
 
  /**
   * Pushes a an array of bits onto the array
   * @param values The bits to push onto the array
   */
  public pushAll(values: Array<bit>) {
    // TODO: Improve performance
    values.forEach((value) => {
      this.push(value);
    });
  }
 
  /**
   * Gets the bit at a given index
   * @param index The index of the bit to return
   */
  public atIndex(index: number): bit {
    Iif (index > this._size) {
      throw `Index (${index}) exceeds the size of the bit array (${this._size})`;
    }
 
    const mask = this._createMask(index);
    return this._matchesMask(mask, this._array[this._arrayIndex(index)]) ? 1 : 0;
  }
 
  /**
   * Gets count bits at a given index
   * @param index The index of the first bit to return
   * @param count The amount of bits to fetch starting at the index
   */
  public atIndexRange(index: number, count: number): bit[] {
    Iif (index + count - 1 > this._size) {
      throw `Index (${index}) exceeds the size of the bit array (${this._size})`;
    }
  
    const values: bit[] = [];
    for (let i = 0; i < count; i++) {
      const mask = this._createMask(index + i);
      values.push(this._matchesMask(mask, this._array[this._arrayIndex(index + i)]) ? 1 : 0);
    }
    return  values;
  }
  
  // Checks whether a value has a bit of 1 at the mask position
  private _matchesMask(mask: byte, value: byte) {
    // returns true if bit is set
    return (mask & value) != 0;
  }
 
  // Creates a mask for a given index
  private _createMask(index: number): byte {
    // supposing the index is 2, the created mask is
    // 00100000
    return  1 << (this._bitPerIndex - 1) - this._arrayIndexOffset(index);
  }
 
  // Gets the Uint8Array index
  private _arrayIndex(index: number) {
    return Math.floor(index / this._bitPerIndex);
  }
 
  // Gets the offset within the Uint8Array
  private _arrayIndexOffset(index: number) {
    return index % this._bitPerIndex;
  }
};