diff options
Diffstat (limited to 'src/algebra/table.spad.pamphlet')
| -rw-r--r-- | src/algebra/table.spad.pamphlet | 265 |
1 files changed, 265 insertions, 0 deletions
diff --git a/src/algebra/table.spad.pamphlet b/src/algebra/table.spad.pamphlet new file mode 100644 index 00000000..4d073045 --- /dev/null +++ b/src/algebra/table.spad.pamphlet @@ -0,0 +1,265 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra table.spad} +\author{Stephen M. Watt, Barry Trager} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{domain HASHTBL HashTable} +<<domain HASHTBL HashTable>>= +)abbrev domain HASHTBL HashTable +++ Author: Stephen M. Watt +++ Date Created: 1985 +++ Date Last Updated: June 21, 1991 +++ Basic Operations: +++ Related Domains: Table, EqTable, StringTable +++ Also See: +++ AMS Classifications: +++ Keywords: +++ Examples: +++ References: +++ Description: +++ This domain provides access to the underlying Lisp hash tables. +++ By varying the hashfn parameter, tables suited for different +++ purposes can be obtained. + +HashTable(Key, Entry, hashfn): Exports == Implementation where + Key, Entry: SetCategory + hashfn: String -- Union("EQ", "UEQUAL", "CVEC", "ID") + + Exports ==> TableAggregate(Key, Entry) with + finiteAggregate + + Implementation ==> add + Pair ==> Record(key: Key, entry: Entry) + Ex ==> OutputForm + failMsg := GENSYM()$Lisp + + t1 = t2 == EQ(t1, t2)$Lisp + keys t == HKEYS(t)$Lisp + # t == HCOUNT(t)$Lisp + setelt(t, k, e) == HPUT(t,k,e)$Lisp + remove_!(k:Key, t:%) == + r := HGET(t,k,failMsg)$Lisp + not EQ(r,failMsg)$Lisp => + HREM(t, k)$Lisp + r pretend Entry + "failed" + + empty() == + MAKE_-HASHTABLE(INTERN(hashfn)$Lisp, + INTERN("STRONG")$Lisp)$Lisp + + search(k:Key, t:%) == + r := HGET(t, k, failMsg)$Lisp + not EQ(r, failMsg)$Lisp => r pretend Entry + "failed" + +@ +\section{domain INTABL InnerTable} +<<domain INTABL InnerTable>>= +)abbrev domain INTABL InnerTable +++ Author: Barry Trager +++ Date Created: 1992 +++ Date Last Updated: Sept 15, 1992 +++ Basic Operations: +++ Related Domains: HashTable, AssociationList, Table +++ Also See: +++ AMS Classifications: +++ Keywords: +++ Examples: +++ References: +++ Description: +++ This domain is used to provide a conditional "add" domain +++ for the implementation of \spadtype{Table}. + +InnerTable(Key: SetCategory, Entry: SetCategory, addDom):Exports == Implementation where + addDom : TableAggregate(Key, Entry) with + finiteAggregate + Exports ==> TableAggregate(Key, Entry) with + finiteAggregate + Implementation ==> addDom + +@ +\section{domain TABLE Table} +<<domain TABLE Table>>= +)abbrev domain TABLE Table +++ Author: Stephen M. Watt, Barry Trager +++ Date Created: 1985 +++ Date Last Updated: Sept 15, 1992 +++ Basic Operations: +++ Related Domains: HashTable, EqTable, StringTable, AssociationList +++ Also See: +++ AMS Classifications: +++ Keywords: +++ Examples: +++ References: +++ Description: +++ This is the general purpose table type. +++ The keys are hashed to look up the entries. +++ This creates a \spadtype{HashTable} if equal for the Key +++ domain is consistent with Lisp EQUAL otherwise an +++ \spadtype{AssociationList} + +Table(Key: SetCategory, Entry: SetCategory):Exports == Implementation where + Exports ==> TableAggregate(Key, Entry) with + finiteAggregate + + Implementation ==> InnerTable(Key, Entry, + if hashable(Key)$Lisp then HashTable(Key, Entry, "UEQUAL") + else AssociationList(Key, Entry)) + +@ +\section{domain EQTBL EqTable} +<<domain EQTBL EqTable>>= +)abbrev domain EQTBL EqTable +++ Author: Stephen M. Watt +++ Date Created: +++ Date Last Updated: June 21, 1991 +++ Basic Operations: +++ Related Domains: HashTable, Table, StringTable +++ Also See: +++ AMS Classifications: +++ Keywords: equation +++ Examples: +++ References: +++ Description: +++ This domain provides tables where the keys are compared using +++ \spadfun{eq?}. Thus keys are considered equal only if they +++ are the same instance of a structure. +EqTable(Key: SetCategory, Entry: SetCategory) == + HashTable(Key, Entry, "EQ") + +@ +\section{domain STRTBL StringTable} +<<domain STRTBL StringTable>>= +)abbrev domain STRTBL StringTable +++ Author: Stephen M. Watt +++ Date Created: +++ Date Last Updated: June 21, 1991 +++ Basic Operations: +++ Related Domains: Table +++ Also See: +++ AMS Classifications: +++ Keywords: equation +++ Examples: +++ References: +++ Description: +++ This domain provides tables where the keys are strings. +++ A specialized hash function for strings is used. +StringTable(Entry: SetCategory) == + HashTable(String, Entry, "CVEC") + +@ +\section{domain GSTBL GeneralSparseTable} +<<domain GSTBL GeneralSparseTable>>= +)abbrev domain GSTBL GeneralSparseTable +++ Author: Stephen M. Watt +++ Date Created: 1986 +++ Date Last Updated: June 21, 1991 +++ Basic Operations: +++ Related Domains: Table +++ Also See: +++ AMS Classifications: +++ Keywords: equation +++ Examples: +++ References: +++ Description: +++ A sparse table has a default entry, which is returned if no other +++ value has been explicitly stored for a key. +GeneralSparseTable(Key, Entry, Tbl, dent): TableAggregate(Key, Entry) == Impl + where + Key, Entry: SetCategory + Tbl: TableAggregate(Key, Entry) + dent: Entry + + Impl ==> Tbl add + Rep := Tbl + + elt(t:%, k:Key) == + (u := search(k, t)$Rep) case "failed" => dent + u::Entry + + setelt(t:%, k:Key, e:Entry) == + e = dent => (remove_!(k, t); e) + setelt(t, k, e)$Rep + + search(k:Key, t:%) == + (u := search(k, t)$Rep) case "failed" => dent + u + +@ +\section{domain STBL SparseTable} +<<domain STBL SparseTable>>= +)abbrev domain STBL SparseTable +++ Author: Stephen M. Watt +++ Date Created: 1986 +++ Date Last Updated: June 21, 1991 +++ Basic Operations: +++ Related Domains: Table +++ Also See: +++ AMS Classifications: +++ Keywords: equation +++ Examples: +++ References: +++ Description: +++ A sparse table has a default entry, which is returned if no other +++ value has been explicitly stored for a key. + +SparseTable(Key:SetCategory, Ent:SetCategory, dent:Ent) == + GeneralSparseTable(Key, Ent, Table(Key, Ent), dent) + +@ +\section{License} +<<license>>= +--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. +--All rights reserved. +-- +--Redistribution and use in source and binary forms, with or without +--modification, are permitted provided that the following conditions are +--met: +-- +-- - Redistributions of source code must retain the above copyright +-- notice, this list of conditions and the following disclaimer. +-- +-- - Redistributions in binary form must reproduce the above copyright +-- notice, this list of conditions and the following disclaimer in +-- the documentation and/or other materials provided with the +-- distribution. +-- +-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the +-- names of its contributors may be used to endorse or promote products +-- derived from this software without specific prior written permission. +-- +--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +@ +<<*>>= +<<license>> + +<<domain HASHTBL HashTable>> +<<domain INTABL InnerTable>> +<<domain TABLE Table>> +<<domain EQTBL EqTable>> +<<domain STRTBL StringTable>> +<<domain GSTBL GeneralSparseTable>> +<<domain STBL SparseTable>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |