Title

Basic hash tables

Author

Panu Kalliokoski

Status

This SRFI is currently in ``final'' status. To see an explanation of each status that a SRFI can hold, see here. It will remain in draft status until 2005/09/09, or as amended. To provide input on this SRFI, please mailto:srfi-69@srfi.schemers.org. See instructions here to subscribe to the list. You can access previous messages via the archive of the mailing list.

概要

この SRFI は簡単なハッシュテーブルを定義する。 ハッシュテーブルは様々なアプリケーションで用いられる 基礎的なデータ構造として広く知られている。 ハッシュテーブルは以下のようなデータ構造である。

  1. キーの集合とそれに対応するキーの集合への写像を提供する
  2. 格納するキー・値の関連に固有の順序を持たない
  3. ハッシュテーブルの要素を設定する基礎的な方法として in place 修正をサポートする
  4. よいハッシュ関数が使われている場合、キーの検索と破壊的な更新は 償却定数時間で行われる

この SRFI の目標は以下の通りである。

  1. 一般的で一貫性があり、広範囲に適用可能なハッシュテーブルの API を提供する
  2. 動作の保証された標準的なハッシュテーブルを提供し、 コードの可搬性を高める
  3. ハッシュテーブルをつかうもっとも一般的な状況で使える ユーティリティルーチンを定義し、プログラマの助けになる

問題点

ハッシュテーブルをつくる唯一の正解の方法はない。 この SRFI では、概念的に単純で、 様々なアプリケーションで使用可能なことを目標にする。 ポータブルな実装が提供されていたとしても、実装側では、 例えば、シンボルに対して内部ハッシュ関数を提供するなどして、 大幅に高速化をはかることができる。また、ほとんどの実装には、 大域環境を実装する自然な方法として、具体的には string->symbol を提供するために、 既に何らかの低レベルハッシュテーブル機能がある。 ここで紹介する API と実装依存のデータ型を統合することには 何らかの利益あるだろうが、ここではこの問題については保留しておく。

この SRFI は SRFI 44 の map のインタフェースには従わない。 SRFI 44 に従うことにより、ハッシュテーブルのインタフェースは 著しく不自由になる。 SRFI 44 の map に対する操作の命名規則は一般的な用法に反し、 不自然なものにになっている。 しかしながら、この SRFI は SRFI 44 の API をハッシュテーブルに 適用することを妨げるものではない。 この SRFI と SRFI 44 の両方をサポートする処理系は、 ここに示すものに加えて、SRFI 44 のインタフェースをハッシュテーブル用に 提供することをおすすめする。

理論的根拠

ハッシュテーブルは様々な種類の計算タスクのための基礎的な データ構造として広く知られている。 今のところ、Scheme のハッシュテーブルには標準的なものがなく、 ごく小さな実装を除いてほとんどの実装が別個に 何らかのハッシュテーブル機能を提供している。

しかし悲しいかな、何らかの似通ったところはあるものの、 これらのハッシュテーブルには差違が多い。 ささいな点でいえば、特定の関数の名前のようなものであったり、 複雑なものでは、実装内部の異なる側面がユーザーに見えていたり、 お粗末なところでは、キーが何か特定の型であることを要求するという ようなことであったり、 微妙な点では、最適な性能を得るためには、ユーザーに前もって ハッシュテーブルのサイズを見積ってもらう必要がある、等々、 様々である。結果として、既存のハッシュテーブルはポータブルな プログラムを書くのには使えないのである。

この SRFI のいちばんの目標は標準的なハッシュテーブルの API を確立し、ハッシュテーブルを有効に利用したポータブルな プログラムを書けるようにすることである。 この SRFI では、さまざまなハッシュテーブルの API の間に存在する、 命名規則やハッシュテーブルの操作の意味論についての違いを解決する。 API を、一貫性があり、単純で一般性のあるものにするために 多大な努力が支払われた。 この SRFI では他にも、様々なアプリケーションを書くのに必要になるであろう、 もっとも一般的なユーティリティルーチンも定義している。

