import { arrayStream } from "polar-shared/src/util/ArrayStreams" ; import { Tuples } from "polar-shared/src/util/Tuples" ; /**
 * Positional Arrays are based on LSeq:
 *
 * LSEQ: an Adaptive Structure for Sequences in DistributedCollaborative Editing
 *
 * The general idea here is that we can implement distributed arrays as CRDT-like stuctures
 * where the keys are the position in a map and the 'array' order is determined by the key.
 *
 * This is a ROUGH approximation of the LSEQ idea but designed for rapid
 * iteration and fewer total keys.
 *
 * https://bartoszsypytkowski.com/operation-based-crdts-arrays-1/
 * https://www.researchgate.net/publication/262162421_LSEQ_an_Adaptive_Structure_for_Sequences_in_Distributed_Collaborative_Editing
 *
 *
 */ export namespace PositionalArrays { /**
     * A number encoded as an string that can be used to place something into a
     * positional array.
     */ export type PositionalArrayPositionStr = string ; export type PositionalArray < T > = { [ position ] : T ; } ; export interface IPositionalArrayPosition < T > { readonly pos : number ; readonly value : T ; } /**
     * An entry in the dictionary.
     */ type PositionalArrayEntry < T > = [ string , T ] ; export function create < T > ( values ? ) { const result = { } ; if ( values !== undefined ) { for ( const value of values ) { append ( result , value ) ; } } return result ; } export function entries < T > ( positionalArray ) { return Object . entries ( positionalArray ) ; } export function compare < T > ( a , b ) { return parseFloat ( a [ 0 ] ) - parseFloat ( b [ 0 ] ) ; } export function insert < T > ( positionalArray , ref , value , pos ) { const sorted = arrayStream ( entries ( positionalArray ) ) . sort ( ( a , b ) => compare ( a , b ) ) . collect ( ) ; const pointers = arrayStream ( Tuples . createSiblings ( sorted ) ) . sort ( ( a , b ) => compare ( a . curr , b . curr ) ) . collect ( ) ; const ptr = arrayStream ( pointers ) . filter ( current => current . curr [ 1 ] === ref ) . first ( ) ; if ( ptr ) { const computeKey = ( ) => { const base = parseFloat ( ptr . curr [ 0 ] ) ; const computeDelta = ( ) => { const computeDeltaFromSibling = ( entry ) => { if ( entry !== undefined ) { return Math . abs ( parseFloat ( entry [ 0 ] ) - base ) / 2 ; } else { return 1.0 ; } } ; switch ( pos ) { case "before" : return computeDeltaFromSibling ( ptr . prev ) * - 1 ; case "after" : return computeDeltaFromSibling ( ptr . next ) ; } } ; const delta = computeDelta ( ) ; const idx = base + delta ; return `${ idx }` ; } ; const key = computeKey ( ) ; positionalArray [ key ] = value ; return positionalArray ; } else { throw new Error ( `Unable to find reference to ${ ref } in: ` + JSON . stringify ( positionalArray ) ) ; } } /**
     * Put a value into the positional array with the exact key position.
     */ export function put < T > ( positionalArray , key , value ) { positionalArray [ key ] = value ; return positionalArray ; } export function unshift < T > ( positionalArray , value ) { const min = arrayStream ( Object . keys ( positionalArray ) ) . map ( parseFloat ) . sort ( ( a , b ) => a - b ) . first ( ) || 0.0 ; const idx = min - 1.0 ; const key = `${ idx }` ; positionalArray [ key ] = value ; return positionalArray ; } export function append < T > ( positionalArray , value ) { const max = arrayStream ( Object . keys ( positionalArray ) ) . map ( parseFloat ) . sort ( ( a , b ) => a - b ) . last ( ) || 0.0 ; const idx = max + 1.0 ; const key = `${ idx }` ; positionalArray [ key ] = value ; return positionalArray ; } export function remove < T > ( positionalArray , value ) { const key = arrayStream ( Object . entries ( positionalArray ) ) . filter ( current => current [ 1 ] === value ) . map ( current => current [ 0 ] ) . first ( ) ; if ( key !== undefined ) { delete positionalArray [ key ] ; return positionalArray ; } return positionalArray ; } export function clear < T > ( positionalArray ) { for ( const key of Object . keys ( positionalArray ) ) { delete positionalArray [ key ] ; } } /**
     * Set will take new items, and give them keys that will be unique, then
     * remove the old keys.  This way the set has new values and it's safe from
     * the existing data and can't conflict with anyone.
     */ export function set < T > ( positionalArray , values ) { const convertToArray = ( ) : ReadonlyArray < T > => { if ( Array . isArray ( values ) ) { return values ; } if ( typeof values === 'object' ) { return toArray ( values as any ) ; } throw new Error ( "Unknown values" ) ; } ; const converted = convertToArray ( ) ; const existing = Object . keys ( positionalArray ) ; for ( const value of converted ) { append ( positionalArray , value ) ; } for ( const key of existing ) { delete positionalArray [ key ] ; } return positionalArray ; } export function keyForValue < T > ( positionalArray , value ) { return arrayStream ( Object . entries ( positionalArray ) ) . filter ( current => current [ 1 ] === value ) . map ( current => current [ 0 ] ) . first ( ) ; } /**
     * This is needed by the UI so that we can sort base on position.
     */ export function toArray < T > ( positionalArray ) { const toPosition = ( entry ) : IPositionalArrayPosition < T > => { return { pos : parseFloat ( entry [ 0 ] ) , value : entry [ 1 ] } ; } ; return Object . entries ( positionalArray ) . map ( toPosition ) . sort ( ( a , b ) => a . pos - b . pos ) . map ( current => current . value ) ; } }