Research
Security News
Quasar RAT Disguised as an npm Package for Detecting Vulnerabilities in Ethereum Smart Contracts
Socket researchers uncover a malicious npm package posing as a tool for detecting vulnerabilities in Etherium smart contracts.
little-ds-toolkit
Advanced tools
This is a little collection of some useful data structures. The goal is not giving an exhaustive list and implementation of all existing data structures. But rather a small set of the most useful ones.
This data structure is particularly efficient when it comes to repetitively return the minimum (or maximum, depending on the sorting) item contained, while inserting items in a random order.
You can import it with:
var Heap = require('little-ds-toolkit/lib/heap');
or
var Heap = require('little-ds-toolkit').Heap;
Creating an instance:
var heap = new Heap();
The constructor function can take as argument the comparator used to internally sort the items (just like Array.prototype.sort):
var heap = new Heap(function (a, b) {
return a.value - b.value;
});
You can add items:
heap.push(item); // Θ(log n)
remove and get the minimum (or maximum, depending on the comparator)
var min = heap.pop(); // Θ(log n)
Peeking without removing it is even more efficient:
var min = heap.peek(); // Θ(1)
Searching across the data structure is not particularly efficient, it returns a valid index or -1 (not found):
heap.indexOf(item); // Θ(n)
You can also pass a function that should return true when the item is found:
heap.indexOf(function (item) { // Θ(n)
return item.prop === 5;
});
Using the index you can get or remove an item:
heap.get(3); // Θ(1)
heap.removeIndex(3); // Θ(log n)
removeIndex returns the item removed.
The "remove" method is a short for indexOf + removeIndex.
heap.remove(item); // Θ(n + log n)
// is the same as:
heap.removeIndex(heap.indexOf(item)); // Θ(n + log n)
You can get the length of the heap with:
heap.size(); // Θ(1)
With buildHeap you can populate the heap with the values in an array (it resets the heap). It is very efficient, only O(n). The array used as argument will be mutated! "popAll" is a utility method to return all items in the heap. These two methods, combined together the can be used to build the heapsort sorting algorithm:
var heap = new Heap();
heap.buildHeap(unsorted_array); // O(n)
heap.popAll(); // returns a sorted array O(nlogn)
The "toArray" method returns the inner array representation (partially sorted).
An algorithm may require to remove items or update the sorting order. These operations can be expensive as they require to search the item to remove or replace (O(n)). You can solve this problem with some additional book keeping, using the "onMove" callback. This function can be passed to the contructor (as second argument) and is called every time an item moves in the heap.
var itemPos = {};
var heap = new Heap(undefined, function (item, nextPos, previousPos) {
itemPos[item.id] = nextPos;
});
Using this you can easily remove or replace an item in O(log n):
// removing item "A"
heap.removeIndex(itemPos.A);
// replace item "A"
heap.replaceIndex(itemPos.A, newItem);
This data structure implements the same features of the heap (with the same asymptotic running time), but it also allow to pop maximum values in the same way. It is implemented internally by 2 heaps, with the opposite comparator, pointing one another. You can create an instance with:
var MinMaxHeap = require('little-ds-toolkit/lib/min-max-heap');
or
var MinMaxHeap = require('little-ds-toolkit').MinMaxHeap;
var heap = new MinMaxHeap(optionalComparator);
Here is a list of the methods:
This data structure is useful to group item together and tell if one or more items belongs to the same group.
You can import it with:
var UnionFind = require('little-ds-toolkit/lib/union-find');
or
var UnionFind = require('little-ds-toolkit').UnionFind;
You can create an UnionFind node:
var item = new UnionFind(value);
It has only two methods. Union:
item.union(item2); // almost O(1) (grows very slowly)
and find:
item.find(); // almost O(1) (grows very slowly)
Both "find" and "union" return the "leader" element. The important part is that 2 elements with the same leader belong to the same set. You can retrieve the original value with "item.data".
The object contains 2 useful helper functions "union" and "find" that runs on both UnionFind instances or other values.
// the arguments can be any value (or a UnionFind instance)
var leader = UnionFind.find(item);
var leader = UnionFind.union(item1, item2);
This data structure is a key value cache. The least used items are purged from the cache when it reaches its maximum size (or length). If ES2015 Map are available this can use anything as "key". For old js it only supports strings.
You can import it with:
var LRUCache = require('little-ds-toolkit/lib/lru-cache');
or
var LRUCache = require('little-ds-toolkit').LRUCache;
You create a cache using:
var cache = new LRUCache(options);
The options are:
If maxLen is not set that would be equal Infinity, in this way it is going to behave just like a simple map (please set one!).
Stale items are not removed from the cache, they are not returned and they should go towards the end of the queue, and therefore be purged by the LRU algorithm.
You can set an item:
cache.set(key, value, ttl); // the time to live is optional Θ(1)
and get an item:
var value = cache.get(key); // Θ(1)
If the item is not in the cache or stale, it'll return undefined. The "peek" method is not altering the LRU data structure while returning a value. It is also returning stale objects.
var value = cache.peek(key); // Θ(1)
You can remove an item from the cache using:
cache.del(key); // Θ(1)
You can check if a value is in the cache using "has":
cache.has(key); // Θ(1)
It returns a boolean. cache.len is an attribute containing the number of items.
FAQs
A small collection of useful data structures
We found that little-ds-toolkit demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Research
Security News
Socket researchers uncover a malicious npm package posing as a tool for detecting vulnerabilities in Etherium smart contracts.
Security News
Research
A supply chain attack on Rspack's npm packages injected cryptomining malware, potentially impacting thousands of developers.
Research
Security News
Socket researchers discovered a malware campaign on npm delivering the Skuld infostealer via typosquatted packages, exposing sensitive data.