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" ; import { Status } from "./status" ; const { bit , take , skip , test , set , clear , popCount } = Bits ; /**
 * Maps are stored as an hash-table of keys.
 * The hash-table is stored as a tree where each internal node is a partial
 * match of the hashes of its subtree.
 *
 * Nodes in the tree can be:
 * * empty;
 * * a Leaf, containing one single key;
 * * a Collision, containing several keys with the same hash, this is
 *   effectively a leaf of the tree, even though it actually has several Leaf
 *   children (but no other kind);
 * * a Sparse, which is an internal node. Sparses have masks and all hashes in
 *   this subtree share the same mask (partial hash collision). The matching of
 *   masks is done with a shift, which essentially take slices of n (=5) bits
 *   of the hash. The shift is automatically increased when looking down the
 *   tree, hence the same mask cannot be used at another level of a tree.
 */ internal export interface Node < K , V > extends Functor < V > , Iterable < [ K , V ] > , Equatable { isEmpty ( ) : this is Empty ; isLeaf ( ) : this is Leaf < K , V > ; get ( key , hash , shift ) : Option < V > ; set ( key , value , hash , shift ) : Status < Node < K , V > > ; delete ( key , hash , shift ) : Status < Node < K , V > > ; map < U > ( mapper ) : Node < K , U > ; } internal export namespace Node { export const Bits = 5 ; export function fragment ( hash , shift ) { return take ( skip ( hash , shift ) , Bits ) ; } export function index ( fragment , mask ) { return popCount ( take ( mask , fragment ) ) ; } } internal export interface Empty extends Node < never , never > { } internal export const Empty = new ( class Empty { public isEmpty ( ) { return true ; } public isLeaf ( ) { return false ; } public get ( ) { return None ; } public set < K , V > ( key , value , hash ) { return Status . created ( Leaf . of ( hash , key , value ) ) ; } public delete < K , V > ( ) { return Status . unchanged ( this ) ; } public map ( ) { return this ; } public equals ( value ) { return value instanceof Empty ; } public * [ Symbol . iterator ] ( ) { } } ) ( ) ; internal export class Leaf < K , V > implements Node < K , V > { public static of < K , V > ( hash , key , value ) { return new Leaf ( hash , key , value ) ; } private readonly _hash : number ; private readonly _key : K ; private readonly _value : V ; private constructor ( hash , key , value ) { this . _hash = hash ; this . _key = key ; this . _value = value ; } public get key ( ) : K { return this . _key ; } public get value ( ) : V { return this . _value ; } public isEmpty ( ) { return false ; } public isLeaf ( ) { return true ; } public get ( key , hash , shift ) { return hash === this . _hash && Equatable . equals ( key , this . _key ) ? Option . of ( this . _value ) : None ; } public set ( key , value , hash , shift ) { if ( hash === this . _hash ) { if ( Equatable . equals ( key , this . _key ) ) { if ( Equatable . equals ( value , this . _value ) ) { return Status . unchanged ( this ) ; } return Status . updated ( Leaf . of ( hash , key , value ) ) ; } return Status . created ( Collision . of ( hash , [ this , Leaf . of ( hash , key , value ) ] ) ) ; } const fragment = Node . fragment ( this . _hash , shift ) ; return Sparse . of ( bit ( fragment ) , [ this ] ) . set ( key , value , hash , shift ) ; } public delete ( key , hash ) { return hash === this . _hash && Equatable . equals ( key , this . _key ) ? Status . deleted ( Empty ) : Status . unchanged ( this ) ; } public map < U > ( mapper ) { return Leaf . of ( this . _hash , this . _key , mapper ( this . _value , this . _key ) ) ; } public equals ( value ) { return ( value instanceof Leaf && value . _hash === this . _hash && Equatable . equals ( value . _key , this . _key ) && Equatable . equals ( value . _value , this . _value ) ) ; } public * [ Symbol . iterator ] ( ) { yield [ this . _key , this . _value ] ; } } internal export class Collision < K , V > implements Node < K , V > { public static of < K , V > ( hash , nodes ) { return new Collision ( hash , nodes ) ; } private readonly _hash : number ; private readonly _nodes : Array < Leaf < K , V > > ; private constructor ( hash , nodes ) { this . _hash = hash ; this . _nodes = nodes ; } public isEmpty ( ) { return false ; } public isLeaf ( ) { return false ; } public get ( key , hash , shift ) { if ( hash === this . _hash ) { for ( const node of this . _nodes ) { const value = node . get ( key , hash , shift ) ; if ( value . isSome ( ) ) { return value ; } } } return None ; } public set ( key , value , hash , shift ) { if ( hash === this . _hash ) { for ( let i = 0 , n = this . _nodes . length ; i < n ; i ++ ) { const node = this . _nodes [ i ] ; if ( Equatable . equals ( key , node . key ) ) { if ( Equatable . equals ( value , node . value ) ) { return Status . unchanged ( this ) ; } return Status . updated ( Collision . of ( this . _hash , replace ( this . _nodes , i , Leaf . of ( hash , key , value ) ) ) ) ; } } return Status . created ( Collision . of ( this . _hash , this . _nodes . concat ( Leaf . of ( hash , key , value ) ) ) ) ; } const fragment = Node . fragment ( this . _hash , shift ) ; return Sparse . of ( bit ( fragment ) , [ this ] ) . set ( key , value , hash , shift ) ; } public delete ( key , hash ) { if ( hash === this . _hash ) { for ( let i = 0 , n = this . _nodes . length ; i < n ; i ++ ) { const node = this . _nodes [ i ] ; if ( Equatable . equals ( key , node . key ) ) { const nodes = remove ( this . _nodes , i ) ; if ( nodes . length === 1 ) { return Status . deleted ( nodes [ 0 ] ) ; } return Status . deleted ( Collision . of ( this . _hash , nodes ) ) ; } } } return Status . unchanged ( this ) ; } public map < U > ( mapper ) { return Collision . of ( this . _hash , this . _nodes . map ( ( node ) => node . map ( mapper ) ) ) ; } public equals ( value ) { return ( value instanceof Collision && value . _hash === this . _hash && 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 ; } } } internal export class Sparse < K , V > implements Node < K , V > { public static of < K , V > ( mask , nodes ) { return new Sparse ( mask , nodes ) ; } private readonly _mask : number ; private readonly _nodes : Array < Node < K , V > > ; private constructor ( mask , nodes ) { this . _mask = mask ; this . _nodes = nodes ; } public isEmpty ( ) { return false ; } public isLeaf ( ) { return false ; } public get ( key , hash , shift ) { const fragment = Node . fragment ( hash , shift ) ; if ( test ( this . _mask , fragment ) ) { const index = Node . index ( fragment , this . _mask ) ; return this . _nodes [ index ] . get ( key , hash , shift + Node . Bits ) ; } return None ; } public set ( key , value , hash , shift ) { const fragment = Node . fragment ( hash , shift ) ; const index = Node . index ( fragment , this . _mask ) ; if ( test ( this . _mask , fragment ) ) { const { result : node , status } = this . _nodes [ index ] . set ( key , value , hash , shift + Node . Bits ) ; if ( status === "unchanged" ) { return Status . unchanged ( this ) ; } const sparse = Sparse . of ( this . _mask , replace ( this . _nodes , index , node ) ) ; switch ( status ) { case "created" : return Status . created ( sparse ) ; case "updated" : default : return Status . updated ( sparse ) ; } } return Status . created ( Sparse . of ( set ( this . _mask , fragment ) , insert ( this . _nodes , index , Leaf . of ( hash , key , value ) ) ) ) ; } public delete ( key , hash , shift ) { const fragment = Node . fragment ( hash , shift ) ; if ( test ( this . _mask , fragment ) ) { const index = Node . index ( fragment , this . _mask ) ; const { result : node , status } = this . _nodes [ index ] . delete ( key , hash , shift + Node . Bits ) ; if ( status === "unchanged" ) { return Status . unchanged ( this ) ; } if ( node . isEmpty ( ) ) { const nodes = remove ( this . _nodes , index ) ; if ( nodes . length === 1 ) { if ( nodes [ 0 ] . isLeaf ( ) || nodes [ 0 ] instanceof Collision ) { return Status . deleted ( nodes [ 0 ] ) ; } } return Status . deleted ( Sparse . of ( clear ( this . _mask , fragment ) , nodes ) ) ; } return Status . deleted ( Sparse . of ( this . _mask , replace ( this . _nodes , index , node ) ) ) ; } return Status . unchanged ( this ) ; } public map < U > ( mapper ) { return Sparse . of ( this . _mask , this . _nodes . map ( ( node ) => node . map ( mapper ) ) ) ; } public equals ( value ) { return ( value instanceof Sparse && value . _mask === this . _mask && 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 ; } } } function insert < T > ( array , index , value ) { const result = new Array ( array . length + 1 ) ; result [ index ] = value ; for ( let i = 0 , n = index ; i < n ; i ++ ) { result [ i ] = array [ i ] ; } for ( let i = index , n = array . length ; i < n ; i ++ ) { result [ i + 1 ] = array [ i ] ; } return result ; } function remove < T > ( array , index ) { const result = new Array ( array . length - 1 ) ; for ( let i = 0 , n = index ; i < n ; i ++ ) { result [ i ] = array [ i ] ; } for ( let i = index , n = result . length ; i < n ; i ++ ) { result [ i ] = array [ i + 1 ] ; } return result ; } function replace < T > ( array , index , value ) { const result = array . slice ( 0 ) ; result [ index ] = value ; return result ; }