path: root/src/algebra/table.spad.pamphlet

\documentclass{article}
\usepackage{open-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", "EQL", "EQUAL", "UEQUAL", "CVEC", "ID")

    Exports ==> TableAggregate(Key, Entry)
    Implementation ==> add
        import tableValue: (%,Key) -> Entry from Foreign Builtin
        import tableLength: % -> NonNegativeInteger from Foreign Builtin

        Pair ==> Record(key: Key, entry: Entry)
        Ex   ==> OutputForm
        failMsg := GENSYM()$Lisp

        t1 = t2              == %peq(t1,t2)$Foreign(Builtin)
        keys t               == HKEYS(t)$Lisp
        # t                  == tableLength t
        setelt(t, k, e)      == %store(tableValue(t,k),e)$Foreign(Builtin)
        remove!(k:Key, t:%) ==
          r := HGET(t,k,failMsg)$Lisp
          not %peq(r,failMsg)$Foreign(Builtin) =>
            HREM(t, k)$Lisp
            r pretend Entry
          "failed"

        empty() ==
            hashTable(INTERN(hashfn)$Lisp)$Lisp

        search(k:Key, t:%)  ==
            r := HGET(t, k, failMsg)$Lisp
            not %peq(r,failMsg)$Foreign(Builtin) => 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)
    Exports ==> TableAggregate(Key, Entry)
    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)
    Implementation ==> InnerTable(Key, Entry,
        if hashable(Key)$Lisp then HashTable(Key, Entry, "EQUAL")
          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, "EQUAL")

@
\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}