js-sdsl / js-sdsl Goto Github PK

Is your feature request related to a problem? Please describe.
I have such problem: I want to know how much values are between of two keys.
I have a timeline of thousands of events, and I use an OrderedMap (key is timestamp, value — event data), because I draw a line chart for them. I want to give a user an opportunity to know, how many events are between two chosen points.

Describe the solution you'd like
If I'd have an index of an item, I could do this:

// eventMap is an OrderedMap
const leftIndex = eventMap.getIndexByKey(leftKey)
const rightIndex = eventMap.getIndexByKey(rightKey)
const eventsBetween = rightIndex - leftIndex - 1

Describe alternatives you've considered
I could also have a simple method like OrderedMap.prototype.itemsBetweenKeys:

// eventMap is an OrderedMap
const eventsBetween = eventMap.itemsBetweenKeys(leftKey, rightKey)

https://github.com/js-sdsl/js-sdsl/actions/runs/3964428948

Since I was forced to enable secondary authentication by npm, the automated CI could not be released successfully.

Describe the bug

Get wrong tree index when tree size is 1.

To Reproduce

const st = new OrderedSet([1], undefined, true);
console.log(st.begin().index);  // expected 0 but get 2

Expected behavior

Expected 0 but get 2.

Is there any possibility to use comparison by two fields for a set of objects?

Example:
I have simple objects, like

{
    "id": 1,
    "price": 10
},
{
    "id": 2,
    "price": 9
},
{
    "id": 3,
    "price": 3
}

I wanna set of this objects, but ordered by price ASC and id DESC.
Is it real?

Thanks for any advice!

Optimize the red-black tree insertion function until the performance is equal to functional-red-black-tree

Is your feature request related to a problem? Please describe.

This is not really a problem, but I noticed accessing an iterator's pointer causes users some confusion (e.g. #145).

From what I can tell, the correct way to check if an iterator's pointer can be accessed varies slightly for each collection, but is usually something like (given collection, collection, and the appropriate iterator instance, it):

!it.equals(collection.end())

Describe the solution you'd like

I wonder if it is a good idea to have an isAccessible boolean getter on all the iterators so you can check if it can be accessed.

Describe alternatives you've considered
Otherwise you can just try to access it and catch the RangeError, but this is not the best practice in JavaScript (errors are best used for genuine runtime errors etc. rather than for logic).

Users making sure they understand how the collection works and when the pointer can be accessed or not is always a good idea, of course 😉.

Additional context

This could also help with enhancing the code readability and self-documenting, as there would be functions defined in the source providing definitive way of checking if the pointer can be accessed.

Is your feature request related to a problem? Please describe.

Now:

import { OrderedSet } from '@js-sdsl/ordered-set';

Describe the solution you'd like

I want:

import OrderedSet from '@js-sdsl/ordered-set';

Additional context

import { OrderedSet } from '@js-sdsl/ordered-set';

It doesn't make sense because there is only one member has been exported which named OrderedSet.

Does it possible? @noname0310

I think the problem will be require doesn't support default.

Is your feature request related to a problem? Please describe.

I want to update the element in the TreeContainer (e.g. OrderedSet), but it is prohibited.
It is reasonable because updated element could insert the different position.

However, users sometimes know the updated element is still the same position.
For example,

Before update:
    V
[1, 3, 5]

After update:
    V
[1, 4, 5]

When I want to update the element, I need to do the following steps:

1. container.find(key) the element's iterator. Then got it.
2. container.eraseElementByIterator(it)
3. Create the new element based on the gotten element and insert it.

Step1 and 3 are O(logN) time complexity.
I want to eliminate Step3 cost.

Describe the solution you'd like
js-sdsl's design refers to C++ STL.
C++ std::set::insert has insert(hint, value) overload.
https://en.cppreference.com/w/cpp/container/set/insert
See (3) (4) overloads.

Since C++ 11
3-4) Amortized constant if the insertion happens in the position just before the hint, logarithmic in the size of the container otherwise.

container.eraseElementByIterator(it) at the step2 returns the iterator just after the erased element.
So if I use the returned iterator as the hint, then the hint iterator is the insertion happens in the position just before the hint.

So the steps become as follows:

1. container.find(key) the element's iterator. Then got it.
2. it = container.eraseElementByIterator(it)
3. Create the new element based on the gotten element and insert it with hint. container.insertWithHint(it, 4)

Step3 becomes O(1) time complexity thanks to the hint it.

I guess that js-sdsl can implement similar way to the C++ one.

Describe alternatives you've considered

Directly modify the element value by user's risk. However, insert() with hint achieves the same goal (eliminate extra O(logN) time complexity) more elegant way.

Additional context

libc++ implementation of std::set::insert(hint, value)
https://github.com/llvm-mirror/libcxx/blob/2f961a057f1ecb29d40892fe9198fe4e4b5c5619/include/set#L704-L711

Like this:

Thank you for writing a great library.
I'm looking for https://stackoverflow.com/questions/65948823/sorted-ordered-collection-for-javascript

https://github.com/ZLY201/js-sdsl/blob/1ea84551eb7c7cf07cce5752406e18896f0c34ab/src/Map/Map.ts
seems to have the follwoing methods:

• size()
• empty()
• clear()
• front()
• back()
• forEach()
• getElementByPos()
• eraseElementByPos()
• eraseElementByKey()
• setElement()
• find()
• getElementByKey()
• union()
• getHeight()

I'd like to do as follows.
Let's say the Map has the key [1, 3, 6, 7] (values are not important so I omit them), and call some lower_bound() like function with the argument 4, then return node 6 because it is just after the 4.
I guess that I can't do that using a combination of existing methods.

Describe the bug

Tree shaking not work with js-sdsl when use import { xxx } from 'js-sdsl'

To Reproduce

Expected behavior

Tree shaking should work.

Screenshots

Additional context

See here.

• sidorares/node-mysql2#1629
• redis/ioredis#1649
• mongodb/node-mongodb-native#3419

Describe the bug
The last value comes out even though the size of the queue is 0.

To Reproduce
Steps to reproduce the behavior:

import { Queue } from "js-sdsl";

const testQueue = new Queue<number>();
testQueue.push(1);
testQueue.push(2);

console.log(testQueue.front(), testQueue.size());
testQueue.pop();
console.log(testQueue.front(), testQueue.size());
testQueue.pop();
console.log(testQueue.front(), testQueue.size());

Expected behavior
expected behavior is:

1 2
2 1
undefined 0

actual result is:

1 2
2 1 
2 0

Additional context
There was a similar problem with version 4.1.2 and it was fixed in 4.1.3

This problem occurred again in 4.1.4-beta.0

In my opinion, adding operations on empty containers to the test case will prevent recurrence of this problem in future updates.

After swapping functional-red-black-tree to js-sdsl in ethereumjs/ethereumjs-monorepo#2283, we now run into an out-of-memory exception in one of the unit tests which uses a big chunk of memory. This seems to imply that js-sdsl is worse in memory usage than functional-red-black-tree. Is there any theory of this memory complexity?

Describe the bug
OrderedSet with less than 3 (exactly 2 or 1) items reverse iteration falls into infinite loop

• Tested on node 16.8.1 / FF 113.0.2 (Mac)
• @js-sdsl/ordered-set version 4.4.0

To Reproduce

const orderedSet = new OrderedSet([1, 2]);
const result = [];
const begin = orderedSet.rBegin();
const end = orderedSet.rEnd();
for (const it = begin; !it.equals(end); it.next()) {
  result.push(it.pointer);
}
console.log(result); // Must be [2, 1]

Expected behavior
Everything works

Actual behavior
Browser just goes into infinite loop. Node crashes:

#
# Fatal error in , line 0
# Fatal JavaScript invalid size error 169220804
#
#
#
#FailureMessage Object: 0x7ff7bd33b880
 1: 0x102cf8cf2 node::NodePlatform::GetStackTracePrinter()::$_3::__invoke() [~/.nvm/versions/node/v16.18.1/bin/node]
 2: 0x103ccddf3 V8_Fatal(char const*, ...) [~/.nvm/versions/node/v16.18.1/bin/node]
 3: 0x102f74826 v8::internal::FactoryBase<v8::internal::Factory>::NewFixedArray(int, v8::internal::AllocationType) [~/.nvm/versions/node/v16.18.1/bin/node]
 4: 0x103102014 v8::internal::(anonymous namespace)::ElementsAccessorBase<v8::internal::(anonymous namespace)::FastPackedSmiElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)0> >::GrowCapacity(v8::internal::Handle<v8::internal::JSObject>, unsigned int) [~/.nvm/versions/node/v16.18.1/bin/node]
 5: 0x10332601d v8::internal::Runtime_GrowArrayElements(int, unsigned long*, v8::internal::Isolate*) [~/.nvm/versions/node/v16.18.1/bin/node]
 6: 0x1036dcc19 Builtins_CEntry_Return1_DontSaveFPRegs_ArgvOnStack_NoBuiltinExit [~/.nvm/versions/node/v16.18.1/bin/node]
 7: 0x10d7b1890 
 8: 0x10366f6ea Builtins_InterpreterEntryTrampoline [~/.nvm/versions/node/v16.18.1/bin/node]

Update api documentation.

See files published on NPM:
ESM: https://unpkg.com/browse/[email protected]/dist/esm/container/OtherContainer/Queue.js

var __extends = this && this.t || function() {
    var extendStatics = function(t, i) {
        extendStatics = Object.setPrototypeOf || {
            __proto__: []
        } instanceof Array && function(t, i) {
            t.__proto__ = i;
        } || function(t, i) {
            for (var n in i) if (Object.prototype.hasOwnProperty.call(i, n)) t[n] = i[n];
        };
        return extendStatics(t, i);
    };
    return function(t, i) {
        if (typeof i !== "function" && i !== null) throw new TypeError("Class extends value " + String(i) + " is not a constructor or null");
        extendStatics(t, i);
        function __() {
            this.constructor = t;
        }
        t.prototype = i === null ? Object.create(i) : (__.prototype = i.prototype, new __);
    };
}();

import { Base } from "../ContainerBase";

var Queue = function(t) {
    __extends(Queue, t);
    function Queue(i) {
        if (i === void 0) {
            i = [];
        }
        var n = t.call(this) || this;
        n.A = 0;
        n.tt = [];
        var e = n;
        i.forEach((function(t) {
            e.push(t);
        }));
        return n;
    }
    Queue.prototype.clear = function() {
        this.tt = [];
        this.M = this.A = 0;
    };
    Queue.prototype.push = function(t) {
        var i = this.tt.length;
        if (this.A / i > .5 && this.A + this.M >= i && i > 4096) {
            var n = this.M;
            for (var e = 0; e < n; ++e) {
                this.tt[e] = this.tt[this.A + e];
            }
            this.A = 0;
            this.tt[this.M] = t;
        } else this.tt[this.A + this.M] = t;
        return ++this.M;
    };
    Queue.prototype.pop = function() {
        if (this.M === 0) return;
        var t = this.tt[this.A++];
        this.M -= 1;
        return t;
    };
    Queue.prototype.front = function() {
        if (this.M === 0) return;
        return this.tt[this.A];
    };
    return Queue;
}(Base);

export default Queue;
//# sourceMappingURL=Queue.js.map

CJS: https://unpkg.com/browse/[email protected]/dist/cjs/container/OtherContainer/Queue.js

"use strict";

Object.defineProperty(exports, "t", {
    value: true
});

exports.default = void 0;

var _ContainerBase = require("../ContainerBase");

class Queue extends _ContainerBase.Base {
    constructor(t = []) {
        super();
        this.j = 0;
        this.q = [];
        const s = this;
        t.forEach((function(t) {
            s.push(t);
        }));
    }
    clear() {
        this.q = [];
        this.i = this.j = 0;
    }
    push(t) {
        const s = this.q.length;
        if (this.j / s > .5 && this.j + this.i >= s && s > 4096) {
            const s = this.i;
            for (let t = 0; t < s; ++t) {
                this.q[t] = this.q[this.j + t];
            }
            this.j = 0;
            this.q[this.i] = t;
        } else this.q[this.j + this.i] = t;
        return ++this.i;
    }
    pop() {
        if (this.i === 0) return;
        const t = this.q[this.j++];
        this.i -= 1;
        return t;
    }
    front() {
        if (this.i === 0) return;
        return this.q[this.j];
    }
}

var _default = Queue;

exports.default = _default;
//# sourceMappingURL=Queue.js.map

If I had to guess it's because the ESM build is set to target ES5:

Describe the bug
Could it be that this changes now hides that index file in the cjs build?
https://github.com/js-sdsl/js-sdsl/pull/57/files#diff-8a95d77a8ee9283d083856706c50385315d87a75d2ab9f963b64a16c06b8c332R4

It breaks for me here

To Reproduce
Steps to reproduce the behavior:

1. Run eslint >= 8.23.1 with some indenting rules active
2. See error

> eslint "./src/**/*.ts"


Oops! Something went wrong! :(

  ESLint: 8.26.0

Error: Cannot find module './Base'
Require stack:
- my_project/node_modules/js-sdsl/dist/cjs/container/TreeContainer/OrderedSet.js
- my_project/node_modules/js-sdsl/dist/cjs/index.js
- my_project/node_modules/eslint/lib/rules/indent.js
- my_project/node_modules/eslint/lib/rules/index.js
- my_project/node_modules/eslint/lib/linter/rules.js
- my_project/node_modules/eslint/lib/linter/linter.js
- my_project/node_modules/eslint/lib/linter/index.js
- my_project/node_modules/eslint/lib/cli-engine/cli-engine.js
- my_project/node_modules/eslint/lib/eslint/eslint.js
- my_project/node_modules/eslint/lib/eslint/index.js
- my_project/node_modules/eslint/lib/cli.js
- my_project/node_modules/eslint/bin/eslint.js
at Module._resolveFilename (node:internal/modules/cjs/loader:985:15)
at Module._load (node:internal/modules/cjs/loader:833:27)
at Module.require (node:internal/modules/cjs/loader:1051:19)
at require (node:internal/modules/cjs/helpers:103:18)
at Object.<anonymous> (my_project/node_modules/js-sdsl/dist/cjs/container/TreeContainer/OrderedSet.js:9:36)
    at Module._compile (node:internal/modules/cjs/loader:1149:14)
    at Module._extensions..js (node:internal/modules/cjs/loader:1203:10)
    at Module.load (node:internal/modules/cjs/loader:1027:32)
    at Module._load (node:internal/modules/cjs/loader:868:12)
    at Module.require (node:internal/modules/cjs/loader:1051:19)

Expected behavior
A compilable module is packaged.

Screenshots
See above

Additional context

Describe the bug
The value returned by OrderedMapIterator#pointer only supports access by index and does not implement iterable protocol, and hence you can't use it with destructuring assignment syntax.

I am working with OrderedMap but presumably the same problem applies to iterators for the other map collections.

To Reproduce
Given an OrderedMapIterator, it, which is not pointing to end() or rEnd()
(example setup code):

const map = new OrderedMap();
map.setElement('a', 1);
map.setElement('c', 2);
const it = map.lowerBound('b'); // Will be pointing to key 'c'

// Does not work:
const [key, value] = it.pointer; // Throws TypeError: it.pointer is not iterable
// Works:
const key = it.pointer[0];
const value = it.pointer[1];

Expected behavior
Array destructuring assignment is idiomatic so I think it would be expected to be able to do this.
The solution is to implement Symbol.iterator method on the Proxy object returned by pointer.
However, I would like to suggest a simpler solution, maybe we can just allow accessing by property names "key" and "value".
So we could do e.g.

// ...
const {key, value} = it.pointer;
// Or if we want to assign different local variable names:
const {key: diffNameForKey, value: diffNameForValue} = it.pointer;

This would not be a breaking change as accessing by index could still be supported. For completeness, the iterable implementation is pretty simple and allows using the array destructuring syntax. (I can have a go at providing an implementation if you want). I wonder if it would be simpler to just return an array rather than use a Proxy, but I assume Proxy was chosen for a reason?

Additional context
This problem may not show up if transpiling to an older ES target, where destructuring assignment is transpiled to accessing by index syntax.

Another idea for a solution: I wonder if it would be a good idea to provide convenience property getters directly on the OrderedMapIterator? e.g. it.key and it.value.

Add follow functions to heap:

• find (check if element is in heap)
• remove (remove specified item)
• updateItem (update item and it's pos in the heap)
• toArray (return copy array of heap)

In previous versions, I relied too much on C++ STL.

In fact, many designs in C++ STL are not suitable for Javascript, especially in the function name specification.

This RFC (Request for Comment) outlines the all updates to js-sdsl which will be done in 2023.

• Modify the names of all apis to conform to the specification in javascript.
• Organize the code of the red-black tree or perform simple refactoring to make its code structure clearer. #159
• If possible further optimize hash table performance, at least as a good polyfill.
• Improve performance of iterators for sequential containers, especially Deque.
• Add algorithm and awesome module.
• Change oop to functional programming. [Refused]
• Change ESM building target to ES6. #158

Although this is a RFC for 5.x, I think some works could be done in version 4.x.