import { isIterable , isFunction , isMissing , isInstance } from "@esfx/internal-guards" ; import { Collection , ReadonlyCollection } from "@esfx/collection-core" ; import { Equaler , EqualityComparison } from "@esfx/equatable" ; const kList = Symbol ( "LinkedListNode.list" ) ; const kPrevious = Symbol ( "LinkedListNode.previous" ) ; const kNext = Symbol ( "LinkedListNode.next" ) ; /**
 * A node in a [doubly-linked list](https://en.wikipedia.org/wiki/Doubly_linked_list).
 */ export class LinkedListNode < T > { [ kList ] : LinkedList < T > | undefined = undefined ; [ kPrevious ] : LinkedListNode < T > | undefined = undefined ; [ kNext ] : LinkedListNode < T > | undefined = undefined ; /**
     * The value for the node.
     */ value : T ; constructor ( value ) { this . value = value ; } /**
     * Gets the list associated with this node. If the node is not attached to a  LinkedList , then this returns
     * `undefined`.
      get list ( ) : LinkedList < T > | undefined { return this [ kList ] ; } /**
     * Gets the  LinkedListNode preceding this node in the list. If this is the first node in the list, or the
     * node is not attached to a  LinkedList , then this returns `undefined`.
      get previous ( ) : LinkedListNode < T > | undefined { if ( this [ kPrevious ] && this . list && this !== this . list . first ) { return this [ kPrevious ] ; } return undefined ; } /**
     * Gets the  LinkedListNode following this node in the list. If this is the last node in the list, or the
     * node is not attached to a  LinkedList , then this returns `undefined`.
      get next ( ) : LinkedListNode < T > | undefined { if ( this [ kNext ] && this . list && this [ kNext ] !== this . list . first ) { return this [ kNext ] ; } return undefined ; } returns detachSelf ( ) { return this . list ? this . list . deleteNode ( this ) : false ; } [ Symbol . toStringTag ] ! : string ; } Object . defineProperty ( LinkedListNode . prototype , Symbol . toStringTag , { enumerable : false , configurable : true , writable : true , value : "LinkedListNode" } ) ; const enum Position { before , after } /**
 * A collection representing a [doubly-linked list](https://en.wikipedia.org/wiki/Doubly_linked_list).
 */ export class LinkedList < T > implements Collection < T > { private _size : number = 0 ; private _head : LinkedListNode < T > | undefined = undefined ; private _equaler : Equaler < T > ; constructor ( equaler ? ) ; constructor ( iterable ? , equaler ? ) ; constructor ( ... args ) { let iterable ; let equaler ; if ( args . length > 0 ) { if ( isIterable ( args [ 0 ] ) || isMissing ( args [ 0 ] ) ) { iterable = args [ 0 ] ; if ( args . length > 1 ) equaler = args [ 1 ] ; } else { equaler = args [ 0 ] ; } } if ( isMissing ( equaler ) ) { equaler = Equaler . defaultEqualer ; } this . _equaler = typeof equaler === "function" ? Equaler . create ( equaler ) : equaler ; if ( iterable ) { for ( const value of iterable ) { this . push ( value ) ; } } } /**
     * Gets the  Equaler used for equality comparisons in this list.
      get equaler ( ) : Equaler < T > { return this . _equaler ; } /**
     * Gets the first node in the list. If the list is empty, this returns `undefined`.
     */ get first ( ) : LinkedListNode < T > | undefined { return this . _head ; } /**
     * Gets the last node in the list. If the list is empty, this returns `undefined`.
     */ get last ( ) : LinkedListNode < T > | undefined { if ( this . _head ) { return this . _head [ kPrevious ] ; } return undefined ; } /**
     * Gets the number of elements in the list.
     */ get size ( ) : number { return this . _size ; } [ Symbol . iterator ] ( ) { return this . values ( ) ; } * values ( ) { for ( const node of this . nodes ( ) ) { yield node . value ; } } * nodes ( ) { let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; yield node ; } } /**
     * Returns an iterator that removes each node from the list before yielding the node's value.
     */ * drain ( ) { for ( const node of this . nodes ( ) ) { this . deleteNode ( node ) ; yield node . value ; } } param value param fromNode nodeOf ( value , fromNode ? ) { if ( ! isMissing ( fromNode ) && ! isInstance ( fromNode , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: fromNode" ) ; if ( ! isMissing ( fromNode ) && fromNode . list !== this ) throw new TypeError ( "Wrong list." ) ; for ( let node = fromNode || this . first ; node ; node = node . next ) { if ( this . _equaler . equals ( node . value , value ) ) { return node ; } } return undefined ; } param value param fromNode lastNodeOf ( value , fromNode ? ) { if ( ! isMissing ( fromNode ) && ! isInstance ( fromNode , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: fromNode" ) ; if ( ! isMissing ( fromNode ) && fromNode . list !== this ) throw new TypeError ( "Wrong list." ) ; for ( let node = fromNode || this . last ; node ; node = node . previous ) { if ( this . _equaler . equals ( node . value , value ) ) { return node ; } } return undefined ; } param callback param thisArg find < S extends T > ( callback , thisArg ? ) ; param callback param thisArg find ( callback , thisArg ? ) ; find ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; const value = node . value ; if ( callback . call ( thisArg , value , node , this ) ) return value ; } return undefined ; } param callback param thisArg findLast < S extends T > ( callback , thisArg ? ) ; param callback param thisArg findLast ( callback , thisArg ? ) ; findLast ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let node ; let prev = this . last ; while ( prev !== undefined ) { node = prev ; prev = node . previous ; const value = node . value ; if ( callback . call ( thisArg , value , node , this ) ) return value ; } return undefined ; } /**
     * Finds the first  LinkedListNode in the list that matches the provided callback.
     *  param callback param thisArg findNode < S extends T > ( callback , thisArg ? ) ; /**
     * Finds the first  LinkedListNode in the list that matches the provided callback.
     *  param callback param thisArg findNode ( callback , thisArg ? ) ; findNode ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; if ( callback . call ( thisArg , node . value , node , this ) ) return node ; } return undefined ; } /**
     * Finds the last  LinkedListNode in the list that matches the provided callback, starting from the end of the list.
     *  param callback param thisArg findLastNode < S extends T > ( callback , thisArg ? ) ; /**
     * Finds the last  LinkedListNode in the list that matches the provided callback, starting from the end of the list.
     *  param callback param thisArg findLastNode ( callback , thisArg ? ) ; findLastNode ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let node ; let prev = this . last ; while ( prev !== undefined ) { node = prev ; prev = node . previous ; if ( callback . call ( thisArg , node . value , node , this ) ) return node ; } return undefined ; } /**
     * Returns a value indicating whether `value` exists within the list.
     */ has ( value ) { return this . nodeOf ( value ) !== undefined ; } /**
     * Inserts a new  LinkedListNode containing `value` into the list before the provided `node`.
     * If `node` is either `null` or `undefined`, the new node is inserted at the beginning of the list.
     *  param node param value returns The new  LinkedListNode for `value`.
      insertBefore ( node , value ) { if ( ! isMissing ( node ) && ! isInstance ( node , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: node" ) ; if ( ! isMissing ( node ) && node . list !== this ) throw new Error ( "Wrong list." ) ; return this . _insertNode ( node || undefined , new LinkedListNode ( value ) , Position . before ) ; } param node param newNode insertNodeBefore ( node , newNode ) { if ( ! isMissing ( node ) && ! isInstance ( node , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: node" ) ; if ( ! isInstance ( newNode , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: newNode" ) ; if ( ! isMissing ( node ) && node . list !== this ) throw new Error ( "Wrong list." ) ; if ( ! isMissing ( newNode . list ) ) throw new Error ( "Node is already attached to a list." ) ; this . _insertNode ( node || undefined , newNode , Position . before ) ; } /**
     * Inserts a new  LinkedListNode containing `value` into the list after the provided `node`.
     * If `node` is either `null` or `undefined`, the new node is inserted at the end of the list.
     *  param node param value returns The new  LinkedListNode for `value`.
      insertAfter ( node , value ) { if ( ! isMissing ( node ) && ! isInstance ( node , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: node" ) ; if ( ! isMissing ( node ) && node . list !== this ) throw new Error ( "Wrong list." ) ; return this . _insertNode ( node || undefined , new LinkedListNode ( value ) , Position . after ) ; } param node param newNode insertNodeAfter ( node , newNode ) { if ( ! isMissing ( node ) && ! isInstance ( node , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: node" ) ; if ( ! isInstance ( newNode , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: newNode" ) ; if ( ! isMissing ( node ) && node . list !== this ) throw new Error ( "Wrong list." ) ; if ( ! isMissing ( newNode . list ) ) throw new Error ( "Node is already attached to a list." ) ; this . _insertNode ( node || undefined , newNode , Position . after ) ; } /**
     * Inserts a new  LinkedListNode containing `value` at the end of the list.
     *  param value returns The new  LinkedListNode for `value`.
      push ( value ) { return this . _insertNode ( undefined , new LinkedListNode ( value ) , Position . after ) ; } param newNode pushNode ( newNode ) { if ( ! isInstance ( newNode , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: newNode" ) ; if ( ! isMissing ( newNode . list ) ) throw new Error ( "Node is already attached to a list." ) ; this . _insertNode ( undefined , newNode , Position . after ) ; } /**
     * Removes the last node from the list and returns its value. If the list is empty, `undefined` is returned instead.
     */ pop ( ) { const node = this . popNode ( ) ; return node ? node . value : undefined ; } /**
     * Removes the last node from the list and returns it. If the lsit is empty, `undefined` is returned instead.
     */ popNode ( ) { const node = this . last ; if ( this . deleteNode ( node ) ) { return node ; } } /**
     * Removes the first node from the list and returns its value. If the list is empty, `undefined` is returned instead.
     */ shift ( ) { const node = this . shiftNode ( ) ; return node ? node . value : undefined ; } /**
     * Removes the first node from the list and returns it. If the list is empty, `undefined` is returned instead.
     */ shiftNode ( ) { const node = this . first ; if ( this . deleteNode ( node ) ) { return node ; } } /**
     * Inserts a new  LinkedListNode containing `value` at the beginning of the list.
     *  param value returns The new  LinkedListNode for `value`.
      unshift ( value ) { return this . _insertNode ( undefined , new LinkedListNode ( value ) , Position . before ) ; } param newNode unshiftNode ( newNode ) { if ( ! isInstance ( newNode , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: newNode" ) ; if ( ! isMissing ( newNode . list ) ) throw new Error ( "Node is already attached to a list." ) ; this . _insertNode ( undefined , newNode , Position . before ) ; } /**
     * Finds the first node in the list containing `value`, removes it from the list, and returns it. If a node
     * containing `value` could not be found, `undefined` is returned instead.
     */ delete ( value ) { const node = this . nodeOf ( value ) ; if ( node && this . deleteNode ( node ) ) { return node ; } return undefined ; } returns deleteNode ( node ) { if ( ! isMissing ( node ) && ! isInstance ( node , LinkedListNode ) ) throw new TypeError ( "LinkedListNode expected: node" ) ; if ( ! isMissing ( node ) && ! isMissing ( node . list ) && node . list !== this ) throw new TypeError ( "Wrong list." ) ; if ( isMissing ( node ) || isMissing ( node . list ) ) return false ; return this . _deleteNode ( node ) ; } param predicate param thisArg deleteAll ( predicate , thisArg ? ) { if ( ! isFunction ( predicate ) ) throw new TypeError ( "Function expected: predicate" ) ; let count = 0 ; let node = this . first ; while ( node ) { const next = node . next ; if ( predicate . call ( thisArg , node . value , node , this ) && node . list === this ) { this . _deleteNode ( node ) ; ++ count ; } node = next ; } return count ; } /**
     * Removes all nodes from the list.
     */ clear ( ) { while ( this . size > 0 ) { this . deleteNode ( this . last ) ; } } forEach ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; callback . call ( thisArg , node . value , node , this ) ; } } /**
     * Calls the provided `callback` function on each element of the list, and returns a new  LinkedList that contains the results.
     *  param callback param thisArg map < U > ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; [ ] . map ; const mappedList = new LinkedList < U > ( ) ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; const mappedValue = callback . call ( thisArg , node . value , node , this ) ; mappedList . push ( mappedValue ) ; } return mappedList ; } param callback param thisArg filter < S extends T > ( callback , thisArg ? ) ; param callback param thisArg filter ( callback , thisArg ? ) ; filter ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; const mappedList = new LinkedList < T > ( this . equaler ) ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; const value = node . value ; if ( callback . call ( thisArg , value , node , this ) ) { mappedList . push ( value ) ; } } return mappedList ; } param callback reduce ( callback ) ; param callback param initialValue reduce ( callback , initialValue ) ; param callback param initialValue reduce < U > ( callback , initialValue ) ; reduce ( callback , initialValue ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let hasInitialValue = arguments . length > 1 ; let result = initialValue ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; const value = node . value ; if ( ! hasInitialValue ) { result = value ; hasInitialValue = true ; } else { result = callback ( result ! , value , node , this ) ; } } return result ; } param callback reduceRight ( callback ) ; param callback param initialValue reduceRight ( callback , initialValue ) ; param callback param initialValue reduceRight < U > ( callback , initialValue ) ; reduceRight ( callback , initialValue ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let hasInitialValue = arguments . length > 1 ; let result = initialValue ; let node ; let prev = this . last ; while ( prev !== undefined ) { node = prev ; const value = node . value ; if ( ! hasInitialValue ) { result = value ; hasInitialValue = true ; } else { result = callback ( result ! , value , node , this ) ; } prev = node . previous ; } return result ; } some ( callback ? , thisArg ? ) { if ( ! isMissing ( callback ) && ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; if ( ! callback || callback . call ( thisArg , node . value , node , this ) ) return true ; } return false ; } every ( callback , thisArg ? ) { if ( ! isFunction ( callback ) ) throw new TypeError ( "Function expected: callback" ) ; let hasMatch = false ; let node ; let next = this . first ; while ( next !== undefined ) { node = next ; next = node . next ; if ( ! callback . call ( thisArg , node . value , node , this ) ) return false ; hasMatch = true ; } return hasMatch ; } private _deleteNode ( node ) { if ( node [ kNext ] === node ) { this . _head = undefined ; } else { node [ kNext ] ! [ kPrevious ] = node [ kPrevious ] ; node [ kPrevious ] ! [ kNext ] = node [ kNext ] ; if ( this . _head === node ) { this . _head = node [ kNext ] ; } } node [ kList ] = undefined ; node [ kNext ] = undefined ; node [ kPrevious ] = undefined ; this . _size -- ; return true ; } private _insertNode ( adjacentNode , newNode , position ) { newNode [ kList ] = this ; if ( this . _head === undefined ) { newNode [ kNext ] = newNode ; newNode [ kPrevious ] = newNode ; this . _head = newNode ; } else { switch ( position ) { case Position . before : if ( adjacentNode === undefined ) { adjacentNode = this . _head ; this . _head = newNode ; } else if ( adjacentNode === this . _head ) { this . _head = newNode ; } newNode [ kNext ] = adjacentNode ; newNode [ kPrevious ] = adjacentNode [ kPrevious ] ; adjacentNode [ kPrevious ] ! [ kNext ] = newNode ; adjacentNode [ kPrevious ] = newNode ; break ; case Position . after : if ( adjacentNode === undefined ) { adjacentNode = this . _head [ kPrevious ] ! ; } newNode [ kPrevious ] = adjacentNode ; newNode [ kNext ] = adjacentNode [ kNext ] ; adjacentNode [ kNext ] ! [ kPrevious ] = newNode ; adjacentNode [ kNext ] = newNode ; break ; } } this . _size ++ ; return newNode ; } [ Symbol . toStringTag ] ! : string ; get [ ReadonlyCollection . size ] ( ) { return this . size ; } [ ReadonlyCollection . has ] ( value ) { return this . has ( value ) ; } [ Collection . add ] ( value ) { this . push ( value ) ; } [ Collection . delete ] ( value ) { return ! ! this . delete ( value ) ; } [ Collection . clear ] ( ) { this . clear ( ) ; } } Object . defineProperty ( LinkedList . prototype , Symbol . toStringTag , { enumerable : false , configurable : true , writable : true , value : "LinkedList" } ) ;