この SRFI を実装の標準機能に加えれば、ハッシュテーブルをつかった、 効率のよいポータブルなプログラムを書けるようになるだろう。

仕様書

この SRFI で定義される名前

型構築子と述語
make-hash-table, hash-table?, alist->hash-table
反射型クエリ
hash-table-equivalence-function, hash-table-hash-function
単一の要素を扱うもの
hash-table-ref, hash-table-ref/default, hash-table-set!, hash-table-delete!, hash-table-exists?, hash-table-update!, hash-table-update!/default
要素すべてを扱うもの
hash-table-size, hash-table-keys, hash-table-values, hash-table-walk, hash-table-fold, hash-table->alist, hash-table-copy, hash-table-merge!
ハッシング
hash, string-hash, string-ci-hash, hash-by-identity

hash-table-refhash-table-set!hash-table-delete!hash-table-update!hash-table-exists?hash-table-size が(よいハッシュ関数が与えられた場合に)償却定数時間で実行されない、 ないしは、hashstring-hashstring-ci-hashhash-by-identity について、よいハッシュ関数の定義の与えられないものは、この SRFI に合致しない。

ハッシュテーブルの実装はテーブル中のキーのハッシュ値が変化しないことに 依存してもよい。大抵の場合、ハッシュテーブルにキーを挿入したあとに、 キーを in-place に変更すると、この制約がおかされ未定義のふるまいを ひきおこす。

型構築子と述語

Procedure: make-hash-table [ equal? [ hash [ args … ]]] → hash-table

何の対応も格納しない新しいハッシュテーブルを作成する。 equal? は述語で、キーをふたつ受け取り、それらが同一のキー値を 持つかどうかを返す。デフォルトは equal? である。

hash はハッシュ関数で、デフォルト値は与えられた equal? 述語に適したハッシュ関数になる (ハッシュ関数 の節を参照)。 ただし、strinc-ci=? を除き、equal? よりも粗い同値関係については許容可能なデフォルト値は保証されない [1]。関数 hashequal? を許容可能でなければならない。すなわち、string-ci=? 以外の、equal? よりも粗い同値関係を使う場合には、 hash を使用者が指定しなければならない。

[1] 同値述語 c1 が同値述語 c2 について、 (and (c1 x y) (not (c2 x y))) なる xy が存在するときかつそのときにかぎり、c1c2 よりも粗い、という。

残りの args を実装依存の拡張に使ってもかまわない。 ただし、このような拡張をつかうと、プログラムのポータビリティが そこなわれることには注意しなけらばならない。

Procedure: hash-table? objboolean

与えられたオブジェクト obj がハッシュテーブルかどうかをテストする述語。ハッシュテーブル型は、 可能であれば、ほかのすべての型と互いに素であるべきである。

Procedure: alist->hash-table alist [ equal? [ hash [ args … ]]] → hash-table

連想リスト alist を取り、連想リストの car を対応する cdr に写像するハッシュテーブルを作成する。 equal?hashargsmake-hash-table と同様に解釈される。 キーが alist のなかに複数回現れた場合には、 最初の対応に現れたものの方があとのものよりも優先される (注: 値として(cadr の代わりに)cdr をつかうのは、ふたつの方法のバランスをとろうとしたものである。 cadr を使うとこの手続きは cdr 連想リストに使えなくなるが、逆は真ではない)。

反射型クエリ

Procedure: hash-table-equivalence-function hash-table

hash-table のキーに使われる同値述語を返す。

Procedure: hash-table-hash-function hash-table

hash-table のキーに使われるハッシュ関数を返す。

単一の要素を扱うもの

Procedure: hash-table-ref hash-table key [ thunk ] → value

この手続きは hash-table 中の key に対応する value を返す。 key に対応する value がない場合、 thunk があたえられていれば、thunk を呼び出し、その戻り値を返し、 thunk が与えられていない場合にはエラーが通知される。 よいハッシュ関数が与えられていれば、この操作の(償却)計算量は hash-table 中の対応の数に対して O(1) になる (注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される)。

Procedure: hash-table-ref/default hash-table key defaultvalue

