A light-weight node library to manage a sorted & indexed collection with pagination support. All done using Binary Search. Based off my swift code for Queenfisher
npm i github:adiwajshing/keyed-db
npm test
db = new KeyedDB<T> (t => t.uniqueNumberKeyProperty, t => t.optionalUniqueIDProperty)
// compare with a custom function
db = new KeyedDB<T> ({
key: t => t.someProperty,
compare: (t1, t2) => someComputation(t1, t2) // return -1 if t1 < t2, 0 if t1=t2 & 1 if t1 > t2
}, t => t.optionalUniqueIDProperty)
db.insert (value) // insert value in DB
db.upsert (value) // upserts value
db.insertIfAbsent (value) // only inserts if not already present in DB
db.delete (value) // delete value
db.deleteById (value.optionalUniqueIDProperty) // delete value by referencing the ID
// update the key of a value,
// will automatically place object after key change
db.updateKey (value, value => value.uniqueKeyProperty = newValue)
db.paginated (someCursor, 20) // get X results after the given cursor (null for the first X results)import KeyedDB from '@adiwajshing/keyed-db'
// Let's use the db to sort & maintain a list of chats
// Chats must be accessed quickly via the chatID (the person you're chatting with)
// Chats must be sorted by recency
type Chat = {
timestamp: Date
chatID: string
}
// first argument -- sorting property, second argument -- ID property
const db = new KeyedDB<Chat>(value => value.timestamp.getTime()*-1, value => value.chatID)
for (let i = 0; i < 1000;i++) {
// insert data
db.insert (
{
timestamp: new Date( new Date().getTime() - Math.random()*10000 ),
chatID: `person ${i}`
}
)
}
console.log (db.all()) // return internal sorted array
console.log (db.paginated(null, 20)) // return first 20 chats
console.log (db.paginated(null, 20, null, 'before')) // return last 20 chats
console.log (db.paginated(null, 20, chat => chat.chatID.includes('something'))) // return first 20 chats where the chatID contains 'something'
const someDate = new Date().getTime()
const cursorPaginated = db.paginated(someDate, 20)
console.log (cursorPaginated) // return 20 chats after the specified date
db.delete (cursorPaginated[0]) // delete paginated chats
// update chat timestamp
db.updateKey(cursorPaginated[1], value => value.timestamp = new Date().getTime()) | Operation | Time Complexity |
|---|---|
| db.insert() | O(logN) |
| db.delete() | O(logN) |
| db.get() | O(1) |
| db.updateKey() | O(logN) |