#lang racket
 
(require (only-in srfi/41 stream-drop-while stream-from))
 
;; 素数列
(define primes
  (stream-cons
   2
   (stream-filter prime? (stream-from 3))))
 
(define (prime? n)
  (let loop ((ps primes))
    (let ((x (stream-first ps)))
      (or (> (expt (stream-first ps) 2) n)
          (and ((compose1 not zero?) (remainder n x))
               (loop (stream-rest ps)))))))
 
;; メルセンヌ素数(の一部)のテーブル(12個のみ)
(define *mersenne-primes*
  (vector 3 7 31 127 8191 131071 524287 2147483647 2305843009213693951
          618970019642690137449562111 162259276829213363391578010288127
          170141183460469231731687303715884105727))
 
;; キーと値のペアを形作る構造体
(struct entry (key value) #:transparent)
 
;;; ハッシュテーブル生成関数
(define make-ht
  (case-lambda
    ((n)
     (let ((bucket (make-vector n '())))
       ;;; 多項式ローリングハッシュ関数
       (define hashval
         (case-lambda
           ((s ht p)
            (let ((s (map char->integer (string->list s))))
              (modulo
               (apply +
                      (map (lambda (i s)
                             (* (expt p i) s))
                           (range (length s))
                           s))
               (vector-length ht))))
           ((s ht)
            (hashval s ht (vector-ref *mersenne-primes* 2)))
           ((s)
            (hashval s bucket))))
       ;;; ハッシュテーブル操作関数
       ;; 検索
       (define (lookup key)
         (let ((lst (vector-ref bucket (hashval key))))
           (and ((compose1 not null?) lst)
                (entry-value
                 (car
                  (member key lst
                          (lambda (x y)
                            (string=? x (entry-key y)))))))))
       ;; 削除
       (define (delete key)
         (let ((hv (hashval key)))
           (vector-set! bucket hv
                        (remove key
                                (vector-ref bucket hv)
                                (lambda (x y)
                                  (string=? x (entry-key y)))))))
       ;; 挿入
       (define insert
         (case-lambda
           ((vec key val flag)
            (let ((hv (hashval key vec)))
              (when flag
                (delete key))
              (vector-set! vec hv
                           (cons (entry key val) (vector-ref vec hv)))))
           ((vec key val)
            (insert vec key val #f))
           ((key val)
            (when (check-size?)
              (rehash))
            (insert bucket key val #t))))
       ;; キーのリストを返す
       (define (getkeys)
         (get-entries entry-key))
       ;; 値のリストを返す
       (define (getvalues)
         (get-entries entry-value))
       ;;; ユーティリティ
       ;; エントリを返す
       (define get-entries
         (case-lambda
           ((proc)
            (map proc (get-entries)))
           (()
            (flatten (vector->list bucket)))))
       ;; ハッシュテーブルを占めるデータの割合を計算する
       (define check-size?
         (case-lambda
           ((threshold)
            (> (/ (length (get-entries)) (vector-length bucket)) threshold))
           (()
            (check-size? 0.8))))
       ;; リハッシュ
       (define (rehash)
         (let* ((n (vector-length bucket))
                (v (make-vector
                    (stream-first
                     (stream-drop-while
                      (lambda (x)
                        (< x (* 2 n))) primes)) '())))
           (for-each (lambda (key val)
                       (insert v key val)) (getkeys) (getvalues))
           (set! bucket v)))
       ;; デバッグ用
       (define (print)
         (display bucket)
         (newline))
       ;; *ディスパッチ関数*
       ;; ここでオブジェクト外に「公開する」メソッドと「隠蔽する」メソッド
       ;; に分かれる(登録すると「公開」される)。
       ;; 通常のOOPで言う"public"と"private"だ。
       (define (dispatch message)
         (case message
           ((delete) delete)
           ((getkeys) getkeys)
           ((getvalues) getvalues)
           ((insert) insert)
           ((lookup) lookup)
           ;; デバッグ用
;;            ((check-size?) check-size?)
;;            ((get-entries) get-entries)
;;            ((print) print)
;;            ((rehash) rehash)
           (else (error "Unknown request --MAKE-HT" message))))
       dispatch
       ))
    (() (make-ht (stream-ref primes 25)))))
 
;; メッセージ送信
; 「オブジェクト指向の理論的モデル」で書くと
; ((object message) arg0 arg1 ...)
; と面倒臭い形式で関数記述を行わないとならない。
; それを避け、「objectにmessageをsendする」と言う
; 明解な「形式」に語順を変える。
(define (send object message . args)
  (apply (object message) args))
 
; 以下の関数は send を利用して object の外部で「フツーの関数」として
; 定義されている。
;; 削除関数
(define (delete object key)
  (send object 'delete key))
 
;; キーのリストを得る
(define (getkeys object)
  (send object 'getkeys))
 
;; 値のリストを得る
(define (getvalues object)
  (send object 'getvalues))
 
;; 挿入関数
(define (insert object key val)
  (send object 'insert key val))
 
;; 検索関数
(define (lookup object key)
  (send object 'lookup key))

I2xhbmcgcmFja2V0CgoocmVxdWlyZSAob25seS1pbiBzcmZpLzQxIHN0cmVhbS1kcm9wLXdoaWxlIHN0cmVhbS1mcm9tKSkKCjs7IOe0oOaVsOWIlwooZGVmaW5lIHByaW1lcwogIChzdHJlYW0tY29ucwogICAyCiAgIChzdHJlYW0tZmlsdGVyIHByaW1lPyAoc3RyZWFtLWZyb20gMykpKSkKCihkZWZpbmUgKHByaW1lPyBuKQogIChsZXQgbG9vcCAoKHBzIHByaW1lcykpCiAgICAobGV0ICgoeCAoc3RyZWFtLWZpcnN0IHBzKSkpCiAgICAgIChvciAoPiAoZXhwdCAoc3RyZWFtLWZpcnN0IHBzKSAyKSBuKQogICAgICAgICAgKGFuZCAoKGNvbXBvc2UxIG5vdCB6ZXJvPykgKHJlbWFpbmRlciBuIHgpKQogICAgICAgICAgICAgICAobG9vcCAoc3RyZWFtLXJlc3QgcHMpKSkpKSkpCgo7OyDjg6Hjg6vjgrvjg7Pjg4zntKDmlbAo44Gu5LiA6YOoKeOBruODhuODvOODluODqygxMuWAi+OBruOBvykKKGRlZmluZSAqbWVyc2VubmUtcHJpbWVzKgogICh2ZWN0b3IgMyA3IDMxIDEyNyA4MTkxIDEzMTA3MSA1MjQyODcgMjE0NzQ4MzY0NyAyMzA1ODQzMDA5MjEzNjkzOTUxCiAgICAgICAgICA2MTg5NzAwMTk2NDI2OTAxMzc0NDk1NjIxMTEgMTYyMjU5Mjc2ODI5MjEzMzYzMzkxNTc4MDEwMjg4MTI3CiAgICAgICAgICAxNzAxNDExODM0NjA0NjkyMzE3MzE2ODczMDM3MTU4ODQxMDU3MjcpKQoKOzsg44Kt44O844Go5YCk44Gu44Oa44Ki44KS5b2i5L2c44KL5qeL6YCg5L2TCihzdHJ1Y3QgZW50cnkgKGtleSB2YWx1ZSkgIzp0cmFuc3BhcmVudCkKCjs7OyDjg4/jg4Pjgrfjg6Xjg4bjg7zjg5bjg6vnlJ/miJDplqLmlbAKKGRlZmluZSBtYWtlLWh0CiAgKGNhc2UtbGFtYmRhCiAgICAoKG4pCiAgICAgKGxldCAoKGJ1Y2tldCAobWFrZS12ZWN0b3IgbiAnKCkpKSkKICAgICAgIDs7OyDlpJrpoIXlvI/jg63jg7zjg6rjg7PjgrDjg4/jg4Pjgrfjg6XplqLmlbAKICAgICAgIChkZWZpbmUgaGFzaHZhbAogICAgICAgICAoY2FzZS1sYW1iZGEKICAgICAgICAgICAoKHMgaHQgcCkKICAgICAgICAgICAgKGxldCAoKHMgKG1hcCBjaGFyLT5pbnRlZ2VyIChzdHJpbmctPmxpc3QgcykpKSkKICAgICAgICAgICAgICAobW9kdWxvCiAgICAgICAgICAgICAgIChhcHBseSArCiAgICAgICAgICAgICAgICAgICAgICAobWFwIChsYW1iZGEgKGkgcykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoKiAoZXhwdCBwIGkpIHMpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAocmFuZ2UgKGxlbmd0aCBzKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgcykpCiAgICAgICAgICAgICAgICh2ZWN0b3ItbGVuZ3RoIGh0KSkpKQogICAgICAgICAgICgocyBodCkKICAgICAgICAgICAgKGhhc2h2YWwgcyBodCAodmVjdG9yLXJlZiAqbWVyc2VubmUtcHJpbWVzKiAyKSkpCiAgICAgICAgICAgKChzKQogICAgICAgICAgICAoaGFzaHZhbCBzIGJ1Y2tldCkpKSkKICAgICAgIDs7OyDjg4/jg4Pjgrfjg6Xjg4bjg7zjg5bjg6vmk43kvZzplqLmlbAKICAgICAgIDs7IOaknOe0ogogICAgICAgKGRlZmluZSAobG9va3VwIGtleSkKICAgICAgICAgKGxldCAoKGxzdCAodmVjdG9yLXJlZiBidWNrZXQgKGhhc2h2YWwga2V5KSkpKQogICAgICAgICAgIChhbmQgKChjb21wb3NlMSBub3QgbnVsbD8pIGxzdCkKICAgICAgICAgICAgICAgIChlbnRyeS12YWx1ZQogICAgICAgICAgICAgICAgIChjYXIKICAgICAgICAgICAgICAgICAgKG1lbWJlciBrZXkgbHN0CiAgICAgICAgICAgICAgICAgICAgICAgICAgKGxhbWJkYSAoeCB5KQogICAgICAgICAgICAgICAgICAgICAgICAgICAgKHN0cmluZz0/IHggKGVudHJ5LWtleSB5KSkpKSkpKSkpCiAgICAgICA7OyDliYrpmaQKICAgICAgIChkZWZpbmUgKGRlbGV0ZSBrZXkpCiAgICAgICAgIChsZXQgKChodiAoaGFzaHZhbCBrZXkpKSkKICAgICAgICAgICAodmVjdG9yLXNldCEgYnVja2V0IGh2CiAgICAgICAgICAgICAgICAgICAgICAgIChyZW1vdmUga2V5CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKHZlY3Rvci1yZWYgYnVja2V0IGh2KQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChsYW1iZGEgKHggeSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChzdHJpbmc9PyB4IChlbnRyeS1rZXkgeSkpKSkpKSkKICAgICAgIDs7IOaMv+WFpQogICAgICAgKGRlZmluZSBpbnNlcnQKICAgICAgICAgKGNhc2UtbGFtYmRhCiAgICAgICAgICAgKCh2ZWMga2V5IHZhbCBmbGFnKQogICAgICAgICAgICAobGV0ICgoaHYgKGhhc2h2YWwga2V5IHZlYykpKQogICAgICAgICAgICAgICh3aGVuIGZsYWcKICAgICAgICAgICAgICAgIChkZWxldGUga2V5KSkKICAgICAgICAgICAgICAodmVjdG9yLXNldCEgdmVjIGh2CiAgICAgICAgICAgICAgICAgICAgICAgICAgIChjb25zIChlbnRyeSBrZXkgdmFsKSAodmVjdG9yLXJlZiB2ZWMgaHYpKSkpKQogICAgICAgICAgICgodmVjIGtleSB2YWwpCiAgICAgICAgICAgIChpbnNlcnQgdmVjIGtleSB2YWwgI2YpKQogICAgICAgICAgICgoa2V5IHZhbCkKICAgICAgICAgICAgKHdoZW4gKGNoZWNrLXNpemU/KQogICAgICAgICAgICAgIChyZWhhc2gpKQogICAgICAgICAgICAoaW5zZXJ0IGJ1Y2tldCBrZXkgdmFsICN0KSkpKQogICAgICAgOzsg44Kt44O844Gu44Oq44K544OI44KS6L+U44GZCiAgICAgICAoZGVmaW5lIChnZXRrZXlzKQogICAgICAgICAoZ2V0LWVudHJpZXMgZW50cnkta2V5KSkKICAgICAgIDs7IOWApOOBruODquOCueODiOOCkui/lOOBmQogICAgICAgKGRlZmluZSAoZ2V0dmFsdWVzKQogICAgICAgICAoZ2V0LWVudHJpZXMgZW50cnktdmFsdWUpKQogICAgICAgOzs7IOODpuODvOODhuOCo+ODquODhuOCowogICAgICAgOzsg44Ko44Oz44OI44Oq44KS6L+U44GZCiAgICAgICAoZGVmaW5lIGdldC1lbnRyaWVzCiAgICAgICAgIChjYXNlLWxhbWJkYQogICAgICAgICAgICgocHJvYykKICAgICAgICAgICAgKG1hcCBwcm9jIChnZXQtZW50cmllcykpKQogICAgICAgICAgICgoKQogICAgICAgICAgICAoZmxhdHRlbiAodmVjdG9yLT5saXN0IGJ1Y2tldCkpKSkpCiAgICAgICA7OyDjg4/jg4Pjgrfjg6Xjg4bjg7zjg5bjg6vjgpLljaDjgoHjgovjg4fjg7zjgr/jga7libLlkIjjgpLoqIjnrpfjgZnjgosKICAgICAgIChkZWZpbmUgY2hlY2stc2l6ZT8KICAgICAgICAgKGNhc2UtbGFtYmRhCiAgICAgICAgICAgKCh0aHJlc2hvbGQpCiAgICAgICAgICAgICg+ICgvIChsZW5ndGggKGdldC1lbnRyaWVzKSkgKHZlY3Rvci1sZW5ndGggYnVja2V0KSkgdGhyZXNob2xkKSkKICAgICAgICAgICAoKCkKICAgICAgICAgICAgKGNoZWNrLXNpemU/IDAuOCkpKSkKICAgICAgIDs7IOODquODj+ODg+OCt+ODpQogICAgICAgKGRlZmluZSAocmVoYXNoKQogICAgICAgICAobGV0KiAoKG4gKHZlY3Rvci1sZW5ndGggYnVja2V0KSkKICAgICAgICAgICAgICAgICh2IChtYWtlLXZlY3RvcgogICAgICAgICAgICAgICAgICAgIChzdHJlYW0tZmlyc3QKICAgICAgICAgICAgICAgICAgICAgKHN0cmVhbS1kcm9wLXdoaWxlCiAgICAgICAgICAgICAgICAgICAgICAobGFtYmRhICh4KQogICAgICAgICAgICAgICAgICAgICAgICAoPCB4ICgqIDIgbikpKSBwcmltZXMpKSAnKCkpKSkKICAgICAgICAgICAoZm9yLWVhY2ggKGxhbWJkYSAoa2V5IHZhbCkKICAgICAgICAgICAgICAgICAgICAgICAoaW5zZXJ0IHYga2V5IHZhbCkpIChnZXRrZXlzKSAoZ2V0dmFsdWVzKSkKICAgICAgICAgICAoc2V0ISBidWNrZXQgdikpKQogICAgICAgOzsg44OH44OQ44OD44Kw55SoCiAgICAgICAoZGVmaW5lIChwcmludCkKICAgICAgICAgKGRpc3BsYXkgYnVja2V0KQogICAgICAgICAobmV3bGluZSkpCiAgICAgICA7OyAq44OH44Kj44K544OR44OD44OB6Zai5pWwKgogICAgICAgOzsg44GT44GT44Gn44Kq44OW44K444Kn44Kv44OI5aSW44Gr44CM5YWs6ZaL44GZ44KL44CN44Oh44K944OD44OJ44Go44CM6Zqg6JS944GZ44KL44CN44Oh44K944OD44OJCiAgICAgICA7OyDjgavliIbjgYvjgozjgoso55m76Yyy44GZ44KL44Go44CM5YWs6ZaL44CN44GV44KM44KLKeOAggogICAgICAgOzsg6YCa5bi444GuT09Q44Gn6KiA44GGInB1YmxpYyLjgagicHJpdmF0ZSLjgaDjgIIKICAgICAgIChkZWZpbmUgKGRpc3BhdGNoIG1lc3NhZ2UpCiAgICAgICAgIChjYXNlIG1lc3NhZ2UKICAgICAgICAgICAoKGRlbGV0ZSkgZGVsZXRlKQogICAgICAgICAgICgoZ2V0a2V5cykgZ2V0a2V5cykKICAgICAgICAgICAoKGdldHZhbHVlcykgZ2V0dmFsdWVzKQogICAgICAgICAgICgoaW5zZXJ0KSBpbnNlcnQpCiAgICAgICAgICAgKChsb29rdXApIGxvb2t1cCkKICAgICAgICAgICA7OyDjg4fjg5Djg4PjgrDnlKgKOzsgICAgICAgICAgICAoKGNoZWNrLXNpemU/KSBjaGVjay1zaXplPykKOzsgICAgICAgICAgICAoKGdldC1lbnRyaWVzKSBnZXQtZW50cmllcykKOzsgICAgICAgICAgICAoKHByaW50KSBwcmludCkKOzsgICAgICAgICAgICAoKHJlaGFzaCkgcmVoYXNoKQogICAgICAgICAgIChlbHNlIChlcnJvciAiVW5rbm93biByZXF1ZXN0IC0tTUFLRS1IVCIgbWVzc2FnZSkpKSkKICAgICAgIGRpc3BhdGNoCiAgICAgICApKQogICAgKCgpIChtYWtlLWh0IChzdHJlYW0tcmVmIHByaW1lcyAyNSkpKSkpCgo7OyDjg6Hjg4Pjgrvjg7zjgrjpgIHkv6EKOyDjgIzjgqrjg5bjgrjjgqfjgq/jg4jmjIflkJHjga7nkIboq5bnmoTjg6Ljg4fjg6vjgI3jgafmm7jjgY/jgagKOyAoKG9iamVjdCBtZXNzYWdlKSBhcmcwIGFyZzEgLi4uKQo7IOOBqOmdouWAkuiHreOBhOW9ouW8j+OBp+mWouaVsOiomOi/sOOCkuihjOOCj+OBquOBhOOBqOOBquOCieOBquOBhOOAggo7IOOBneOCjOOCkumBv+OBkeOAgeOAjG9iamVjdOOBq21lc3NhZ2XjgpJzZW5k44GZ44KL44CN44Go6KiA44GGCjsg5piO6Kej44Gq44CM5b2i5byP44CN44Gr6Kqe6aCG44KS5aSJ44GI44KL44CCCihkZWZpbmUgKHNlbmQgb2JqZWN0IG1lc3NhZ2UgLiBhcmdzKQogIChhcHBseSAob2JqZWN0IG1lc3NhZ2UpIGFyZ3MpKQoKOyDku6XkuIvjga7plqLmlbDjga8gc2VuZCDjgpLliKnnlKjjgZfjgaYgb2JqZWN0IOOBruWklumDqOOBp+OAjOODleODhOODvOOBrumWouaVsOOAjeOBqOOBl+OBpgo7IOWumue+qeOBleOCjOOBpuOBhOOCi+OAggo7OyDliYrpmaTplqLmlbAKKGRlZmluZSAoZGVsZXRlIG9iamVjdCBrZXkpCiAgKHNlbmQgb2JqZWN0ICdkZWxldGUga2V5KSkKCjs7IOOCreODvOOBruODquOCueODiOOCkuW+l+OCiwooZGVmaW5lIChnZXRrZXlzIG9iamVjdCkKICAoc2VuZCBvYmplY3QgJ2dldGtleXMpKQoKOzsg5YCk44Gu44Oq44K544OI44KS5b6X44KLCihkZWZpbmUgKGdldHZhbHVlcyBvYmplY3QpCiAgKHNlbmQgb2JqZWN0ICdnZXR2YWx1ZXMpKQoKOzsg5oy/5YWl6Zai5pWwCihkZWZpbmUgKGluc2VydCBvYmplY3Qga2V5IHZhbCkKICAoc2VuZCBvYmplY3QgJ2luc2VydCBrZXkgdmFsKSkKCjs7IOaknOe0oumWouaVsAooZGVmaW5lIChsb29rdXAgb2JqZWN0IGtleSkKICAoc2VuZCBvYmplY3QgJ2xvb2t1cCBrZXkpKQ==