sano

Overview

Sano is a library of Lua data structures and algorithms.

Among the highlights are: Several sequence types, including the humble Tuple (a lightweight, hashable table wrapper), Vector (slightly more industrial strength table wrapper, including negative indexing), QueueVector (random access + efficient inserts at head OR tail), a basic LinkedList, and SkipVector (a skip-list based random access sequence with efficient inserts or removals at ANY position).

The library also includes several map implementations: among them the basic HashMap (a table-based map with plenty of convenience methods and support for user-defined hashing functions), an ordered, mergeable, spliceable SkipMap, and a LinkedMap (iteration order same as insertion order). For each of these map types, Sano also has the parallel set type - HashSet, SkipSet, LinkedSet.

In addition, the library contains a PairingHeap (constant-time mergeable heap), Multimap (implements one to many mappings), Multiset (ordered or unordered), and numerous algorithms and utility functions for working with all the data structures in the library.

To get help on any object, function, or module, sano.summary(obj) prints a brief one sentance description of obj, and, if obj is an object or module, a brief one sentance description of each of the methods of the object or functions of the module. sano.doc(obj) prints full documentation for obj.

Summary

`HashMap`	Table-based implementation of a map with support for user-defined hash functions and nil values.
`HashSet`	Table-based set implementation with support for user defined hash functions and nil elements.
`LinkedList`	Basic doubly linked list implementation.
`LinkedMap`	Map implementation in which iteration order is same as insertion order.
`LinkedSet`	Set implementation in which iteration order is same as insertion order.
`Multimap`	Map in which each key maps to a collection of values.
`Multiset`	Collection in which duplicate elements are not explicitly stored.
`PairingHeap`	Heap implementation with constant-time merge and get-first operations.
`Phonebook`	An ordered map based on SkipMap which allows duplicate keys.
`QueueVector`	Table-based vector implementation with efficient (amortized O(1)) inserts and removals at both the start and end of the vector.
`SkipMap`	An ordered map implementation with performance characteristics similar to a balanced binary tree.
`SkipSet`	Ordered set implementation based on SkipMap.
`SkipVector`	Skip-list implementation of a general purpose vector.
`Tuple`	A lightweight sequence type mainly for use as keys in a map or as elements of a set.
`Vector`	Table implementation of a general purpose vector.
`collections`	Module containing methods shared by multiple collection implementations.
`doc`	Prints the full documentation for obj.
`heaps`	Module containing methods shared across heap implementations.
`iter`	A collection of useful functions for working with iterators and iterable objects.
`makers`	Table of convenience functions for accessing the value constructors of Sano data structures.
`maps`	Module containing methods shared across map implementations.
`oop`	Internally used module for miscellaneous object-oriented programming support functions.
`ordering`	A collection of utility functions and algorithms for working with ordered data.
`sequences`	Module containing methods shared across sequence implementations.
`sets`	Module containing methods shared across set implementations.
`summary`	Prints a brief, one sentance description of obj, and, if obj is an object or module, a brief one sentance description of each of the methods of the object or functions of the module.
`testAll`	Runs unit tests on all modules in the Sano library.
`utils`	A collection of miscellaneous utility functions.

Detail

`sano.doc(obj)`

Prints the full documentation for obj.

`sano.makers`

Table of convenience functions for accessing the value constructors of Sano data structures.

These function exist only to make creating data structures less verbose. Each function in sano.makers returns class:make(...) for some class.

The mapping between function name and class is as follows:

vector             = Vector,
list, skipvector   = SkipVector,
queue, queuevector = QueueVector,
llist, linkedlist  = LinkedList,
heap, pairingheap  = PairingHeap,
set, hset, hashset = HashSet,
oset, orderedset   = SkipSet,
lset, linkedset    = LinkedSet,
map, hmap, hashmap = HashMap,
omap, orderedmap   = SkipMap,
lmap, linkedmap    = LinkedMap,
phonebook          = Phonebook,
multiset, mset     = Multiset,
multimap, mmap     = Multimap,
tuple              = Tuple

Examples:

v = vector(1,2,3,4) <-->   v = Vector:make(1,2,3,4)
sl = list(1,2,3,4)  <-->   sl = SkipVector:make(1,2,3,4)
q = queue(1,2,3,4)  <-->   q = QueueVector:make(1,2,3,4)
ll = llist(1,2,3,4) <-->   ll = LinkedList:make(1,2,3,4)
s = set(1,2,3,4)    <-->   s = HashSet:make(1,2,3,4)

`sano.summary(obj)`

Prints a brief, one sentance description of obj, and, if obj is an object or module, a brief one sentance description of each of the methods of the object or functions of the module.

`sano.testAll()`

Runs unit tests on all modules in the Sano library.