import { Atom } from './Atom' ; import { AtomList } from './AtomList' ; import { Ident } from '../idents' ; /**
 * An implementation of AtomList<T> that uses a binary insertion sort over
 * an array to track a sorted list of atoms.
 */ export class ArrayAtomList < T > implements AtomList < T > { private atoms : Atom < T > [ ] ; /**
     * Creates an instange of ArrayAtomList<T>.
     */ constructor ( ) { this . atoms = [ ] ; } inheritdoc size ( ) { return this . atoms . length ; } inheritdoc get ( pos ) { return this . atoms [ pos ] ; } inheritdoc add ( id , value ) { let pos = this . bisectRight ( id ) ; let existing = this . get ( pos - 1 ) ; if ( existing && id . compare ( existing . id ) == 0 ) { return - 1 ; } let atom = Atom < T > ( id , value ) ; this . atoms . splice ( pos , 0 , atom ) ; return pos ; } inheritdoc remove ( id ) { let pos = this . indexOf ( id ) ; if ( pos >= 0 ) { this . atoms . splice ( pos , 1 ) ; return pos ; } return - 1 ; } inheritdoc indexOf ( id ) { let pos = this . bisectLeft ( id ) ; if ( pos !== this . atoms . length && this . atoms [ pos ] . id . compare ( id ) == 0 ) { return pos ; } else { return - 1 ; } } inheritdoc forEach ( func ) { this . atoms . forEach ( func ) ; } inheritdoc map < R > ( func ) { return this . atoms . map ( func ) ; } inheritdoc toArray ( ) { return this . atoms . slice ( 0 ) ; } param id returns private bisectLeft ( id ) { let min = 0 ; let max = this . atoms . length ; while ( min < max ) { let curr = Math . floor ( ( min + max ) / 2 ) ; if ( this . atoms [ curr ] . id . compare ( id ) < 0 ) { min = curr + 1 ; } else { max = curr ; } } return min ; } param id returns private bisectRight ( id ) { let min = 0 ; let max = this . atoms . length ; while ( min < max ) { let curr = Math . floor ( ( min + max ) / 2 ) ; if ( id . compare ( this . atoms [ curr ] . id ) < 0 ) { max = curr ; } else { min = curr + 1 ; } } return min ; } }