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

HashMapTable-based implementation of a map with support for user-defined hash functions and nil values.
HashSetTable-based set implementation with support for user defined hash functions and nil elements.
LinkedListBasic doubly linked list implementation.
LinkedMapMap implementation in which iteration order is same as insertion order.
LinkedSetSet implementation in which iteration order is same as insertion order.
MultimapMap in which each key maps to a collection of values.
MultisetCollection in which duplicate elements are not explicitly stored.
PairingHeapHeap implementation with constant-time merge and get-first operations.
PhonebookAn ordered map based on SkipMap which allows duplicate keys.
QueueVectorTable-based vector implementation with efficient (amortized O(1)) inserts and removals at both the start and end of the vector.
SkipMapAn ordered map implementation with performance characteristics similar to a balanced binary tree.
SkipSetOrdered set implementation based on SkipMap.
SkipVectorSkip-list implementation of a general purpose vector.
TupleA lightweight sequence type mainly for use as keys in a map or as elements of a set.
VectorTable implementation of a general purpose vector.
collectionsModule containing methods shared by multiple collection implementations.
docPrints the full documentation for obj.
heapsModule containing methods shared across heap implementations.
iterA collection of useful functions for working with iterators and iterable objects.
makersTable of convenience functions for accessing the value constructors of Sano data structures.
mapsModule containing methods shared across map implementations.
oopInternally used module for miscellaneous object-oriented programming support functions.
orderingA collection of utility functions and algorithms for working with ordered data.
sequencesModule containing methods shared across sequence implementations.
setsModule containing methods shared across set implementations.
summaryPrints 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.
testAllRuns unit tests on all modules in the Sano library.
utilsA 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.