@casret/dedupe - npm Package Compare versions

Comparing version 0.0.3 to 0.1.0

index.js

@@ -1,4 +0,6 @@
-const SortedItems = Symbol("SortedItems")
-const SortedKeys = Symbol("SortedKeys")
-const Unsorted = Symbol("Unsorted")
+const Strategies = {
+  SortedItems: Symbol("SortedItems"),
+  SortedKeys: Symbol("SortedKeys"),
+  Unsorted: Symbol("Unsorted"),
+}
 
@@ -12,3 +14,18 @@ class DedupeError extends Error {
 
-function dedupe(strategy, items, key_cache, key_mapper = item => item.id) {
+function dedupe(items, opts) {
+  const strategy = opts.strategy || Strategies.SortedItems
+  if (strategy !== Strategies.SortedItems &&
+    strategy !== Strategies.SortedKeys &&
+    strategy !== Strategies.Unsorted)
+    throw new DedupeError("Unknown strategy passed")
+
+  const key_mapper = opts.key_mapper || (item => item.id)
+  let key_cache
+  if (opts.auto_checkpoint) {
+    key_cache = opts.auto_checkpoint.$checkpoint
+  }
+
+  // Allow overriding the auto_checkpoint if you want
+  key_cache = opts.key_cache || key_cache
+
   const isArray = Array.isArray(items)
@@ -41,3 +58,3 @@ if (!isArray) {
     key_cache = current_keys
-  } else if (strategy == SortedKeys) {
+  } else if (strategy == Strategies.SortedKeys) {
     key_cache = key_cache.concat(current_keys)
@@ -47,3 +64,3 @@ items = items.filter(
     )
-  } else if (strategy == SortedItems) {
+  } else if (strategy == Strategies.SortedItems) {
     const index = current_keys.findIndex(key => key == key_cache[0])
@@ -68,3 +85,9 @@ if (index > -1) items = items.slice(0, index)
 
-    // TODO: heuristic on add order
+    // If current_keys[0] was already in the key_cache, it's more likely
+    // that the array is sorted from oldest to youngest, so we'll reverse the order
+    // of how we insert them
+    if(undropped_keys.length > 0 && undropped_keys[0] != current_keys[0]) {
+      undropped_keys.reverse()
+    }
+
     key_cache = undropped_keys.concat(key_cache)
@@ -77,3 +100,3 @@ }
     switch (strategy) {
-      case SortedKeys:
+      case Strategies.SortedKeys:
         key_cache = [
@@ -86,6 +109,6 @@ key_cache.reduce(
         break
-      case SortedItems:
+      case Strategies.SortedItems:
         key_cache = key_cache.slice(0, 1)
         break
-      case Unsorted:
+      case Strategies.Unsorted:
         key_cache = key_cache.slice(0, 1000)
@@ -101,2 +124,6 @@ break
 
+  if (opts.auto_checkpoint) {
+    opts.auto_checkpoint.$checkpoint = key_cache
+  }
+
   return {items, key_cache}
@@ -106,3 +133,3 @@ }
 module.exports = {
-  SortedItems, SortedKeys, Unsorted, dedupe
+  dedupe, Strategies
 }

index.test.js

@@ -1,6 +0,6 @@
-const {SortedItems, SortedKeys, Unsorted, dedupe} = require("./index")
+const {Strategies, dedupe} = require("./index")
 
 describe("SortedItems strategy", () => {
   test("should drop any key to the right of the pivot and update key_cache", () => {
-    const { items, key_cache } = dedupe(SortedItems, [{id: "a"}, {id: "b"}, {id:"c"}], ["b"])
+    const { items, key_cache } = dedupe([{id: "a"}, {id: "b"}, {id:"c"}], { strategy: Strategies.SortedItems, key_cache: ["b"]})
     expect(items).toEqual([{id: "a"}])
@@ -11,3 +11,3 @@ expect(key_cache).toEqual(["a"])
   test("should drop all keys if pivot is the key_cache", () => {
-    const { items, key_cache } = dedupe(SortedItems, [{id: "a"}, {id: "b"}, {id:"c"}], ["a"])
+    const { items, key_cache } = dedupe([{id: "a"}, {id: "b"}, {id:"c"}], { strategy: Strategies.SortedItems, key_cache: ["a"]})
     expect(items).toEqual([])
@@ -17,3 +17,3 @@ expect(key_cache).toEqual(["a"])
   test("should keep all keys and update key_cache if pivot doesn't match", () => {
-    const { items, key_cache } = dedupe(SortedItems, [{id: "a"}, {id: "b"}, {id:"c"}], ["d"])
+    const { items, key_cache } = dedupe([{id: "a"}, {id: "b"}, {id:"c"}], { strategy: Strategies.SortedItems, key_cache: ["d"]})
     expect(items).toEqual([{id: "a"}, {id: "b"}, {id: "c"}])
@@ -26,3 +26,3 @@ expect(key_cache).toEqual(["a"])
   test("should drop any key less then pivot", () => {
-    const { items, key_cache } = dedupe(SortedKeys, [{id: "a"}, {id: "b"}, {id:"c"}], ["b"])
+    const { items, key_cache } = dedupe([{id: "a"}, {id: "b"}, {id:"c"}], {strategy: Strategies.SortedKeys, key_cache: ["b"]})
     expect(items).toEqual([{id: "c"}])
@@ -35,6 +35,34 @@ expect(key_cache).toEqual(["c"])
   test("should drop any key it has seen before", () => {
-    const { items, key_cache } = dedupe(Unsorted, [{id: "a"}, {id: "b"}, {id:"c"}], ["b"])
+    const { items, key_cache } = dedupe([{id: "a"}, {id: "b"}, {id:"c"}], {strategy: Strategies.Unsorted, key_cache: ["b"]})
     expect(items).toEqual([{id: "a"}, {id: "c"}])
     expect(key_cache).toEqual(["a","c", "b"])
   })
+  test("should reverse the key cache insertion order if it notices that it drops items from the left", () => {
+    const { items, key_cache } = dedupe([{id: "a"}, {id: "b"}, {id:"c"}], {strategy: Strategies.Unsorted, key_cache: ["a"]})
+    expect(items).toEqual([{id: "b"}, {id: "c"}])
+    expect(key_cache).toEqual(["c", "b", "a"])
+  })
 })
+
+describe("When using auto_checkpoint", () => {
+  test("should use $checkpoint as the key_cache", () => {
+    const checkpointer = { $checkpoint: ["b"] }
+    const { items, key_cache } = dedupe([{id: "a"}, {id: "b"}, {id:"c"}], {auto_checkpoint: checkpointer})
+    expect(items).toEqual([{id: "a"}])
+    expect(key_cache).toEqual(["a"])
+  })
+
+  test("should update $checkpoint", () => {
+    const checkpointer = { $checkpoint: ["b"] }
+    dedupe([{id: "a"}, {id: "b"}, {id:"c"}], {auto_checkpoint: checkpointer})
+    expect(checkpointer.$checkpoint).toEqual(["a"])
+  })
+})
+
+describe("When passing in your own key mapper", () => {
+  test("should use it", () => {
+    const { items, key_cache } = dedupe([{id: "a", sec: 3}, {id: "b", sec:2}, {id:"c", sec:1}], {strategy: Strategies.SortedKeys, key_cache: [2], key_mapper: item => item.sec})
+    expect(items).toEqual([{id: "a", sec:3}])
+    expect(key_cache).toEqual([3])
+  })
+})

package.json

 {
   "name": "@casret/dedupe",
-  "version": "0.0.3",
+  "version": "0.1.0",
   "description": "Dedupe utilities for pipedream",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

 # dedupe
 Dedupe utility functions for pipedream
+
+## Usage
+```
+const {dedupe, Strategies} = require ("@casret/dedupe")
+
+return dudupe(steps.foo.$return_value, {auto_checkpoint: this}).items
+```
+
+## API
+
+### dedupe(items, opts)
+
+Returns an object with `items' and `key_cache' fields, which are the deduped items
+and updated key_cache based on a strategy and key_cache that are passed in.
+
+#### items
+
+Type: Array | object
+
+The array or item you want to check against the key_cache.  If array is passed in, and array (
+possibly empty or singular) will be returned, if an object is passed in, that object or null
+will be passed back (under the `items`).
+
+#### opts
+
+Type: object
+
+Options to configure the dedupe action
+
+##### strategy
+
+Type: symbol
+
+One of the symbols from the Strategies object
+
+- `Strategies.SortedItems` - the default strategy, this assumes that items passed in are already sorted from most recent to oldest.  The key_cache will store the most recent key, and filter that item and any following.  This is storage efficient as long as the source of data that is sorted and does not delete any data.
+- `Strategies.SortedKeys` - This strategy assumes will filter any items that are less or equal to the key_cache and update the key_cache.  The items do not have to be sorted. This is a great strategy when you have a monotonicly increasing key (e.g. high resolution timestamp, or database id).
+- `Strategies.Unsorted` - This strategy will cache and filter out the last 1000 keys it has seen.  While this works for data without much structure, obvivously has drawbacks if you need deal with large or high volume datasets.
+
+##### key_mapper
+
+Type: function
+
+This function maps the items to a key that uniquely identifies the item.  It defaults to `(item) => item.id`.  A key should be a number or a string of length of 64 or less.
+
+##### key_cache
+
+Type: Array
+
+Specifies the key_cache from the previous run.  If it's `undefined`, then all items are filtered and cached in accordance to the Strategy.  If it's empty (`[]`), then all items are passed back, and cached in accordance to the Strategy.  To provide that consistent API, key_cache will always be an array, even if a strategy uses only a single key.
+
+##### auto_checkpoint
+
+Type: object
+
+If you pass in the pipedream `this` from a step, it will use the `this.$checkpoint` as the key_cache, and update it automatically.  This means that the deduper should be the only code that is using `this.$checkpoint` in that step

No alert changes

Improved metrics

Total package byte prevSize

10398

increased by82.33%

Lines of code

168

increased by38.84%

Number of lines in readme file

59

increased by1866.67%

No dependency changes