alexbol99 / flatten-interval-tree Goto Github PK

Hi Alexbol, in your readme you have a link to the scoped npm package but the npm website links back to this github repository.

Documentation for this module includes many font files and other miscellaneous files which are at this moment being published on npm along with the rest of the module. This leads to a size of 1.69MB of the unpacked module which is bad for two reasons:

1. projects including this module will have a larger footprint
2. initiates a distrust of this module as its functionality is not supposed to be so big that it is ~2MB in size
   @alexbol99 I really appreciate what a wonderful and beautiful module this is. However, can you please add all irrelevant files to a .npmignore and publish a new version on npm so that published size is reduced.
   Thanks, and Best Regards,

Hi @alexbol99 . It looks like you v1.1.1 hasn't been published to npm. Would you mind publishing it?

Test setup:

const IntervalTree = require('@flatten-js/interval-tree').default
const intervalTree3 = new IntervalTree()

intervalTree3.insert([2, 5], 10)
intervalTree3.insert([2, 5], 20)
intervalTree3.insert([2, 5], 30)

if (!intervalTree3.exist([2, 5], 10)) {
  console.log('item does not exist')
}

Runkit https://runkit.com/embed/mv6xfvsl298g

Specifically it can't find what used to be a "root" node. I debugged code a little bit and it doesn't seem like node with value 10 is part of the traversal. It seems that the issue is somewhere around this line:

https://github.com/alexbol99/flatten-interval-tree/blob/master/src/classes/intervalTree.js#L457

But I am not certain.

Thanks for creating this package.

I was working with it and noticed that it creates clones of the key and value objects instead of just using the original objects. I was curious about what was the reason for this?

Asking because I ran into an issue in my code where IntervalTree had cloned a value and my code was expecting to get the same object back (not a clone).

Currenly when [4,5] is checked with a tree [[7,8],[1,4],[11,12],[1,1],[5,7]] for intersection, the program returns true.
However in many situations like scheduling, this is seldom considered as intersecting. Activities occur after activities in the same venue and the information that they touch each other could often be perceived as noise.

Upon inspecting the code, I noticed that adding equal signs to the Interval.not_intersect method seems to have worked

/**
     * Predicate returns true if this interval does not intersect other interval
     * @param other_interval
     * @returns {boolean}
     */
    not_intersect(other_interval) {
        return (this.high <= other_interval.low || other_interval.high <= this.low);
    }

It doesn't appear to break other operations like the tree balancing either, but I can't be sure.

This is a great library and I know it can be used for 2D ranges, but all the examples are 1D. I think need to use the Interval class for this, right?

I think functions like these are useful

export default class IntervalTree<T = any> extends BaseIntervalTree<T> {

  removeInterval(interval: [number, number]) {
    let search_node = new Node(interval);
    let resp_nodes = [];
    this.tree_search_interval(this.root, search_node, resp_nodes);

    for (let n of resp_nodes ) {
      this.tree_delete(n);
    }
    return resp_nodes as Node<T>[];
  }

  clear() {
    this.root = null;
  }
}

Hey there,

I'm looking for a way to quickly tell if a given interval collides with even 1 of the existing intervals within a tree.
I assume tree.search keeps looking for all the other intervals within the input query interval (in order to return them), but I'm looking for a method that's faster than that, and just returns if it even encounters just 1 interval that collides with the input (query) interval.

Something like tree.intersects([low, high]): boolean
Is there any way to do that (since I'm not interested about the values and I'm not interested in getting any of the intervals within the range, just the information of wether more than 1 exists or not).

I hope my question makes sense.

Thanks

How can I use this package with TypeScript?

Can we adapt the code so that it supports bigint?

/@flatten-js/interval-tree/dist/main.mjs:155
this.item.key = new Interval(Math.min(key[0], key[1]), Math.max(key[0], key[1]));
^

TypeError: Cannot convert a BigInt value to a number
at Math.min ()

hello. thanks for this useful library! I was wondering if there is any hint to make typescript recognize the returned type of search

it is often type any

example

import IntervalTree from '@flatten-js/interval-tree';

let tree = new IntervalTree<string>();

let intervals = [
  [6, 8],
  [1, 4],
  [5, 12],
  [1, 1],
  [5, 7],
] as [number, number][];

// Insert interval as a key and string "val0", "val1" etc. as a value
for (let i = 0; i < intervals.length; i++) {
  tree.insert(intervals[i], 'val' + i);
}

