A JavaScript implementation of Redis' Sorted Sets. Keeps a set of keys in order based on their score. Uses skip lists under the hood, like Redis does.
This is a fork of the brilliant but abandoned sorted-map package by Eli Skeggs.
Image: The skip list data structure allows search, insert, and removal in O(log(n)) time in average.
With NPM:
$ npm install redis-sorted-setThe API follows Redis' Sorted Set Commands as precisely as possible, with a few additional methods such as .has(member).
var SortedSet = require('redis-sorted-set')
var z = new SortedSet()
// average O(log(N))
z.add('Terminator', 8.0) // => null
z.add('District 9', 8.0) // => null
z.add('Ex Machina', 0.7) // => null
z.add('Ex Machina', 7.7) // => 0.7
// alias
z.set('The Matrix', 8.7) // => null
// average O(1)
z.has('Terminator') // => true
z.has('Blade Runner') // => false
// average O(1)
z.score('Ex Machina') // => 7.7
z.score('Blade Runner') // => null
// alias
z.get('The Matrix') // => 8.7
// average O(log(N))
z.rem('Ex Machina') // => 7.7
// average O(1)
z.rem('Ex Machina') // => null
// alias
z.del('Ex Machina') // => null
// average O(log(N)+M) where M is the number of elements between min and max
z.rangeByScore(7, 8)
// => ['Ex Machina', 'District 9', 'Terminator']
z.rangeByScore(8) // [8.0-∞)
// => ['District 9', 'Terminator', 'The Matrix']
z.rangeByScore(8, null, { withScores: true })
// => [['District 9', 8.0], ['Terminator', 8.0], ['The Matrix', 8.7]]
// average O(log(N)+log(M)) where M as in rangeByScore
z.count(7, 8) // => 3
// average O(log(N))
z.rank('Ex Machina') // => 0
z.rank('Terminator') // => 2
z.rank('Blade Runner') // => null
// average O(log(N)+M) where M as in range
z.range(0, 2)
// => ['Ex Machina', 'District 9', 'Terminator']
z.range(0, 2, { withScores: true })
// => [['Ex Machina', 7.7],
// ['District 9', 8],
// ['Terminator', 8]]
z.range(-1) // => ['The Matrix']
// almost alias
z.slice(0, 3)
// => ['Ex Machina', 'District 9', 'Terminator']
// Set cardinality (number of elements)
// average O(1)
z.card() // => 4
// alias
z.length // => 4var a = new SortedSet()
var b = new SortedSet()
a.add('5a600e10', 16)
a.add('5a600e12', 10)
a.add('5a600e14', 9)
a.add('5a600e15', 14)
a.add('5a600e17', 20)
a.add('5a600e18', 13)
a.add('5a600e19', 15)
a.add('5a600e1a', 19)
a.add('5a600e1b', 7)
a.add('5a600e1c', 13)
a.add('5a600e1e', 10)
b.add('5a600e10', 0)
b.add('5a600e11', 15)
b.add('5a600e13', 5)
b.add('5a600e14', 3)
b.add('5a600e15', 14)
b.add('5a600e17', 12)
b.add('5a600e19', 12)
b.add('5a600e1b', 16)
b.add('5a600e1c', 12)
b.add('5a600e1d', 17)
b.add('5a600e1f', 3)
SortedSet.intersect(a, b)
// => ['5a600e10', '5a600e14', '5a600e17', '5a600e19', '5a600e1c', '5a600e15', '5a600e1b']
SortedSet.intersect(b, a)
// => ['5a600e1b', '5a600e14', '5a600e1c', '5a600e15', '5a600e19', '5a600e10', '5a600e17']
// works, but not preferred
a.intersect(b)
// => ['5a600e10', '5a600e14', '5a600e17', '5a600e19', '5a600e1c', '5a600e15', '5a600e1b']
var c = new SortedSet()
c.add('5a600e10', 7)
c.add('5a600e12', 20)
c.add('5a600e13', 9)
c.add('5a600e14', 19)
c.add('5a600e16', 19)
c.add('5a600e17', 1)
c.add('5a600e18', 18)
c.add('5a600e1a', 6)
c.add('5a600e1c', 15)
c.add('5a600e1f', 4)
// for best performance, the smallest set should be first
SortedSet.intersect(c, a, b)
// => ['5a600e10', '5a600e14', '5a600e17', '5a600e1c']You can enable unique values with the unique option, which causes set to throw an error if the value provided already belongs to a different key.
var z = new SortedSet({ unique: true })
z.add('5a600e10', 16)
z.add('5a600e11', 6)
z.add('5a600e12', 17)
z.add('5a600e13', 11)
z.add('5a600e14', 14)
z.add('5a600e15', 19)
z.add('5a600e16', 3)
z.add('5a600e17', 12)
z.add('5a600e18', 10)
// currently O(log(N)) because it needs to attempt to insert the value
z.add('5a600e19', 11) // throws
z.add('5a600e14', 14) // => 14Pull requests and bug reports via GitHub are highly appreciated. Please test your contribution with the following scripts:
$ npm install
$ npm test
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent