@kitsu/bfs@0.1.6

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275
function* chain<T>(...iterators: IteratorObject<T>[]): Generator<T> {
  for (const iter of iterators) {
    for (const value of Iterator.from(iter)) {
      yield value
    }
  }
}

export type Bit = 1 | 0
export type Bits = number
export type Index = number

export interface IBitSet {
  get flags(): Bits
  get length(): number

  add(index: Index): Bits
  clear(): void
  difference(other: IBitSet): IteratorObject<Index>
  extend(indices: Iterable<Index>): void
  grow(bits: number): void
  has(index: Index): boolean
  intersection(other: IBitSet): IteratorObject<Index>
  isDisjoint(other: IBitSet): boolean
  isSubset(other: IBitSet): boolean
  isSuperset(other: IBitSet): boolean
  isEmpty(): boolean
  ones(): IteratorObject<Index>
  remove(index: Index): Bits
  set(index: Index, enabled: boolean): Bits
  symmetricDifference(other: IBitSet): IteratorObject<Index>
  union(other: IBitSet): IteratorObject<Index>
  zeroes(): IteratorObject<Index>
}

export class FixedBitSet implements IBitSet {
  _value: Bits
  _length: number

  get flags(): Bits {
    return this._value
  }

  get length(): number {
    return this._length
  }

  constructor(value: Bits = 0, length: number = 32) {
    this._value = value
    this._length = length
  }

  static from(value: Iterable<Index> | FixedBitSet): FixedBitSet {
    if (value instanceof FixedBitSet) {
      return value
    }

    const iter = Iterator.from(value)
    const next = iter.next()

    if (next.value == null || next.done) {
      return new FixedBitSet()
    }

    let bits = next.value
    let len = 0

    for (const index of iter) {
      bits |= 1 << index
      len = index
    }

    return new FixedBitSet(bits, Math.max(32, len))
  }

  static has(value: Bits, index: Index): boolean {
    return (value & (1 << index)) !== 0
  }

  static *ones(value: Bits, length: number = 32): Generator<Index> {
    for (let i = 0; i < length; i++) {
      if ((value & 1) > 0) {
        yield i
      }

      value = value >> 1
    }
  }

  static *zeros(value: Bits, length: number = 32): Generator<Index> {
    for (let i = 0; i < length; i++) {
      if ((value & 1) === 0) {
        yield i
      }
      value = value >> 1
    }
  }

  static length(value: Bits): number {
    value = value - (value >> 1) & 0x55555555
    value = (value & 0x33333333) + (value >> 2) & 0x33333333
    return ((value + (value >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
  }

  static *intersection(a: IBitSet, b: IBitSet): Generator<Index> {
    for (const index of FixedBitSet.ones(a.flags)) {
      if (b.has(index)) {
        yield index
      }
    }
  }

  static *difference(a: IBitSet, b: IBitSet): Generator<Index> {
    for (const index of FixedBitSet.ones(a.flags)) {
      if (!b.has(index)) {
        yield index
      }
    }
  }

  static *union(a: IBitSet, b: IBitSet): Generator<Index> {
    for (
      const index of chain(
        FixedBitSet.ones(a.flags, a.length),
        FixedBitSet.difference(b, a),
      )
    ) {
      yield index
    }
  }

  static *symmetricDifference(a: IBitSet, b: IBitSet): Generator<Index> {
    for (
      const index of chain(
        FixedBitSet.difference(a, b),
        FixedBitSet.difference(b, a),
      )
    ) {
      yield index
    }
  }

  static isDisjoint(a: IBitSet, b: IBitSet): boolean {
    return FixedBitSet.intersection(a, b).next().done || false
  }

  static isSubset(a: IBitSet, b: IBitSet): boolean {
    for (const index of FixedBitSet.ones(a.flags, a.length)) {
      if (!b.has(index)) {
        return false
      }
    }

    return true
  }

  static isSuperset(a: IBitSet, b: IBitSet): boolean {
    return b.isSubset(a)
  }

  static isEmpty(value: Bits): boolean {
    return value === 0
  }

  static add(value: Bits, index: Index): Bits {
    return value |= 1 << index
  }

  static remove(value: Bits, index: Index): Bits {
    return value & ~(1 << index)
  }

  static set(value: Bits, index: Index, enabled: boolean): Bits {
    return enabled
      ? FixedBitSet.add(value, index)
      : FixedBitSet.remove(value, index)
  }

  clear() {
    this._value = 0
  }

  has(b: Index): boolean {
    return FixedBitSet.has(this._value, b)
  }

  set(index: Index, enabled: boolean): Bits {
    this._value = FixedBitSet.set(this._value, index, enabled)
    return this._value
  }

  extend(indices: Iterable<Index>): void {
    for (const index of indices) {
      if (index >= this._length) {
        this.grow(index + 1)
      }

      this.add(index)
    }
  }

  grow(bits: number): void {
    if (bits > this._length) {
      this._length = bits
    }
  }

  growAndAdd(index: Index): Bits {
    this.grow(index)
    return this.add(index)
  }

  union(other: IBitSet): IteratorObject<Index> {
    return FixedBitSet.union(this, other)
  }

  add(index: Index): Bits {
    this._value = FixedBitSet.add(this._value, index)
    return this._value
  }

  remove(index: Index): Bits {
    this._value = FixedBitSet.remove(this._value, index)
    return this._value
  }

  isDisjoint(other: IBitSet): boolean {
    return FixedBitSet.isDisjoint(this, other)
  }

  isSubset(other: IBitSet): boolean {
    return FixedBitSet.isSubset(this, other)
  }

  isSuperset(other: IBitSet): boolean {
    return FixedBitSet.isSuperset(this, other)
  }

  isEmpty(): boolean {
    return FixedBitSet.isEmpty(this._value)
  }

  ones(): IteratorObject<Index> {
    return FixedBitSet.ones(this._value, this._length)
  }

  zeroes(): IteratorObject<Index> {
    return FixedBitSet.zeros(this._value, this._length)
  }

  intersection(other: IBitSet): IteratorObject<Index> {
    return FixedBitSet.intersection(this, other)
  }

  difference(other: IBitSet): IteratorObject<Index> {
    return FixedBitSet.difference(this, other)
  }

  symmetricDifference(other: IBitSet): IteratorObject<Index> {
    return FixedBitSet.symmetricDifference(this, other)
  }

  toString(): string {
    return this._value.toString(2)
  }

  *[Symbol.iterator](): Generator<Bit> {
    const len = this._length
    let value = this._value
    for (let i = 0; i < len; i++) {
      yield (value & 1) as Bit
      value = value >> 1
    }
  }
}