Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/bucket/delta.ts169
-rw-r--r--test/bucket/delta.ts99
2 files changed, 268 insertions, 0 deletions
diff --git a/src/bucket/delta.ts b/src/bucket/delta.ts
new file mode 100644
index 0000000..429873d
--- /dev/null
+++ b/src/bucket/delta.ts
@@ -0,0 +1,169 @@
+/**
+ * A delta
+ *
+ * Copyright (C) 2010-2019 R-T Specialty, LLC.
+ *
+ * This file is part of the Liza Data Collection Framework.
+ *
+ * liza is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** The data structure expected for a document's internal key/value store */
+export type Kv<T = any> = Record<string, T[]>;
+
+/** Possible delta values for Kv array indexes */
+export type DeltaDatum<T> = T | null | undefined;
+
+
+/**
+ * The constructor type for a delta generating function
+ *
+ * @param src - the source data set
+ * @param dest - the destination data set
+ *
+ * @return the delta which transforms src to dest
+ */
+export type DeltaConstructor<T = any, U extends Kv<T> = Kv<T>, V extends Kv<T> = U> = (
+ src: U,
+ dest: V,
+) => DeltaResult<U & V>;
+
+
+/** Transform type T to hold possible delta values */
+export type DeltaResult<T> = { [K in keyof T]: DeltaDatum<T[K]> | null };
+
+
+ /**
+ * Create delta to transform from src into dest
+ *
+ * @param src - the source data set
+ * @param dest - the destination data set
+ *
+ * @return the delta
+ */
+export function createDelta<T, U extends Kv<T>, V extends Kv<T>>(
+ src: U,
+ dest: V,
+): DeltaResult<U & V>
+{
+ const delta: DeltaResult<any> = {};
+
+ // Loop through all keys
+ const key_set = new Set(
+ Object.keys( src ).concat( Object.keys( dest ) ) );
+
+ key_set.forEach( key =>
+ {
+ const src_data = src[ key ];
+ const dest_data = dest[ key ];
+
+ // If source does not contain the key, use entire dest data
+ if ( !src_data || !src_data.length )
+ {
+ delta[ key ] = dest_data;
+
+ return;
+ }
+
+ // If the key no longer exists in dest then nullify this key
+ if ( !dest_data || !dest_data.length )
+ {
+ delta[ key ] = null;
+
+ return;
+ }
+
+ // If neither condition above is true then create the key iteratively
+ const delta_key = _createDeltaKey( src_data, dest_data );
+
+ if ( delta_key.changed )
+ {
+ delta[ key ] = delta_key.data;
+ }
+ } );
+
+ return <DeltaResult<U & V>>delta;
+}
+
+
+/**
+ * Build the delta key iteratively
+ *
+ * @param src - the source data array
+ * @param dest - the destination data array
+ *
+ * @return an object with an identical flag and a data array
+ */
+function _createDeltaKey<T>(
+ src: T[],
+ dest: T[],
+): { changed: boolean, data: DeltaDatum<T>[] }
+{
+ const data = [];
+ const max_size = Math.max( dest.length, src.length );
+
+ let changed: boolean = false;
+
+ for ( let i = 0; i < max_size; i++ )
+ {
+ const dest_datum = dest[ i ];
+ const src_datum = src[ i ];
+
+ // terminate the key if we don't have a dest value
+ if ( dest_datum === undefined )
+ {
+ changed = true;
+ data[ i ] = null;
+
+ break;
+ }
+ else if ( _deepEqual( dest_datum, src_datum ) )
+ {
+ data[ i ] = undefined;
+ }
+ else
+ {
+ changed = true;
+ data[ i ] = dest_datum;
+ }
+ }
+
+ return {
+ changed: changed,
+ data: data,
+ };
+}
+
+
+/**
+ * Compare two arrays by index
+ *
+ * @param a - the first array to compare
+ * @param b - the second array to compare
+ */
+function _deepEqual( a: any, b: any ): boolean
+{
+ if ( Array.isArray( a ) )
+ {
+ if ( !Array.isArray( b ) || ( a.length !== b.length ) )
+ {
+ return false;
+ }
+
+ return a.map( ( item, i ) => _deepEqual( item, b[ i ] ) )
+ .every( res => res === true );
+ }
+
+ return ''+a === ''+b;
+}
diff --git a/test/bucket/delta.ts b/test/bucket/delta.ts
new file mode 100644
index 0000000..ba1d192
--- /dev/null
+++ b/test/bucket/delta.ts
@@ -0,0 +1,99 @@
+/**
+ * Test the delta generated from two key/value stores
+ *
+ * Copyright (C) 2010-2019 R-T Specialty, LLC.
+ *
+ * This file is part of liza.
+ *
+ * liza is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+import { createDelta as sut, Kv , DeltaResult} from "../../src/bucket/delta";
+
+import { expect, use as chai_use } from 'chai';
+chai_use( require( 'chai-as-promised' ) );
+
+interface SutTestCase<T>
+{
+ label: string;
+ src_data: T;
+ dest_data: T;
+ expected: DeltaResult<T>;
+}
+
+describe( 'Delta', () =>
+{
+ ( <SutTestCase<Kv<string>>[]>[
+ {
+ label: "No changes are made, key is dropped",
+ src_data: { foo: [ 'bar', 'baz' ] },
+ dest_data: { foo: [ 'bar', 'baz' ] },
+ expected: {},
+ },
+ {
+ label: "Only the unchanged key is dropped",
+ src_data: { foo: [ 'bar', 'baz' ], bar: [ 'qwe' ] },
+ dest_data: { foo: [ 'bar', 'baz' ], bar: [ 'asd' ] },
+ expected: { bar: [ 'asd' ] },
+ },
+ {
+ label: "Changed values are updated by index with old value",
+ src_data: { foo: [ "bar", "baz", "quux" ] },
+ dest_data: { foo: [ "bar", "quuux" ], moo: [ "cow" ] },
+ expected: { foo: [ undefined, "quuux", null ], moo: [ "cow" ] },
+ },
+ {
+ label: "The keys are null when they don't exist in first set",
+ src_data: {},
+ dest_data: { foo: [ "bar", "quuux" ], moo: [ "cow" ] },
+ expected: { foo: [ "bar", "quuux" ], moo: [ "cow" ] },
+ },
+ {
+ label: "Removed keys in new set show up",
+ src_data: { foo: [ "bar" ] },
+ dest_data: {},
+ expected: { foo: null },
+ },
+ {
+ label: "Indexes after a null terminator aren't included",
+ src_data: { foo: [ "one", "two", "three", "four" ] },
+ dest_data: { foo: [ "one", "done" ] },
+ expected: { foo: [ undefined, "done", null ] },
+ },
+ {
+ label: "Consider nested arrays to be scalar values",
+ src_data: { foo: [ [ "one" ], [ "two", "three" ] ] },
+ dest_data: { foo: [ [ "one" ], [ "two" ] ] },
+ expected: { foo: [ undefined, [ "two" ] ] },
+ },
+ {
+ label: "Don't evaluate zeros as falsy",
+ src_data: { foo: [ 0 ] },
+ dest_data: { foo: [ 0 ] },
+ expected: {},
+ },
+ {
+ label: "Don't evaluate empty strings as falsy",
+ src_data: { foo: [ '' ] },
+ dest_data: { foo: [ '' ] },
+ expected: {},
+ },
+ ] ).forEach( ( { label, src_data, dest_data, expected } ) =>
+ {
+ it( label, () =>
+ {
+ expect( sut( src_data, dest_data ) ).to.deep.equal( expected );
+ } );
+ } );
+} );