An abstract table api with various mutable and immmutable concrete implementations, such as property lists, association lists, hash tables, and balanced trees.
You will need alexandria, closer-mop, named-let, series, and str
-
Clone this repository into
~/quicklisp/local-projects/ -
(ql:quickload "table")
Four implementation strategies are provided, with a mutable and immutable variant for each strategy. Tables are instances of classes of the appropriate strategy. immutable- tables can never be side effected, and an error is signalled on any attempt to do so.
alist-table
immutable-alist
- a table implemented as an association list
- operations on alists are typically linear in the number of entries, but fast enough for small tables
hash-table
immutable-hash-table
- a table implemented as a hash-table
- many operations on hash tables are O(1), but hash tables waste space
- some operations on hash tables are O(n)
plist-table
immutable-plist
- a table implemented as a property list
- operations on plists are typically linear in the number of entries, but fast enough for small plists
- keys are always compared with eql
wttree-table
immutable-wttree
- a table implemented as a weight-balanced tree
- operations on weight-balanced trees are typically O(log n) in the number of entries, leading to algoriths almost as fast as a hash table.
- Entries preserve order of keys, so finding the smallest and largest key in the table is O(log n)
In addition, a symbol may be used as a table. The entries are stored in the property list of the symbol.
Tables are constructed ab initio by instantiating the appropriate class. If no initargs are suppled, an empty table with default properties is constructed. The following initargs are valid:
:testspecifies the key equivalance predicate for the table. plist-tables ignore this and always use'eql:initial-contentsspecifies an initial set of entries to be placed in the table. This may be specified as an association list, a property list, a hash table, or another instance of a table object.
make-instance implementation &rest initargs
Create a table.
tablep object
table? object
Returns T iff object is a table.
table/immutable? object
table/immutablep object
Returns T if object is an immutable table.
table/empty? table
Returns T if there are no entries in table.
table/equal? table1 table2 &optional (test #'eql)
Returns T if table1 and table2 contain the same entries. Entry keys are compared by the key compare function associated with table1. Entry values are compared using test. This operation is quite expensive as it must iterate through all entries in both tables.
table/subset? subtable supertable &optional (test #'eql)
Returns T if every entry in subtable is contained in supertable. Entry values are compare using test. This operation takes O(n)*O(lookup)
metadata table
Returns a plist associated with the table that can be used for metadata. Guaranteed to not be used by the implementation.
representation table
Returns the underlying representation of the table (an alist, plist, hashtable, or wttree-node). If used on an immutable table, a copy of the representation is returned.
table/keys table
Returns a list of the keys in table. List structure may be shared, so do not modify it. O(n) in the number of entries in the table.
table/values table
Returns a list of the values in table. List structure may be shared, so do not modify it. O(n) in the number of entries in the table.
table/size table
Returns the number of entries in table. O(1) for hash tables and trees, O(n) for alists and plists.
table/test table
Returns the predicate used to compare keys in table.
do-table (key value table &optional (retval nil)) &body body
Iterate over key, value pairs in table running body on each pair. Return retval when done.
These operations modify the table object and possibly modify any shared data structures within in the table. An error is signalled if one of these is called on an immutable table.
table/clear! table
Delete all entries from table. O(1) for alists, plists, and wttrees. O(n) for hash tables.
table/delete table key
table/remove! table key
Delete the entry associated with key from table.
table/insert! table key value
Insert a new entry mapping key to value in table. If key refers to an old value, it is overwritten.
table/pop-maximum! table
Returns two values, the greatest key and its associated value. The entry associated with this key and value is deleted from the table.
table/pop-minimum! table
Returns two values, the least key and its associated value. The entry associated with this key and value is deleted from the table.
table/union! left right
Adds to left those entries in right that do not already appear in left.
table/union-merge! left right merge-fn
Adds to left the entries in right. If an entry appears in both, merge-fn is called to merge the values.
These operations leave their arguments unmodified. The results may share storage with the arguments. These operations can be inefficient if they need to copy their arguments.
fold-table procedure init table
procedure takes three arguments, the result of the previous fold step, a key, and a value.
table/clear table
Returns a table like the argument, but with no entries.
table/copy table
Returns a copy of table that shares no storage with table. Destructive operations on the copy will not cause side effects on the original. Table keys and values, however, are not copied.
table/insert table key value
Returns a new table with additional entry of key associated with value. Original table is unmodified, but storage may be shared with original table.
table/lookup table key &optional default
Returns the value associated with key if it is in the table, _default if it is not.
table/maximum table
Returns two values, the largest key in table, and its associated value.
table/minimum table
Returns two values, the smallest key in table, and its associated value.
table/pop-maximum table
Returns three values, the largest key in table, its associated value, and table without an entry for that key. New table may share storage with original table. Original table is not modified.
table/pop-minimum table
Returns three values, the smallest key in table, its associated value, and table without an entry for that key. New table may share storage with original table. Original table is not modified.
table/remove table key
Returns a new table without an entry for key. Original table is not modified. Returned table may share storage with original table.
table/split-gt table pivot
Returns a new table with only those entries greater than pivot.
table/split-lt table pivot
Returns a new table with only those entries less than pivot.
table/union left right
Returns a new table with all the entries in left and any entries in right that do not already appear in left.
table/union-merge left right merge-fn
Returns a new table with all the entries in left and all entries in right. Entries in both are passed to merge-fn to determine the value in the result.
table->alist table
Return table as an association list. Resulting alist may share storage with table.
table->hash-table table
Return table as a hashtable. Resulting hashtable by share storage with table.
table->plist table
Return table as a property list. Resulting plist may share storage with table.
change-class table new-table-class
Modifies the implementation class for the table instance. You cannot change a symbol to a new class, however.