(hash-table-ref hash-table key (lambda () default)). と同じ値に評価される。 よいハッシュ関数が与えられていれば、この操作の(償却)計算量は hash-table 中の対応の数に対して O(1) になる (注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される)。

Procedure: hash-table-set! hash-table key value → undefined

この手続きは hash-table 中の key に対して value を設定する。以前の対応は(もしあれば)取り除かれる。 よいハッシュ関数が与えられていれば、この操作の(償却)計算量は hash-table 中の対応の数に対して O(1) になる (注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される)。

Procedure: hash-table-delete! hash-table key → undefined

この手続きは hash-table 中の key への対応をすべて取り除く。キーに対する対応が存在しない場合、 エラーにはならず、何もしない。 よいハッシュ関数が与えられていれば、この操作の(償却)計算量は hash-table 中の対応の数に対して O(1) になる (注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される)。

Procedure: hash-table-exists? hash-table keyboolean

この述語は hash-table 中に key に関する対応があるかどうかを返す。 よいハッシュ関数が与えられていれば、この操作の(償却)計算量は hash-table 中の対応の数に対して O(1) になる (注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される)。

Procedure: hash-table-update! hash-table key function [ thunk ] → undefined

意味的には以下のコードと同等だが、 より効率的に実装されるかもしれない。

(hash-table-set! hash-table key
                 (function (hash-table-ref hash-table key thunk)))

Procedure: hash-table-update!/default hash-table key function default → undefined

(hash-table-update! hash-table key function (lambda () default)) を評価したようにふるまう。

要素すべてを扱うもの

Procedure: hash-table-size hash-tableinteger

hash-table 中の対応の個数を返す。この操作は、 hash-table 中の対応の個数に対して O(1) の複雑さでなければならない。

Procedure: hash-table-keys hash-tablelist

hash-table 中のキーのリストを返す。 キーの順番は未定義である。

Procedure: hash-table-values hash-tablelist

hash-table 中の値のリストを返す。値の順序は未定義で、 hash-table-keys の結果のキーの順序と一致することは保証されない。

Procedure: hash-table-walk hash-table proc → unspecified

prockeyvalue のふたつの引数を取る関数でなければならない。 この手続きは hash-table 中の各対応について proc を呼び出す。proc の戻り値は捨てられる。 別の対応に対する proc の呼び出し順序は規定されていない。

