#lang scribble/doc @(require scribble/manual scribble/eval (for-label scheme) (for-label (prefix-in set: "set.ss")) (for-label (prefix-in bag: "bag.ss")) (for-label (prefix-in table: "table.ss")) (for-label srfi/67)) @title{Data Structures Galore} @author[@author+email["Carl Eastlund" "cce@ccs.neu.edu"] @author+email["Jens Axel Soegaard" "jensaxel@soegaard.net"] @author+email["Stevie Strickland" "sstrickl@ccs.neu.edu"]] This library implements commonly used immutable data structures. Currently Galore provides: @itemize[ @item{@as-index{Sets} (collections of distinct elements).} @item{@as-index{Bags} (a.k.a. multi-sets, collections of elements).} @item{@as-index{Tables} (finite mappings from distinct keys to arbitrary values).} ] @(table-of-contents) @section{Introduction} This library implements commonly used immutable data structures. Currently Galore provides: @itemize[ @item{@as-index{Sets} (collections of distinct elements).} @item{@as-index{Bags} (a.k.a. multi-sets, collections of elements).} @item{@as-index{Tables} (finite mappings from distinct keys to arbitrary values).} ] (Other data structures provided by previous versions of Galore will be added in time. The previous versions of Galore will continue to be available in PLaneT.) These data structures are immutable, meaning that no operation alters its input. Instead, each operation produces a new data structure, often sharing some of its structure with its input. This means that old values remain valid until they are garbage collected and that these structures are safe for multi-threaded programs. Each data structure can have multiple implementations. The primary module for each data structure provides one or more constructors for each implementation, and operations which work for any of the implementations. Different implementations may operate on different kinds of data, provide different invariants, or have different time/space efficiency tradeoffs. The operations for each data structure are provided by names describing only their purpose (and not their kind of data structure). To prevent clashes with each other and with existing Scheme operations, it is recommended to import these modules with a prefix: @schemeblock[ (require (prefix-in set: (planet soegaard/galore:4:1/set)) (prefix-in bag: (planet soegaard/galore:4:1/bag)) (prefix-in table: (planet soegaard/galore:4:1/table)))] Data structures are implemented in the MzScheme class system (see documentation for @filepath{class.ss}). Each kind of data structure is an interface, each implementation is a class, and each operation is a method. Users can write their own implementation of Galore data structures by writing classes that implement the given interfaces. So long as new implementations adhere to the interfaces and expected invariants, the functions provided by Galore will work with them and they will be interoperable with all other Galore data structures. @subsection{Previous Versions} Galore version 2 supports the following datastructures: @as-index{sets}, @as-index{bags}, @as-index{heaps}, @as-index{finite maps}, @as-index{priority queues}, @as-index{stacks}, @as-index{queues}, @as-index{deques}. For any datastructures or operations not yet provided by Galore version 3, use the previous version: @schemeblock[(require (planet "FILE.scm" ("soegaard" "galore.plt" 2)))] The @PLaneT server contains the @link["http://planet.plt-scheme.org/display.ss?package=galore.plt&owner=soegaard"]{documentation and code} for the earlier versions of Galore. @section{Sets} @defmodule[(planet soegaard/galore:4:1/set)] A set is a collection of elements. @defproc[(set? (v any/c)) boolean?]{ Predicate for sets. } @defthing[set/c flat-contract?]{ Contract for sets of arbitrary objects. } @deftogether[ (@defproc[(set-of/c (elem/c flat-contract?)) flat-contract?] @defproc[(non-empty-set-of/c (elem/c flat-contract?)) flat-contract?])]{ Contracts for sets whose contents match @scheme[elem/c]} @subsection{Set Constructors} A set implementation must have a way to distinguish its elements (how to tell whether one element is the same as another). Some implementations need to know more about their elements, and use this to provide better invariants. Each implementation provides two constructors. The first accepts set elements as additional arguments. The second accepts set elements as a list. Unordered sets require an equality predicate for their elements. Most single element operations will complete in linear time. Unordered sets have two constructors: @deftogether[ (@defproc[(make-unordered (elem=? (-> any/c any/c boolean?)) (elem any/c) ...) set?] @defproc[(list->unordered (elem=? (-> any/c any/c boolean?)) (elems (listof any/c))) set?])]{ These operations construct a set containing the given elements as distinguished by elem=?.} Ordered sets require a total ordering for their elements. These orderings are represented as comparisons in the SRFI 67 style. A comparison produces @scheme[0] if its arguments are equal, @scheme[1] if the first argument is greater, and @scheme[-1] if its second argument is greater. Most single element operations will complete in logarithmic time. Ordered sets have two constructors: @deftogether[ (@defproc[(make-ordered (elem-compare (-> any/c any/c (integer-in -1 1))) (elem any/c) ...) set?] @defproc[(list->ordered (elem-compare (-> any/c any/c (integer-in -1 1))) (elems (listof any/c))) set?])]{ These operations construct a set containing the given elements as distinguished by @scheme[elem-compare]. Operations which traverse the set will traverse the elements in increasing order.} Hashed sets group their elements by hash code; the hash function must respect the given equality predicate (equal values must have the same hash code). Operations will take time logarithmic in the number of distinct hash codes and linear in the number of elements in a single hash code. Hashed sets have two constructors: @deftogether[ (@defproc[(make-hashed (elem-hash (-> any/c integer?)) (elem=? (-> any/c any/c boolean?)) (elem any/c) ...) set?] @defproc[(list->hashed (elem-hash (-> any/c integer?)) (elem=? (-> any/c any/c boolean?)) (elems (listof any/c))) set?])]{ These operations construct a set containing the given elements as distinguished by @scheme[elem=?].} Galore also provides six shortcut constructors for sets whose elements are distinguished by the standard Scheme comparisons eq?, eqv?, and equal?. @deftogether[ (@defproc[(make-eq (elem any/c) ...) set?] @defproc[(list->eq (elems (listof any/c))) set?])]{ These operations construct a hashed set containing the given elements as distinguished by eq?.} @deftogether[ (@defproc[(make-eqv (elem any/c) ...) set?] @defproc[(list->eqv (elems (listof any/c))) set?])]{ These operations construct an unordered set containing the given elements as distinguished by eqv?.} @deftogether[ (@defproc[(make-equal (elem any/c) ...) set?] @defproc[(list->equal (elems (listof any/c))) set?])]{ These operations construct a hashed set containing the given elements as distinguished by equal?.} @subsection{Set Accessors} These operations extract information from a set. @defproc[(elements (set set?)) (listof any/c)]{ Produces a list of all of @scheme[set]'s elements. The elements are in increasing order for ordered sets.} @defproc[(empty? (set set?)) boolean?]{ Reports whether @scheme[set] contains no elements.} @defproc[(size (set set?)) natural-number/c]{ Produces the number of elements in @scheme[set].} @defproc[(member? (elem any/c) (set set?)) boolean?]{ Reports whether @scheme[set] contains @scheme[elem].} @defproc[(lookup (elem any/c) (set set?) (failure-thunk (-> any) (lambda () #f)) (success-function (-> any/c any) (lambda (e) e))) any/c]{ Finds an element in @scheme[set] that is equal to @scheme[elem]. If such an element @scheme[e] is found, lookup produces @scheme[(success-function e)]. If no such element is found, lookup produces @scheme[(failure-thunk)]. The default success-function returns @scheme[e]. The default failure-thunk returns @scheme[#f].} @defproc[(select (set set?)) any/c]{ Produces an element from the non-empty set. It is unspecified which element is produced.} @subsection{Set Updaters} These operations construct updated forms of their input set. The result is always of the same implementation as the input. @defproc[(insert (elem any/c) (set set?)) set?]{ Produces a @scheme[set] containing @scheme[elem] and all elements of @scheme[set].} @defproc[(remove (elem any/c) (set set?)) set?]{ Produces a set containing all elements of @scheme[set] except @scheme[elem].} @defproc[(clear (set set?)) set?]{ Produces an empty set.} @subsection{Set Traversals} These operations work on each element of a set. Each traversal works on elements in the same order they are produced by the elements operation. @defproc[(fold (combine (-> any/c any/c any)) (init any/c) (set set?)) any/c]{ Builds a result from set's elements. If @scheme[(elements set)] is @scheme[(list e1 e2 ... en)], the result is @scheme[(combine en ... (combine e2 (combine e1 init))...)].} @defproc[(map (transform (-> any/c any)) (set set?)) set?]{ Produces a new set containing the transformed image of each element of @scheme[set].} @defproc[(for-each (action (-> any/c any)) (set set?)) any/c]{ Calls @scheme[action] for each element of @scheme[set].} @defproc[(filter (predicate (-> any/c boolean?)) (set set?)) set?]{ Produces a set containing the elements of @scheme[set] that satisfy @scheme[predicate]. The result is of the same implementation as @scheme[set].} @deftogether[ (@defproc[(all? (predicate (-> any/c boolean?)) (set set?)) boolean?] @defproc[(andmap (predicate (-> any/c boolean?)) (set set?)) boolean?])]{ Reports whether all elements of @scheme[set] satify @scheme[predicate]. These operations are synonymous.} @deftogether[ (@defproc[(any? (predicate (-> any/c boolean?)) (set set?)) boolean?] @defproc[(ormap (predicate (-> any/c boolean?)) (set set?)) boolean?])]{ Reports whether any element of @scheme[set] satisfies @scheme[predicate]. These operations are synonymous.} @subsection[#:tag "Subsec:SetCombinations"]{Set Combinations} These operations represent set-theoretic operations combining multiple sets. In all cases, the result is of the same implementation as the first set argument. Multiple sets may only be combined if their notions of distinct elements are the same. If two sets with different equality are combined the result will be unpredictable and may yield an error. Here are some concrete examples: @itemize[ @item{@scheme[(make-unordered = 1 2 3)] and @scheme[(make-ordered number-compare 4 5 6)] may be combined, because @scheme[=] and @scheme[number-compare] represent the same equality relation. Both will distinguish numbers based on numerical equivalence.} @item{@scheme[(make-equal "A" "B" "C")] and @scheme[(make-eq "A" "B" "C")] may not be combined, because @scheme[equal?] and @scheme[eq?] do not represent the same equality relation. Specifically, it is ambiguous whether both @scheme["A"]s represent equivalent elements.}] @defproc[(union (set1 set?) (set2 set?) (combine (-> any/c any/c any) (lambda (e1 e2) e1))) set?]{ Produces a set containing all elements present in either @scheme[set1] or @scheme[set2]. If @scheme[set1] and @scheme[set2] contain equivalent elements @scheme[e1] and @scheme[e2] respectively, union adds @scheme[(combine e1 e2)] to the result in their place. The default combine returns @scheme[e1].} @defproc[(intersection (set1 set?) (set2 set?) (combine (-> any/c any/c any) (lambda (e1 e2) e1))) set?]{ Produces a set containing all elements present in both @scheme[set1] and @scheme[set2]. For each pair of equivalent elements @scheme[e1] and @scheme[e2] found in @scheme[set1] and @scheme[set2] respectively, intersection adds @scheme[(combine e1 e2)] to the result. The default @scheme[combine] returns @scheme[e1].} @defproc[(difference (set1 set?) (set2 set?)) set?]{ Produces a set containing all elements of @scheme[set1] not found in @scheme[set2].} @subsection{Set Relations} These operations compare multiple sets. As in @secref["Subsec:SetCombinations"], multiple sets may only be meaningfully compared if their notions of distinct elements are the same. @defproc[(subset? (set1 set?) (set2 set?)) boolean?]{ Reports whether all elements in @scheme[set1] are present in @scheme[set2].} @defproc[(equal? (set1 set?) (set2 set?)) boolean?]{ Reports whether both sets contain the same elements.} @subsection{Sets and Eager Comprehensions} @defmodule[(planet soegaard/galore:4:1/comprehensions)] Support for srfi-42 eager comprehensions are provided by @filepath{comprehensions.ss}'s comprehension @scheme[set-ec] and generator @scheme[:set]. @defform[(set-ec empty-expr qualifier ... expr)]{ The comprehension @scheme[set-ec] evaluates the expression @scheme[empty-expr] whose result must be an empty set. Then the values obtained by evaluating @scheme[expr] once for each binding are inserted into the set. If there are no qualifiers the result is a singleton set whose element is the result of evaluating @scheme[expr].} @defform[(:set var arg)]{ The generator @scheme[:set] runs through the elements in a set. First @scheme[arg] is evaluated then the variable @scheme[var] is bound to each element of the set in turn. The effect of assigning a value to @scheme[var] is undefined.} An example: @interaction[ (require (prefix-in set: (planet "set.ss" ("soegaard" "galore.plt" 4 1))) (planet "comprehensions.ss" ("soegaard" "galore.plt" 4 1)) (lib "42.ss" "srfi") (lib "67.ss" "srfi")) (define a-set (set-ec (set:make-ordered integer-compare) (:range i -5 5) (* i i))) (set:elements a-set) (list-ec (:set x a-set) x) (list-ec (: x a-set) x)] @section{Tables} @defmodule[(planet soegaard/galore:4:1/table)] A @deftech{table} is a finite mapping from distinct keys to distinct values. A single key/value pair in a table is called a @deftech{binding}. Galore provides the following operations for creating and manipulating tables. @subsection{Table Predicates} These operations determine whether values are tables. @defproc[(table? (v any/c)) boolean?]{Basic predicate for tables.} @deftogether[ (@defthing[table/c flat-contract?] @defthing[non-empty-table/c flat-contract?])]{ These contracts accept tables. The @scheme[non-empty-table/c] contract requires tables to contain at least one binding.} @deftogether[ (@defproc[(table-of/c (key/c flat-contract?) (value/c flat-contract?)) flat-contract?] @defproc[(non-empty-table-of/c (key/c flat-contract?) (value/c flat-contract?)) flat-contract?])]{ These produce a contract that accepts tables of with bindings matching the given contracts. The result of @scheme[non-empty-table-of/c] requires tables to contain at least one binding.} @subsection{Table Constructors} A table implementation must be able to distinguish its keys just like a set implementation must distinguish its elements. Like sets, tables have different implementations that require different information about their keys. Each implementation provides four constructors. The first accepts bindings as additional arguments, alternating keys and values. The second accepts bindings as an s-expression: a list of two-element lists, each a key followed by a value. The third accepts bindings as an association list of key/value pairs. The last accepts bindings as a list of keys and a separate list of their respective values. @deftogether[ (@defproc[(make-unordered (key=? (-> any/c any/c boolean?)) (key any/c) (value any/c) ...) table?] @defproc[(sexp->unordered (key=? (-> any/c any/c boolean?)) (sexp (listof (listof any/c any/c)))) table?] @defproc[(alist->unordered (key=? (-> any/c any/c boolean?)) (alist (listof (cons/c any/c any/c)))) table?] @defproc[(lists->unordered (key=? (-> any/c any/c boolean?)) (keys (listof any/c)) (values (listof any/c))) table?])]{ Unordered tables require an equality predicate for their keys. Most single-binding operations will complete in linear time. Keys are distinguished by @scheme[key=?].} @deftogether[ (@defproc[(make-ordered (key-compare (-> any/c any/c (integer-in -1 1))) (key any/c) (value any/c) ...) table?] @defproc[(sexp->ordered (key-compare (-> any/c any/c (integer-in -1 1))) (sexp (listof (listof any/c any/c)))) table?] @defproc[(alist->ordered (key-compare (-> any/c any/c (integer-in -1 1))) (alist (listof (cons/c any/c any/c)))) table?] @defproc[(lists->ordered (key-compare (-> any/c any/c (integer-in -1 1))) (keys (listof any/c)) (values (listof any/c))) table?])]{ Ordered tables require a total ordering for their keys. These orderings are represented as comparisons in the SRFI 67 style (see description for ordered sets, above). Most single-binding operations will complete in logarithmic time. Operations which traverse the table will traverse the bindings in increasing order of their keys.} @deftogether[ (@defproc[(make-hashed (key-hash (-> any/c integer?)) (key=? (-> any/c any/c boolean?)) (key any/c) (value any/c) ...) table?] @defproc[(sexp->hashed (key-hash (-> any/c integer?)) (key=? (-> any/c any/c boolean?)) (sexp (listof (listof any/c any/c)))) table?] @defproc[(alist->hashed (key-hash (-> any/c integer?)) (key=? (-> any/c any/c boolean?)) (alist (listof (cons/c any/c any/c)))) table?] @defproc[(lists->hashed (key-hash (-> any/c integer?)) (key=? (-> any/c any/c boolean?)) (keys (listof any/c)) (values (listof any/c))) table?])]{ Hashed tables group their keys by hash code; the hash function must respect the given equality predicate (equal keys must have the same hash code). Operations will take time logarithmic in the number of distinct hash codes and linear in the number of keys in a single hash code. These operations construct a table containing the given bindings with keys distinguished by @scheme[key=?]. } @deftogether[ (@defproc[(make-eq (key any/c) (value any/c) ...) table?] @defproc[(sexp->eq (sexp (listof (listof any/c any/c)))) table?] @defproc[(alist->eq (alist (listof (cons/c any/c any/c)))) table?] @defproc[(lists->eq (keys (listof any/c)) (values (listof any/c))) table?] @defproc[(make-eqv (key any/c) (value any/c) ...) table?] @defproc[(sexp->eqv (sexp (listof (listof any/c any/c)))) table?] @defproc[(alist->eqv (alist (listof (cons/c any/c any/c)))) table?] @defproc[(lists->eqv (keys (listof any/c)) (values (listof any/c))) table?] @defproc[(make-equal (key any/c) (value any/c) ...) table?] @defproc[(sexp->equal (sexp (listof (listof any/c any/c)))) table?] @defproc[(alist->equal (alist (listof (cons/c any/c any/c)))) table?] @defproc[(lists->equal (keys (listof any/c)) (values (listof any/c))) table?])]{ Galore also provides shortcut constructors for tables whose keys are distinguished by the standard Scheme comparisons @scheme[eq?], @scheme[eqv?], and @scheme[equal?].} @subsection{Table Accessors} @defproc[(keys (table table?)) (listof any/c)]{ Produces a list of @scheme[table]'s keys. For ordered tables, the keys are sorted from least to greatest.} @defproc[(values (table table?)) (listof any/c)]{ Produces a list of @scheme[table]'s values. The values appear in the same order as their respective keys in @scheme[(keys table)].} @defproc[(to-sexp (table table?)) (listof (listof any/c any/c))]{ Produces a list of table's bindings as two-element lists, each a key followed by its value. The bindings appear in the same order as their respective keys in @scheme[(keys table)].} @defproc[(empty? (table table?)) boolean?]{@scheme[#f] unless @scheme[table] is empty} @defproc[(size (table table?)) natural-number/c]{Produces the number of bindings in @scheme[table].} @defproc[(contains? (key any/c) (table table?)) boolean?]{Reports whether table contains @scheme[key].} @defproc[(lookup (key any/c) (table table?) (failure-thunk (-> any) (lambda () #f)) (success-function (-> any/c any) (lambda (value) value))) any/c]{ Looks up the value bound to @scheme[key] in table. If such a value @scheme[v] is found, lookup produces @scheme[(success-function v)]. If no such value is found, lookup produces @scheme[(failure-thunk)]. The default @scheme[success-function] returns @scheme[v]. The default @scheme[failure-thunk] returns @scheme[#f].} @defproc[(lookup/key (key any/c) (table table?) (failure-thunk (-> any) (lambda () #f)) (success-function (-> any/c any/c any) (lambda (key value) key))) table?]{ Looks up the binding for @scheme[key] in table. If a binding of @scheme[k] to @scheme[v] is found, @scheme[lookup/key] produces @scheme[(success-function k v)]. If no such binding is found, @scheme[lookup/key] produces @scheme[(failure-thunk)]. The default @scheme[success-function] returns @scheme[k]. The default @scheme[failure-thunk] returns @scheme[#f].} @deftogether[ (@defproc[(select (table table?)) (values any/c any/c)] @defproc[(select/key (table table?)) any/c] @defproc[(select/value (table table?)) any/c])]{ These operations select a binding from a non-empty table, returning its key, value, or both as appropriate. It is not specified which binding is chosen.} @subsection{Table Updaters} These operations construct updated forms of their input table. The result is always of the same implementation as the input. @defproc[(insert (key any/c) (value any/c) (table table?)) table?]{ Produces a table in which @scheme[key] is bound to @scheme[value] and containing all other bindings of @scheme[table].} @defproc[(remove (key any/c) (table table?)) table?]{ Produces a table containing all bindings of @scheme[table] except any binding for @scheme[key].} @defproc[(update (key any/c) (transform (-> any/c any/c any)) (table table?)) table?]{ Produces a table with all bindings of @scheme[table] except any binding for @scheme[key]. If @scheme[table] maps @scheme[k] to @scheme[v] (with @scheme[k] equal to @scheme[key]), the result maps @scheme[k] to @scheme[(transform k v)]. If @scheme[table] has no binding for @scheme[key], the result has none.} @defproc[(update/value (key any/c) (transform (-> any/c any)) (table table?)) table?]{ As @scheme[update], but produces a new value based only on the previous value.} @defproc[(update/insert (key any/c) (transform (-> any/c any/c any)) (value any/c) (table table?)) table?]{ Produces a table with all bindings of @scheme[table] except any binding for @scheme[key]. If table maps @scheme[key] to @scheme[v], the result maps @scheme[key] to @scheme[(transform v)]. If table has no binding for @scheme[key], the result maps @scheme[key] to @scheme[value].} @defproc[(update/insert/value (key any/c) (transform (-> any/c any)) (value any/c) (table table?)) table?]{ As @scheme[update/insert], but produces a new value based only on the previous value.} @defproc[(clear (table table?)) table?]{ Produces an empty table.} @subsection{Table Traversals} These operations work on each binding of a table. Each traversal works on bindings in the same order their keys are produced by the @scheme[keys] operation. Each traversal has three forms. The basic form processes they key and value of each binding. The @scheme[/key] form processes only the key of each binding. The @scheme[/value] form processes only the value of each binding. @deftogether[ (@defproc[(fold (combine (-> any/c any/c any/c any)) (init any/c) (table table?)) any/c] @defproc[(fold/key (combine/key (-> any/c any/c any)) (init any/c) (table table?)) any/c] @defproc[(fold/value (combine/value (-> any/c any/c any)) (init any/c) (table table?)) any/c])]{ These operations build a result from table's bindings. If @scheme[(keys table)] produces @scheme[(list k1 k2 ... kn)] and @scheme[(values table)] produces @scheme[(list v1 v2 ... vn)], the respective results will be: @schemeblock[ (combine kn vn ... (combine k2 v2 (combine k1 v1 init))...) (combine/key kn ... (combine/key k2 (combine/key k1 init))...) (combine/value vn ... (combine/value v2 (combine/value v1 init))...)]} @deftogether[ (@defproc[(for-each (action (-> any/c any/c any)) (table table?)) any/c] @defproc[(for-each/key (action/key (-> any/c any)) (table table?)) any/c] @defproc[(for-each/value (action/value (-> any/c any)) (table table?)) any/c])]{ These operations call @scheme[action] (or @scheme[action/key] or @scheme[action/value]) for each binding in @scheme[table].} @deftogether[ (@defproc[(map (transform (-> any/c any/c any)) (table table?)) table?] @defproc[(map/key (transform/key (-> any/c any)) (table table?)) table] @defproc[(map/value (transform/value (-> any/c any)) (table table?)) table])]{ These operations produce a table binding each key from @scheme[table] to the image of the previous binding produced by @scheme[transform] (or @scheme[transform/key] or @scheme[transform/value]). The result is of the same implementation as @scheme[table].} @deftogether[ (@defproc[(filter (predicate (-> any/c any/c boolean?)) (table table?)) table?] @defproc[(filter/key (predicate/key (-> any/c boolean?)) (table table?)) table?] @defproc[(filter/value (predicate/value (-> any/c boolean?)) (table table?)) table?])]{ These operations produce a table containing each binding in @scheme[table] that satisfies @scheme[predicate] (or @scheme[predicate/key] or @scheme[predicate/value]). The result is of the same implementation as @scheme[table].} @deftogether[ (@defproc[(all? (predicate (-> any/c any/c boolean?)) (table table?)) table?] @defproc[(all?/key (predicate/key (-> any/c boolean?)) (table table?)) table?] @defproc[(all?/value (predicate/value (-> any/c boolean?)) (table table?)) table?] @defproc[(andmap (predicate (-> any/c any/c boolean?)) (table table?)) table?] @defproc[(andmap/key (predicate/key (-> any/c boolean?)) (table table?)) table?] @defproc[(andmap/value (predicate/value (-> any/c boolean?)) (table table?)) table?])]{ Reports whether all bindings of @scheme[table] satisfy @scheme[predicate] (or @scheme[predicate/key] or @scheme[predicate/value]). The @scheme[all?] variants are synonymous with the @scheme[andmap] variants.} @deftogether[ (@defproc[(any? (predicate (-> any/c any/c boolean?)) (table table?)) table?] @defproc[(any?/key (predicate/key (-> any/c boolean?)) (table table?)) table?] @defproc[(any?/value (predicate/value (-> any/c boolean?)) (table table?)) table?] @defproc[(ormap (predicate (-> any/c any/c boolean?)) (table table?)) table?] @defproc[(ormap/key (predicate/key (-> any/c boolean?)) (table table?)) table?] @defproc[(ormap/value (predicate/value (-> any/c boolean?)) (table table?)) table?])]{ Reports whether any binding of @scheme[table] satisfies @scheme[predicate] (or @scheme[predicate/key] or @scheme[predicate/value]). The @scheme[any?] variants are synonmous with the @scheme[ormap] variants. } @subsection[#:tag "Subsec:TableCombinations"]{Table Combinations} These operations mimic set operations combining the bindings of multiple tables by their corresponding keys. In all cases, the result is of the same implementation as the first table argument. Multiple tables may only be combined if their notion of distinct keys are the same. If two tables with different equality are combined the result will be unpredictable and may yield an error. For concrete examples, see @secref["Subsec:SetCombinations"] above. @deftogether[ (@defproc[(union (table1 table?) (table2 table?) (combine (-> any/c any/c any/c any) (lambda (key value1 value2) value1))) table?] @defproc[(union/value (table1 table?) (table2 table?) (combine/value (-> any/c any/c any) (lambda (value1 value2) value1))) table?])]{ These operations produce a table containing all bindings present in either @scheme[table1] or @scheme[table2]. If @scheme[table1] and @scheme[table2] bind key @scheme[k] to values @scheme[v1] and @scheme[v2] respectively, @scheme[union] binds @scheme[k] to @scheme[(combine k v1 v2)] and @scheme[union/value] binds @scheme[k] to @scheme[(combine/value v1 v2)] in the result.} @deftogether[ (@defproc[(intersection (table1 table?) (table2 table?) (combine (-> any/c any/c any/c any) (lambda (key value1 value2) value1))) table?] @defproc[(intersection/value (table1 table?) (table2 table?) (combine/value (-> any/c any/c any) (lambda (key value1 value2) value1))) table?])]{ These operations produce a table containing all bindings present in both @scheme[table1] and @scheme[table2]. For each key @scheme[k] bound to values @scheme[v1] and @scheme[v2] in @scheme[table1] and @scheme[table2] respectively, @scheme[intersection] binds @scheme[k] to @scheme[(combine k v1 v2)] and @scheme[intersection/value] binds @scheme[k] to @scheme[(combine/value v1 v2)] in the result.} @defproc[(difference (table1 table?) (table2 table?)) table?]{Produces a table containing all bindings of table1 whose key is not in table2.} @subsection{Table Relations} These operations compare multiple tables. As in @secref["Subsec:TableCombinations"], multiple tables may only be meaningfully compared if their notions of distinct keys are the same. @defproc[(subtable? (value=? (-> any/c any/c boolean?)) (table1 table?) (table2 table?)) boolean?]{ Reports whether all keys in @scheme[table1] are present in @scheme[table2], and that the values bound to each key in both tables are the same with respect to @scheme[value=?].} @defproc[(equal? (value=? (-> any/c any/c boolean?)) (table1 table?) (table2 table?)) table?]{ Reports whether both tables contain the same keys, and that the values bound to each key in both tables are the same with respect to @scheme[value=?].} @section{Bags} @defmodule[(planet soegaard/galore:4:1/bag)] A @deftech{bag} is a collection of elements. Unlike sets, the elements in a bag need not be distinct. Galore provides the following operations for creating and manipulating bags. @subsection{Bag Predicates} @defproc[(bag? (v any/c)) boolean?]{Reports whether @scheme[v] is a bag.} @deftogether[ (@defthing[bag/c flat-contract?] @defthing[non-empty-bag/c flat-contract?])]{ These contracts accept bags. The @scheme[non-empty-bag/c] contract requires bags to contain at least one element.} @deftogether[ (@defproc[(bag-of/c (elem/c flat-contract?)) flat-contract?] @defproc[(non-empty-bag-of/c (elem/c flat-contract?)) flat-contract?])]{ These produce a contract that accepts bags, where @scheme[elem/c] accepts elements. The result of @scheme[non-empty-bag-of/c] requires bags to contain at least one element.} @subsection{Bag Constructors} A bag implementation must have a way to distinguish its elements (how to tell whether one element is the same as another). Some implementations need to know more about their elements, and use this to provide better invariants. Each implementation provides two constructors. The first accepts bag elements as additional arguments. The second accepts bag elements as a list. @deftogether[ (@defproc[(make-unordered (elem=? (-> any/c any/c boolean?)) (elem any/c) ...) bag?] @defproc[(list->unordered (elem=? (-> any/c any/c boolean?)) (elems (listof any/c))) bag?])]{ Unordered bags require an equality predicate for their elements. Most single element operations will complete in linear time. These operations construct a bag containing the given elements as distinguished by @scheme[elem=?].} @deftogether[ (@defproc[(make-ordered (elem-compare (-> any/c any/c (integer-in -1 1))) (elem any/c) ...) bag?] @defproc[(list->ordered (elem-compare (-> any/c any/c (integer-in -1 1))) (elems (listof any/c))) bag?])]{ Ordered bags require a total ordering for their elements. These orderings are represented as comparisons in the SRFI 67 style. A comparison produces @scheme[0] if its arguments are equal, @scheme[1] if the first argument is greater, and @scheme[-1] if its second argument is greater. Most single element operations will complete in logarithmic time. These operations construct a bag containing the given elements as distinguished by @scheme[elem-compare]. Operations which traverse the bag will traverse the elements in increasing order.} @deftogether[ (@defproc[(make-hashed (elem-hash (-> any/c integer?)) (elem=? (-> any/c any/c boolean?)) (elem any/c) ...) bag?] @defproc[(list->hashed (elem-hash (-> any/c integer?)) (elem=? (-> any/c any/c boolean?)) (elems (listof any/c))) bag?])]{ Hashed bags group their elements by hash code; the hash function must respect the given equality predicate (equal values must have the same hash code). Operations will take time logarithmic in the number of distinct hash codes and linear in the number of elements in a single hash code. These operations construct a bag containing the given elements as distinguished by @scheme[elem=?].} @deftogether[ (@defproc[(make-eq (elem any/c) ...) bag?] @defproc[(list->eq (elems (listof any/c))) bag?] @defproc[(make-eqv (elem any/c) ...) bag?] @defproc[(list->eqv (elems (listof any/c))) bag?] @defproc[(make-equal (elem any/c) ...) bag?] @defproc[(list->equal (elems (listof any/c))) bag?])]{ Galore also provides six shortcut constructors for bags whose elements are distinguished by the standard Scheme comparisons @scheme[eq?], @scheme[eqv?], and @scheme[equal?].} @subsection{Bag Accessors} These operations extract information from a bag. @defproc[(elements (bag bag?)) (listof any/c)]{Produces a list of all of the @scheme[bag]'s elements. The elements are in increasing order for ordered bags.} @defproc[(to-sexp (bag bag?)) (listof (list any/c natural-number/c))]{ Produces a list of lists where each list contains an element of the @scheme[bag] and how many times that element appears in the @scheme[bag]. The ordering is the same as for @scheme[(elements bag)].} @defproc[(to-alist (bag bag?)) (listof (cons/c any/c natural-number/c))]{ Produces a list of pairs where each pair contains an element of the @scheme[bag] and how many times that element appears in the @scheme[bag]. The ordering is the same as for @scheme[(elements bag)].} @defproc[(empty? (bag bag?)) boolean?]{Reports whether bag contains no elements.} @defproc[(size (bag bag?)) natural-number/c]{Produces the number of elements in bag.} @defproc[(size/unique (bag bag?)) natural-number/c]{Produces the number of distinct elements in the bag.} @defproc[(member? (elem any/c) (bag bag?)) boolean?]{Reports whether bag contains elem.} @defproc[(count (elem any/c) (bag bag?)) natural-number/c]{Produces the number of times the element appears in the bag. If it does not, then @scheme[0] is produced.} @defproc[(lookup (elem any/c) (bag bag?) (failure-thunk (-> any) (lambda () #f)) (success-function (-> any/c any) (lambda (e) e))) any/c]{ Finds an element in @scheme[bag] that is equal to @scheme[elem]. If such an element @scheme[e] is found, @scheme[lookup] produces @scheme[(success-function e)]. If no such element is found, @scheme[lookup] produces @scheme[(failure-thunk)]. The default @scheme[success-function] returns @scheme[e]. The default @scheme[failure-thunk] returns @scheme[#f].} @defproc[(lookup/count (elem any/c) (bag bag?) (failure-thunk (-> any) (lambda () #f)) (success-function (-> any/c natural-number/c any) (lambda (e c) e))) any/c]{ Finds an element in @scheme[bag] that is equal to @scheme[elem]. If such an element @scheme[e] is found, @scheme[lookup/count] produces @scheme[(success-function e c)] (where @scheme[c] is the element's count). If no such element is found, @scheme[lookup/count] produces @scheme[(failure-thunk)]. The default @scheme[success-function] returns @scheme[e]. The default @scheme[failure-thunk] returns @scheme[#f].} @defproc[(select (bag bag?)) any/c]{Produces an element from the non-empty @scheme[bag]. It is unspecified which element is produced.} @defproc[(select/count (bag bag?)) (values any/c natural-number/c)]{ Produces an element and its count from the non-empty @scheme[bag]. It is unspecified which element is produced.} @subsection{Bag Updaters} These operations construct updated forms of their input bag. The result is always of the same implementation as the input. @defproc[(insert (elem any/c) (bag bag?)) bag?]{ Produces a bag containing all elements of @scheme[bag], plus one more occurrence of @scheme[elem].} @defproc[(insert/count (elem any/c) (count natural-number/c) (bag bag?)) bag?]{ Produces a bag containing all elements of @scheme[bag], plus @scheme[n] more occurrences of @scheme[elem].} @defproc[(remove (elem any/c) (bag bag?)) bag?]{ Produces a bag containing all elements of @scheme[bag] except one less occurence of @scheme[elem], or no occurrences if @scheme[bag] had none.} @defproc[(remove/count (elem any/c) (n natural-number/c) (bag bag?)) bag?]{ Produces a bag containing all elements of @scheme[bag] except @scheme[n] fewer occurrences of @scheme[elem], or no occurrences if there were less than @scheme[n] occurrences.} @defproc[(clear (bag bag?)) bag?]{Produces an empty bag.} @subsection{Bag Traversals} These operations work on each element of a bag. Each traversal works on elements in the same order they are produced by the elements operation. @deftogether[ (@defproc[(fold (combine (-> any/c any/c any)) (init any/c) (bag bag?)) any/c] @defproc[(fold/count (combine (-> any/c natural-number/c any/c any)) (init any/c) (bag bag?)) any/c])]{ Builds a result from @scheme[bag]'s elements. If @scheme[(elements bag)] is @scheme[(list e1 e2 ... en)], the result is @scheme[(combine en ... (combine e2 (combine e1 init))...)].} @deftogether[ (@defproc[(map (transform (-> any/c any)) (bag bag?)) bag?] @defproc[(map/count (transform (-> any/c natural-number/c any)) (bag bag?)) bag?])]{ Produces a new bag containing the transformed image of each element of the bag.} @deftogether[ (@defproc[(for-each (action (-> any/c any)) (bag bag?)) bag?] @defproc[(for-each/count (action (-> any/c natural-number/c any)) (bag bag?)) bag?])]{ Calls @scheme[action] for each element of @scheme[bag].} @deftogether[ (@defproc[(filter (predicate (-> any/c boolean?)) (bag bag?)) bag?] @defproc[(filter/count (predicate/count (-> any/c natural-number/c boolean?)) (bag bag?)) bag?])]{ Produces a bag containing the elements of @scheme[bag] that satisfy @scheme[predicate]. The result is of the same implementation as bag.} @deftogether[ (@defproc[(all? (predicate (-> any/c boolean?)) (bag bag?)) boolean?] @defproc[(andmap (predicate (-> any/c boolean?)) (bag bag?)) boolean?] @defproc[(all?/count (predicate/count (-> any/c natural-number/c boolean?)) (bag bag?)) boolean?] @defproc[(andmap/count (predicate/count (-> any/c natural-number/c boolean?)) (bag bag?)) boolean?])]{ Reports whether all elements of bag satify predicate.} @deftogether[ (@defproc[(any? (predicate (-> any/c boolean?)) (bag bag?)) boolean?] @defproc[(ormap (predicate (-> any/c boolean?)) (bag bag?)) boolean?] @defproc[(any?/count (predicate/count (-> any/c natural-number/c boolean?)) (bag bag?)) boolean?] @defproc[(ormap/count (predicate/count (-> any/c natural-number/c boolean?)) (bag bag?)) boolean?])]{ Reports whether any element of bag satisfies predicate.} @subsection[#:tag "Subsec:BagCombinations"]{Bag Combinations} These operations represent bag-theoretic operations combining multiple bags. In all cases, the result is of the same implementation as the first bag argument. Multiple bags may only be combined if their notions of distinct elements are the same. If two bags with different equality are combined the result will be unpredictable and may yield an error. Here are some concrete examples: @itemize[ @item{@scheme[(make-unordered = 1 2 3)] and @scheme[(make-ordered number-compare 4 5 6)] may be combined, because @scheme[=] and @scheme[number-compare] represent the same equality relation. Both will distinguish numbers based on numerical equivalence.} @item{@scheme[(make-equal "A" "B" "C")] and @scheme[(make-eq "A" "B" "C")] may not be combined, because @scheme[equal?] and @scheme[eq?] do not represent the same equality relation. Specifically, it is ambiguous whether both @scheme["A"]s represent equivalent elements.}] @defproc[(union (bag1 bag?) (bag2 bag?)) bag?]{Produces a bag containing all elements present in either @scheme[bag1] or @scheme[bag2]. If @scheme[bag1] and @scheme[bag2] contain equivalent elements @scheme[e1] and @scheme[e2] respectively, union adds @scheme[e1] to the result in their place with a total number of occurrences equal to the maximum of either @scheme[e1]'s occurrences in @scheme[bag1] or @scheme[e2]'s occurrences in @scheme[bag2].} @defproc[(intersection (bag1 bag?) (bag2 bag?)) bag?]{Produces a bag containing all elements present in both @scheme[bag1] or @scheme[bag2]. If @scheme[bag1] and @scheme[bag2] contain equivalent elements @scheme[e1] and @scheme[e2] respectively, intersection adds @scheme[e1] to the result in their place with a total number of occurrences equal to the minimum of either @scheme[e1]'s occurrences in @scheme[bag1] and @scheme[e2]'s occurrences in @scheme[bag2].} @defproc[(difference (bag1 bag?) (bag2 bag?)) bag?]{Produces a bag containing all elements of @scheme[bag1] not found in @scheme[bag2]. This means that if an element appears in @scheme[bag1] @scheme[n] times and @scheme[bag2] @scheme[m] times, then the resulting bag will have @scheme[(- n m)] copies of the element (and will not contain it if @scheme[(>= m n)]).} @subsection{Bag Relations} These operations compare multiple bags. As in @secref["Subsec:BagCombinations"], multiple bags may only be meaningfully compared if their notions of distinct elements are the same. @defproc[(subbag? (bag1 bag?) (bag2 bag?)) boolean?]{Reports whether all elements in @scheme[bag1] are present in @scheme[bag2]. This includes checking that the number of times the element appears in @scheme[bag2] is at least as many as the number of times it appears in @scheme[bag1].} @defproc[(equal? (bag1 bag?) (bag2 bag?)) boolean?]{Reports whether both bags contain the same elements with the same number of occurrences.} @section{Acknowledgements} @itemize[ @item{The red-black trees implementation started as a port of Jean-Christophe Filliatre's Ocaml implementation.} @item{Versions 1 and 2 of Galore and its documentation were written entirely by Jens Axel Soegaard.} @item{Many thanks to Richard Cobbe and Sam Tobin-Hochstadt for helpful proofreading and functionality suggestions.}] @section{Copyright and License} For any questions not answered by this documentation, write to the PLT Scheme mailing list at: @link["mailto:plt-scheme@list.cs.brown.edu" "plt-scheme@list.cs.brown.edu"]. Alternately, contact one of the authors. This documentation and all source code of Galore are published under the terms of the @link["http://www.gnu.org/licenses/lgpl.html"]{GNU LGPL}. See @filepath{license.txt} and @filepath{lgpl.txt} in the Galore collection for more details. @bibliography[ @bib-entry[#:key "Ada" #:title "Implementing Sets Efficiently in a Functional Language" #:author "Stephen Adams" #:url "http://groups.csail.mit.edu/mac/users/adams/BB/index.html"] @bib-entry[#:key "Mar" #:title "Randomized Binary Search Trees" #:author "Conrado Martinez and Salvador Roura" #:url "http://portal.acm.org/citation.cfm?id=274812"] @bib-entry[#:key "Oka" #:title "Purely Functional Data Structures" #:author "Chris Okasaki" #:url "http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#cup98"] ] @(index-section)