Uint4 (hexadecimal digit) ordered set (16bits memory usage and O(1) computational complexity)

uint4ordset.ts

/*
Copyright (c) 2018 Victorien Elvinger
This Source Code Form is subject to the terms of the Mozilla Public
License, v. 2.0. If a copy of the MPL was not distributed with this
file, You can obtain one at http://mozilla.org/MPL/2.0/.
*/

export type uint4 = number

/**
 * Ordered set of 4bits unsigned integers (hexadecimal digits)
 */
export type Uint4OrdSet = uint4

/**
 * Empty set
 */
export const EMPTY = 0

export function count (s: Uint4OrdSet): uint4 {
    const countBy2 = s - ((s >>> 1) & 0x5555_5555)
    const countBy4 = (countBy2 & 0x3333_3333) + ((countBy2 >>> 2) & 0x3333_3333)
    const countBy8 = (countBy4 + (countBy4 >>> 4)) & 0x0F0F_0F0F
    return (countBy8 * 0x0101_0101) >>> 24
    // left 8 bits of countBy8 + (countBy8 << 8) + (countBy8 << 16) + (countBy8 << 24)
}

export function has (s: Uint4OrdSet, n: uint4): boolean {
    const pos = 0b1 << n
    return (s & pos) !== 0
}

/**
 * @param s ordered set of uint4
 * @param n Index where the element is or can be inserted
 */
export function insIndex (s: Uint4OrdSet, n: uint4): uint4 {
    const pos = 0b1 << n
    const mask = pos - 1
    const relevant = s & mask
    return count(relevant)
}

export function last (s: Uint4OrdSet): uint4 {
    return Math.log2(s) >>> 0
}

export function first (s: Uint4OrdSet): uint4 {
    const relevant = s ^ (s - 1)
    return count(relevant) - 1
    //return last(relevant)
}

export function previous (s: Uint4OrdSet, n: uint4): uint4 {
    const pos = 0b1 << n
    const mask = pos - 1
    const relevant = s & mask
    return last(relevant)
}

export function next (s: Uint4OrdSet, n: uint4): uint4 {
    const pos = 0b1 << n
    const mask = ((pos << 1) - 1) ^ 0xFF
    const relevant = s & mask
    return first(relevant)
}

export function add (s: Uint4OrdSet, n: uint4): Uint4OrdSet {
    const pos = 0b1 << n
    return s | pos
}

export function remove (s: Uint4OrdSet, n: uint4): Uint4OrdSet {
    const pos = 0b1 << n
    return (s | pos) - pos // ensure that pos is set and then unset it
}