import { each , IIterable , IIterator , IRetroable , IterableOrArrayLike } from '@lumino/algorithm' ; /**
 * A generic doubly-linked list.
 */ export class LinkedList < T > implements IIterable < T > , IRetroable < T > { /**
     * Whether the list is empty.
     *
     * #### Complexity
     * Constant.
     */ get isEmpty ( ) : boolean { return this . _size === 0 ; } /**
     * The size of the list.
     *
     * #### Complexity
     * `O(1)`
     *
     * #### Notes
     * This is equivalent to `length`.
     */ get size ( ) : number { return this . _size ; } /**
     * The length of the list.
     *
     * #### Complexity
     * Constant.
     *
     * #### Notes
     * This is equivalent to `size`.
     *
     * This property is deprecated.
     */ get length ( ) : number { return this . _size ; } /**
     * The first value in the list.
     *
     * This is `undefined` if the list is empty.
     *
     * #### Complexity
     * Constant.
     */ get first ( ) : T | undefined { return this . _first ? this . _first . value : undefined ; } /**
     * The last value in the list.
     *
     * This is `undefined` if the list is empty.
     *
     * #### Complexity
     * Constant.
     */ get last ( ) : T | undefined { return this . _last ? this . _last . value : undefined ; } /**
     * The first node in the list.
     *
     * This is `null` if the list is empty.
     *
     * #### Complexity
     * Constant.
     */ get firstNode ( ) : LinkedList . INode < T > | null { return this . _first ; } /**
     * The last node in the list.
     *
     * This is `null` if the list is empty.
     *
     * #### Complexity
     * Constant.
     */ get lastNode ( ) : LinkedList . INode < T > | null { return this . _last ; } returns iter ( ) { return new LinkedList . ForwardValueIterator < T > ( this . _first ) ; } returns retro ( ) { return new LinkedList . RetroValueIterator < T > ( this . _last ) ; } returns nodes ( ) { return new LinkedList . ForwardNodeIterator < T > ( this . _first ) ; } returns retroNodes ( ) { return new LinkedList . RetroNodeIterator < T > ( this . _last ) ; } param values assign ( values ) { this . clear ( ) ; each ( values , value => { this . addLast ( value ) ; } ) ; } param value push ( value ) { this . addLast ( value ) ; } returns pop ( ) { return this . removeLast ( ) ; } param value shift ( value ) { this . addFirst ( value ) ; } returns unshift ( ) { return this . removeFirst ( ) ; } param value returns addFirst ( value ) { let node = new Private . LinkedListNode < T > ( this , value ) ; if ( ! this . _first ) { this . _first = node ; this . _last = node ; } else { node . next = this . _first ; this . _first . prev = node ; this . _first = node ; } this . _size ++ ; return node ; } param value returns addLast ( value ) { let node = new Private . LinkedListNode < T > ( this , value ) ; if ( ! this . _last ) { this . _first = node ; this . _last = node ; } else { node . prev = this . _last ; this . _last . next = node ; this . _last = node ; } this . _size ++ ; return node ; } param value param ref returns insertBefore ( value , ref ) { if ( ! ref || ref === this . _first ) { return this . addFirst ( value ) ; } if ( ! ( ref instanceof Private . LinkedListNode ) || ref . list !== this ) { throw new Error ( 'Reference node is not owned by the list.' ) ; } let node = new Private . LinkedListNode < T > ( this , value ) ; let _ref = ref as Private . LinkedListNode < T > ; let prev = _ref . prev ! ; node . next = _ref ; node . prev = prev ; _ref . prev = node ; prev . next = node ; this . _size ++ ; return node ; } param value param ref returns insertAfter ( value , ref ) { if ( ! ref || ref === this . _last ) { return this . addLast ( value ) ; } if ( ! ( ref instanceof Private . LinkedListNode ) || ref . list !== this ) { throw new Error ( 'Reference node is not owned by the list.' ) ; } let node = new Private . LinkedListNode < T > ( this , value ) ; let _ref = ref as Private . LinkedListNode < T > ; let next = _ref . next ! ; node . next = next ; node . prev = _ref ; _ref . next = node ; next . prev = node ; this . _size ++ ; return node ; } returns removeFirst ( ) { let node = this . _first ; if ( ! node ) { return undefined ; } if ( node === this . _last ) { this . _first = null ; this . _last = null ; } else { this . _first = node . next ; this . _first ! . prev = null ; } node . list = null ; node . next = null ; node . prev = null ; this . _size -- ; return node . value ; } returns removeLast ( ) { let node = this . _last ; if ( ! node ) { return undefined ; } if ( node === this . _first ) { this . _first = null ; this . _last = null ; } else { this . _last = node . prev ; this . _last ! . next = null ; } node . list = null ; node . next = null ; node . prev = null ; this . _size -- ; return node . value ; } param node removeNode ( node ) { if ( ! ( node instanceof Private . LinkedListNode ) || node . list !== this ) { throw new Error ( 'Node is not owned by the list.' ) ; } let _node = node as Private . LinkedListNode < T > ; if ( _node === this . _first && _node === this . _last ) { this . _first = null ; this . _last = null ; } else if ( _node === this . _first ) { this . _first = _node . next ; this . _first ! . prev = null ; } else if ( _node === this . _last ) { this . _last = _node . prev ; this . _last ! . next = null ; } else { _node . next ! . prev = _node . prev ; _node . prev ! . next = _node . next ; } _node . list = null ; _node . next = null ; _node . prev = null ; this . _size -- ; } /**
     * Remove all values from the list.
     *
     * #### Complexity
     * Linear.
     */ clear ( ) { let node = this . _first ; while ( node ) { let next = node . next ; node . list = null ; node . prev = null ; node . next = null ; node = next ; } this . _first = null ; this . _last = null ; this . _size = 0 ; } private _first : Private . LinkedListNode < T > | null = null ; private _last : Private . LinkedListNode < T > | null = null ; private _size = 0 ; } /**
 * The namespace for the `LinkedList` class statics.
 */ export namespace LinkedList { /**
     * An object which represents a node in a linked list.
     *
     * #### Notes
     * User code will not create linked list nodes directly. Nodes
     * are created automatically when values are added to a list.
     */ export interface INode < T > { /**
         * The linked list which created and owns the node.
         *
         * This will be `null` when the node is removed from the list.
         */ readonly list : LinkedList < T > | null ; /**
         * The next node in the list.
         *
         * This will be `null` when the node is the last node in the list
         * or when the node is removed from the list.
         */ readonly next : INode < T > | null ; /**
         * The previous node in the list.
         *
         * This will be `null` when the node is the first node in the list
         * or when the node is removed from the list.
         */ readonly prev : INode < T > | null ; /**
         * The user value stored in the node.
         */ readonly value : T ; } param values returns export function from < T > ( values ) { let list = new LinkedList < T > ( ) ; list . assign ( values ) ; return list ; } /**
     * A forward iterator for values in a linked list.
     */ export class ForwardValueIterator < T > implements IIterator < T > { param node constructor ( node ) { this . _node = node ; } returns iter ( ) { return this ; } returns clone ( ) { return new ForwardValueIterator < T > ( this . _node ) ; } returns next ( ) { if ( ! this . _node ) { return undefined ; } let node = this . _node ; this . _node = node . next ; return node . value ; } private _node : INode < T > | null ; } /**
     * A reverse iterator for values in a linked list.
     */ export class RetroValueIterator < T > implements IIterator < T > { param node constructor ( node ) { this . _node = node ; } returns iter ( ) { return this ; } returns clone ( ) { return new RetroValueIterator < T > ( this . _node ) ; } returns next ( ) { if ( ! this . _node ) { return undefined ; } let node = this . _node ; this . _node = node . prev ; return node . value ; } private _node : INode < T > | null ; } /**
     * A forward iterator for nodes in a linked list.
     */ export class ForwardNodeIterator < T > implements IIterator < INode < T > > { param node constructor ( node ) { this . _node = node ; } returns iter ( ) { return this ; } returns clone ( ) { return new ForwardNodeIterator < T > ( this . _node ) ; } returns next ( ) { if ( ! this . _node ) { return undefined ; } let node = this . _node ; this . _node = node . next ; return node ; } private _node : INode < T > | null ; } /**
     * A reverse iterator for nodes in a linked list.
     */ export class RetroNodeIterator < T > implements IIterator < INode < T > > { param node constructor ( node ) { this . _node = node ; } returns iter ( ) { return this ; } returns clone ( ) { return new RetroNodeIterator < T > ( this . _node ) ; } returns next ( ) { if ( ! this . _node ) { return undefined ; } let node = this . _node ; this . _node = node . prev ; return node ; } private _node : INode < T > | null ; } } /**
 * The namespace for the module implementation details.
 */ namespace Private { /**
     * The internal linked list node implementation.
     */ export class LinkedListNode < T > { /**
         * The linked list which created and owns the node.
         */ list : LinkedList < T > | null = null ; /**
         * The next node in the list.
         */ next : LinkedListNode < T > | null = null ; /**
         * The previous node in the list.
         */ prev : LinkedListNode < T > | null = null ; /**
         * The user value stored in the node.
         */ readonly value : T ; param list param value constructor ( list , value ) { this . list = list ; this . value = value ; } } }