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

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

remove bitwise-utils dependency, strict types, fix real-number-hash & complex-number-hash type

File size: 3.9 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
56;;
57
58;w/ cplxnum since type cannot check value!
59(define-type real (or integer float ratnum cplxnum))
60
61(define-type alist (list-of pair))
62
63(define-type <hash-trie-type> (struct <hash-trie-type>))
64(define-type <hash-trie> (struct <hash-trie>))
65
66(: make-hash-trie-type (procedure procedure -> <hash-trie-type>))
67(: hash-trie-type? (* -> boolean : <hash-trie-type>))
68(: hash-trie-type/key-equality-predicate (<hash-trie-type> -> procedure))
69(: hash-trie-type/key-hash-function (<hash-trie-type> -> procedure))
70
71(: make-hash-trie (<hash-trie-type> -> <hash-trie>))
72(: hash-trie? (* -> boolean : <hash-trie>))
73(: hash-trie/type (<hash-trie> -> <hash-trie-type>))
74(: hash-trie/count (<hash-trie> -> fixnum))
75(: hash-trie/empty? (<hash-trie> -> boolean))
76
77(: hash-trie/search (<hash-trie> * procedure procedure -> void))
78(: hash-trie/lookup (<hash-trie> * * -> *))
79(: hash-trie/member? (<hash-trie> * -> boolean))
80
81(: hash-trie/update (<hash-trie> * procedure procedure  -> void))
82(: hash-trie/insert (<hash-trie> * * -> <hash-trie>))
83(: hash-trie/modify (<hash-trie> * * procedure -> <hash-trie>))
84(: hash-trie/intern (<hash-trie> * procedure -> * <hash-trie>))
85(: hash-trie/delete (<hash-trie> * -> <hash-trie>))
86
87#; ;i feel violated
88(: hash-trie/fold (forall (e) (<hash-trie> e (* * e -> e) -> e)))
89(: hash-trie/fold (<hash-trie> * (* * * -> *) -> *))
90
91(: hash-trie->alist (<hash-trie> -> alist))
92(: hash-trie/key-list (<hash-trie> -> alist))
93(: hash-trie/datum-list (<hash-trie> -> alist))
94(: alist->hash-trie (alist <hash-trie-type> -> <hash-trie>))
95
96(: string-hash (string -> fixnum))
97(: symbol-hash (symbol -> fixnum))
98(: exact-integer-hash (integer -> fixnum))
99(: real-number-hash (real -> fixnum))
100(: complex-number-hash (real -> fixnum))
101
102;;
103
104;from srfi-60 example implementation - slib logical.scm
105
106(define lognot bitwise-not)
107
108;@
109(define bitwise-bit-count
110  (letrec ((logcnt (lambda (n tot)
111                     (if (zero? n)
112                          tot
113                          (logcnt (quotient n 16)
114                                  (+ (vector-ref
115                                      '#(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)
116                                      (modulo n 16))
117                                     tot))))))
118    (lambda (n)
119      (cond ((negative? n) (lognot (logcnt (lognot n) 0)))
120                  ((positive? n) (logcnt n 0))
121                  (else 0)))))
122;@
123(define (logcount n)
124  (cond ((negative? n) (bitwise-bit-count (lognot n)))
125              (else (bitwise-bit-count n))))
126
127(define bit-count logcount)
128
129(include "hash-trie.incl")
130
131;hash-trie->stream uses branch? bucket? bucket/list
132;what would make a "protected" API?
133(define hash-trie-root hash-trie.root)
134(define hash-trie-branch? branch?)
135(define (hash-trie-branch-vector branch) branch)
136(define hash-trie-bucket? bucket?)
137(define hash-trie-bucket-list bucket/list)
138
139); hash-trie
Note: See TracBrowser for help on using the repository browser.