import { Bits } from "@siteimprove/alfa-bits" ; import { Equatable } from "@siteimprove/alfa-equatable" ; import { Functor } from "@siteimprove/alfa-functor" ; import { Iterable } from "@siteimprove/alfa-iterable" ; import { Mapper } from "@siteimprove/alfa-mapper" ; import { None , Option } from "@siteimprove/alfa-option" ; const { bit , take , skip } = Bits ; internal export interface Node < T > extends Functor < T > , Iterable < T > , Equatable { isEmpty ( ) : this is Empty ; isLeaf ( ) : this is Leaf < T > ; get ( index , shift ) : Option < T > ; set ( index , value , shift ) : Node < T > ; map < U > ( mapper ) : Node < U > ; } internal export namespace Node { export const Bits = 5 ; export const Capacity = bit ( Bits ) ; export function fragment ( index , shift ) { return take ( skip ( index , shift ) , Bits ) ; } export function overflow ( shift ) { return Capacity << ( shift - Bits ) ; } export function underflow ( shift ) { return Capacity << ( shift - Bits * 2 ) ; } } internal export interface Empty extends Node < never > { } internal export const Empty = new ( class Empty { public isEmpty ( ) { return true ; } public isLeaf ( ) { return false ; } public get ( ) { return None ; } public set ( ) { return this ; } public map ( ) { return this ; } public equals ( value ) { return value instanceof Empty ; } public * [ Symbol . iterator ] ( ) { } } ) ( ) ; internal export class Leaf < T > implements Node < T > { public static of < T > ( values ) { return new Leaf ( values ) ; } private readonly _values : Array < T > ; private constructor ( values ) { this . _values = values ; } public get values ( ) : Array < T > { return this . _values ; } public isEmpty ( ) { return false ; } public isLeaf ( ) { return true ; } public hasCapacity ( ) { return this . _values . length < Node . Capacity ; } public get ( index ) { const fragment = take ( index , Node . Bits ) ; return Option . of ( this . _values [ fragment ] ) ; } public set ( index , value ) { const fragment = take ( index , Node . Bits ) ; if ( Equatable . equals ( value , this . _values [ fragment ] ) ) { return this ; } const values = this . _values . slice ( 0 ) ; values [ fragment ] = value ; return Leaf . of ( values ) ; } public map < U > ( mapper ) { return Leaf . of ( this . _values . map ( mapper ) ) ; } public equals ( value ) { return ( value instanceof Leaf && value . _values . length === this . _values . length && value . _values . every ( ( value , i ) => Equatable . equals ( value , this . _values [ i ] ) ) ) ; } public * [ Symbol . iterator ] ( ) { yield * this . _values ; } } internal export class Branch < T > implements Node < T > { public static of < T > ( nodes ) { return new Branch ( nodes ) ; } public static empty < T > ( ) { return new Branch ( [ ] ) ; } private readonly _nodes : Array < Branch < T > | Leaf < T > > ; private constructor ( nodes ) { this . _nodes = nodes ; } public get nodes ( ) : Array < Branch < T > | Leaf < T > > { return this . _nodes ; } public isEmpty ( ) { return false ; } public isLeaf ( ) { return false ; } public clone ( ) { return Branch . of ( this . _nodes . slice ( 0 ) ) ; } public get ( index , shift ) { const fragment = Node . fragment ( index , shift ) ; return this . _nodes [ fragment ] . get ( index , shift - Node . Bits ) ; } public set ( index , value , shift ) { const fragment = Node . fragment ( index , shift ) ; const node = this . _nodes [ fragment ] . set ( index , value , shift - Node . Bits ) ; if ( node === this . _nodes [ fragment ] ) { return this ; } const nodes = this . _nodes . slice ( 0 ) ; nodes [ fragment ] = node ; return Branch . of ( nodes ) ; } public map < U > ( mapper ) { return Branch . of ( this . _nodes . map ( ( node ) => ( node as Node < T > ) . map ( mapper ) as Branch < U > | Leaf < U > ) ) ; } public equals ( value ) { return ( value instanceof Branch && value . _nodes . length === this . _nodes . length && value . _nodes . every ( ( node , i ) => node . equals ( this . _nodes [ i ] ) ) ) ; } public * [ Symbol . iterator ] ( ) { for ( const node of this . _nodes ) { yield * node ; } } }