mauriciosantos / buckets-js

A complete, fully tested and documented data structure library written in pure JavaScript.

Buckets

A JavaScript Data Structure Library

Buckets is a complete, fully tested and documented data structure library written in pure JavaScript.

Included data structures

• Linked List
• Dictionary
• Multi Dictionary
• Binary Search Tree
• Stack
• Queue
• Set
• Bag
• Binary Heap
• Priority Queue

Buckets also includes several functions for manipulating arrays.

Supported platforms

• Every desktop and mobile browser (including IE6)
• Node.js

If it supports JavaScript, it probably supports buckets.

Downloading Buckets

Download directly

• buckets.js (for development) or
• buckets.min.js (for production)

Then, add it as a script tag to your page:

<script src="buckets.js"></script>
<script>
  var aSet = new buckets.Set();
</script>

Or install bucketsjs using bower

bower install bucketsjs

Or use an AMD loader

require(["./bower/bucketsjs/buckets.js"], function(buckets) {
  var hm = new buckets.Dictionary();
});

Or install buckets-js using npm

npm install buckets-js

In Node.js: var buckets = require('buckets-js');.

Usage

var a = new buckets.Set();
var b = new buckets.Set();
a.add(1);
a.add(2);
b.add(2);
a.union(b); // {1,2}

Read the documentation.

Building Buckets

There's nothing else you need to use buckets. However, this guide may help you if you wish to contribute to the project or modify it.

buckets-js's Issues

npm published package

It would be great if buckets was published as an NPM package to allow standard node/npm package management to track the latest release of buckets. I'd do it, but your name should be on it!

Various Dictionary bugs

var dict = new buckets.Dictionary();

dict.set("toString", 42);
dict.size() === 0; // wrong, should be 1
dict.remove("toString");
dict.size() === -1; // wrong, should be 0

dict.set("hasOwnProperty", "foo");
try {
    dict.keys(); // throws an error trying to invoke "foo" as a function
} catch(e) {
    dict.remove("hasOwnProperty");
}

dict.set("__proto__", {value: 123});
dict.get("value") === 123; // wrong, should be undefined

The __proto__ issue can be prevented by prefixing all keys with a weird character like "~" before storing them into table.
this.table["~" + key] = {.....}

Instead of this.table.hasOwnProperty, do:

var has = function(obj, key) {
    Object.prototype.hasOwnProperty.call(obj, key);
}
has(table, key); // instead of table.hasOwnProperty(key)

When checking whether or not the dictionary has a certain key, always use has().

feature Bag1 <= Bag2

Hello,

is there an easy way to test for inclusion of a Bag inside another Bag with buckets ?
By inclusion I mean nCopies <= nCopies for each keys ?

Thanks

BSTree - inorderTraversal from specific starting point

Hi, this library is awesome thanks for the work you put into it.

We’re using BSTree to index domain names from documents. We can use inorderTraversal to traverse documents by our custom domain ranking.

Is there a way to inorderTraverse from a specific starting point? (vs. traversing the whole tree). It seems like some other trees provide this and maybe it could be fairly straightforward to implement in BSTree.

Use case: we want to get all docs for a certain domain (I.e. trello.com) without traversing the entire tree.

performance question

Hello this is more of a question rather than an issue. I understand the theory behind these data structures, but i run a little test in action and i didn't really understand the results. I used a simple array from [0...10000] and the same as btree. I used underscore to give me the min,max and if array contains 9999, so it's the worst situation for array because it will do O(n) for these actions. So benchmarking that, btree is really good 2x faster than underscore functions. But in overall btree is like 10x slower than underscore functions. I believe this has to do with constructing the btree versus constructing a simple array? Is this expected? And if so, what is the point of using structures in javascript?

BSTree isn't balancing?

e.g. red-black tree or splay tree, c.f. npm bbtree

If you insert into a non-balancing binary search tree from a sorted array, that can happen easily, the lookup performance breaks down to linear, the tree will look like

            o
             \
              o
               \
                o
                 \
                  o
                   \
                    . . .

Add buckets to bower and npm

It would be nice if you can install the library from a package manager instead of downloading it manually.

Question: Sorted dictionary

Does this library provide a sorted dictionary type like C++ STL map? Or ... just use BST?

Does LinkedList expose the head node directly?

All of the methods I see in the documentation return the element from the underlying array. This makes it impossible to do something like node.next to walk the linked list. I looked at the source for a minute, am I missing something?

Balanced Tree

Hi,
Are there any plans to add balanced tree in future (AVL or Red Black?)
Thanks!

methods created when creating new object should be in prototype chain not in object itself

methods created when creating new object should be in prototype chain not in object itself.

Since functions/method itself an object , it memory for it , when creating a object.

var que = new buckets.Queue();

que object is created , and method like enqueue and dequeue is also created in object itself , not in prototype chain.

If I create a hundreds of object like this. It will take a lot of memory .

[Feature Request] Add N-ary tree data structure

Any chance you will add N-ary tree structure support?

Removing the last element from a LinkedList is unnecessarily slow

Removing the first element from a LinkedList is fast, however, removing the last element is slow.

The problem seems to be that in the removeElementAtIndex function rather than simply accessing the lastNode element, the nodeAtIndex is called, fetching the second to last element, which is done by iterating over the entire list.

Removing the last element from a LinkedList is very common, so it being crippled severely hampers the usability of the data structure.

Thanks

AMD Loading

It's easy enough to add a define() after pull but would be great to have in the base lib.

how to judge the element which type is object with contains method?

I got it in the test file, thank you

Naming of minified file

Hi @mauriciosantos,

Is it possible to change buckets-minified.js to buckets.min.js? I think it's a common usage :)