source: project/release/5/hash-trie/trunk/hash-trie.scm @ 38590

Last change on this file since 38590 was 38590, checked in by Kon Lovett, 6 months ago

depends on bitwise-utils for a correct bit-count

File size: 3.1 KB
Line 
1;;; -*- Mode: Scheme -*-
2
3;;;; Hash Tries: Persistent Trie-Structured Hash Tables
4
5;;; Copyright (c) 2009, Taylor R. Campbell
6;see "hash-trie.incl.scm"
7
8(module hash-trie
9
10(;export
11  make-hash-trie-type
12  hash-trie-type?
13  hash-trie-type/key-equality-predicate
14  hash-trie-type/key-hash-function
15  make-hash-trie
16  hash-trie?
17  hash-trie/type
18  hash-trie/count
19  hash-trie/empty?
20  hash-trie/search
21  hash-trie/lookup
22  hash-trie/member?
23  hash-trie/update
24  hash-trie/insert
25  hash-trie/modify
26  hash-trie/intern
27  hash-trie/delete
28  hash-trie/fold
29  hash-trie->alist
30  hash-trie/key-list
31  hash-trie/datum-list
32  alist->hash-trie
33  string-hash
34  symbol-hash
35  exact-integer-hash
36  real-number-hash
37  complex-number-hash
38  hash-trie-type:complex-number
39  hash-trie-type:real-number
40  hash-trie-type:exact-integer
41  hash-trie-type:symbol
42  hash-trie-type:string
43  ;
44  hash-trie-root
45  hash-trie-branch?
46  hash-trie-branch-vector
47  hash-trie-bucket?
48  hash-trie-bucket-list)
49
50(import scheme)
51(import (chicken base))
52(import (chicken type))
53(import (chicken foreign))
54(import (chicken bitwise))
55(import (only bitwise-utils bitwise-count))
56
57;;
58
59(define-type alist (list-of pair))
60
61(define-type <hash-trie-type> (struct <hash-trie-type>))
62(define-type <hash-trie> (struct <hash-trie>))
63
64(: make-hash-trie-type (procedure procedure -> <hash-trie-type>))
65(: hash-trie-type? (* -> boolean : <hash-trie-type>))
66(: hash-trie-type/key-equality-predicate (<hash-trie-type> -> procedure))
67(: hash-trie-type/key-hash-function (<hash-trie-type> -> procedure))
68
69(: make-hash-trie (<hash-trie-type> -> <hash-trie>))
70(: hash-trie? (* -> boolean : <hash-trie>))
71(: hash-trie/type (<hash-trie> -> <hash-trie-type>))
72(: hash-trie/count (<hash-trie> -> fixnum))
73(: hash-trie/empty? (<hash-trie> -> boolean))
74
75(: hash-trie/search (<hash-trie> * procedure procedure -> void))
76(: hash-trie/lookup (<hash-trie> * * -> *))
77(: hash-trie/member? (<hash-trie> * -> boolean))
78
79(: hash-trie/update (<hash-trie> * procedure procedure  -> void))
80(: hash-trie/insert (<hash-trie> * * -> <hash-trie>))
81(: hash-trie/modify (<hash-trie> * * procedure -> <hash-trie>))
82(: hash-trie/intern (<hash-trie> * procedure -> * <hash-trie>))
83(: hash-trie/delete (<hash-trie> * -> <hash-trie>))
84
85#; ;i feel violated
86(: hash-trie/fold (forall (e) (<hash-trie> e (* * e -> e) -> e)))
87(: hash-trie/fold (<hash-trie> * (* * * -> *) -> *))
88
89(: hash-trie->alist (<hash-trie> -> alist))
90(: hash-trie/key-list (<hash-trie> -> alist))
91(: hash-trie/datum-list (<hash-trie> -> alist))
92(: alist->hash-trie (alist <hash-trie-type> -> <hash-trie>))
93
94(: string-hash (string -> fixnum))
95(: symbol-hash (symbol -> fixnum))
96(: exact-integer-hash (fixnum -> fixnum))
97(: real-number-hash (float -> fixnum))
98(: complex-number-hash (cplxnum -> fixnum))
99
100;;
101
102(define bit-count bitwise-count)
103(include "hash-trie.incl")
104
105;hash-trie->stream uses branch? bucket? bucket/list
106;what would make a "protected" API?
107(define hash-trie-root hash-trie.root)
108(define hash-trie-branch? branch?)
109(define (hash-trie-branch-vector branch) branch)
110(define hash-trie-bucket? bucket?)
111(define hash-trie-bucket-list bucket/list)
112
113); hash-trie
Note: See TracBrowser for help on using the repository browser.