qwertie / btree-typescript Goto Github PK

Is it possible that, when we loop and delete multiple entries from btree, some of the entries/keys in the tree becomes undefined?
Our config: we have entries around 1800, and the base was chosen as 10.
Is this to do with how the balancing logic works?

Is there a way we can do btree.indexOf(key) in O(log(n)) instead of O(n) in the implementation? Currently I am just doing a forEach and counting.

Similarly, it would be awesome if the set and remove methods returned the position of the inserted or removed entries respectively instead of boolean. This would save a round trip to indexOf.

How could one approach a need to access values in the comparator?

We have a set of objects, where want to:

• maintain sorting based on object attributes
• have access to objects, having a key at hand

At first, I was manually maintaining Map<Foo['id'], Foo> as the main collection of all objects plus Set<Foo['id']> as a collection of IDs representing an order by some criteria (not relevant here, I believe) + another such set for sorting.

Now, I thought that re-implementing the main collection to BTree<Foo['id'], Foo> with a custom comparator would serve me well…

…however, I need to have access to the Foo objects (which are quite complex) to be able to provide the sorting behavior, but that gets me infinite recursion from calling get in the comparator, since BTree uses the comparator in the implementation of get.

I must admit that I might be conceptually missing some bigger picture here since this data structure is entirely new to me (as I've started to play with this just a few hours ago)…

…however, it seems to me that my use-case could be achieved relatively easily if there was

• a way to prevent the need for the comparator in the getter
• or have a different comparator for getter(s)

Hello, thank you for providing high quality source code.

Q1. Is the reason why there is no 'find() method' only for 'Map Interface' compatibility?

Q2. Should I use 'values() iterable' instead?

Seems that Btree become corrupted (forgots some keys) after some operations.
Here is an example:

const BTree = require('sorted-btree').default;

const tree = new BTree();
const keys = new Set();

// tree and keys should always contain same keys
for (let i=0; ; i++) {
    // add to both
    tree.set(i, i);
    keys.add(i);
    if (tree.size > 25000 && i % 2 == 0) {
        const key = Math.floor(i / 2);
        // delete from both
        tree.delete(key);
        keys.delete(key);
        for (let key of keys) {
            if (!tree.has(key)) {
                console.error('No key ' + key + ' found in tree at cycle', i);
                process.exit(1);
            }
        }
    }
}

Use version 1.2.1 of sorted-btree and Node 13.5.0.

Thank you, incredibly fast lib.

Without esm build i.e.

"build:esm": "tsc --module es2015 --target es5 --outDir dist/esm"

its impossible to use this library if "type": "module", is set in package.json.
i.e having commonjs I need add .default and this breaks typings

import BTree from 'sorted-btree';
var tree = new BTree.default<number, [number, number]>(undefined, (a, b) => a - b);

To have near zero setup of esm+commonjs support I can recoomend https://github.com/developit/microbundle

Tried to use your btree implementation today, but when importing as you stated, it returns an error that there is no exported member BTree. There is an EmptyBTree, but that isn't usable. The only things exported, according to intellisense, are the interfaces.

Since BTree is optimized for implementing sets efficiently, I expected BTree<K, V> to implement the ISortedSet<K> interface as well.

If used as follows (which I expect to be the standard):

const myMap: IMap<K, V> = new BTree();
const mySortedMap: ISortedMap<K, V> = new BTree();
const mySet: ISet<K> = new BTree();
const mySortedSet: ISet<K> = new BTree();

the extra methods would not be exposed unless necessary.

I can work on it and open a PR to fix it, if there are no downsides.

Thanks for the nice project! ❤️

What would be the best method for serialization of a sorted btree (using interface ISortedMap)?

Is it safe to use JSON.stringify, or would you recommend serializing the iterable and then reconstructing the tree from the resulting array?

const tree = new BTree()

get error
Uncaught TypeError: BTree is not a constructor

This seems to be an issue with 0 being falsy. I haven't tested on any of the other variants.

This package fails to webpack with our setup due to:

ERROR in ./node_modules/sorted-btree/b+tree.js 13:24-31
Critical dependency: require function is used in a way in which dependencies cannot be statically extracted

Looking at the javascript, the 'factory' function 'require' is being passed into never uses its first argument (the 'require'), so I replaced the call site's 'require' with undefined and it fixed the webpacking. This workaround is a kludge though: I believe this code is part of the generated module format related boilerplate, and should be fixed by changing the module type.

Looking at tutorials for making npm packages with typescript, module format commonjs seems to be preferred over umd (ex: https://itnext.io/step-by-step-building-and-publishing-an-npm-typescript-package-44fe7164964c ), and I suspect setting commonjs in tsconfig.json will fix this (all my team's internal packages use it, and it works fine with node and webpack).

Hi, this lib is awesome, thanks for your sharing.
but I had a little problem when I wanted to extend a .next() method to loop through the entire tree

this._cursor = undefined
...

BTree.prototype.nextCyclePair = function () {
    var key = this._compare(this._cursor, this.maxKey()) >= 0 ? undefined : this._cursor
    var it  = this.entries(key, ReusedArray)
    var r   = it.next()
    if (!r.done && key !== undefined && this._compare(r.value[0], key) <= 0) {
      r = it.next()
    }
    this._cursor = r.value ? r.value[0] : r.value
    return r.value
  }

It works, but unfortunately, not threads safety,
if I call async functions in parallel ,
There is a probability that get the same result,

I think it's because .entries() returns a new iterator each time,
so it.next() could possible return a same pair
That's why this._cursor not work,

so, my question is
Is there a way to implement a thread-safe iterator?

Here's a quick & dirty implementation I wrote, base on Map

module.exports = class CycledMap extends Map {
  constructor (...args) {
    super(...args)
    this._indexArr = this.setIndexArr()
    this._index    = 0
  }

  get index () {
    return this._index >= this.size ? 0 : this._index
  }

  set index (index) {
    this._index = index
  }

  getkey (index) {
    return this._indexArr[index]
  }

  next () {
    const key = this.getkey(this.index++)
    return { [key]: this.get(key) }
  }

  setIndexArr () {
    this._indexArr = [...this.keys()]
  }

  clear () {
    super.clear()
    this._index = []
  }

  delete (key) {
    super.delete(key)
    this.setIndexArr()
  }

  set (...args) {
    super.set(...args)
    this.setIndexArr()
  }
}