(注: この手続きと同じことをする hash-table-map という手続きのある実装もあるが、 hash-table-map が何か別のことをする実装もある。 著者の知っている範囲で、hash-table-map が通常の関数をハッシュテーブルのドメインに持ち上げる (that lifts an ordinary function to the domain of hash tables) ような実装は存在しない。このような理由により、 hash-table-map はこの SRFI の範囲外になっている。

Procedure: hash-table-fold hash-table f init-valuefinal-value

この手続きは hash-table 中の各対応について f を、対応の key、対応の値 value累積値 val を引き数に呼び出す。 valf の最初の呼び出し時には init-value になり、以下の f の呼び出しでは 直前の f の呼び出しの戻り値になる。 hash-table-fold の返す final-value の値は f の最後の呼び出しの値である。 別の対応に対する proc の呼び出し順序は規定されていない。

Procedure: hash-table->alist hash-tablealist

各要素の carhash-table のキーで、対応する cdr がキーに対応する値であるような連想リストを返す。 要素の順序は規定されていない。

以下のコードは常に h と同じ写像のハッシュテーブルを 返さなければならない。

(alist->hash-table (hash-table->alist h)
                        (hash-table-equivalence-function h)
                        (hash-table-hash-function h))

Procedure: hash-table-copy hash-tablehash-table

hash-table と同じ同値述語、ハッシュ関数、写像の、 新しいハッシュテーブルを返す。

Procedure: hash-table-merge! hash-table1 hash-table2hash-table

hash-table2 中の写像をすべて hash-table1 に追加し、結果のハッシュテーブルを返す。この関数は hash-table1 を破壊的に変更するかもしれない。

ハッシング

ハッシングは何らかの値を受け取り、その値から数値を生成することをいう。 ハッシュ関数はこれをする関数である。 同値述語 e にはそれぞれ許容可能なハッシュ関数がある。 (e obj1 obj2)(= (hash obj1) (hash obj2)) であるときかつそのときにかぎり、ハッシュ関数 hash が許容可能である、という。

ハッシュ関数 h が 同値関数 e に対して よい というのは、 (e にとって)等しくないオブジェクトに対して、 特に、等しくないオブジェクト同士が互いに似通っている、 例えば、共通の部分列をもつ場合に、 結果の値(ハッシュ値)がハッシュ値の値域にできるだけ 均一に分散することをいう。 この定義は曖昧であるが、例えば、定数関数がよいハッシュ関数ではない ことを主張するには十分である。

上の make-hash-table の定義で e に対して 適切なハッシュ関数と言ったとき、 ハッシュ関数が e に対して許容可能でよく、 さらに(ハッシング操作に対して)優れた性能を示すことをいう。 この定義もまた、意図的に曖昧になっている。

Procedure: hash object [ bound ] → integer

object に対して (0, bound) の範囲のハッシュ値を生成する。bound が与えられなかった場合、 デフォルトの bound が普通のアプリケーションで想定可能な どんなハッシュテーブルよりも大きな値であれば、 実装側は自由に bound を選んでよい (これは、デフォルトの bound として、実装側が fixnum の範囲で何かとても大きな値を選択できるためにである)。 このハッシュ関数は equal? に対して許容可能である。

Procedure: string-hash string [ bound ] → integer

引き数 string が文字列でなければならないことを除いて hash と同じである。

Procedure: string-ci-hash string [ bound ] → integer

string の大文字・小文字の別がハッシュ値に影響を与えないことを除けば、 string-hash と同じである。

Procedure: hash-by-identity object [ bound ] → integer

eq? に対して許容可能であることが保証されていることを除けば hash と同じである。この関数を提供するのは、 hash よりも極めて効率よく実装されているかもしれないからである。 実装側ではこの関数を組み込みで提供することが好ましい。

実装

この実装はハッシュテーブル型の明瞭さのために SRFI 9 を、 エラー通知のために SRFI 23 を使っている。 それ以外の部分は、純粋な R5RS である。

(define *default-bound* (- (expt 2 29) 3))

(define (%string-hash s ch-conv bound)
  (let ((hash 31)
        (len (string-length s)))
    (do ((index 0 (+ index 1)))
      ((>= index len) (modulo hash bound))
      (set! hash (modulo (+ (* 37 hash)
                            (char->integer (ch-conv (string-ref s index))))
                         *default-bound*)))))

(define (string-hash s . maybe-bound)
  (let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
    (%string-hash s (lambda (x) x) bound)))

(define (string-ci-hash s . maybe-bound)
  (let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
    (%string-hash s char-downcase bound)))

(define (symbol-hash s . maybe-bound)
  (let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
    (%string-hash (symbol->string s) (lambda (x) x) bound)))

(define (hash obj . maybe-bound)
  (let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
    (cond ((integer? obj) (modulo obj bound))
          ((string? obj) (string-hash obj bound))
          ((symbol? obj) (symbol-hash obj bound))
          ((real? obj) (modulo (+ (numerator obj) (denominator obj)) bound))
          ((number? obj)
           (modulo (+ (hash (real-part obj)) (* 3 (hash (imag-part obj))))
                   bound))
          ((char? obj) (modulo (char->integer obj) bound))
          ((vector? obj) (vector-hash obj bound))
          ((pair? obj) (modulo (+ (hash (car obj)) (* 3 (hash (cdr obj))))
                               bound))
          ((null? obj) 0)
          ((not obj) 0)
          ((procedure? obj) (error "hash: procedures cannot be hashed" obj))
          (else 1))))

(define hash-by-identity hash)

(define (vector-hash v bound)
  (let ((hashvalue 571)
        (len (vector-length v)))
    (do ((index 0 (+ index 1)))
      ((>= index len) (modulo hashvalue bound))
      (set! hashvalue (modulo (+ (* 257 hashvalue) (hash (vector-ref v index)))
                              *default-bound*)))))

(define %make-hash-node cons)
(define %hash-node-set-value! set-cdr!)
(define %hash-node-key car)
(define %hash-node-value cdr)

(define-record-type <srfi-hash-table>
  (%make-hash-table size hash compare associate entries)
  hash-table?
  (size hash-table-size hash-table-set-size!)
  (hash hash-table-hash-function)
  (compare hash-table-equivalence-function)
  (associate hash-table-association-function)
  (entries hash-table-entries hash-table-set-entries!))

(define *default-table-size* 64)

(define (appropriate-hash-function-for comparison)
  (or (and (eq? comparison eq?) hash-by-identity)
      (and (eq? comparison string=?) string-hash)
      (and (eq? comparison string-ci=?) string-ci-hash)
      hash))

(define (make-hash-table . args)
  (let* ((comparison (if (null? args) equal? (car args)))
         (hash
           (if (or (null? args) (null? (cdr args)))
             (appropriate-hash-function-for comparison) (cadr args)))
         (size
           (if (or (null? args) (null? (cdr args)) (null? (cddr args)))
             *default-table-size* (caddr args)))
         (association
           (or (and (eq? comparison eq?) assq)
               (and (eq? comparison eqv?) assv)
               (and (eq? comparison equal?) assoc)
               (letrec
                 ((associate
                    (lambda (val alist)
                      (cond ((null? alist) #f)
                            ((comparison val (caar alist)) (car alist))
                            (else (associate val (cdr alist)))))))
                 associate))))
    (%make-hash-table 0 hash comparison association (make-vector size '()))))

(define (make-hash-table-maker comp hash)
  (lambda args (apply make-hash-table (cons comp (cons hash args)))))
(define make-symbol-hash-table
  (make-hash-table-maker eq? symbol-hash))
(define make-string-hash-table
  (make-hash-table-maker string=? string-hash))
(define make-string-ci-hash-table
  (make-hash-table-maker string-ci=? string-ci-hash))
(define make-integer-hash-table
  (make-hash-table-maker = modulo))

(define (%hash-table-hash hash-table key)
  ((hash-table-hash-function hash-table)
     key (vector-length (hash-table-entries hash-table))))

(define (%hash-table-find entries associate hash key)
  (associate key (vector-ref entries hash)))

(define (%hash-table-add! entries hash key value)
  (vector-set! entries hash
               (cons (%make-hash-node key value)
                     (vector-ref entries hash))))

(define (%hash-table-delete! entries compare hash key)
  (let ((entrylist (vector-ref entries hash)))
    (cond ((null? entrylist) #f)
          ((compare key (caar entrylist))
           (vector-set! entries hash (cdr entrylist)) #t)
          (else
            (let loop ((current (cdr entrylist)) (previous entrylist))
              (cond ((null? current) #f)
                    ((compare key (caar current))
                     (set-cdr! previous (cdr current)) #t)
                    (else (loop (cdr current) current))))))))

(define (%hash-table-walk proc entries)
  (do ((index (- (vector-length entries) 1) (- index 1)))
    ((< index 0)) (for-each proc (vector-ref entries index))))

(define (%hash-table-maybe-resize! hash-table)
  (let* ((old-entries (hash-table-entries hash-table))
         (hash-length (vector-length old-entries)))
    (if (> (hash-table-size hash-table) hash-length)
      (let* ((new-length (* 2 hash-length))
             (new-entries (make-vector new-length '()))
             (hash (hash-table-hash-function hash-table)))
        (%hash-table-walk
          (lambda (node)
            (%hash-table-add! new-entries
                              (hash (%hash-node-key node) new-length)
                              (%hash-node-key node) (%hash-node-value node)))
          old-entries)
        (hash-table-set-entries! hash-table new-entries)))))

(define (hash-table-ref hash-table key . maybe-default)
  (cond ((%hash-table-find (hash-table-entries hash-table)
                           (hash-table-association-function hash-table)
                           (%hash-table-hash hash-table key) key)
         => %hash-node-value)
        ((null? maybe-default)
         (error "hash-table-ref: no value associated with" key))
        (else ((car maybe-default)))))

(define (hash-table-ref/default hash-table key default)
  (hash-table-ref hash-table key (lambda () default)))

(define (hash-table-set! hash-table key value)
  (let ((hash (%hash-table-hash hash-table key))
        (entries (hash-table-entries hash-table)))
    (cond ((%hash-table-find entries
                             (hash-table-association-function hash-table)
                             hash key)
           => (lambda (node) (%hash-node-set-value! node value)))
          (else (%hash-table-add! entries hash key value)
                (hash-table-set-size! hash-table
                                       (+ 1 (hash-table-size hash-table)))
                (%hash-table-maybe-resize! hash-table)))))

(define (hash-table-update! hash-table key function . maybe-default)
  (let ((hash (%hash-table-hash hash-table key))
        (entries (hash-table-entries hash-table)))
    (cond ((%hash-table-find entries
                             (hash-table-association-function hash-table)
                             hash key)
           => (lambda (node)
                (%hash-node-set-value!
                  node (function (%hash-node-value node)))))
          ((null? maybe-default)
           (error "hash-table-update!: no value exists for key" key))
          (else (%hash-table-add! entries hash key
                                  (function ((car maybe-default))))
                (hash-table-set-size! hash-table
                                       (+ 1 (hash-table-size hash-table)))
                (%hash-table-maybe-resize! hash-table)))))

(define (hash-table-update!/default hash-table key function default)
  (hash-table-update! hash-table key function (lambda () default)))

(define (hash-table-delete! hash-table key)
  (if (%hash-table-delete! (hash-table-entries hash-table)
                           (hash-table-equivalence-function hash-table)
                           (%hash-table-hash hash-table key) key)
    (hash-table-set-size! hash-table (- (hash-table-size hash-table) 1))))

(define (hash-table-exists? hash-table key)
  (and (%hash-table-find (hash-table-entries hash-table)
                         (hash-table-association-function hash-table)
                         (%hash-table-hash hash-table key) key) #t))

(define (hash-table-walk hash-table proc)
  (%hash-table-walk
    (lambda (node) (proc (%hash-node-key node) (%hash-node-value node)))
    (hash-table-entries hash-table)))

(define (hash-table-fold hash-table f acc)
  (hash-table-walk hash-table 
                       (lambda (key value) (set! acc (f key value acc))))
  acc)

(define (alist->hash-table alist . args)
  (let* ((comparison (if (null? args) equal? (car args)))
         (hash
           (if (or (null? args) (null? (cdr args)))
             (appropriate-hash-function-for comparison) (cadr args)))
         (size
           (if (or (null? args) (null? (cdr args)) (null? (cddr args)))
             (max *default-table-size* (* 2 (length alist))) (caddr args)))
         (hash-table (make-hash-table comparison hash size)))
    (for-each
      (lambda (elem)
        (hash-table-update!/default
          hash-table (car elem) (lambda (x) x) (cdr elem)))
      alist)
    hash-table))

(define (hash-table->alist hash-table)
  (hash-table-fold hash-table
                   (lambda (key val acc) (cons (cons key val) acc)) '()))

(define (hash-table-copy hash-table)
  (let ((new (make-hash-table (hash-table-equivalence-function hash-table)
                              (hash-table-hash-function hash-table)
                              (max *default-table-size*
                                   (* 2 (hash-table-size hash-table))))))
    (hash-table-walk hash-table
                     (lambda (key value) (hash-table-set! new key value)))
    new))

(define (hash-table-merge! hash-table1 hash-table2)
  (hash-table-walk
    hash-table2
    (lambda (key value) (hash-table-set! hash-table1 key value)))
  hash-table1)

(define (hash-table-keys hash-table)
  (hash-table-fold hash-table (lambda (key val acc) (cons key acc)) '()))

(define (hash-table-values hash-table)
  (hash-table-fold hash-table (lambda (key val acc) (cons val acc)) '()))

Copyright

Copyright © Panu Kalliokoski(2005). All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the Software), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED AS IS, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


Editor: David Van Horn
Last modified: Wed Sep 14 09:54:51 EDT 2005