A Sorted Map and a Sorted Set, implemented as a binary tree

Usage

Install in your node project with npm i somap and use it inside your code via

const {SoMap, SoSet} = require('somap'); or alternatively import {SoMap, SoSet} from 'somap';

Construct a Sorted Map

Construct with new SoMap([iterable], [comparator]) which will be sorted by the keys of the key-value pairs.

iterable - optional

An Array or other iterable object whose elements are key-value pairs (arrays with two elements, e.g. [[ 1, 'one' ],[ 2, 'two' ]]). Each key-value pair is added to the new Map; null values are treated as undefined.

comparator - optional

Specifies a function that defines the sort order of the keys. If omitted, the contents are sorted according by natural order of the keys.

If a and b are two elements being compared, then:

If comparator(a, b) is less than 0, sort a to an index lower than b, i.e. a comes first. If comparator(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. If comparator(a, b) is greater than 0, sort b to an index lower than a, i.e. b comes first. comparator(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned then the sort order is undefined.

Sorted Map API

You may want to refer to Javascript Map API for more context.

Map.prototype.size

Returns the number of key/value pairs in the SoMap object.

SoMap.prototype.clear()

Removes all key/value pairs from the SoMap object.

SoMap.prototype.delete(key)

Returns true if an element in the SoMap object existed and has been removed, or false if the element does not exist. SoMap.prototype.has(key) will return false afterwards.

SoMap.prototype.entries()

Returns a new Iterator object that contains an array of [key, value] for each element in the SoMap object in defined order.

SoMap.prototype.forEach(callbackFn[, thisArg])

Calls callbackFn once for each key-value pair present in the SoMap object, in defined order. If a thisArg parameter is provided to forEach, it will be used as the this value for each callback.

SoMap.prototype.get(key)

Returns the value associated to the key, or null if there is none.

SoMap.prototype.has(key)

Returns a boolean asserting whether a value has been associated to the key in the SoMap object or not.

SoMap.prototype.keys()

Returns a new Iterator object that contains the keys for each element in the SoMap object in defined order.

SoMap.prototype.set(key, value)

Sets the value for the key in the SoMap object. Returns the SoMap object.

SoMap.prototype.values()

Returns a new Iterator object that contains the values for each element in the SoMap object in defined order.

SoMap.prototype[@@iterator]()

Returns a new Iterator object that contains an array of [key, value] for each element in the SoMap object in defined order.

SoMap.prototype.min()

Returns the minimum key-value pair of the SoMap object

SoMap.prototype.max()

Returns the maximum key-value of the SoMap object

Construct a Sorted Set

Construct with new SoSet([iterable], [comparator])

iterable - optional

An Array or other iterable object whose elements values. Each value is added to the new set; null values are treated as undefined.

comparator - optional

Specifies a function that defines the sort order. If omitted, the contents are sorted according by natural order of the values.

If a and b are two elements being compared, then:

If comparator(a, b) is less than 0, sort a to an index lower than b, i.e. a comes first. If comparator(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. If comparator(a, b) is greater than 0, sort b to an index lower than a, i.e. b comes first. comparator(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned then the sort order is undefined.

SoSet API

You may want to refer to Javascript Set API for more context.

SoSet.prototype.add(value)

Appends a new element with the given value to the SoSet object. Returns the SoSet object.

SoSet.prototype.clear()

Removes all elements from the SoSet object.

SoSet.prototype.delete(value)

Removes the element associated to the value and returns the value that SoSet.prototype.has(value) would have previously returned. SoSet.prototype.has(value) will return false afterwards.

SoSet.prototype.entries()

Returns a new Iterator object that contains an array of [value, value] for each element in the SoSet object, in defined order. This is kept similar to the Map object, so that each entry has the same value for its key and value here.

SoSet.prototype.forEach(callbackFn[, thisArg])

Calls callbackFn once for each value present in the SoSet object, in defined order. If a thisArg parameter is provided to forEach, it will be used as the this value for each callback.

SoSet.prototype.has(value)

Returns a boolean asserting whether an element is present with the given value in the SoSet object or not.

SoSet.prototype.values()

Returns a new Iterator object that contains the values for each element in the SoSet object in defined order.

SoSet.prototype[@@iterator]()

Returns a new Iterator object that contains the values for each element in the SoSet object in defined order

SoSet.prototype.min()

Returns the minimum value of the SoSet object

SoSet.prototype.max()

Returns the maximum value of the SoSet object

Tests

The tests for this code require npm and Jest to be installed on the machine. With that, tests will be fired by issuing

npm test

from inside the working directory.

The working directory contains a pre-commit.sh script. When you create a symbol link to the git pre-commit hook via

ln -s ../../pre-commit.sh .git/hooks/pre-commit

The Jest tests will be run before any commit. In case the tests fail, a commit will not be possible. In order to make this pre-commit behavior available in Tower for Mac, an environment.plist file needs to be created in the ~/Library/Application Support/com.fournova.Tower2 directory. That environment.plist needs to contain the $PATH setting of your shell. Here is an example how the environment.plist could look like:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
  <dict>
    <key>PATH</key>
        <string>/usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin</string>
  </dict>
</plist>