import { Array } from "@siteimprove/alfa-array" ; import { Callback } from "@siteimprove/alfa-callback" ; import { Collection } from "@siteimprove/alfa-collection" ; import { Comparable , Comparer , Comparison } from "@siteimprove/alfa-comparable" ; import { Hash } from "@siteimprove/alfa-hash" ; import { Iterable } from "@siteimprove/alfa-iterable" ; import { Serializable } from "@siteimprove/alfa-json" ; import { Map } from "@siteimprove/alfa-map" ; import { Mapper } from "@siteimprove/alfa-mapper" ; import { None , Option } from "@siteimprove/alfa-option" ; import { Predicate } from "@siteimprove/alfa-predicate" ; import { Reducer } from "@siteimprove/alfa-reducer" ; import { Refinement } from "@siteimprove/alfa-refinement" ; import { Set } from "@siteimprove/alfa-set" ; import { Branch , Empty , Leaf , Node } from "./node" ; const { not } = Predicate ; const { compareComparable } = Comparable ; public export class List < T > implements Collection . Indexed < T > { public static of < T > ( ... values ) { const size = values . length ; if ( size <= Node . Capacity ) { return new List ( Empty , Leaf . of ( values ) , 0 , size ) ; } return values . reduce ( ( list , value ) => list . _push ( value ) , List . empty < T > ( ) ) ; } private static _empty = new List < never > ( Empty , Empty , 0 , 0 ) ; public static empty < T = never > ( ) { return this . _empty ; } private readonly _head : Empty | Leaf < T > | Branch < T > ; private readonly _tail : Empty | Leaf < T > ; private readonly _shift : number ; private readonly _size : number ; private constructor ( head , tail , shift , size ) { this . _head = head ; this . _tail = tail ; this . _shift = shift ; this . _size = size ; } public get size ( ) : number { return this . _size ; } public isEmpty ( ) { return this . _tail . isEmpty ( ) ; } public forEach ( callback ) { Iterable . forEach ( this , callback ) ; } public map < U > ( mapper ) { let index = 0 ; const tail = ( this . _tail as Node < T > ) . map ( ( value ) => mapper ( value , index ++ ) ) ; const head = ( this . _head as Node < T > ) . map ( ( value ) => mapper ( value , index ++ ) ) ; return new List ( head as Empty | Leaf < U > | Branch < U > , tail as Empty | Leaf < U > , this . _shift , this . _size ) ; } public apply < U > ( mapper ) { return mapper . flatMap ( ( mapper ) => this . map ( mapper ) ) ; } public flatMap < U > ( mapper ) { return this . reduce ( ( list , value , index ) => list . concat ( mapper ( value , index ) ) , List . empty < U > ( ) ) ; } public flatten < T > ( this ) { return this . flatMap ( ( list ) => list ) ; } public reduce < U > ( reducer , accumulator ) { return Iterable . reduce ( this , reducer , accumulator ) ; } public reduceWhile < U > ( predicate , reducer , accumulator ) { return Iterable . reduceWhile ( this , predicate , reducer , accumulator ) ; } public reduceUntil < U > ( predicate , reducer , accumulator ) { return Iterable . reduceUntil ( this , predicate , reducer , accumulator ) ; } public filter < U extends T > ( refinement ) ; public filter ( predicate ) ; public filter ( predicate ) { return List . from ( Iterable . filter ( this , predicate ) ) ; } public reject < U extends T > ( refinement ) ; public reject ( predicate ) ; public reject ( predicate ) { return this . filter ( not ( predicate ) ) ; } public find < U extends T > ( refinement ) ; public find ( predicate ) ; public find ( predicate ) { return Iterable . find ( this , predicate ) ; } public includes ( value ) { return Iterable . includes ( this , value ) ; } public collect < U > ( mapper ) { return List . from ( Iterable . collect ( this , mapper ) ) ; } public collectFirst < U > ( mapper ) { return Iterable . collectFirst ( this , mapper ) ; } public some ( predicate ) { return Iterable . some ( this , predicate ) ; } public none ( predicate ) { return Iterable . none ( this , predicate ) ; } public every ( predicate ) { return Iterable . every ( this , predicate ) ; } public count ( predicate ) { return Iterable . count ( this , predicate ) ; } public distinct ( ) { let seen = Set . empty < T > ( ) ; let list = List . empty < T > ( ) ; for ( const value of this ) { if ( seen . has ( value ) ) { continue ; } seen = seen . add ( value ) ; list = list . append ( value ) ; } return list ; } public get ( index ) { if ( index < 0 || index >= this . _size || this . _tail . isEmpty ( ) ) { return None ; } const offset = this . _size - this . _tail . values . length ; let value ; if ( index < offset ) { value = this . _head . get ( index , this . _shift - Node . Bits ) ; } else { value = this . _tail . get ( index - offset ) ; } return value ; } public has ( index ) { return index >= 0 && index < this . _size ; } public set ( index , value ) { if ( index < 0 || index >= this . _size || this . _tail . isEmpty ( ) ) { return this ; } const offset = this . _size - this . _tail . values . length ; let head = this . _head ; let tail = this . _tail ; if ( index < offset ) { if ( head . isEmpty ( ) ) { return this ; } head = head . set ( index , value , this . _shift ) ; if ( head === this . _head ) { return this ; } } else { tail = tail . set ( index - offset , value ) ; if ( tail === this . _tail ) { return this ; } } return new List ( head , tail , this . _shift , this . _size ) ; } public insert ( index , value ) { if ( index < 0 || index > this . size ) { return this ; } if ( index === 0 ) { return this . prepend ( value ) ; } if ( index === this . size ) { return this . append ( value ) ; } return List . from ( Iterable . concat ( Iterable . take ( this , index ) , Iterable . from ( [ value ] ) , Iterable . skip ( this , index ) ) ) ; } public append ( value ) { return this . _push ( value ) ; } public prepend ( value ) { return List . of ( value ) . concat ( this ) ; } public concat ( iterable ) { return Iterable . reduce < T , List < T > > ( iterable , ( list , value ) => list . _push ( value ) , this ) ; } public subtract ( iterable ) { return List . from ( Iterable . subtract ( this , iterable ) ) ; } public intersect ( iterable ) { return List . from ( Iterable . intersect ( this , iterable ) ) ; } public zip < U > ( iterable ) { return List . from ( Iterable . zip ( this , iterable ) ) ; } public first ( ) { return this . _tail . isEmpty ( ) ? None : Option . of ( this . _tail . values [ 0 ] ) ; } public last ( ) { return Iterable . last ( this ) ; } public take ( count ) { return List . from ( Iterable . take ( this , count ) ) ; } public takeWhile < U extends T > ( refinement ) ; public takeWhile ( predicate ) ; public takeWhile ( predicate ) { return List . from ( Iterable . takeWhile ( this , predicate ) ) ; } public takeUntil ( predicate ) { return this . takeWhile ( not ( predicate ) ) ; } public takeLast ( count = 1 ) { return List . from ( Iterable . takeLast ( this , count ) ) ; } public takeLastWhile < U extends T > ( refinement ) ; public takeLastWhile ( predicate ) ; public takeLastWhile ( predicate ) { return List . from ( Iterable . takeLastWhile ( this , predicate ) ) ; } public takeLastUntil ( predicate ) { return this . takeLastWhile ( not ( predicate ) ) ; } public skip ( count ) { return List . from ( Iterable . skip ( this , count ) ) ; } public skipWhile ( predicate ) { return List . from ( Iterable . skipWhile ( this , predicate ) ) ; } public skipUntil ( predicate ) { return this . skipWhile ( not ( predicate ) ) ; } public skipLast ( count = 1 ) { let list = this ; while ( count -- > 0 ) { list = list . _pop ( ) ; } return list ; } public skipLastWhile ( predicate ) { return List . from ( Iterable . skipLastWhile ( this , predicate ) ) ; } public skipLastUntil ( predicate ) { return this . skipLastWhile ( not ( predicate ) ) ; } public trim ( predicate ) { return this . trimLeading ( predicate ) . trimTrailing ( predicate ) ; } public trimLeading ( predicate ) { return this . skipWhile ( predicate ) ; } public trimTrailing ( predicate ) { return this . skipLastWhile ( predicate ) ; } public rest ( ) { return this . skip ( 1 ) ; } public slice ( start , end ? ) { return List . from ( Iterable . slice ( this , start , end ) ) ; } public reverse ( ) { return List . from ( Iterable . reverse ( this ) ) ; } public join ( separator ) { return Iterable . join ( this , separator ) ; } public sort < T extends Comparable < T > > ( this ) { return this . sortWith ( compareComparable ) ; } public sortWith ( comparer ) { return List . from ( Iterable . sortWith ( this , comparer ) ) ; } public compare < T > ( this , iterable ) { return this . compareWith ( iterable , compareComparable ) ; } public compareWith < U = T > ( iterable , comparer ) { return Iterable . compareWith ( this , iterable , comparer ) ; } public groupBy < K > ( grouper ) { return this . reduce ( ( groups , value ) => { const group = grouper ( value ) ; return groups . set ( group , groups . get ( group ) . getOrElse ( ( ) => List . empty < T > ( ) ) . _push ( value ) ) ; } , Map . empty < K , List < T > > ( ) ) ; } public equals < T > ( value ) ; public equals ( value ) ; public equals ( value ) { return ( value instanceof List && value . _size === this . _size && value . _head . equals ( this . _head ) && value . _tail . equals ( this . _tail ) ) ; } public hash ( hash ) { for ( const value of this ) { hash . writeUnknown ( value ) ; } hash . writeUint32 ( this . _size ) ; } public * [ Symbol . iterator ] ( ) { yield * this . _head ; yield * this . _tail ; } public toArray ( ) { return [ ... this ] ; } public toJSON ( ) { return this . toArray ( ) . map ( ( value ) => Serializable . toJSON ( value ) ) ; } public toString ( ) { const values = this . join ( ", " ) ; return `List [${ values === "" ? "" : ` ${ values } ` }]` ; } private _push ( value ) { if ( this . _tail . isEmpty ( ) ) { return new List ( Empty , Leaf . of ( [ value ] ) , 0 , 1 ) ; } if ( this . _tail . hasCapacity ( ) ) { return new List ( this . _head , Leaf . of ( [ ... this . _tail . values , value ] ) , this . _shift , this . _size + 1 ) ; } if ( this . _head . isEmpty ( ) ) { return new List ( this . _tail , Leaf . of ( [ value ] ) , this . _shift + Node . Bits , this . _size + 1 ) ; } const index = this . _size - Node . Capacity ; let head = this . _head ; let shift = this . _shift ; if ( head . isLeaf ( ) || index === Node . overflow ( shift ) ) { head = Branch . of ( [ head ] ) ; shift += Node . Bits ; } else { head = head . clone ( ) ; } let prev = head ; let level = shift - Node . Bits ; while ( level > 0 ) { const i = Node . fragment ( index , level ) ; level -= Node . Bits ; const next = prev . nodes [ i ] as Branch < T > | undefined ; if ( next === undefined ) { if ( level === 0 ) { prev . nodes [ i ] = this . _tail ; } else { prev . nodes [ i ] = prev = Branch . empty < T > ( ) ; } } else { prev . nodes [ i ] = prev = next . clone ( ) ; } } return new List ( head , Leaf . of ( [ value ] ) , shift , this . _size + 1 ) ; } private _pop ( ) { if ( this . _tail . isEmpty ( ) ) { return this ; } if ( this . _size === 1 ) { return List . empty ( ) ; } if ( this . _tail . values . length > 1 ) { return new List ( this . _head , Leaf . of ( this . _tail . values . slice ( 0 , this . _tail . values . length - 1 ) ) , this . _shift , this . _size - 1 ) ; } if ( this . _head . isLeaf ( ) || this . _head . isEmpty ( ) ) { return new List ( Empty , this . _head , this . _shift - Node . Bits , this . _size - 1 ) ; } let head = this . _head . clone ( ) ; let tail = this . _tail ; let shift = this . _shift ; const index = this . _size - Node . Capacity - 1 ; let prev = head ; let level = shift - Node . Bits ; while ( level > 0 ) { const fragment = Node . fragment ( index , level ) ; level -= Node . Bits ; const next = prev . nodes [ fragment ] ; if ( next . isLeaf ( ) ) { prev . nodes . pop ( ) ; tail = next ; } else { prev = prev . nodes [ fragment ] = next . clone ( ) ; } } if ( index === Node . underflow ( shift ) ) { head = head . nodes [ 0 ] ; shift -= Node . Bits ; } return new List ( head , tail , shift , this . _size - 1 ) ; } } public export namespace List { export type JSON < T > = Collection . Indexed . JSON < T > ; export function isList < T > ( value ) ; export function isList < T > ( value ) ; export function isList < T > ( value ) { return value instanceof List ; } export function from < T > ( iterable ) { if ( isList ( iterable ) ) { return iterable ; } if ( Array . isArray ( iterable ) ) { return fromArray ( iterable ) ; } return fromIterable ( iterable ) ; } export function fromArray < T > ( array ) { const size = array . length ; if ( size <= Node . Capacity ) { return List . of ( ... array ) ; } return Array . reduce ( array , ( list , value ) => list . append ( value ) , List . empty ( ) ) ; } export function fromIterable < T > ( iterable ) { return Iterable . reduce ( iterable , ( list , value ) => list . append ( value ) , List . empty ( ) ) ; } }