// Get array of keys sorted in ascendant order
let sorted_intervals = tree.keys; //  expected array [[1,1],[1,4],[5,7],[5,12],[6,8]]

// Search items which keys intersect with given interval, and return array of values
let values_in_range = tree.search([2, 3]); // values_in_range is SearchOutput<string>
const x=values_in_range[0] //<-- x is any
let values_in_range = tree.search([2, 3]).forEach((e) => { //<-- e is any
  console.log('e', e);
});

There is a method to remove a single item from the tree.

tree.remove(key, value)

I was wondering is there any method to remove all items within a range?

Hello @alexbol99,
Thank you for this wonderful library.

May I ask if we can assume that the intervals returned by search are sorted?

(I checked the docs, and prior issues before posting)

In my implementation I need not only the value of a interval but also the low, high offsets. Because I'm doing something like:

   const nodes = useInternalSearch(tree, offset, rangeHigh)

    nodes.forEach((node) => {
      const { value: { marks }, key, key: { low, high } } = node.item

      if (offset <= low && rangeHigh >= high) {
        // one block
        marks.push(getTextMarkFromRangeStyle(range))
        return
      }

Therefore I used the internal method tree_search_interval in:

function useInternalSearch (tree, low, high) {
  if (!tree.root) return []

  const resultNodes = []
  tree.tree_search_interval(tree.root, new Node([low, high]), resultNodes)
  return resultNodes
}

But therefore I need the Node class to be exposed.

So for my usecase I either need the Node class or a search function which take low, high and results in [low, high, value] pairs or simply both ^^,

Hi, in the function delete_fixup at

// Go to cases 2..4
if (brother_node.left.color == RB_TREE_COLOR_BLACK &&
    brother_node.right.color == RB_TREE_COLOR_BLACK)

the brother_node has color 1 and a parent node but is otherwise is undefined or null
Do you have a idea how to fix this?

I ran into an issue when using "@flatten-js/interval-tree": "^1.0.6" from NPM.

function setupTreeAndSearch(intervals, searchInterval) {
    let tree = new IntervalTree();
    
    for (let i=0; i < intervals.length; i++) {
        tree.insert(intervals[i],"val"+i);
    }
    
    return tree.search(searchInterval);
}

setupTreeAndSearch(
    [[1,1], [1,4], [5,6], [5.5,7], [7,8]],
    [5.5, 5.7] 
); 
// ["val2", "val3"]
// Correct!

setupTreeAndSearch(
    [[1,1], [1,4], [5,6], [6,7], [7,8]],
    [5.5, 5.7]
);
// []
// Incorrect - expected ["val2"]

The right branch of this.tree_search_interval(...) called from tree.search(...) is excluding the matching (right) branch .

As it is currently running the right conditional is false because, node.not_intersect_right_subtree(...) does not check the left child branch in this line:

let low = this.right.max.low ? this.right.max.low : this.right.item.key.low;

Note: this.right.max is a number, not an object when the line above is run. Perhaps it should be?

Thoughts?

Not a big deal because you provide the ability to insert your own function. The default outputMapperFn tests for truthy on the value. So if you store a value of '0' or other falsey values you will get back an array of keys that intersect the range.
https://github.com/alexbol99/flatten-interval-tree/blob/master/src/classes/intervalTree.js#L126
search(interval, outputMapperFn = (value, key) => value ? value : key.output()) {
Wondering if this should test for value !== undefined ? value : key.output()? If the user is storing numbers that happen to have '0', intentional 'null' values or 'false' in the interval tree this will allow them to get the result if it exists without overriding the outputMapperFn.

Just using pure ES6 in browser (without some processor/packer/bundler in between), the current export/import statements in index.js do not resolve. They are pointing to an extension-less-file or directory that does not exist. Adding '.js' should not break existing use of the file in a bundler/node.js and still support in-browser use. Some more info.

index.js

export {default as Node} from './src/classes/node';
export {default as Interval} from './src/classes/interval';
// export {default as IntervalTree} from './src/classes/intervalTree.js';
import IntervalTree from './src/classes/intervalTree.js';
export default IntervalTree;

should be...

export {default as Node} from './src/classes/node.js';
export {default as Interval} from './src/classes/interval.js';
// export {default as IntervalTree} from './src/classes/intervalTree.js';
import IntervalTree from './src/classes/intervalTree.js';
export default IntervalTree;