Created
April 10, 2013 09:21
-
-
Save yamasushi/5353139 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
diff --git a/ext/sparse/sparse.scm b/ext/sparse/sparse.scm | |
index 0ea6ec0..20a6727 100644 | |
--- a/ext/sparse/sparse.scm | |
+++ b/ext/sparse/sparse.scm | |
@@ -271,7 +271,7 @@ | |
;;=============================================================== | |
;; dictionary protocol | |
-;; | |
+;; <sparse-table> | |
(define-method dict-get ((dict <sparse-table>) key . maybe-default) | |
(if (null? maybe-default) | |
@@ -290,3 +290,63 @@ | |
(define-method dict-fold ((dict <sparse-table>) proc seed) | |
(sparse-table-fold dict proc seed)) | |
+(define-method dict-for-each ((dict <sparse-table>) proc) | |
+ (sparse-table-for-each dict proc) ) | |
+ | |
+(define-method dict-map ((dict <sparse-table>) proc) | |
+ (sparse-table-map dict proc) ) | |
+ | |
+(define-method dict-keys ((dict <sparse-table>)) | |
+ (sparse-table-keys dict) ) | |
+ | |
+(define-method dict-values ((dict <sparse-table>)) | |
+ (sparse-table-values dict) ) | |
+ | |
+(define-method dict-pop! ((dict <sparse-table>) key :optional default) | |
+ (sparse-table-pop! dict key default) ) | |
+ | |
+(define-method dict-push! ((dict <sparse-table>) key value) | |
+ (sparse-table-push! dict key value) ) | |
+ | |
+(define-method dict-update! ((dict <sparse-table>) key proc :optional default) | |
+ (sparse-table-update! dict key proc default) ) | |
+ | |
+;; <sparse-vector-base> | |
+ | |
+(define-method dict-get ((dict <sparse-vector-base>) key . maybe-default) | |
+ (if (null? maybe-default) | |
+ (sparse-vector-ref dict key) | |
+ (sparse-vector-ref dict key (car maybe-default)))) | |
+ | |
+(define-method dict-put! ((dict <sparse-vector-base>) key val) | |
+ (sparse-vector-set! dict key val)) | |
+ | |
+(define-method dict-delete! ((dict <sparse-vector-base>) key) | |
+ (sparse-vector-delete! dict key)) | |
+ | |
+(define-method dict-exists? ((dict <sparse-vector-base>) key) | |
+ (sparse-vector-exists? dict key)) | |
+ | |
+(define-method dict-fold ((dict <sparse-vector-base>) proc seed) | |
+ (sparse-vector-fold dict proc seed)) | |
+ | |
+(define-method dict-for-each ((dict <sparse-vector-base>) proc) | |
+ (sparse-vector-for-each dict proc) ) | |
+ | |
+(define-method dict-map ((dict <sparse-vector-base>) proc) | |
+ (sparse-vector-map dict proc) ) | |
+ | |
+(define-method dict-keys ((dict <sparse-vector-base>)) | |
+ (sparse-vector-keys dict) ) | |
+ | |
+(define-method dict-values ((dict <sparse-vector-base>)) | |
+ (sparse-vector-values dict) ) | |
+ | |
+(define-method dict-pop! ((dict <sparse-vector-base>) key :optional default) | |
+ (sparse-vector-pop! dict key default) ) | |
+ | |
+(define-method dict-push! ((dict <sparse-vector-base>) key value) | |
+ (sparse-vector-push! dict key value) ) | |
+ | |
+(define-method dict-update! ((dict <sparse-vector-base>) key proc :optional default) | |
+ (sparse-vector-update! dict key proc default) ) | |
diff --git a/lib/gauche/dictionary.scm b/lib/gauche/dictionary.scm | |
index 3e52116..62c2023 100644 | |
--- a/lib/gauche/dictionary.scm | |
+++ b/lib/gauche/dictionary.scm | |
@@ -38,6 +38,9 @@ | |
dict-fold dict-fold-right | |
dict-for-each dict-map | |
dict-keys dict-values | |
+ ; | |
+ dict->alist dict-pop! dict-push! dict-update! | |
+ ; | |
<bimap> make-bimap bimap-put! | |
bimap-left bimap-left-get bimap-left-exists? bimap-left-delete! | |
bimap-right bimap-right-get bimap-right-exists? bimap-right-delete! | |
@@ -84,7 +87,6 @@ | |
(hash-table-exists? dict key)) | |
(define-method dict-exists? ((dict <tree-map>) key) | |
(tree-map-exists? dict key)) | |
- | |
;;----------------------------------------------- | |
;; dict-fold, dict-fold-right | |
;; | |
@@ -98,7 +100,6 @@ | |
(define-method dict-fold ((dict <tree-map>) proc seed) | |
(tree-map-fold dict proc seed)) | |
- | |
(define-method dict-fold-right ((dict <ordered-dictionary>) proc seed) | |
(fold-right dict (lambda (kv seed) (proc (car kv) (cdr kv) seed)) seed)) | |
@@ -115,7 +116,6 @@ | |
(define-method dict-for-each ((dict <hash-table>) proc) | |
(hash-table-for-each dict proc)) | |
- | |
(define-method dict-map ((dict <dictionary>) proc) | |
(dict-fold dict (lambda (k v r) (cons (proc k v) r)) '())) | |
@@ -150,6 +150,35 @@ | |
(define-method dict-values ((dict <tree-map>)) | |
(tree-map-values dict)) | |
+;;----------------------------------------------- | |
+;; dict->alist | |
+(define-method dict->alist ((dict <hash-table>)) (hash-table->alist dict)) | |
+(define-method dict->alist ((dict <tree-map>)) (tree-map->alist dict)) | |
+ | |
+;;----------------------------------------------- | |
+;; dict-pop! | |
+(define-method dict-pop! ((dict <hash-table>) key :optional default) | |
+ (hash-table-pop! dict key default) ) | |
+ | |
+(define-method dict-pop! ((dict <tree-map>) key :optional default) | |
+ (tree-map-pop! dict key default) ) | |
+ | |
+;;----------------------------------------------- | |
+;; dict-push! | |
+(define-method dict-push! ((dict <hash-table>) key value) | |
+ (hash-table-push! dict key value) ) | |
+ | |
+(define-method dict-push! ((dict <tree-map>) key value) | |
+ (tree-map-push! dict key value) ) | |
+ | |
+;;----------------------------------------------- | |
+;; dict-update! | |
+(define-method dict-update! ((dict <hash-table>) key proc :optional default) | |
+ (hash-table-update! dict key proc default) ) | |
+ | |
+(define-method dict-update! ((dict <tree-map>) key proc :optional default) | |
+ (tree-map-update! dict key proc default) ) | |
+ | |
;;; | |
;;; Bidirectional map | |
;;; | |
diff --git a/lib/util/trie.scm b/lib/util/trie.scm | |
index f0ad54a..f0c0f27 100644 | |
--- a/lib/util/trie.scm | |
+++ b/lib/util/trie.scm | |
@@ -39,6 +39,7 @@ | |
(define-module util.trie | |
(use srfi-1) | |
(use gauche.sequence) | |
+ (use gauche.dictionary) | |
(use util.list) | |
(export <trie> | |
make-trie trie trie-with-keys | |
@@ -53,6 +54,12 @@ | |
trie->list trie->hash-table | |
trie-keys trie-values trie-fold trie-map trie-for-each | |
call-with-iterator call-with-builder size-of lazy-size-of | |
+ ; | |
+ dict-put! dict-get dict-exists? dict-delete! dict-keys dict-values | |
+ dict-update! dict-for-each dict-map dict-fold dict->alist | |
+ ; | |
+ alist->trie | |
+ ; | |
)) | |
(select-module util.trie) | |
@@ -85,7 +92,7 @@ | |
(define-class <trie-meta> (<class>) | |
()) | |
-(define-class <trie> (<collection>) | |
+(define-class <trie> ( <dictionary> ) | |
((root :init-form (%make-node)) | |
(size :init-value 0) | |
(tab-make :init-keyword :tab-make | |
@@ -339,3 +346,44 @@ | |
(define-method coerce-to ((class <hash-table-meta>) (trie <trie>)) | |
(trie->hash-table trie 'equal?)) | |
+(define (alist->trie alist . rest) | |
+ (apply trie rest alist) ) | |
+ | |
+;;;=========================================================== | |
+;;; Dictionary framework | |
+;;; | |
+;; TODO dict-push! for <trie> | |
+;; TODO dict-pop! for <trie> | |
+ | |
+(define-method dict-get ((dict <trie>) key :optional default ) | |
+ (trie-get dict key default) ) | |
+ | |
+(define-method dict-put! ((dict <trie>) key value ) | |
+ (trie-put! dict key value) ) | |
+ | |
+(define-method dict-delete! ((dict <trie>) key) | |
+ (trie-delete! dict key) ) | |
+ | |
+(define-method dict-exists? ((dict <trie>) key) | |
+ (trie-exists? dict key) ) | |
+ | |
+(define-method dict-fold((dict <trie>) proc seed) | |
+ (trie-fold dict proc seed) ) | |
+ | |
+(define-method dict-for-each ((dict <trie>) proc) | |
+ (trie-for-each dict proc) ) | |
+ | |
+(define-method dict-map((dict <trie>) proc) | |
+ (trie-map dict proc) ) | |
+ | |
+(define-method dict-keys ((dict <trie>)) | |
+ (trie-keys dict) ) | |
+ | |
+(define-method dict-values ((dict <trie>)) | |
+ (trie-values dict) ) | |
+ | |
+(define-method dict->alist ((dict <trie>)) (trie->list dict)) | |
+ | |
+(define-method dict-update! ((dict <trie>) key proc :optional default) | |
+ (trie-update! dict key proc default) ) | |
+ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment