CODEWITHSUNDEEP
javascriptcollectionssetsortedset
Takatoshi Kondo
Takatoshi Kondo

Reputation: 3550

Sorted (ordered) collection for JavaScript

I'm looking for sorted container for JavaScript.

I'm using C++ std::set, https://en.cppreference.com/w/cpp/container/set and try porting my code to JavaScript.

JavaScript Map is not ordered container. I need some ordered container.

I don't need completely compatible container of std::set on C++. My requirements are

  1. Custom comparator support
  2. Automatically sorted
  3. Find the specific value. If value is not found, get the next value (insertion position value).
  4. Iterator increment/decrement operation (move to prev/next element)

Here is C++ code example that demonstrates my requirements: https://wandbox.org/permlink/wGnTvTPyOej4G9jo

#include <set>
#include <iostream>

int main() {
    // 1. Custom comparator support
    auto comp = [](auto lhs, auto rhs) { return lhs < rhs; };
    std::set<int, decltype(comp)> s(comp);
    
    // 2. Automatically sorted
    s.insert(5);
    s.insert(2);
    s.insert(3);
    for (auto v : s) std::cout << v << std::endl;
    
    auto finder = [&](auto v) {
        std::cout << "try find " << v << std::endl;
        // 3. Find the specific value.
        //    If value is not found, get the next value (insertion position value).
        auto it = s.lower_bound(v);
        auto end = s.end();
        if (it == end) { 
            std::cout << v << " not found. Insertion point is tail" << std::endl;
        }
        else {
            if (*it == v) {
                std::cout << v << " found" << std::endl;
                if (it != s.begin()) {
                    auto left = it;
                    // 4. Iterator increment/decrement operation
                    --left;
                    std::cout << "prev elem is " << *left << std::endl;
                }
                if (it != --end) {
                    auto right = it;
                    // 4. Iterator increment/decrement operation
                    ++right;
                    std::cout << "next elem is " << *right << std::endl;
                }
            }
            else {
                std::cout << v << " not found. Insertion point is just before " << *it << std::endl;
            }
        }
    };

    finder(1);
    finder(3);
}

I found the following containers:

collctions/sorted-set https://www.npmjs.com/package/sorted-btree

It satisfies 1, 2, and 3, but not support 4.

collctions/sorted-array-set http://www.collectionsjs.com/sorted-array-set

It satisfies 1, 2, and 4(maybe), but not support 3.

Does someone know any container that support my requirements?

Upvotes: 2

Views: 1719

Answers (3)

Vasily Ivanov
Vasily Ivanov

Reputation: 380

I've just created a simplified TypeScript implementation of PriorityQueue ported from .NET. Might work for you. https://github.com/VasilyIvanov/priority-queue/blob/master/src/app/priority-queue.ts

Upvotes: 0

Zilong Yao
Zilong Yao

Reputation: 74

js-sdsl

A javascript standard data structure library which benchmark against C++ STL.

This library has strict time complexity guarantee and can be used with confidence.

The latest beta version includes iterator functions which can be used like iterator in c++.

Included data structures

  • Vector
  • Stack
  • Queue
  • LinkList
  • Deque
  • PriorityQueue
  • Set (using RBTree)
  • Map (using RBTree)
  • HashSet (for reference only)
  • HashMap (for reference only)

Usage

To help you have a better use, we provide this API document.

Upvotes: 2

Takatoshi Kondo
Takatoshi Kondo

Reputation: 3550

collctions/sorted-array-set http://www.collectionsjs.com/sorted-array-set

It satisfies following requirement efficiently.

  1. Custom comparator support. See http://www.collectionsjs.com/sorted-set constructor (top-right of the page).

  2. Automatically sorted. It is obvious. The collection is sorted-set.

  3. Find the specific value. If value is not found, get the next value (insertion position value). Use findLeastGreaterThanOrEqual(value) http://www.collectionsjs.com/method/find-least-greater-than-or-equal If you want to find the specific value, and if value is not found, get the previous value, then you can use findGreatestLessThanOrEqual(value) http://www.collectionsjs.com/method/find-greatest-less-than-or-equal Time complexity is O(logN).

It is inefficient but it also satisfies the following requirement.

  1. Iterator increment/decrement operation (move to prev/next element). There are no iterators to access the sibling elements but you can use findLGreatestLessThan(value) http://www.collectionsjs.com/method/find-greatest-less-than to access the previous element, and can use findLeastGreaterThan(value) http://www.collectionsjs.com/method/find-least-greater-than to access the next element. The search is started from the root element of the tree. So each time to access to the sibling element, it requires O(logN) time complexity.

Upvotes: 1

Related Questions