Build a function memoizer [Part-4]
Tags: javascript, memo, interview
Published: 2020-07-31 14:45:02

In the final part of the series we'll be adding expiry to cached values.

Breakdown:

- Just like the cacheSize we'll accept an expiresAt param with value in ms. 
- If it's present then each node should store a timestamp of when it was created
- after finding a node we have to check if it expired
- clean expired nodes


Update cache options
```js
  let options = {
    cacheSize: DEFAULT_CACHE_SIZE,
    expiresAt: null,
    ...params,
  };
```

Update Node structure
```js
function Node(key, value, expires) {
  this.key = key;
  this.value = value;
  this.next = null;
  this.prev = null;
  this.timestamp = expires ? Date.now() : null;
}
```

Add a function to check expiry
```js
Node.prototype.hasExpired = function (diff) {
  if (diff && this.timestamp) {
    return Date.now() - this.timestamp >= diff;
  }
};
```

Pass expires flag when creating a new node
```js
// inside add function
const node = new Node(key, value, options.expiresAt);

```

Update find function to ignore an expired node
```js
  // check for cached node
  function find(key) {
    if (key in hash) {
      const node = hash[key];
      if (!node.hasExpired(options.expiresAt)) {
        refresh(node);
        return node;
      }
      // TODO: remove expired node
    }
    return null;
  }
```

Time for some tests,
```js
(async function () {
  // expires after one second
  const testCache = Cache({ cacheSize: 3, expiresAt: 1000 });

  testCache.add("1-2", 3);
  testCache.add("2-3", 5);
  testCache.add("5-5", 10);
  testCache.add("4-2", 6);

  console.log(testCache.find("2-3")); // returns Node

  // wait for 2 seconds
  await new Promise((r) => setTimeout(r, 2000));

  console.log(testCache.find("2-3")); // returns null
})();
```
Find returned null for "2-3" because it expired after one second.

To remove expired nodes we have to modify the remove function to remove any node passed to it rather than just the tail node.
```js
  function remove(node) {
    if (node) {
      delete hash[node.key];

      // if the node is in the middle
      if (node.prev) {
        node.prev.next = node.next;
      }
      if (node.next) {
        node.next.prev = node.prev;
      }
      // if it's the tail node
      if (node === tail) {
        tail = node.prev;
      }
      // if it's the head node
      if (node === head) {
        head = node.next;
      }
      size--;
    }
  }
```

Also update the existing call in the `add` function to `remove(tail)`

Update the find function to remove expired nodes
```js
  function find(key) {
    if (key in hash) {
      const node = hash[key];
      if (node.hasExpired(options.expiresAt)) {
        remove(node);
      } else {
        refresh(node);
        return node;
      }
    }
    return null;
  }
```

Update the test above, add a print at the end
```js
console.log(testCache.print());
// output: "[4-2: 6] -> [5-5: 10]"
```

Referring an expired node removed it from the linked list. The cache is working, let's test the memoizer

```js
(async function () {
  let count = 0;
  function add(a, b, c = 0) {
    count++;
    return a + b + c;
  }
  const memoAdd = memoizer(add, { cacheSize: 3, expiresAt: 1000 });

  memoAdd(5, 3);
  memoAdd(3, 3);
  memoAdd(1, 2);
  memoAdd(2, 4);
  console.log(count); // 4

  await new Promise((r) => setTimeout(r, 2000));

  memoAdd(1, 2);
  console.log(count); // 5, cache expired

  memoAdd(1, 2);
  console.log(count); // 5, pulled from cache

  memoAdd(2, 4);
  console.log(count); // 6, expired value
})();
```

Works as expected, we are done with a good enough implementation of a memoizer function with support for cacheSize and expiry.

The memoizer code and jest tests can reviewed [here](https://github.com/Kailash-Sankar/fn-memoizer)


That's all folks :)

---
Photo by [Steve Johnson](https://unsplash.com/@steve_j?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText) on [Unsplash](https://unsplash.com/t/textures-patterns?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText")