[gnu-emacs-elpa] / packages / dict-tree / dict-tree.el

;;; dict-tree.el --- Dictionary data structure package

;; Copyright (C) 2004-2012  Free Software Foundation, Inc

;; Author: Toby Cubitt <toby-predictive@dr-qubit.org>
;; Version: 0.12.7
;; Keywords: extensions, matching, data structures
;;           trie, tree, dictionary, completion, regexp
;; Package-Requires: ((trie "0.2.5") (tNFA "0.1.1") (heap "0.3"))
;; URL: http://www.dr-qubit.org/emacs.php

;; This file is part of Emacs.
;;
;; GNU Emacs is free software: you can redistribute it and/or modify it under
;; the terms of the GNU General Public License as published by the Free
;; Software Foundation, either version 3 of the License, or (at your option)
;; any later version.
;;
;; GNU Emacs is distributed in the hope that it will be useful, but WITHOUT
;; ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
;; FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
;; more details.
;;
;; You should have received a copy of the GNU General Public License along
;; with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.


;;; Commentary:
;;
;; A dictionary is used to store strings, along with arbitrary data associated
;; with each string. As well as basic data insertion, manipulation and
;; retrieval, a dictionary can perform prefix searches on those strings,
;; retrieving all strings with a given prefix in either alphabetical or any
;; other order (see the `dictree-complete' and `dictree-complete-ordered'
;; functions), and is able to cache results in order to speed up those
;; searches. The package also provides persistent storage of the data
;; structures to files.
;;
;; You create a dictionary using `dictree-create', add entries to it using
;; `dictree-insert', lookup entries using `dictree-lookup', find completions
;; of sequences using `dictree-complete', find completions and sort them in
;; any order you speficy using `dictree-complete-ordered', map over it using
;; `dictree-map' and `dictree-mapcar', save it to a file using `dictree-save'
;; or `dictree-write', and load from file it using `dictree-load'. Various
;; other useful functions are also provided.
;;
;; This package uses the trie package trie.el. the tagged NFA package tNFA.el,
;; and the heap package heap.el.


;;; Change Log:
;;
;; Version 0.12.7
;; * create defstruct copier functions for dict-trees and meta-dict-trees
;; * don't transform hash tables to alists when writing dictionaries if
;;   running in an Emacs version that supports print-readable hash tables
;; * simplified `dictree-write', `dictree--write-dict-code' and
;;   `dictree--write-meta-dict-code'
;;
;; Version 0.12.6
;; * replaced obsolete `interactive-p' with `called-interactively-p'
;;
;; Version 0.12.5
;; * fixed default value handling in `read-dict'
;;
;; Version 0.12.4
;; * minor bug-fix to `dictree--edebug-pretty-print' to print "nil" instead
;;   of "()"
;; * modified `dictree-save-modified' to catch errors when saving
;;   dictionaries, and indicate failures via its return value
;; * removed `dictree-save-modified' from `kill-emacs-hook' and added it
;;   instead to `kill-emacs-query-functions', so that dictionary save failures
;;   don't make it impossible to quit Emacs
;; * fixed bug in `dictree--merge' that caused it to retain one too many list
;;   elements for non-null MAXNUM
;; * fixed `dictree--update-cache', which previously never updated cached
;;   results for lists of prefixes in `dictree-complete' queries
;; * fixed implementation of 'both cache policy
;; * fixed bug in `read-dict' preventing completion on dictionary files
;;   in `load-path'
;; * fixed bugs in synchronisation of regexp query caches, renaming
;;   `dictree--synchronise-query-cache' and
;;   `dictree--synchronise-ranked-query-cache' to
;;   `dictree--synchronise-completion-cache' and
;;   `dictree--synchronise-ranked-completion-cache', and creating separate
;;   `dictree--synchronise-regexp-cache' and
;;   `dictree--synchronise-ranked-regep-cache' functions to handle regexp
;;   query caches
;;
;; Version 0.12.3
;; * bug-fix in `dictree--edebug-pretty-print'
;;
;; Version 0.12.2
;; * bug-fix to DEFAULT argument handling in `read-dict'
;;
;; Version 0.12.1
;; * added `edebug-prin1' and `edebug-prin1-to-string' advice to prevent
;;   edebug hanging whilst printing large dictionaries
;;
;; Version 0.12
;; * complete rewrite using new trie.el library
;;
;; Note: version 0.11.1 dictionaries not compatible with version 0.12 and
;;       above
;;
;; Version 0.11.1
;; * set and restore value of `byte-compile-disable-print-circle' instead of
;;   let-binding it, to avoid warnings when compiling
;; * added `dictree-goto-line' macro to work around `goto-line' bug
;;
;; Version 0.11
;; * modified `dictree-write' so that, by default, both compiled and
;;   uncompiled versions of dictionaries are created when writing dictionaries
;;   to file
;; * fixed slow byte-compilation under Emacs 22
;;
;; Version 0.10.2
;; * very minor changes to text of some messages
;;
;; Version 0.10.1
;; * added optional DICTLIST argument to `read-dict', to allow completion from
;;   a restricted set of dictionaries
;;
;; Version 0.10
;; * finally wrote a `dictree-delete' function!
;;
;; Version 0.9.1
;; * fixed bug in `dictree-dump-words-to-buffer' (thanks to Dan Pomohaci for
;;   reporting it)
;; * replaced "word" with "key" in function arguments and docstrings, since
;;   keys don't have to be words
;; * removed "words" from dump functions' names, added TYPE argument in line
;;   with other functions, and made them non-interactive
;; * added COMPARE-FUNCTION argument to `dictree-create', which defaults to
;;   subtraction as before
;; * `dictree-read-line' reads the keys with `read', and no longer evals the
;;   data as this fails for simple, useful cases (e.g. constant lists)
;;
;; Version 0.9
;; * added meta-dictionary functionality
;; * dictionary data can now be referenced by any sequence type, not just
;;   strings * removed cl dependency
;;
;; Note: version 0.8 dictionaries not compatible with version 0.9 and above
;;
;; Version 0.8.4
;; * fixed small bug in `read-dict'
;;
;; Version 0.8.3
;; * fixed internal function and macro names
;; * changed naming prefix from dict- to dictree- to avoid conflicts
;; * `dict-write' now unloads old name and reloads new
;;
;; Version 0.8.2
;; * added more commentary
;;
;; Version 0.8.1
;; * fixed nasty bug in `dict-map' and `dict-mapcar' caused by dynamic scoping
;;
;; Version 0.8
;; * changed `dict-map(car)' into functions and made them work with
;;   lookup-only dicts
;; * `dict-insert' now returns the new data value
;; * rewrote cache data structures: data is now wrapped inside a cons cell, so
;;   that cache entries can point to it instead of duplicating it. This fixes
;;   some caching bugs and makes updating cached data when inserting words
;;   much faster
;; * dictionaries (but not lookup-only) can now associate two pieces of data
;;   with each word: normal data, used to rank words returned by
;;   `dict-complete-ordered', and meta-data, not used for ranking
;; * modified functions to work with new caching and meta-data, and added
;;   `dict-set-meta-data' and `dict-lookup-meta-data'
;; * renamed to `dict-tree' to help avoid conflicts with other packages
;;
;; Version 0.7
;; * added `dict-mapcar' macro
;;
;; Version 0.6.2
;; * minor bug fixes
;;
;; Version 0.6.1
;; * minor bug fixes
;;
;; Version 0.6
;; * added dict-size function
;; * added dict-dump-words-to-buffer function
;; * dictionaries now set their names and filenames by doing a library search
;;   for themselves when loaded using require
;; * added `read-dict' minibuffer completion function
;; * interactive commands that read a dictionary name now provide completion
;;
;; Version 0.5
;; * added dict-dump-words-to-file function
;;
;; Version 0.4
;; * fixed bug in dict-read-line
;;
;; Version 0.3
;; * added dict-map function
;;
;; Version 0.2
;; * added dictionary autosave flag and related functions;
;; * fixed bug preventing dict caches being loaded properly;
;; * explicitly require cl.el;
;;
;; Note: version 0.1 dictionaries not compatible with version 0.2 and above
;;
;; Version 0.1
;; * initial release



;;; Code:

(eval-when-compile (require 'cl))
(require 'trie)
(require 'tNFA)
(require 'bytecomp)



;;; ================================================================
;;;            Replacements for CL and Elisp functions

;; copied from cl-extra.el
(defun dictree--subseq (seq start &optional end)
  "Return the subsequence of SEQ from START to END.
If END is omitted, it defaults to the length of the sequence.
If START or END is negative, it counts from the end."
  (if (stringp seq) (substring seq start end)
    (let (len)
      (and end (< end 0) (setq end (+ end (setq len (length seq)))))
      (when (< start 0)
        (setq start (+ start (or len (setq len (length seq))))))
      (cond ((listp seq)
             (if (> start 0) (setq seq (nthcdr start seq)))
             (if end
                 (let ((res nil))
                   (while (>= (setq end (1- end)) start)
                     (push (pop seq) res))
                   (nreverse res))
               (copy-sequence seq)))
            (t
             (or end (setq end (or len (length seq))))
             (let ((res (make-vector (max (- end start) 0) nil))
                   (i 0))
               (while (< start end)
                 (aset res i (aref seq start))
                 (setq i (1+ i) start (1+ start)))
               res))))))



;; `goto-line' without messing around with mark and messages
;; Note: This is a bug in simple.el. There's clearly a place for
;;       non-interactive calls to goto-line from Lisp code, and there's
;;       no warning against doing this in the documentation. Yet
;;       goto-line *always* calls push-mark, which usually *shouldn't*
;;       be invoked by Lisp programs, as its docstring warns.
(defmacro dictree--goto-line (line)
  "Goto line LINE, counting from line 1 at beginning of buffer."
  `(progn
     (goto-char 1)
     (if (eq selective-display t)
         (re-search-forward "[\n\C-m]" nil 'end (1- ,line))
       (forward-line (1- ,line)))))



;;; ====================================================================
;;;  Internal functions and variables for use in the dictionary package

(defvar dictree-loaded-list nil
  "Stores list of loaded dictionaries.")


;; ----------------------------------------------------------------
;;                   Dictionary data cell structures

;; Note: It would be more elegant to use a defstruct for the data cells,
;;       but the problem is that the resulting setf in
;;       `dictree--wrap-insfun' won't get expanded into the cell-data
;;       accessor function at compile-time because it's burried inside a
;;       backquote construct. Not only is it inelegant to have to expand
;;       macros at run-time whenever `dictree--wrap-insfun' is called,
;;       but it also requires the 'cl-macs package to be loaded at
;;       run-time rather than just at compile-time. We could use
;;       `lexical-let' instead, but it doesn't seem worth it here.

;; wrap data in a cons cell
(defalias 'dictree--cell-create 'cons)  ; INTERNAL USE ONLY

;; get data component from data cons cell
(defalias 'dictree--cell-data 'car)  ; INTERNAL USE ONLY

;; get property list component from data cons cell
(defalias 'dictree--cell-plist 'cdr)  ; INTERNAL USE ONLY

;; set data component of data cons cell
(defalias 'dictree--cell-set-data 'setcar)  ; INTERNAL USE ONLY

;; set property list component of data cons cell
(defalias 'dictree--cell-set-plist 'setcdr)  ; INTERNAL USE ONLY

;; define setf methods so we can use setf abstraction wherever possible
(defsetf dictree--cell-data dictree--cell-set-data)
(defsetf dictree--cell-plist dictree--cell-set-plist)


;; ----------------------------------------------------------------
;;                 Dictionary cache entry structures

;; Note: We *could* us a defstruct for the cache entries, but for
;;       something this simple it doesn't seem worth it, especially
;;       given that we're using the defalias approach anyway for the
;;       data cells (above).

;; Construct and return a completion cache entry
(defalias 'dictree--cache-create 'cons)  ; INTERNAL USE ONLY

;; Return the completions list for cache entry CACHE
(defalias 'dictree--cache-results 'car)  ; INTERNAL USE ONLY

;; Return the max number of completions returned for cache entry CACHE
(defalias 'dictree--cache-maxnum 'cdr)  ; INTERNAL USE ONLY

;; Set the completions list for cache entry CACHE
(defalias 'dictree--cache-set-completions 'setcar)  ; INTERNAL USE ONLY

;; Set the completions list for cache entry CACHE
(defalias 'dictree--cache-set-maxnum 'setcdr)  ; INTERNAL USE ONLY


;; ----------------------------------------------------------------
;;                     Wrapping functions

(defun dictree--wrap-insfun (insfun)  ; INTERNAL USE ONLY
  ;; return wrapped insfun to deal with data wrapping
  `(lambda (new old)
     (dictree--cell-set-data old (,insfun (dictree--cell-data new)
                                          (dictree--cell-data old)))
     old))

(defun dictree--wrap-rankfun (rankfun)  ; INTERNAL USE ONLY
  ;; return wrapped rankfun to deal with data wrapping
  `(lambda (a b)
     (,rankfun (cons (car a) (dictree--cell-data (cdr a)))
               (cons (car b) (dictree--cell-data (cdr b))))))

(defun dictree--wrap-combfun (combfun)  ; INTERNAL USE ONLY
  ;; return wrapped combfun to deal with data wrapping
  `(lambda (cell1 cell2)
     (cons (,combfun (dictree--cell-data cell1)
                     (dictree--cell-data cell2))
           (append (dictree--cell-plist cell1)
                   (dictree--cell-plist cell2)))))

(defun dictree--wrap-filter (filter)  ; INTERNAL USE ONLY
  ;; return wrapped filter function to deal with data wrapping
  `(lambda (key data) (,filter key (dictree--cell-data data))))

(defun dictree--wrap-resultfun (resultfun)  ; INTERNAL USE ONLY
  ;; return wrapped result function to deal with data wrapping
  `(lambda (res) (,resultfun (car res) (dictree--cell-data (cdr res)))))



;; ----------------------------------------------------------------
;;                 The dictionary data structures

(defstruct
  (dictree-
   :named
   (:constructor nil)
   (:constructor dictree--create
                 (&optional
                  filename
                  (name (and filename
                             (file-name-sans-extension
                              (file-name-nondirectory filename))))
                  autosave
                  unlisted
                  (comparison-function '<)
                  (insert-function (lambda (a b) a))
                  (rank-function (lambda (a b) (> (cdr a) (cdr b))))
                  (cache-policy 'time)
                  (cache-update-policy 'synchronize)
                  lookup-cache-threshold
                  complete-cache-threshold
                  complete-ranked-cache-threshold
                  regexp-cache-threshold
                  regexp-ranked-cache-threshold
                  key-savefun key-loadfun
                  data-savefun data-loadfun
                  plist-savefun plist-loadfun
                  trie-type
                  &aux
                  (modified nil)
                  (trie (trie-create comparison-function))
                  (insfun (dictree--wrap-insfun insert-function))
                  (rankfun (dictree--wrap-rankfun rank-function))
                  (lookup-cache
                   (if lookup-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (complete-cache
                   (if complete-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (complete-ranked-cache
                   (if complete-ranked-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (regexp-cache
                   (if regexp-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (regexp-ranked-cache
                   (if regexp-ranked-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (metadict-list nil)
                  ))
   (:constructor dictree--create-custom
                 (&optional
                  filename
                  (name (and filename
                             (file-name-sans-extension
                              (file-name-nondirectory filename))))
                  autosave
                  unlisted
                  (comparison-function '<)
                  (insert-function (lambda (a b) a))
                  (rank-function (lambda (a b) (> (cdr a) (cdr b))))
                  (cache-policy 'time)
                  (cache-update-policy 'synchronize)
                  lookup-cache-threshold
                  complete-cache-threshold
                  complete-ranked-cache-threshold
                  regexp-cache-threshold
                  regexp-ranked-cache-threshold
                  key-savefun key-loadfun
                  data-savefun data-loadfun
                  plist-savefun plist-loadfun
                  &key
                  createfun insertfun deletefun
                  lookupfun mapfun emptyfun
                  stack-createfun stack-popfun stack-emptyfun
                  transform-for-print transform-from-read
                  &aux
                  (modified nil)
                  (trie (trie-create-custom
                         comparison-function
                         :createfun createfun
                         :insertfun insertfun
                         :deletefun deletefun
                         :lookupfun lookupfun
                         :mapfun mapfun
                         :emptyfun emptyfun
                         :stack-createfun stack-createfun
                         :stack-popfun stack-popfun
                         :stack-emptyfun stack-emptyfun
                         :transform-for-print transform-for-print
                         :transform-from-read transform-from-read))
                  (insfun (dictree--wrap-insfun insert-function))
                  (rankfun (dictree--wrap-rankfun rank-function))
                  (lookup-cache
                   (if lookup-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (complete-cache
                   (if complete-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (complete-ranked-cache
                   (if complete-ranked-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (regexp-cache
                   (if regexp-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (regexp-ranked-cache
                   (if regexp-ranked-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (metadict-list nil)
                  ))
   (:copier dictree--copy))
  name filename autosave modified
  comparison-function insert-function insfun rank-function rankfun
  cache-policy cache-update-policy
  lookup-cache lookup-cache-threshold
  complete-cache complete-cache-threshold
  complete-ranked-cache complete-ranked-cache-threshold
  regexp-cache regexp-cache-threshold
  regexp-ranked-cache regexp-ranked-cache-threshold
  key-savefun key-loadfun
  data-savefun data-loadfun
  plist-savefun plist-loadfun
  trie meta-dict-list)


(defstruct
  (dictree--meta-dict
   :named
   (:constructor nil)
   (:constructor dictree--meta-dict-create
                 (dictionary-list
                  &optional
                  filename
                  (name (file-name-sans-extension
                         (file-name-nondirectory filename)))
                  autosave
                  unlisted
                  (combine-function '+)
                  (cache-policy 'time)
                  (cache-update-policy 'synchronize)
                  lookup-cache-threshold
                  complete-cache-threshold
                  complete-ranked-cache-threshold
                  regexp-cache-threshold
                  regexp-ranked-cache-threshold
                  &aux
                  (dictlist
                   (mapcar
                    (lambda (dic)
                      (cond
                       ((dictree-p dic) dic)
                       ((symbolp dic) (eval dic))
                       (t (error "Invalid object in DICTIONARY-LIST"))))
                    dictionary-list))
                  (combfun (dictree--wrap-combfun combine-function))
                  (lookup-cache
                   (if lookup-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (complete-cache
                   (if complete-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (complete-ranked-cache
                   (if complete-ranked-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (regexp-cache
                   (if regexp-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  (regexp-ranked-cache
                   (if regexp-ranked-cache-threshold
                       (make-hash-table :test 'equal)
                     nil))
                  ))
   (:copier dictree--meta-dict-copy))
  name filename autosave modified
  combine-function combfun
  cache-policy cache-update-policy
  lookup-cache lookup-cache-threshold
  complete-cache complete-cache-threshold
  complete-ranked-cache complete-ranked-cache-threshold
  regexp-cache regexp-cache-threshold
  regexp-ranked-cache regexp-ranked-cache-threshold
  dictlist meta-dict-list)



;; ----------------------------------------------------------------
;;           Miscelaneous internal functions and macros

(defun dictree--trielist (dict)
  ;; Return a list of all the tries on which DICT is based. If DICT is a
  ;; meta-dict, this recursively descends the hierarchy, gathering all
  ;; the tries from the base dictionaries.
  (let (accumulate)
    (dictree--do-trielist dict)
    accumulate))

(defun dictree--do-trielist (dict)
  (declare (special accumulate))
  (if (dictree-meta-dict-p dict)
      (mapc 'dictree--do-trielist (dictree--meta-dict-dictlist dict))
    (setq accumulate (cons (dictree--trie dict) accumulate))))


(defun dictree--merge (list1 list2 cmpfun &optional combfun maxnum)
  ;; Destructively merge together sorted lists LIST1 and LIST2, sorting
  ;; elements according to CMPFUN. For non-null MAXNUM, only the first
  ;; MAXNUM are kept. For non-null COMBFUN, duplicate elements will be
  ;; merged by passing the two elements as arguments to COMBFUN, and
  ;; using the return value as the merged element.
  (or (listp list1) (setq list1 (append list1 nil)))
  (or (listp list2) (setq list2 (append list2 nil)))
  (let (res (i 0))

    ;; build up result list backwards
    (while (and list1 list2 (or (null maxnum) (< (incf i) maxnum)))
      ;; move smaller element to result list
      (if (funcall cmpfun (car list1) (car list2))
          (push (pop list1) res)
        (if (funcall cmpfun (car list2) (car list1))
            (push (pop list2) res)
          ;; if elements are equal, merge them for non-null COMBFUN
          (if combfun
              (push (funcall combfun (pop list1) (pop list2))
                    res)
            ;; otherwise, add both to result list, in order
            (push (pop list1) res)
            (push (pop list2) res)))))

    ;; return result if we already have MAXNUM entries
    (if (and maxnum (= i maxnum))
        (nreverse res)
      ;; otherwise, return result plus enough leftover entries to make
      ;; up MAXNUM (only one of list1 or list2 will be non-nil)
      (let (tmp)
        (or (null maxnum)
            (and (setq tmp (nthcdr (- maxnum i 1) list1))
                 (setcdr tmp nil))
            (and (setq tmp (nthcdr (- maxnum i 1) list2))
                 (setcdr tmp nil)))
        (nconc (nreverse res) list1 list2)))
    ))


;; (defun dictree--merge-sort (list sortfun &optional combfun)
;;   ;; Destructively sort LIST according to SORTFUN, combining
;;   ;; identical elements using COMBFUN if supplied.
;;   (dictree--do-merge-sort list (/ (length list) 2) sortfun combfun))


;; (defun dictree--do-merge-sort (list1 len sortfun combfun)
;;   ;; Merge sort LIST according to SORTFUN, combining identical
;;   ;; elements using COMBFUN.
;;   (let* ((p (nthcdr (1- len) list1))
;;       (list2 (cdr p)))
;;     (setcdr p nil)
;;     (dictree--merge
;;      (dictree--do-merge-sort list1 (/ len 2) sortfun combfun)
;;      (dictree--do-merge-sort list2 (/ len 2) sortfun combfun)
;;      sortfun combfun)))




;;; ================================================================
;;;    The (mostly) public functions which operate on dictionaries

;;;###autoload
(defun make-dictree
  (&optional
   name filename autosave unlisted
   comparison-function insert-function rank-function
   cache-policy cache-update-policy
   lookup-cache-threshold
   complete-cache-threshold
   complete-ranked-cache-threshold
   regexp-cache-threshold
   regexp-ranked-cache-threshold
   key-savefun key-loadfun
   data-savefun data-loadfun
   plist-savefun plist-loadfun
   trie-type)
  "Create an empty dictionary and return it.

If NAME is supplied, the dictionary is stored in the variable
NAME. Defaults to FILENAME stripped of directory and
extension. (Regardless of the value of NAME, the dictionary will
be stored in the default variable name when it is reloaded from
file.)

FILENAME supplies a directory and file name to use when saving
the dictionary. If the AUTOSAVE flag is non-nil, then the
dictionary will automatically be saved to this file when it is
unloaded or when exiting Emacs.

If UNLISTED is non-nil, the dictionary will not be added to the
list of loaded dictionaries. Note that this disables autosaving.

COMPARE-FUNCTION sets the function used to compare elements of
the keys. It should take two arguments, A and B, both of the type
contained by the sequences used as keys \(e.g. if the keys will
be strings, the function will be passed two characters\). It
should return t if the first is \"less than\" the
second. Defaults to `<'.

INSERT-FUNCTION sets the function used to insert data into the
dictionary. It should take two arguments: the new data, and the
data already in the dictionary, and should return the data to
insert. Defaults to replacing any existing data with the new
data.

RANK-FUNCTION sets the function used to rank the results of
`dictree-complete'. It should take two arguments, each a cons
whose car is a dictree key (a sequence) and whose cdr is the data
associated with that key. It should return non-nil if the first
argument is \"better\" than the second, nil otherwise. It
defaults to \"lexical\" comparison of the keys, ignoring the data
\(which is not very useful, since an unranked `dictree-complete'
query already does this much more efficiently\).

CACHE-POLICY should be a symbol ('time, 'length, or 'both), which
determines which query operations are cached. The 'time setting
caches queries that take longer (in seconds) than the
corresponding CACHE-THRESHOLD value. The 'length setting caches
lookups of key sequences that are longer than
LOOKUP-CACHE-THRESHOLD value (since those are likely to be the
slower ones), and caches completions of prefixes that are shorter
than the corresponding CACHE-THRESHOLD (since those are likely to
be the slower ones in that case). The setting 'both requires both
conditions to be satisfied simultaneously. In this case,
CACHE-THRESHOLD must be a plist with properties :time and :length
specifying the corresponding cache thresholds.

CACHE-UPDATE-POLICY should be a symbol ('synchronize or 'delete),
which determines how the caches are updated when data is inserted
or deleted. The former updates tainted cache entries, which makes
queries faster but insertion and deletion slower, whereas the
latter deletes any tainted cache entries, which makes queries
slower but insertion and deletion faster.

The CACHE-THRESHOLD settings set the threshold for caching the
corresponding dictionary query (lookup, completion, ranked
completion). The meaning of these values depends on the setting
of CACHE-POLICY (see above).

All CACHE-THRESHOLD's default to nil. The values nil and t are
special. If a CACHE-THRESHOLD is set to nil, no caching is done
for that type of query. If it is t, everything is cached for that
type of query \(similar behaviour can be obtained by setting the
CACHE-THRESHOLD to 0, but it is better to use t\).

KEY-SAVEFUN, DATA-SAVEFUN and PLIST-SAVEFUN are functions used to
convert keys, data and property lists into lisp objects that have
a valid read syntax, for writing to file. DATA-SAVEFUN and
PLIST-SAVEFUN are used when saving the dictionary (see
`dictree-save' and `dictree-write'), and all three functions are
used when dumping the contents of the dictionary \(see
`dictree-dump-to-buffer' and `dictree-dump-to-file'\).
KEY-SAVEFUN, DATA-SAVEFUN and PLIST-SAVEFUN should each accept
one argument: a key, data or property list from DICT,
respectively. They should return a lisp object which has a valid
read syntax. When defining these functions, be careful not to
accidentally modify the lisp object in the dictionary; usually,
you will need to make a copy before converting it.

KEY-LOADFUN, DATA-LOADFUN and PLIST-LOADFUN are used to convert
keys, data and property lists back again when loading a
dictionary (only DATA-LOADFUN and PLIST-LOADFUN, see
`dictree-save' and `dictree-write') or populating it from a
file (all three, see `dictree-populate-from-file'). They should
accept one argument: a lisp object of the type produced by the
corresponding SAVEFUN, and return a lisp object to use in the
loaded dictionary.

TRIE-TYPE sets the type of trie to use as the underlying data
structure. See `trie-create' for details."

  ;; sadly, passing null values over-rides the defaults in the defstruct
  ;; dictree--create, so we have to explicitly set the defaults again
  ;; here
  (or name (setq name (and filename (file-name-sans-extension
                                     (file-name-nondirectory filename)))))
  (or comparison-function (setq comparison-function '<))
  (or insert-function (setq insert-function (lambda (a b) a)))
  (or rank-function (setq rank-function (lambda (a b) (> (cdr a) (cdr b)))))
  (or cache-policy (setq cache-policy 'time))
  (or cache-update-policy (setq cache-update-policy 'synchronize))

  (let ((dict
         (dictree--create
          filename (when name (symbol-name name)) autosave unlisted
          comparison-function insert-function rank-function
          cache-policy cache-update-policy
          lookup-cache-threshold
          complete-cache-threshold
          complete-ranked-cache-threshold
          regexp-cache-threshold
          regexp-ranked-cache-threshold
          key-savefun key-loadfun
          data-savefun data-loadfun
          plist-savefun plist-loadfun
          trie-type)))
    ;; store dictionary in variable NAME
    (when name (set name dict))
    ;; add it to loaded dictionary list, unless it's unlisted
    (unless (or (null name) unlisted)
      (push dict dictree-loaded-list))
    dict))


;;;###autoload
(defalias 'dictree-create 'make-dictree)


;;;###autoload
(defun* make-dictree-custom
    (&optional
     name filename autosave unlisted
     &key
     comparison-function insert-function rank-function
     cache-policy cache-update-policy
     lookup-cache-threshold
     complete-cache-threshold
     complete-ranked-cache-threshold
     regexp-cache-threshold
     regexp-ranked-cache-threshold
     key-savefun key-loadfun
     data-savefun data-loadfun
     plist-savefun plist-loadfun
     createfun insertfun deletefun lookupfun mapfun emptyfun
     stack-createfun stack-popfun stack-emptyfun
     transform-for-print transform-from-read)
  "Create an empty dictionary and return it.

The NAME through PLIST-LOADFUN arguments are as for
`dictree-create' (which see).

The remaining arguments control the type of trie to use as the
underlying data structure. See `trie-create' for details."

  ;; sadly, passing null values over-rides the defaults in the defstruct
  ;; dictree--create, so we have to explicitly set the defaults again
  ;; here
  (or name (setq name (and filename (file-name-sans-extension
                                     (file-name-nondirectory filename)))))
  (or comparison-function (setq comparison-function '<))
  (or insert-function (setq insert-function (lambda (a b) a)))
  (or rank-function (setq rank-function (lambda (a b) (< (cdr a) (cdr b)))))
  (or cache-policy (setq cache-policy 'time))
  (or cache-update-policy (setq cache-update-policy 'synchronize))

  (let ((dict
         (dictree--create-custom
          filename (when name (symbol-name name)) autosave unlisted
          comparison-function insert-function rank-function
          cache-policy cache-update-policy
          lookup-cache-threshold
          complete-cache-threshold
          complete-ranked-cache-threshold
          regexp-cache-threshold
          regexp-ranked-cache-threshold
          key-savefun key-loadfun
          data-savefun data-loadfun
          plist-savefun plist-loadfun
          :createfun createfun
          :insertfun insertfun
          :deletefun deletefun
          :lookupfun lookupfun
          :mapfun mapfun
          :emptyfun emptyfun
          :stack-createfun stack-createfun
          :stack-popfun stack-popfun
          :stack-emptyfun stack-emptyfun
          :transform-for-print transform-for-print
          :transform-from-read transform-from-read)))
    ;; store dictionary in variable NAME
    (when name (set name dict))
    ;; add it to loaded dictionary list, unless it's unlisted
    (unless (or (null name) unlisted)
      (push dict dictree-loaded-list))
    dict))


;;;###autoload
(defalias 'dictree-create-custom 'make-dictree-custom)


;;;###autoload
(defun make-dictree-meta-dict
  (dictionary-list
   &optional
   name filename autosave unlisted
   combine-function
   cache-policy cache-update-policy
   lookup-cache-threshold
   complete-cache-threshold
   complete-ranked-cache-threshold
   regexp-cache-threshold
   regexp-ranked-cache-threshold)
  "Create a meta-dictionary based on the list of dictionaries
in DICTIONARY-LIST.

COMBINE-FUNCTION is used to combine data from different
dictionaries. It is passed two pieces of data, each an
association of the same key, but in different dictionaries. It
should return a combined datum.

The other arguments are as for `dictree-create'. Note that
caching is only possible if NAME is supplied, otherwise the
cache-threshold arguments are ignored."

  ;; sadly, passing null values over-rides the defaults in the defstruct
  ;; `dictree--create', so we have to explicitly set the defaults again
  ;; here
  (or name (setq name (and filename
                           (file-name-sans-extension
                            (file-name-nondirectory filename)))))
  (or combine-function (setq combine-function '+))
  (or cache-policy (setq cache-policy 'time))
  (or cache-update-policy (setq cache-update-policy 'synchronize))

  (let ((dict
         (dictree--meta-dict-create
          dictionary-list filename (when name (symbol-name name))
          autosave unlisted
          combine-function
          cache-policy cache-update-policy
          (when name lookup-cache-threshold)
          (when name complete-cache-threshold)
          (when name complete-ranked-cache-threshold)
          (when name regexp-cache-threshold)
          (when name regexp-ranked-cache-threshold))
         ))
    ;; store dictionary in variable NAME
    (when name (set name dict))
    ;; add it to loaded dictionary list, unless it's unlisted
    (unless (or (null name) unlisted)
      (push dict dictree-loaded-list))
    ;; update meta-dict-list cells of constituent dictionaries
    (unless (or (null name)
                (not (or lookup-cache-threshold
                         complete-cache-threshold
                         complete-ranked-cache-threshold
                         regexp-cache-threshold
                         regexp-ranked-cache-threshold)))
      (mapc
       (lambda (dic)
         (if (symbolp dic) (setq dic (eval dic)))
         (setf (dictree--meta-dict-list dic)
               (cons dict (dictree--meta-dict-list dic))))
       dictionary-list))
    dict))

(defalias 'dictree-create-meta-dict 'make-dictree-meta-dict)


;;;###autoload
(defun dictree-p (obj)
  "Return t if OBJ is a dictionary tree, nil otherwise."
  (or (dictree--p obj) (dictree--meta-dict-p obj)))


(defalias 'dictree-meta-dict-p 'dictree--meta-dict-p
  "Return t if argument is a meta-dictionary, nil otherwise.")

(defun dictree-empty-p (dict)
  "Return t if the dictionary DICT is empty, nil otherwise."
  (if (dictree--meta-dict-p dict)
      (catch 'nonempty
        (mapc (lambda (dic)
                (if (not (dictree-empty-p dic)) (throw 'nonempty t)))
              (dictree--meta-dict-dictlist dict)))
    (trie-empty (dictree--trie dict))))

(defsubst dictree-autosave (dict)
  "Return dictionary's autosave flag."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-autosave dict)
    (dictree--autosave dict)))

(defsetf dictree-autosave (dict) (val)
  ;; setf method for dictionary autosave flag
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-autosave ,dict) ,val)
     (setf (dictree--autosave ,dict) ,val)))

(defsubst dictree-modified (dict)
  "Return dictionary's modified flag."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-modified dict)
    (dictree--modified dict)))

(defsetf dictree-modified (dict) (val)
  ;; setf method for dictionary modified flag
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-modified ,dict) ,val)
     (setf (dictree--modified ,dict) ,val)))

(defsubst dictree-name (dict)
  "Return dictionary DICT's name."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-name dict)
    (dictree--name dict)))

(defsetf dictree-name (dict) (name)
  ;; setf method for dictionary name
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-name ,dict) ,name)
    (setf (dictree--name ,dict) ,name)))

(defsubst dictree-filename (dict)
  "Return dictionary DICT's associated file name."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-filename dict)
    (dictree--filename dict)))

(defsetf dictree-filename (dict) (filename)
  ;; setf method for dictionary filename
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-filename ,dict) ,filename)
     (setf (dictree--filename ,dict) ,filename)))

(defun dictree-comparison-function (dict)
  "Return dictionary DICT's comparison function."
  (if (dictree--meta-dict-p dict)
      (dictree-comparison-function
       (car (dictree--meta-dict-dictlist dict)))
    (dictree--comparison-function dict)))

(defalias 'dictree-insert-function 'dictree--insert-function
  "Return the insertion function for dictionary DICT.")

(defun dictree-rank-function (dict)
  "Return the rank function for dictionary DICT"
  (if (dictree--meta-dict-p dict)
      (dictree-rank-function (car (dictree--meta-dict-dictlist dict)))
    (dictree--rank-function dict)))

(defun dictree-rankfun (dict)
  ;; Return the rank function for dictionary DICT
  (if (dictree--meta-dict-p dict)
      (dictree-rankfun (car (dictree--meta-dict-dictlist dict)))
    (dictree--rankfun dict)))

(defalias 'dictree-meta-dict-combine-function
  'dictree--meta-dict-combine-function
  "Return the combine function for meta-dictionary DICT.")

(defalias 'dictree-meta-dict-dictlist
  'dictree--meta-dict-dictlist
  "Return the list of constituent dictionaries
for meta-dictionary DICT.")

(defsubst dictree-cache-policy (dict)
  "Return the cache policy for dictionary DICT."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-cache-policy dict)
    (dictree--cache-policy dict)))

(defsubst dictree-cache-update-policy (dict)
  "Return the cache update policy for dictionary DICT."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-cache-update-policy dict)
    (dictree--cache-update-policy dict)))

(defsubst dictree-lookup-cache-threshold (dict)
  "Return the lookup cache threshold for dictionary DICT."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-lookup-cache-threshold dict)
    (dictree--lookup-cache-threshold dict)))

(defsetf dictree-lookup-cache-threshold (dict) (param)
  ;; setf method for lookup cache threshold
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-lookup-cache-threshold ,dict)
             ,param)
     (setf (dictree--lookup-cache-threshold ,dict)
           ,param)))

(defsubst dictree-lookup-cache (dict)
  ;; Return the lookup cache for dictionary DICT.
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-lookup-cache dict)
    (dictree--lookup-cache dict)))

(defsubst dictree-complete-cache-threshold (dict)
  "Return the completion cache threshold for dictionary DICT."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-complete-cache-threshold dict)
    (dictree--complete-cache-threshold dict)))

(defsetf dictree-complete-cache-threshold (dict) (param)
  ;; setf method for completion cache threshold
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-complete-cache-threshold ,dict)
             ,param)
     (setf (dictree--complete-cache-threshold ,dict)
           ,param)))

(defun dictree-complete-cache (dict)
  ;; Return the completion cache for dictionary DICT.
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-complete-cache dict)
    (dictree--complete-cache dict)))

(defsubst dictree-complete-ranked-cache-threshold (dict)
  "Return the ranked completion cache threshold for dictionary DICT."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-complete-ranked-cache-threshold dict)
    (dictree--complete-ranked-cache-threshold dict)))

(defsetf dictree-complete-ranked-cache-threshold (dict) (param)
  ;; setf method for ranked completion cache threshold
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-complete-ranked-cache-threshold ,dict)
             ,param)
     (setf (dictree--complete-ranked-cache-threshold ,dict)
           ,param)))

(defun dictree-complete-ranked-cache (dict)
  ;; Return the ranked completion cache for dictionary DICT.
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-complete-ranked-cache dict)
    (dictree--complete-ranked-cache dict)))

(defsubst dictree-regexp-cache-threshold (dict)
  "Return the regexp cache threshold for dictionary DICT."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-regexp-cache-threshold dict)
    (dictree--regexp-cache-threshold dict)))

(defsetf dictree-regexp-cache-threshold (dict) (param)
  ;; setf method for regexp cache threshold
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-regexp-cache-threshold ,dict)
             ,param)
     (setf (dictree--regexp-cache-threshold ,dict)
           ,param)))

(defun dictree-regexp-cache (dict)
  ;; Return the regexp cache for dictionary DICT.
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-regexp-cache dict)
    (dictree--regexp-cache dict)))

(defsubst dictree-regexp-ranked-cache-threshold (dict)
  "Return the ranked regexp cache threshold for dictionary DICT."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-regexp-ranked-cache-threshold dict)
    (dictree--regexp-ranked-cache-threshold dict)))

(defsetf dictree-regexp-ranked-cache-threshold (dict) (param)
  ;; setf method for ranked regexp cache threshold
  `(if (dictree--meta-dict-p ,dict)
       (setf (dictree--meta-dict-regexp-ranked-cache-threshold ,dict)
             ,param)
     (setf (dictree--regexp-ranked-cache-threshold ,dict)
           ,param)))

(defun dictree-regexp-ranked-cache (dict)
  ;; Return the ranked regexp cache for dictionary DICT.
  (if (dictree--meta-dict-p dict)
      (dictree--meta-dict-regexp-ranked-cache dict)
    (dictree--regexp-ranked-cache dict)))



;; ----------------------------------------------------------------
;;                  Inserting and deleting data

(defun dictree-insert (dict key &optional data insert-function)
  "Insert KEY and DATA into dictionary DICT.
If KEY does not already exist, this creates it. How the data is
inserted depends on the dictionary's insertion function \(see
`dictree-create'\).

The optional INSERT-FUNCTION over-rides the dictionary's own
insertion function. If KEY already exists in DICT,
INSERT-FUNCTION is called with two arguments: the data DATA, and
the data associated with KEY in the dictionary. Its return value
becomes the new association for KEY."

  ;; if dictionary is a meta-dictionary, insert key into all the
  ;; dictionaries it's based on
  (if (dictree--meta-dict-p dict)
      (mapc (lambda (dic)
              (dictree-insert dic key data insert-function))
            (dictree--meta-dict-dictlist dict))

    ;; otherwise...
    (let (newdata)
      ;; set the dictionary's modified flag
      (setf (dictree-modified dict) t)
      ;; insert key in dictionary's ternary search tree
      (setq newdata
            (trie-insert
             (dictree--trie dict) key (dictree--cell-create data nil)
             (or (and insert-function
                      (dictree--wrap-insfun insert-function))
                 (dictree--insfun dict))))
      ;; update dictionary's caches
      (dictree--update-cache dict key newdata)
      ;; update cache's of any meta-dictionaries based on dict
      (mapc (lambda (dic) (dictree--update-cache dic key newdata))
            (dictree--meta-dict-list dict))

      ;; return the new data
      (dictree--cell-data newdata))))



(defun dictree-delete (dict key &optional test)
  "Delete KEY from DICT.
Returns non-nil if KEY was deleted, nil if KEY was not in DICT.

If TEST is supplied, it should be a function that accepts three
arguments: the key being deleted, its associated data, and its
associated property list. The key will then only be deleted if
TEST returns non-nil."

  (let ((dictree--delete-test test)
        deleted del)
    (cond
     ;; if DICT is a meta-dictionary, delete KEY from all dictionaries
     ;; it's based on
     ((dictree--meta-dict-p dict)
      (dolist (dic (dictree--meta-dict-dictlist dict))
        (when (setq del (dictree-delete dic key))
          (setq deleted (cons del deleted))))
      (setf (dictree-modified dict) (and deleted t))
      (setq deleted (nreverse deleted)))

     ;; otherwise...
     (t
      (setq deleted
            (trie-delete (dictree--trie dict) key
                         (when dictree--delete-test
                           (lambda (k cell)
                             (funcall dictree--delete-test
                                      k (dictree--cell-data cell)
                                      (dictree--cell-plist cell))))))
      ;; if key was deleted, have to update the caches
      (when deleted
        (dictree--update-cache dict key nil t)
        (setf (dictree-modified dict) t)
        ;; update cache's of any meta-dictionaries based on DICT
        (mapc (lambda (dic)
                (dictree--update-cache dic key nil t))
              (dictree--meta-dict-list dict)))))

    ;; return deleted key/data pair
    (when deleted
      (cons (car deleted) (dictree--cell-data (cdr deleted))))))



;; ----------------------------------------------------------------
;;                     Cache updating

(defun dictree--prefix-p (prefix str)
  "Return t if PREFIX is a prefix of STR, nil otherwise.

PREFIX and STR can be any sequence type (string, vector, or
list), but they must both be the same type. PREFIX can also be a
list of sequences, in which case it returns t if any element of
PREFIX is a prefix of STR."
  ;; wrap prefix in a list if necessary
  ;; FIXME: the test for a list of prefixes, below, will fail if the
  ;;        PREFIX sequence is a list, and the elements of PREFIX are
  ;;        themselves lists (there might be no easy way to fully fix
  ;;        this...)
  (when (or (atom prefix)
            (and (listp prefix) (not (sequencep (car prefix)))))
    (setq prefix (list prefix)))
  (let (len)
    (catch 'is-prefix
      (dolist (pfx prefix)
        (setq len (length pfx))
        (when (and (<= len (length str))
                   (equal pfx (dictree--subseq str 0 len)))
          (throw 'is-prefix t))))))


(defun dictree--above-cache-threshold-p
  (time length policy threshold &optional cache-long-keys)
  ;; Return t if query taking TIME seconds for a key of length LENGTH
  ;; should be cached according to the cache POLICY and
  ;; THRESHOLD. Otherwise, return nil. Optional argument CACHE-LONG-KEYS
  ;; means that keys of length longer than THRESHOLD are to be
  ;; cached. Default is keys of length shorter than THRESHOLD.
  (and threshold
       (or (eq threshold t)
           (and (eq policy 'time) (>= time threshold))
           ;; note: we cache lookups of *longer* keys, because those are
           ;;       likely to be slower ones
           (and (eq policy 'length)
                (if cache-long-keys
                    (>= length threshold) (<= length threshold)))
           (and (eq policy 'both)
                (or (>= time (plist-get threshold :time))
                    (if cache-long-keys
                        (>= length (plist-get threshold :length))
                      (<= length (plist-get threshold :length))))))))


(defun dictree--update-cache (dict key newdata &optional deleted)
  ;; Synchronise dictionary DICT's caches, given that the data
  ;; associated with KEY has been changed to NEWDATA, or KEY has been
  ;; deleted if DELETED is non-nil (NEWDATA is ignored in that case)."
  (let (arg reverse cache cache-entry completions cmpl maxnum)

    ;; synchronise the lookup cache if dict is a meta-dictionary, since
    ;; it's not done automatically
    (when (and (dictree--meta-dict-p dict)
               (dictree--meta-dict-lookup-cache-threshold dict))
      (setq cache (dictree--lookup-cache dict))
      (cond
       ;; if updating dirty cache entries...
       ((eq (dictree-cache-update-policy dict) 'synchronize)
        (when (gethash key cache)
          (if deleted (remhash key cache) (puthash key newdata cache))))
       ;; if deleting dirty cache entries...
       (t (remhash key cache))))

    ;; synchronize the completion cache, if it exists
    (when (dictree-complete-cache-threshold dict)
      (setq cache (dictree-complete-cache dict))
      ;; check every cache entry to see if it matches
      (maphash
       (lambda (cache-key cache-entry)
         (setq arg (car cache-key))
         (when (dictree--prefix-p arg key)
           (setq reverse (cdr cache-key))
            (cond
             ;; if updating dirty cache entries...
             ((eq (dictree-cache-update-policy dict) 'synchronize)
              (dictree--synchronize-completion-cache
               dict cache-entry arg reverse key newdata deleted))
             ;; if deleting dirty cache entries...
             (t (remhash (cons arg reverse) cache)))))
       cache))

    ;; synchronize the ranked completion cache, if it exists
    (when (dictree-complete-ranked-cache-threshold dict)
      (setq cache (dictree-complete-ranked-cache dict))
      ;; check every cache entry to see if it matches
      (maphash
       (lambda (cache-key cache-entry)
         (setq arg (car cache-key))
         (when (dictree--prefix-p arg key)
           (setq reverse (cdr cache-key))
            (cond
             ;; if updating dirty cache entries...
             ((eq (dictree-cache-update-policy dict) 'synchronize)
              (dictree--synchronize-ranked-completion-cache
               dict cache-entry arg reverse key newdata deleted))
             ;; if deleting dirty cache entries...
             (t (remhash (cons arg reverse) cache)))))
       cache))

    ;; synchronize the regexp cache, if it exists
    (when (dictree-regexp-cache-threshold dict)
      (setq cache (dictree--regexp-cache dict))
      ;; check every cache entry to see if it matches
      (maphash
       (lambda (cache-key cache-entry)
         (setq arg (car cache-key))
         (when (tNFA-regexp-match
                arg key :test (dictree--comparison-function dict))
           (setq reverse (cdr cache-key))
           (cond
            ;; if updating dirty cache entries...
            ((eq (dictree-cache-update-policy dict) 'synchronize)
             (dictree--synchronize-regexp-cache
              dict cache-entry arg reverse key newdata deleted))
            ;; if deleting dirty cache entries...
            (t (remhash (cons arg reverse) cache)))))
       cache))

    ;; synchronize the ranked regexp cache, if it exists
    (when (dictree-regexp-ranked-cache-threshold dict)
      (setq cache (dictree-regexp-ranked-cache dict))
      ;; have to check every cache entry to see if it matches
      (maphash
       (lambda (cache-key cache-entry)
         (setq arg (car cache-key))
         (when (tNFA-regexp-match
                arg key :test (dictree--comparison-function dict))
           (setq reverse (cdr cache-key))
           (cond
            ;; if updating dirty cache entries...
            ((eq (dictree-cache-update-policy dict) 'synchronize)
             (dictree--synchronize-ranked-regexp-cache
              dict cache-entry arg reverse key newdata deleted))
            ;; if deleting dirty cache entries...
            (t (remhash (cons arg reverse) cache)))))
       cache))
    ))



(defun dictree--synchronize-completion-cache
  (dict cache-entry arg reverse key newdata deleted)
  ;; Synchronize DICT's completion CACHE-ENTRY for ARG and REVERSE, for
  ;; a KEY whose data was either updated to NEWDATA or DELETED.
  (let* ((completions (dictree--cache-results cache-entry))
         (maxnum (dictree--cache-maxnum cache-entry))
         (cmpl (assoc key completions)))
    ;; if key was...
    (cond
     ;; deleted and in cached result: remove cache entry and re-run the
     ;; same completion to update the cache
     ((and deleted cmpl)
      (remhash (cons arg reverse) (dictree-complete-cache dict))
      (dictree-complete dict arg nil maxnum reverse))
     ;; modified and not in cached result: merge it into the completion
     ;; list, retaining only the first maxnum
     ((and (not deleted) (not cmpl))
      (dictree--cache-set-completions
       cache-entry
       (dictree--merge
        (list (cons key newdata)) completions
        `(lambda (a b)
           (,(trie-construct-sortfun
              (dictree-comparison-function dict))
            (car a) (car b)))
        (when (dictree--meta-dict-p dict)
          (dictree--meta-dict-combfun dict))
        maxnum)))
     ;; modified and in the cached result: update the associated data if
     ;; dict is a meta-dictionary (this is done automatically for a
     ;; normal dict)
     ((and (not deleted) cmpl (dictree--meta-dict-p dict))
      (setcdr cmpl newdata))
     ;; deleted and not in cached result: requires no action
     )))



(defun dictree--synchronize-ranked-completion-cache
  (dict cache-entry arg reverse key newdata deleted)
  ;; Synchronize DICT's ranked completion CACHE-ENTRY for ARG and
  ;; REVERSE, for a KEY whose data was either updated to NEWDATA or
  ;; DELETED.
  (let* ((completions (dictree--cache-results cache-entry))
         (maxnum (dictree--cache-maxnum cache-entry))
         (cmpl (assoc key completions))
         (cache (dictree--complete-ranked-cache dict)))
    ;; if key was...
    (cond
     ;; deleted and in cached result: remove cache entry and re-run the
     ;; same query to update the cache
     ((and deleted cmpl)
      (remhash (cons arg reverse) cache)
      (dictree-complete dict arg 'ranked maxnum reverse))
     ;; modified and not in cached result: merge it into the completion
     ;; list, retaining only the first maxnum
     ((and (not deleted) (not cmpl))
      (dictree--cache-set-completions
       cache-entry
       (dictree--merge
        (list (cons key newdata)) completions
        (dictree-rankfun dict)
        (when (dictree--meta-dict-p dict)
          (dictree--meta-dict-combfun dict))
        maxnum)))
     ;; modified and in the cached result: update the associated data if
     ;; dict is a meta-dictionary (this is done automatically for a
     ;; normal dict), re-sort, and if key is now at end of list re-run
     ;; the same query to update the cache
     ((and (not deleted) cmpl)
      (when (dictree--meta-dict-p dict) (setcdr cmpl newdata))
      (dictree--cache-set-completions
       cache-entry (sort completions (dictree-rankfun dict)))
      (when (equal key (car (last completions)))
        (remhash (cons arg reverse) cache)
        (dictree-complete dict arg 'ranked maxnum reverse)))
     ;; deleted and not in cached result: requires no action
     )))


(defun dictree--synchronize-regexp-cache
  (dict cache-entry arg reverse key newdata deleted)
  ;; Synchronize DICT's completion CACHE-ENTRY for ARG and REVERSE, for
  ;; a KEY whose data was either updated to NEWDATA or DELETED.
  (let* ((completions (dictree--cache-results cache-entry))
         (maxnum (dictree--cache-maxnum cache-entry))
         group-data
         (cmpl (catch 'found
                 (dolist (c completions)
                   (if (and (listp (car c))
                            (or (stringp (caar c))
                                (vectorp (caar c))
                                (listp (caar c))))
                       (when (equal key (caar c)) (throw 'found c))
                     (when (equal key (car c)) (throw 'found c)))))))
    ;; if key was...
    (cond
     ;; deleted and in cached result: remove cache entry and re-run the
     ;; same completion to update the cache
     ((and deleted cmpl)
      (remhash (cons arg reverse) (dictree-complete-cache dict))
      (dictree-regexp-search dict arg nil maxnum reverse))
     ;; modified and not in cached result: merge it into the completion
     ;; list, retaining only the first maxnum
     ((and (not deleted) (not cmpl))
      (save-match-data
        (set-match-data nil)
        (tNFA-regexp-match arg key
                           :test (dictree--comparison-function dict))
        (when (setq group-data (nthcdr 2 (match-data)))
          (setq key (cons key group-data))))
      (dictree--cache-set-completions
       cache-entry
       (dictree--merge
        (list (cons key newdata)) completions
        `(lambda (a b)
           (,(trie-construct-sortfun (dictree-comparison-function dict))
            ,(if group-data '(caar a) '(car a))
            ,(if group-data '(caar b) '(car b))))
        (when (dictree--meta-dict-p dict)
          (dictree--meta-dict-combfun dict))
        maxnum)))
     ;; modified and in the cached result: update the associated data if
     ;; dict is a meta-dictionary (this is done automatically for a
     ;; normal dict)
     ((and (not deleted) cmpl (dictree--meta-dict-p dict))
      (setcdr cmpl newdata))
     ;; deleted and not in cached result: requires no action
     )))



(defun dictree--synchronize-ranked-regexp-cache
  (dict cache-entry arg reverse key newdata deleted)
  ;; Synchronize DICT's ranked regexp CACHE-ENTRY for ARG and REVERSE,
  ;; for a KEY whose data was either updated to NEWDATA or DELETED.
  (let ((completions (dictree--cache-results cache-entry))
        (maxnum (dictree--cache-maxnum cache-entry))
        (cache (dictree--regexp-ranked-cache dict))
        cmpl group-data)
    (setq group-data (and (listp (caar completions))
                          (or (stringp (caar (car completions)))
                              (vectorp (caar (car completions)))
                              (listp (caar (car completions))))))
    (setq cmpl
          (catch 'found
            (dolist (c completions)
              (if group-data
                  (when (equal key (caar c)) (throw 'found c))
                (when (equal key (car c)) (throw 'found c))))))
    ;; if key was...
    (cond
     ;; deleted and in cached result: remove cache entry and re-run the
     ;; same query to update the cache
     ((and deleted cmpl)
      (remhash (cons arg reverse) cache)
      (dictree-regexp-search dict arg 'ranked maxnum reverse))
     ;; modified and not in cached result: merge it into the completion
     ;; list, retaining only the first maxnum
     ((and (not deleted) (not cmpl))
      (save-match-data
        (set-match-data nil)
        (tNFA-regexp-match arg key
                           :test (dictree--comparison-function dict))
        (when (setq group-data (nthcdr 2 (match-data)))
          (setq key (cons key group-data))))
      (dictree--cache-set-completions
       cache-entry
       (dictree--merge
        (list (cons key newdata)) completions
        (dictree-rankfun dict)
        (when (dictree--meta-dict-p dict)
          (dictree--meta-dict-combfun dict))
        maxnum)))
     ;; modified and in the cached result: update the associated data if
     ;; dict is a meta-dictionary (this is done automatically for a
     ;; normal dict), re-sort, and if key is now at end of list re-run
     ;; the same query to update the cache
     ((and (not deleted) cmpl)
      (when (dictree--meta-dict-p dict) (setcdr cmpl newdata))
      (dictree--cache-set-completions
       cache-entry
       (sort completions
             (if group-data
                 `(lambda (a b)
                    (,(dictree-rankfun dict)
                     (cons (caar a) (cdr a))
                     (cons (caar b) (cdr b))))
               (dictree-rankfun dict))))
      (when (equal key (car (last completions)))
        (remhash (cons arg reverse) cache)
        (dictree-complete dict arg 'ranked maxnum reverse)))
     ;; deleted and not in cached result: requires no action
     )))


(defun dictree-clear-caches (dict)
  "Clear all DICT's query caches."
  (interactive (list (read-dict "Dictionary: ")))
  (dolist (cachefun '(dictree-lookup-cache
                      dictree-complete-cache
                      dictree-complete-ranked-cache
                      dictree-regexp-cache
                      dictree-regexp-ranked-cache))
    (when (funcall cachefun dict)
      (clrhash (funcall cachefun dict))))
  (when (called-interactively-p 'interactive)
    (message "Cleared caches for dictionary %s" (dictree-name dict))))




;; ----------------------------------------------------------------
;;                        Retrieving data

(defun dictree-member (dict key &optional nilflag)
  "Return the data associated with KEY in dictionary DICT,
or nil if KEY is not in the dictionary.

Optional argument NILFLAG specifies a value to return instead of
nil if KEY does not exist in TREE. This allows a non-existent KEY
to be distinguished from an element with a null association. (See
also `dictree-member-p' for testing existence alone.)"
  (let* ((data (dictree--lookup dict key nilflag)))
    (if (eq data nilflag)
        nilflag
      (dictree--cell-data data))))

(defalias 'dictree-lookup 'dictree-member)

(defun dictree-member-p (dict key)
  "Return t if KEY exists in DICT, nil otherwise."
  (let ((flag '(nil)))
    (not (eq flag (dictree-member dict key flag)))))


(defun dictree--lookup (dict key nilflag)
  ;; Return association of KEY in DICT, or NILFLAG if KEY does not
  ;; exist. Does not do any data/meta-data unwrapping

  (let* ((flag '(nil))
         (data flag)
         time)
    ;; if KEY is in the cache, then we're done
    (unless (and (dictree-lookup-cache dict)
                 (setq data (gethash key (dictree--lookup-cache dict))))

      ;; otherwise, we have to look in the dictionary itself...
      (cond
       ;; if DICT is a meta-dict, look in its constituent dictionaries
       ((dictree--meta-dict-p dict)
        (let (newdata (newflag '(nil)))
          ;; time the lookup for caching
          (setq time (float-time))
          ;; look in each constituent dictionary in turn
          (dolist (dic (dictree--meta-dict-dictlist dict))
            (setq newdata (dictree--lookup dic key newflag))
            ;; skip dictionary if it doesn't contain KEY
            (unless (eq newdata newflag)
              ;; if we haven't found KEY before, we have now!
              (if (eq data flag) (setq data newdata)
                ;; otherwise, combine the previous data with the new
                ;; data
                (setq data (funcall (dictree--meta-dict-combfun dict)
                                    data newdata)))))
          (setq time (- (float-time) time))))

       ;; otherwise, DICT is a normal dictionary, so look in it's trie
       (t
        ;; time the lookup for caching
        (setq time (float-time))
        (setq data (trie-member (dictree--trie dict) key flag))
        (setq time (- (float-time) time))))

      ;; if lookup found something, and we're above the lookup
      ;; cache-threshold, cache the result
      (when (and (not (eq data flag))
                 (dictree--above-cache-threshold-p
                  time (length key) (dictree-cache-policy dict)
                  (dictree-lookup-cache-threshold dict) 'long-keys))
        (setf (dictree-modified dict) t)
        (puthash key data (dictree-lookup-cache dict))))

    ;; return the desired data
    (if (eq data flag) nilflag data)))



;; ----------------------------------------------------------------
;;                 Getting and setting meta-data

(defun dictree-put-property (dict key property value)
  "Set PROPERTY for KEY in dictionary DICT.
PROPERTY should be a symbol. Returns VALUE if successful, nil if
KEY was not found in DICT.

Note that if DICT is a meta-dictionary, then this will set KEY's
PROPERTY to VALUE in *all* its constituent dictionaries.

Unlike the data associated with a key (cf. `dictree-insert'),
properties are not included in the results of queries on the
dictionary \(`dictree-lookup', `dictree-complete',
`dictree-complete-ordered'\), nor do they affect the outcome of
any of the queries. They merely serves to tag a key with some
additional information, and can only be retrieved using
`dictree-get-property'."

  ;; sort out arguments
  (when (symbolp dict) (setq dict (eval dict)))
  (cond
   ;; set PROPERTY for KEY in all constituent dicts of a meta-dict
   ((dictree--meta-dict-p dict)
    (warn "Setting %s property for key %s in all constituent\
 dictionaries of meta-dicttionary %s" property key (dictree-name dict))
    (setf (dictree-modified dict) t)
    (let (dictree--put-property-ret)
      (mapc (lambda (dic k p v)
              (setq dictree--put-property-ret
                    (or dictree--put-property-ret
                        (dictree-put-property dic k p v))))
            (dictree--meta-dict-dictlist dict))
      ;; return VALUE if KEY was found in at least one constituent dict
      dictree--put-property-ret))
   (t  ;; set PROPERTY for KEY in normal dict
    (let ((cell (trie-member (dictree--trie dict) key)))
      (when cell
        (setf (dictree-modified dict) t)
        (setf (dictree--cell-plist cell)
              (plist-put (dictree--cell-plist cell) property value))
        value)))  ; return VALUE
   ))



(defun dictree-delete-property (dict key property)
  "Delete PROPERTY from KEY in dictionary DICT.
Returns the new property list for KEY, with PROPERTY deleted.

Setting PROPERTY to nil using `dictree-put-property' is not quite
the same thing as deleting it, since null property values can
still be detected by supplying the optional argument to
`dictree-get-propery' (which see).

Note that if DICT is a meta-dictionary, then this will delete
KEY's PROPERTY in *all* its constituent dictionaries."
  ;; sort out arguments
  (when (symbolp dict) (setq dict (eval dict)))
  (cond
   ;; delete PROPERTY from KEY in all constituent dicts of a meta-dict
   ((dictree--meta-dict-p dict)
    (warn "Deleting %s property from key %s in all constituent\
 dictionaries of meta-dicttionary %s" property key (dictree-name dict))
    (setf (dictree-modified dict) t)
    (mapcar (lambda (dic k p) (dictree-delete-property dic k p))
            (dictree--meta-dict-dictlist dict)))
   (t  ;; delete PROPERTY from KEY in normal dict
    (let* ((cell (trie-member (dictree--trie dict) key))
           plist tail tail)
      (when (and cell
                 (setq tail
                       (plist-member
                        (setq plist (dictree--cell-plist cell))
                        property)))
        (setf (dictree-modified dict) t)
        ;; delete property and value from plist
        (setcdr tail (cddr tail))
        (setq plist (delq property plist))
        (setf (dictree--cell-plist cell) plist))))
   ))



(defun dictree-get-property (dict key property &optional nilflag)
  "Get the value of PROPERTY for KEY in dictionary DICT,
or return nil if KEY is not in the dictionary.

Optional argument NILFLAG specifies a value to return instead of
nil if KEY does not exist in TREE. This allows a non-existent KEY
to be distinguished from a key for which PROPERTY is not
set. (See also `dictree-member-p' for testing existence alone.)"
  (let ((cell (dictree--lookup dict key nilflag)))
    (unless (eq cell nilflag)
      (plist-get (dictree--cell-plist cell) property))))




;; ----------------------------------------------------------------
;;                        Mapping functions

(defun dictree-mapc (function dict &optional type reverse)
  "Apply FUNCTION to all entries in dictionary DICT,
for side-effects only.

FUNCTION will be passed two arguments: a key of type
TYPE ('string, 'vector, or 'list, defaulting to 'vector) from the
dictionary, and the data associated with that key. The dictionary
entries will be traversed in \"lexical\" order, i.e. the order
defined by the dictionary's comparison function (cf.
`dictree-create').

If TYPE is 'string, it must be possible to apply the function
`string' to the elements of sequences stored in DICT.

FUNCTION is applied in ascending order, or descending order if
REVERSE is non-nil.

Note: to avoid nasty dynamic scoping bugs, FUNCTION must *not*
bind any variables with names commencing \"--\"."

  ;; "rename" FUNCTION to something hopefully unique to lessen the
  ;; likelihood of dynamic scoping bugs caused by a supplied function
  ;; binding a variable with the same name as one of the arguments
  (let ((--dictree-mapc--function function))
    (dictree--mapc
     (lambda (key data plist)
       (funcall --dictree-mapc--function key data))
     dict type reverse)))



(defun dictree--mapc (function dict &optional type reverse)
  ;; Like `dictree-mapc', but FUNCTION is passed three arguments: the
  ;; key, the data, and the property list, instead of just key and data.

  ;; try to avoid dynamic binding bugs
  (let ((--dictree--mapc--function function))
    (if (dictree--meta-dict-p dict)
        ;; for a meta-dict, use a dictree-stack
        (let ((stack (dictree-stack dict))
              entry)
          (while (setq entry (dictree--stack-pop stack))
            (funcall --dictree--mapc--function
                     (car entry)
                     (dictree--cell-data (cdr entry))
                     (dictree--cell-plist (cdr entry)))))
      ;; for a normal dictionary, map the function over its trie
      (trie-mapc
       (lambda (key cell)
         (funcall --dictree--mapc--function
                  key
                  (dictree--cell-data cell)
                  (dictree--cell-plist cell)))
       (dictree--trie dict)
       type reverse)
      )))



(defun dictree-mapf (function combinator dict &optional type reverse)
  "Apply FUNCTION to all entries in dictionary DICT,
and combine the results using COMBINATOR.

FUNCTION should take two arguments: a key sequence from the
dictionary and its associated data.

Optional argument TYPE (one of the symbols vector, lisp or
string; defaults to vector) sets the type of sequence passed to
FUNCTION. If TYPE is 'string, it must be possible to apply the
function `string' to the individual elements of key sequences
stored in DICT.

The FUNCTION will be applied and the results combined in
asscending \"lexical\" order (i.e. the order defined by the
dictionary's comparison function; cf. `dictree-create'), or
descending order if REVERSE is non-nil.

Note: to avoid nasty dynamic scoping bugs, FUNCTION and
COMBINATOR must *not* bind any variables with names
commencing \"--\"."

  ;; try to avoid dynamic scoping bugs
  (let ((--dictree-mapf--function function)
        (--dictree-mapf--combinator combinator))

    ;; for a normal dictionary, map the function over its trie
    (if (not (dictree--meta-dict-p dict))
        (trie-mapf
         `(lambda (key data)
            (,--dictree-mapf--function key (dictree--cell-data data)))
         --dictree-mapf--combinator (dictree--trie dict) type reverse)

      ;; for a meta-dict, use a dictree-stack
      (let ((--dictree-mapf--stack (dictree-stack dict))
            --dictree-mapf--entry
            --dictree-mapf--accumulate)
        (while (setq --dictree-mapf--entry
                     (dictree-stack-pop --dictree-mapf--stack))
          (setq --dictree-mapf--accumulate
                (funcall --dictree-mapf--combinator
                         (funcall --dictree-mapf--function
                                  (car --dictree-mapf--entry)
                                  (cdr --dictree-mapf--entry))
                         --dictree-mapf--accumulate)))
        --dictree-mapf--accumulate))))



(defun dictree-mapcar (function dict &optional type reverse)
  "Apply FUNCTION to all entries in dictionary DICT,
and make a list of the results.

FUNCTION should take two arguments: a key sequence from the
dictionary and its associated data.

Optional argument TYPE (one of the symbols vector, lisp or
string; defaults to vector) sets the type of sequence passed to
FUNCTION. If TYPE is 'string, it must be possible to apply the
function `string' to the individual elements of key sequences
stored in DICT.

The FUNCTION will be applied and the results combined in
asscending \"lexical\" order \(i.e. the order defined by the
dictionary's comparison function; cf. `dictree-create'\), or
descending order if REVERSE is non-nil.

Note that if you don't care about the order in which FUNCTION is
applied, just that the resulting list is in the correct order,
then

  (trie-mapf function 'cons trie type (not reverse))

is more efficient.

Note: to avoid nasty dynamic scoping bugs, FUNCTION must *not*
bind any variables with names commencing \"--\"."
  (nreverse (dictree-mapf function 'cons dict type)))



(defun dictree-size (dict)
  "Return the number of entries in dictionary DICT.
Interactively, DICT is read from the mini-buffer."
  (interactive (list (read-dict "Dictionary: ")))
  (let ((count 0))
    (dictree-mapc (lambda (&rest dummy) (incf count)) dict)
    (when (called-interactively-p 'interactive)
      (message "Dictionary %s contains %d entries"
               (dictree--name dict) count))
    count))



;; ----------------------------------------------------------------
;;                        Using dictrees as stacks

;; A dictree--meta-stack is the meta-dict version of a dictree-stack
;; (the ordinary version is just a single trie-stack). It consists of a
;; heap of trie-stacks for its constituent tries, where the heap order
;; is the usual lexical order over the keys at the top of the
;; trie-stacks.

(defstruct
  (dictree--meta-stack
   (:constructor nil)
   (:constructor dictree--meta-stack-create
                 (dict &optional (type 'vector) reverse
                  &aux
                  (combfun (dictree--meta-dict-combfun dict))
                  (sortfun (trie-construct-sortfun
                            (dictree-comparison-function dict)))
                  (heap (heap-create
                         (dictree--construct-meta-stack-heapfun sortfun)
                         (length (dictree--trielist dict))))
                  (pushed '())
                  (dummy (mapc
                          (lambda (dic)
                            (heap-add
                             heap (trie-stack dic type reverse)))
                          (dictree--trielist dict)))))
   (:constructor dictree--complete-meta-stack-create
                 (dict prefix &optional reverse
                  &aux
                  (combfun (dictree--meta-dict-combfun dict))
                  (sortfun (trie-construct-sortfun
                            (dictree-comparison-function dict)))
                  (heap (heap-create
                         (dictree--construct-meta-stack-heapfun
                          sortfun reverse)
                         (length (dictree--trielist dict))))
                  (pushed '())
                  (dummy (mapc
                          (lambda (trie)
                            (let ((stack (trie-complete-stack
                                          trie prefix reverse)))
                              (unless (trie-stack-empty-p stack)
                                (heap-add heap stack))))
                          (dictree--trielist dict)))))
      (:constructor dictree--regexp-meta-stack-create
                 (dict regexp &optional reverse
                  &aux
                  (combfun (dictree--meta-dict-combfun dict))
                  (sortfun (trie-construct-sortfun
                            (dictree-comparison-function dict)))
                  (heap (heap-create
                         (dictree--construct-meta-stack-heapfun
                          sortfun reverse)
                         (length (dictree--trielist dict))))
                  (pushed '())
                  (dummy (mapc
                          (lambda (trie)
                            (let ((stack (trie-regexp-stack
                                          trie regexp reverse)))
                              (unless (trie-stack-empty-p stack)
                                (heap-add heap stack))))
                          (dictree--trielist dict)))))
   (:copier nil))
  combfun sortfun heap pushed)



(defun dictree--construct-meta-stack-heapfun (sortfun &optional reverse)
  ;; Wrap SORTFUN, which sorts keys, so it can act on
  ;; dictree--meta-stack elements.
  (if reverse
      `(lambda (b a) (,sortfun (car (dictree-stack-first a))
                               (car (dictree-stack-first b))))
    `(lambda (a b) (,sortfun (car (dictree-stack-first a))
                             (car (dictree-stack-first b))))))


(defun dictree-stack (dict &optional type reverse)
  "Create an object that allows DICT to be accessed as a stack.

The stack is sorted in \"lexical\" order, i.e. the order defined
by the DICT's comparison function, or in reverse order if REVERSE
is non-nil. Calling `dictree-stack-pop' pops the top element (a
key and its associated data) from the stack.

Optional argument TYPE (one of the symbols vector, lisp or
string) sets the type of sequence used for the keys.

Note that any modification to DICT *immediately* invalidates all
dictree-stacks created before the modification (in particular,
calling `dictree-stack-pop' will give unpredictable results).

Operations on dictree-stacks are significantly more efficient
than constructing a real stack from the dictionary and using
standard stack functions. As such, they can be useful in
implementing efficient algorithms on dictionaries. However, in
cases where mapping functions `dictree-mapc', `dictree-mapcar' or
`dictree-mapf' would be sufficient, it is better to use one of
those instead."
  (if (dictree--meta-dict-p dict)
      (dictree--meta-stack-create dict type reverse)
    (trie-stack (dictree--trie dict) type reverse)))


(defun dictree-complete-stack (dict prefix &optional reverse)
  "Return an object that allows completions of PREFIX to be accessed
as if they were a stack.

The stack is sorted in \"lexical\" order, i.e. the order defined
by DICT's comparison function, or in reverse order if REVERSE is
non-nil. Calling `dictree-stack-pop' pops the top element (a key
and its associated data) from the stack.

PREFIX must be a sequence (vector, list or string) that forms the
initial part of a TRIE key. (If PREFIX is a string, it must be
possible to apply `string' to individual elements of TRIE keys.)
The completions returned in the alist will be sequences of the
same type as KEY. If PREFIX is a list of sequences, completions
of all sequences in the list are included in the stack. All
sequences in the list must be of the same type.

Note that any modification to DICT *immediately* invalidates all
trie-stacks created before the modification (in particular,
calling `dictree-stack-pop' will give unpredictable results).

Operations on dictree-stacks are significantly more efficient
than constructing a real stack from completions of PREFIX in DICT
and using standard stack functions. As such, they can be useful
in implementing efficient algorithms on tries. However, in cases
where `dictree-complete' or `dictree-complete-ordered' is
sufficient, it is better to use one of those instead."
  (if (dictree--meta-dict-p dict)
      (dictree--complete-meta-stack-create dict prefix reverse)
    (trie-complete-stack (dictree--trie dict) prefix reverse)))


(defun dictree-regexp-stack (dict regexp &optional reverse)
  "Return an object that allows REGEXP matches to be accessed
as if they were a stack.

The stack is sorted in \"lexical\" order, i.e. the order defined
by DICT's comparison function, or in reverse order if REVERSE is
non-nil. Calling `dictree-stack-pop' pops the top element (a key
and its associated data) from the stack.

REGEXP is a regular expression, but it need not necessarily be a
string. It must be a sequence (vector, list of string) whose
elements are either elements of the same type as elements of the
trie keys (which behave as literals in the regexp), or any of the
usual regexp special characters and backslash constructs. If
REGEXP is a string, it must be possible to apply `string' to
individual elements of the keys stored in the trie. The matches
returned in the alist will be sequences of the same type as KEY.

Back-references and non-greedy postfix operators are *not*
supported, and the matches are always anchored, so `$' and `^'
lose their special meanings.

If the regexp contains any non-shy grouping constructs, subgroup
match data is included in the results. In this case, the car of
each match is no longer just a key. Instead, it is a list whose
first element is the matching key, and whose remaining elements
are cons cells whose cars and cdrs give the start and end indices
of the elements that matched the corresponding groups, in order.

Note that any modification to DICT *immediately* invalidates all
trie-stacks created before the modification (in particular,
calling `dictree-stack-pop' will give unpredictable results).

Operations on dictree-stacks are significantly more efficient
than constructing a real stack from completions of PREFIX in DICT
and using standard stack functions. As such, they can be useful
in implementing efficient algorithms on tries. However, in cases
where `dictree-complete' or `dictree-complete-ordered' is
sufficient, it is better to use one of those instead."
  (if (dictree--meta-dict-p dict)
      (dictree--regexp-meta-stack-create dict regexp reverse)
    (trie-regexp-stack (dictree--trie dict) regexp reverse)))


(defun dictree-stack-pop (dictree-stack)
  "Pop the first element from the DICTREE-STACK.
Returns nil if the stack is empty."
  (cond
   ;; if elements have been pushed onto a dict stack, pop those first
   ;; FIXME: shouldn't be using internal trie functions!
   ((and (trie-stack-p dictree-stack)
         (trie--stack-pushed dictree-stack))
    (trie-stack-pop dictree-stack))
   ;; if elements have been pushed onto a meta-dict stack, pop those
   ;; first
   ((and (dictree--meta-stack-p dictree-stack)
         (dictree--meta-stack-pushed dictree-stack))
    (pop (dictree--meta-stack-pushed dictree-stack)))
   ;; otherwise, pop first element from dictree-stack
   (t (let ((popped (dictree--stack-pop dictree-stack)))
        (when popped
          (cons (car popped) (dictree--cell-data (cdr popped))))))
   ))


(defun dictree-stack-push (element dictree-stack)
  "Push ELEMENT onto DICTREE-STACK."
  (if (trie-stack-p dictree-stack)
      ;; normal dict
      (trie-stack-push element dictree-stack)
    ;; meta-dict
    (push element (dictree--meta-stack-pushed dictree-stack))))


(defun dictree-stack-first (dictree-stack)
  "Return the first element from DICTREE-STACK, without removing it.
Returns nil if the stack is empty."
  ;; if elements have been pushed onto the stack, return first of those
  (if (and (dictree--meta-stack-p dictree-stack)
           (dictree--meta-stack-pushed dictree-stack))
      (car (dictree--meta-stack-pushed dictree-stack))
    ;; otherwise, return first element from dictree-stack
    (let ((first (dictree--stack-first dictree-stack)))
      (cons (car first) (dictree--cell-data (cdr first))))))


(defun dictree-stack-empty-p (dictree-stack)
  "Return t if DICTREE-STACK is empty, nil otherwise."
  (if (trie-stack-p dictree-stack)
      ;; normal dict
      (trie-stack-empty-p dictree-stack)
    ;; meta-dict
    (and (heap-empty (dictree--meta-stack-heap dictree-stack))
         (null (dictree--meta-stack-pushed dictree-stack)))))


(defun dictree--stack-first (dictree-stack)
  "Return the first element from DICTREE-STACK, without removing it.
Returns nil if the stack is empty."
  (if (trie-stack-p dictree-stack)
      ;; normal dict
      (trie-stack-first dictree-stack)
    ;; meta-dict
    (if (dictree--meta-stack-pushed dictree-stack)
        ;; pushed element
        (car (dictree--meta-stack-pushed dictree-stack))
      ;; dictree-stack element
      (dictree--stack-first
       (heap-root (dictree--meta-stack-heap dictree-stack))))))


(defun dictree--stack-pop (dictree-stack)
  ;; Pop the raw first element from DICTREE-STACK. Returns nil if the
  ;; stack is empty.

  ;; dictree-stack for normal dictionaries is a trie-stack
  (if (trie-stack-p dictree-stack)
      (trie-stack-pop dictree-stack)

    ;; meta-dictionary dictree-stack...more work!
    ;; if elements have been pushed onto meta-dict stack, pop those
    ;; first
    (if (dictree--meta-stack-pushed dictree-stack)
        (pop (dictree--meta-stack-pushed dictree-stack))
      ;; otherwise...
      (let ((heap (dictree--meta-stack-heap dictree-stack))
            (sortfun (dictree--meta-stack-sortfun dictree-stack))
            stack curr next cell)
        (unless (heap-empty heap)
          ;; remove the first dictree-stack from the heap, pop it's
          ;; first element, and add it back to the heap (note that it
          ;; will almost certainly not end up at the root again)
          (setq stack (heap-delete-root heap))
          (setq curr (dictree--stack-pop stack))
          (unless (dictree-stack-empty-p stack) (heap-add heap stack))
          ;; peek at the first element of the stack now at the root of
          ;; the heap
          (unless (heap-empty heap)
            (setq next (dictree--stack-first (heap-root heap)))
            ;; repeat this as long as we keep finding elements with the
            ;; same key, combining them together as we go
            (when (dictree--meta-stack-combfun dictree-stack)
              (while (and (null (funcall sortfun
                                         (car curr) (car next)))
                          (null (funcall sortfun
                                         (car next) (car curr))))
                (setq stack (heap-delete-root heap))
                (setq next (dictree--stack-pop stack))
                (setq curr
                      (cons
                       (car curr)
                       (dictree--cell-create
                        (funcall
                         (dictree--meta-stack-combfun dictree-stack)
                         (dictree--cell-data (cdr curr))
                         (dictree--cell-data (cdr next)))
                        (append (dictree--cell-plist (cdr curr))
                                (dictree--cell-plist (cdr next))))))
                (heap-add heap stack)
                (setq next (dictree--stack-first (heap-root heap))))))
          ;; return the combined dictionary element
          curr)))))




;; ----------------------------------------------------------------
;;             Functions for building advanced queries

(defun dictree--query
  (dict arg cachefun cacheparamfun triefun stackfun
   &optional rank-function maxnum reverse no-cache filter resultfun)
  ;; Return results of querying DICT with argument ARG using TRIEFUN or
  ;; STACKFUN. If result of calling CACHEPARAMFUN on DICT is non-nil,
  ;; look first for cached result in cache returned by calling CACHEFUN
  ;; on DICT, and cache result if query fulfils caching conditions. If
  ;; RANK-FUNCTION is non-nil, return results ordered accordingly. If
  ;; MAXNUM is an integer, only the first MAXNUM results will be
  ;; returned. If REVERSE is non-nil, results are in reverse order. A
  ;; non-nil NO-CACHE prevents caching of results, irrespective of
  ;; DICT's cache settings. If supplied, only results that pass FILTER
  ;; are included. A non-nil RESULTFUN is applied to results before
  ;; adding them to final results list. Otherwise, an alist of key-data
  ;; associations is returned.

  ;; wrap DICT in a list if necessary
  (when (dictree-p dict) (setq dict (list dict)))

  (let (cache cacheparam completions cmpl cache-entry)
    ;; map over all dictionaries in list
    (dolist (dic dict)
      (setq cache (funcall cachefun dic)
            cacheparam (funcall cacheparamfun dic))
      (cond
       ;; If FILTER or custom RANK-FUNCTION was specified, look in trie
       ;; since we don't cache custom searches. We pass a slightly
       ;; redefined filter to `trie-complete' to deal with data
       ;; wrapping.
       ((or filter
            (and rank-function
                 (not (eq rank-function (dictree-rank-function dic)))))
        (setq cmpl
              (dictree--do-query dic arg triefun stackfun
                                 (dictree--wrap-rankfun rank-function)
                                 maxnum reverse
                                 (when filter
                                   (dictree--wrap-filter filter)))))


       ;; if there's a cached result with enough completions, use it
       ((and (setq cache-entry
                   (if cacheparam
                       (gethash (cons arg reverse) cache)
                     nil))
             (or (null (dictree--cache-maxnum cache-entry))
                 (and maxnum
                      (<= maxnum (dictree--cache-maxnum cache-entry)))))
        (setq cmpl (dictree--cache-results cache-entry))
        ;; drop any excess completions
        (when (and maxnum
                   (or (null (dictree--cache-maxnum cache-entry))
                       (> (dictree--cache-maxnum cache-entry) maxnum)))
          (setcdr (nthcdr (1- maxnum) completions) nil)))


       ;; if there was nothing useful in the cache, do query and time it
       (t
        (let (time)
          (setq time (float-time))
          (setq cmpl
                (dictree--do-query
                 dic arg triefun stackfun
                 (when rank-function
                   (dictree--wrap-rankfun rank-function))
                 maxnum reverse nil))
          (setq time (- (float-time) time))
          ;; if we're above the dictionary's completion cache threshold,
          ;; cache the result
          (when (and (not no-cache)
                     (dictree--above-cache-threshold-p
                      time (length arg) (dictree-cache-policy dic)
                      cacheparam))
            (setf (dictree-modified dic) t)
            (puthash (cons arg reverse)
                     (dictree--cache-create cmpl maxnum)
                     cache)))))

      ;; merge new completion into completions list
      (setq completions
            (dictree--merge
             completions cmpl
             (if rank-function
                 (dictree--wrap-rankfun rank-function)
               `(lambda (a b)
                  (,(trie-construct-sortfun
                     (dictree-comparison-function (car dict)))
                   (car a) (car b))))
             nil maxnum)))

    ;; return completions list, applying RESULTFUN is specified,
    ;; otherwise just stripping meta-data
    (mapcar
     (if resultfun
         (dictree--wrap-resultfun resultfun)
       (lambda (el) (cons (car el) (dictree--cell-data (cdr el)))))
     completions)))



(defun dictree--do-query
  (dict arg triefun stackfun &optional rank-function maxnum reverse filter)
  ;; Return first MAXNUM results of querying DICT with ARG using TRIEFUN
  ;; or STACKFUN that satisfy FILTER, ordered according to RANK-FUNCTION
  ;; (defaulting to "lexical" order).

  ;; for a meta-dict, use a dictree-stack
  (if (dictree--meta-dict-p dict)
      (let ((stack (funcall stackfun dict arg reverse))
            (heap (when rank-function
                    (heap-create   ; heap order is inverse of rank order
                        (if reverse
                            rank-function
                          (lambda (a b)
                            (not (funcall rank-function a b))))
                        (1+ maxnum))))
            (i 0) cmpl completions)
        ;; pop MAXNUM completions from the stack
        (while (and (or (null maxnum) (< i maxnum))
                    (setq cmpl (dictree--stack-pop stack)))
          ;; check completion passes FILTER
          (when (or (null filter) (funcall filter cmpl))
            (if rank-function
                (heap-add heap cmpl)   ; for ranked query, add to heap
              (push cmpl completions)) ; for lexical query, add to list
            (incf i)))
        (if (null rank-function)
            ;; for lexical query, reverse and return completion list (we
            ;; built it backwards)
            (nreverse completions)
          ;; for ranked query, pass rest of completions through heap
          (while (setq cmpl (dictree--stack-pop stack))
            (heap-add heap cmpl)
            (heap-delete-root heap))
          ;; extract completions from heap
          (while (setq cmpl (heap-delete-root heap))
            (push cmpl completions))
          completions))  ; return completion list

    ;; for a normal dict, call corresponding trie function on dict's
    ;; trie. Note: could use a dictree-stack here too - would it be more
    ;; efficient?
    (funcall triefun
             (dictree--trie dict) arg rank-function
             maxnum reverse filter)))



;; ----------------------------------------------------------------
;;                        Completing

(defun dictree-complete
  (dict prefix
   &optional rank-function maxnum reverse no-cache filter resultfun)
  "Return an alist containing all completions of PREFIX in DICT
along with their associated data, sorted according to
RANK-FUNCTION (defaulting to \"lexical\" order, i.e. the order
defined by the dictionary's comparison function,
cf. `dictree-create'). Return nil if no completions are found.

PREFIX can also be a list of sequences, in which case completions of
all elements in the list are returned, merged together in a
single sorted alist.

DICT can also be a list of dictionaries, in which case
completions are sought in all dictionaries in the list. (Note
that if the same key appears in multiple dictionaries, the alist
may contain the same key multiple times, each copy associated
with the data from a different dictionary. If you want to combine
identical keys, use a meta-dictionary; see
`dictree-meta-dict-create'.)

If optional argument RANK-FUNCTION is any non-nil value that is
not a function, the completions are sorted according to the
dictionary's rank-function (see `dictree-create'). Any non-nil
value that *is* a function over-rides this. In that case,
RANK-FUNCTION should accept two arguments, both cons cells. The
car of each contains a sequence from the trie (of the same type
as PREFIX), the cdr contains its associated data. The
RANK-FUNCTION should return non-nil if first argument is ranked
strictly higher than the second, nil otherwise.

The optional integer argument MAXNUM limits the results to the
first MAXNUM completions. The default is to return all matches.

If the optional argument NO-CACHE is non-nil, it prevents caching
of the result. Ignored for dictionaries that do not have
completion caching enabled.

The FILTER argument sets a filter function for the
completions. For each potential completion, it is passed two
arguments: the completion, and its associated data. If the filter
function returns nil, the completion is not included in the
results, and doesn't count towards MAXNUM.

RESULTFUN defines a function used to process results before
adding them to the final result list. If specified, it should
accept two arguments: a key and its associated data. It's return
value is what gets added to the final result list, instead of the
default key-data cons cell."
  ;; run completion query
  (dictree--query
   dict prefix
   (if rank-function
       'dictree-complete-ranked-cache
     'dictree-complete-cache)
   (if rank-function
       'dictree-complete-ranked-cache-threshold
     'dictree-complete-cache-threshold)
   'trie-complete 'dictree-complete-stack
   (when rank-function
     (if (functionp rank-function)
         rank-function
       (dictree-rank-function (if (listp dict) (car dict) dict))))
   maxnum reverse no-cache filter resultfun))



(defun dictree-collection-function (dict string predicate all)
  "Function for use in `try-completion', `all-completions',
and `completing-read'. To complete from dictionary DICT, use the
following as the COLLECTION argument of any of those functions:

  (lambda (string predicate all)
    (dictree-collection-function dict string predicate all))

Note that PREDICATE will be called with two arguments: the
completion, and its associated data."
  (let ((completions
         (dictree-complete dict string nil nil nil nil
                           predicate (lambda (key data) key))))
    (if all completions (try-completion "" completions))))



;; ----------------------------------------------------------------
;;                      Regexp search

(defun dictree-regexp-search
  (dict regexp
   &optional rank-function maxnum reverse no-cache filter resultfun)
  "Return an alist containing all matches for REGEXP in TRIE
along with their associated data, in the order defined by
RANKFUN, defauling to \"lexical\" order (i.e. the order defined
by the trie's comparison function).  If REVERSE is non-nil, the
completions are sorted in the reverse order. Returns nil if no
completions are found.

DICT can also be a list of dictionaries, in which case matches
are sought in all dictionaries in the list. (Note that if the
same key appears in multiple dictionaries, the alist may contain
the same key multiple times, each copy associated with the data
from a different dictionary. If you want to combine identical
keys, use a meta-dictionary; see `dictree-meta-dict-create'.)

REGEXP is a regular expression, but it need not necessarily be a
string. It must be a sequence (vector, list of string) whose
elements are either elements of the same type as elements of the
trie keys (which behave as literals in the regexp), or any of the
usual regexp special characters and backslash constructs. If
REGEXP is a string, it must be possible to apply `string' to
individual elements of the keys stored in the trie. The matches
returned in the alist will be sequences of the same type as KEY.

Only a subset of the full Emacs regular expression syntax is
supported. There is no support for regexp constructs that are
only meaningful for strings (character ranges and character
classes inside character alternatives, and syntax-related
backslash constructs). Back-references and non-greedy postfix
operators are not supported, so `?' after a postfix operator
loses its special meaning. Also, matches are always anchored, so
`$' and `^' lose their special meanings (use `.*' at the
beginning and end of the regexp to get an unanchored match).

If the regexp contains any non-shy grouping constructs, subgroup
match data is included in the results. In this case, the car of
each match is no longer just a key. Instead, it is a list whose
first element is the matching key, and whose remaining elements
are cons cells whose cars and cdrs give the start and end indices
of the elements that matched the corresponding groups, in order.

If optional argument RANK-FUNCTION is any non-nil value that is
not a function, the matches are sorted according to the
dictionary's rank-function (see `dictree-create'). Any non-nil
value that *is* a function over-rides this. In that case,
RANK-FUNCTION should accept two arguments, both cons cells. The
car of each contains a sequence from the dictionary (of the same
type as PREFIX), the cdr contains its associated data. The
RANK-FUNCTION should return non-nil if first argument is ranked
strictly higher than the second, nil otherwise.

The optional integer argument MAXNUM limits the results to the
first MAXNUM matches. The default is to return all matches.

If the optional argument NO-CACHE is non-nil, it prevents caching
of the result. Ignored for dictionaries that do not have wildcard
caching enabled.

The FILTER argument sets a filter function for the matches. If
supplied, it is called for each possible match with two
arguments: the matching key, and its associated data. If the
filter function returns nil, the match is not included in the
results, and does not count towards MAXNUM.

RESULTFUN defines a function used to process results before
adding them to the final result list. If specified, it should
accept two arguments: a key and its associated data. It's return
value is what gets added to the final result list, instead of the
default key-data cons cell."
  ;; run regexp query
  (dictree--query
   dict regexp
   (if rank-function
       'dictree-regexp-ranked-cache
     'dictree-regexp-cache)
   (if rank-function
       'dictree-regexp-ranked-cache-threshold
     'dictree-regexp-cache-threshold)
   'trie-regexp-search 'dictree-regexp-stack
   (when rank-function
     (if (functionp rank-function)
         rank-function
       (dictree-rank-function (if (listp dict) (car dict) dict))))
   maxnum reverse no-cache filter resultfun))




;; ----------------------------------------------------------------
;;                    Persistent storage

(defun dictree-save (dict &optional compilation)
  "Save dictionary DICT to it's associated file.
Use `dictree-write' to save to a different file.

Optional argument COMPILATION determines whether to save the
dictionary in compiled or uncompiled form. The default is to save
both forms. See `dictree-write'.

Interactively, DICT is read from the mini-buffer."
  (interactive (list (read-dict "Dictionary: ")))

  (let ((filename (dictree-filename dict)))

    ;; if dictionary has no associated file, prompt for one
    (unless (and filename (> (length filename) 0))
      (setq filename
            (read-file-name
             (format "Save dictionary %s to file\
 (leave blank to NOT save): "
                     (dictree-name dict))
             nil "")))

    ;; if filename is blank, don't save
    (if (string= filename "")
        (message "Dictionary %s NOT saved" (dictree-name dict))
      ;; otherwise write dictionary to file
      (setf (dictree-filename dict) filename)
      (dictree-write dict filename t compilation))))



(defun dictree-write (dict &optional filename overwrite compilation)
  "Write dictionary DICT to file FILENAME.
Defaults to dictionary's current filename if FILENAME is not
specified (like `dictree-save').

If optional argument OVERWRITE is non-nil, no confirmation will
be asked for before overwriting an existing file.

The default is to create both compiled and uncompiled versions of
the dictionary, with extensions .elc and .el respectively (if
FILENAME has either of these extensions, they are stripped off
before proceeding). The compiled version is always used in
preference to the uncomplied version, as it loads
faster. However, only the uncompiled version is portable between
different Emacs versions.

If optional argument COMPILATION is the symbol 'compiled, only
the compiled version will be created, whereas if it is the symbol
'uncompiled, only the uncompiled version will be created.

Interactively, DICT and FILENAME are read from the mini-buffer,
and OVERWRITE is the prefix argument."
  (interactive (list (read-dict "Dictionary: ")
                     (read-file-name "Write dictionary to file: "
                                     nil "")
                     current-prefix-arg))
  ;; default to DICT's current file, if any
  (when (or (null filename)
            (and (called-interactively-p 'any) (string= filename "")))
    (setq filename (dictree-filename dict)))
  (if (null filename)
      (progn
        (message "Dictionary %s NOT written" (dictree-name dict))
        nil)  ; indicate dictionary wasn't written

    (let (dictname buff tmpfile)
      ;; remove any .el(c) extension from filename
      (cond
       ((and (> (length filename) 3)
             (string= (substring filename -3) ".el"))
        (setq filename (substring filename 0 -3)))
       ((and (> (length filename) 4)
             (string= (substring filename -4) ".elc"))
        (setq filename (substring filename 0 -4))))
      ;; create saved dictionary name from filename
      (setq dictname (file-name-nondirectory filename))

      (save-excursion
        ;; create a temporary file
        (setq buff
              (find-file-noselect
               (setq tmpfile (make-temp-file dictname))))
        (set-buffer buff)
        ;; call the appropriate write function to write the dictionary
        ;; code
        (if (dictree--meta-dict-p dict)
            (dictree--write-meta-dict-code dict dictname filename)
          (dictree--write-dict-code dict dictname filename))
        (save-buffer)
        (kill-buffer buff))

      ;; prompt to overwrite if necessary
      (when (or overwrite
                (and
                 (or (eq compilation 'compiled)
                     (not (file-exists-p (concat filename ".el"))))
                 (or (eq compilation 'uncompiled)
                     (not (file-exists-p (concat filename ".elc")))))
                (y-or-n-p
                 (format "File %s already exists. Overwrite? "
                         (concat filename ".el(c)"))))
        (condition-case nil
            (progn
              ;; move the uncompiled version to its final destination
              (unless (eq compilation 'compiled)
                (copy-file tmpfile (concat filename ".el") t))
              ;; byte-compile and move the compiled version to its final
              ;; destination
              (unless (eq compilation 'uncompiled)
                (if (save-window-excursion
                      (let ((restore byte-compile-disable-print-circle)
                            err)
                        (setq byte-compile-disable-print-circle t)
                        (setq err (byte-compile-file tmpfile))
                        (setq byte-compile-disable-print-circle restore)
                        err))
                    (rename-file (concat tmpfile ".elc")
                                 (concat filename ".elc") t)
                  (error ""))))
          (error "Error writing dictionary. Dictionary %s NOT saved"
                 dictname))

        ;; if writing to a different name, unload dictionary under old
        ;; name and reload it under new one
        (setf (dictree-modified dict) nil)
        (setf (dictree-filename dict) filename)
        (unless (string= dictname (dictree-name dict))
          (dictree-unload dict)
          (dictree-load filename)))

      (delete-file tmpfile)
      (message "Dictionary %s saved to %s" dictname filename)
      t)  ; return t to indicate dictionary was successfully saved
    ))



(defun dictree-save-modified (&optional dict ask compilation force
                                        no-fail-query)
  "Save all modified dictionaries that have their autosave flag set.
Returns t if all dictionaries were successfully saved. Otherwise,
inform the user about the dictionaries which failed to save
properly, ask them whether they wish to continue anyway, and
return t or nil accordingly.

If optional argument DICT is a list of dictionaries or a single
dictionary, only save those.

If optional argument ASK is non-nil, ask for confirmation before
saving.

Optional argument COMPILATION determines whether to save the
dictionaries in compiled or uncompiled form. The default is to
save both forms. See `dictree-write'.

If optional argument FORCE is non-nil, save modified dictionaries
irrespective of their autosave flag.

If optional argument NO-FAIL-QUERY is non-nil, the user will not
be queried if a dictionary fails to save properly, and the return
value is always nil.

Interactively, FORCE is the prefix argument, and the user will not be
asked whether they wish to continue after a failed save."
  (interactive "P")

  ;; sort out arguments
  (when (and (called-interactively-p 'any) dict) (setq dict nil force t))
  (when (dictree-p dict) (setq dict (list dict)))

  ;; For each dictionary in list / each loaded dictionary, check if
  ;; dictionary has been modified. If so, save it if autosave is set or
  ;; FORCE is non-nil.
  (let (save-failures)
    (dolist (dic (if (null dict)
                     dictree-loaded-list
                   dict))
      (when (and (dictree-modified dic)
                 (or force (dictree-autosave dic))
                 (or (not ask)
                     (y-or-n-p (format "Save modified dictionary %s? "
                                       (dictree-filename dic)))))
        (condition-case nil
            (progn
              (dictree-save dic compilation)
              (setf (dictree-modified dic) nil))
          (error (push dic save-failures)))))

    ;; prompt if dictionary saving failed
    (if save-failures
        (if (or (called-interactively-p 'any) no-fail-query)
            (progn
              (message
               (concat
                "Error: failed to save the following modified "
                "dictionaries: "
                (mapconcat 'dictree--name save-failures ", ")))
              nil)
          (yes-or-no-p
           (concat "Error: failed to save the following modified "
                   "dictionaries: "
                   (mapconcat 'dictree--name save-failures ", ")
                   "; continue anyway? ")))
      t)))


;; Add the dictree-save-modified function to the kill-emacs-hook to save
;; modified dictionaries when exiting emacs
(add-hook 'kill-emacs-query-functions 'dictree-save-modified)



;;;###autoload
(defun dictree-load (file)
  "Load a dictionary object from file FILE.
Returns the dictionary if successful, nil otherwise.

Interactively, FILE is read from the mini-buffer."
  (interactive (list (read-dict "Load dictionary: " nil nil t t)))

  ;; sort out dictionary name and file name
  (if (dictree-p file)
      (message "Dictionary %s already loaded" (dictree-name file))

    ;; load the dictionary
    (if (not (load file t))
        ;; if loading failed, throw error interactively, return nil
        ;; non-interactively
        (if (called-interactively-p 'any)
            (error "Cannot open dictionary file: %s" file)
          nil)

      (let (dictname dict)
        (setq dictname
              (file-name-nondirectory (file-name-sans-extension file))
              dict (eval (intern-soft dictname)))
        (if (not (dictree-p dict))
            ;; if loading failed, throw error interactively, return nil
            ;; non-interactively
            (if (called-interactively-p 'any)
                (error "Error loading dictionary file: %s" file)
              nil)

          ;; ensure the dictionary name and file name associated with
          ;; the dictionary match the file it was loaded from
          (when (and (string= (file-name-nondirectory file) file)
                     (setq file
                           (locate-file file load-path load-suffixes)))
            (setf (dictree-filename dict) file))
          (setf (dictree-name dict) dictname)

          ;; make sure the dictionary is in dictree-loaded-list
          ;; (normally the lisp code in the dictionary itself should do
          ;; this, but just to make sure...)
          (unless (memq dict dictree-loaded-list)
            (push dict dictree-loaded-list))
          (message (format "Loaded dictionary %s" dictname))

          ;; return dictionary
          dict)))))



(defun dictree-unload (dict &optional dont-save)
  "Unload dictionary DICT.
If optional argument DONT-SAVE is non-nil, the dictionary will
NOT be saved even if its autosave flag is set.

Interactively, DICT is read from the mini-buffer, and DONT-SAVE
is the prefix argument."
  (interactive (list (read-dict "Dictionary: ")
                     current-prefix-arg))

  ;; if dictionary has been modified, autosave is set and not overidden,
  ;; save it first
  (when (and (dictree-modified dict)
             (null dont-save)
             (or (eq (dictree-autosave dict) t)
                 (and (eq (dictree-autosave dict) 'ask)
                      (y-or-n-p
                       (format
                        "Dictionary %s modified.\
 Save before unloading? "
                        (dictree-name dict))))))
    (dictree-save dict))

  ;; if unloading a meta-dict, remove reference to it from constituent
  ;; dictionaries' meta-dict-list cell
  (when (dictree--meta-dict-p dict)
    (mapc
     (lambda (dic)
       (setf (dictree--meta-dict-list dic)
             (delq dict (dictree--meta-dict-list dic))))
     (dictree--meta-dict-dictlist dict)))

  ;; remove dictionary from list of loaded dictionaries and unload it
  (setq dictree-loaded-list (delq dict dictree-loaded-list))
  (unintern (dictree-name dict))
  (message "Dictionary %s unloaded" (dictree-name dict)))



(defun dictree--write-dict-code (dict dictname filename)
  ;; Write code for normal dictionary DICT to current buffer, giving it
  ;; the name DICTNAME and file FILENAME.
  (let (hashcode tmpdict tmptrie lookup-alist
        complete-alist complete-ranked-alist
        regexp-alist regexp-ranked-alist)

    ;; --- convert trie data ---
    ;; if dictionary doesn't use any custom save functions, write
    ;; dictionary's trie directly as is
    (setq tmptrie (dictree--trie dict))
    ;; otherwise, create a temporary trie and populate it with the
    ;; converted contents of the dictionary's trie
    (when (or (dictree--data-savefun dict)
              (dictree--plist-savefun dict))
      (setq tmptrie
            (trie-create-custom
             (trie-comparison-function tmptrie)
             :createfun (trie--createfun tmptrie)
             :insertfun (trie--insertfun tmptrie)
             :deletefun (trie--deletefun tmptrie)
             :lookupfun (trie--lookupfun tmptrie)
             :mapfun (trie--mapfun tmptrie)
             :emptyfun (trie--emptyfun tmptrie)
             :stack-createfun (trie--stack-createfun tmptrie)
             :stack-popfun (trie--stack-popfun tmptrie)
             :stack-emptyfun (trie--stack-emptyfun tmptrie)))
      (trie-mapc
       (lambda (key cell)
         (trie-insert tmptrie key
                      (dictree--cell-create
                       (funcall (or (dictree--data-savefun dict)
                                    'identity)
                                (dictree--cell-data cell))
                       (funcall (or (dictree--plist-savefun dict)
                                    'identity)
                                (dictree--cell-plist cell)))))
       (dictree--trie dict))

      ;; generate code to convert contents of trie back to original form
      (setq hashcode
            (concat
             hashcode
             " (trie-map\n"
             "  (lambda (key cell)\n"
             "     (dictree--cell-create\n"
             (if (dictree--data-loadfun dict)
                 (concat
                  "(funcall (dictree--data-loadfun " dictname ")\n"
                  "         (dictree--cell-data cell))\n")
               "   (dictree--cell-data cell)\n")
             (if (dictree--plist-loadfun dict)
                 (concat
                  "(funcall (dictree--plist-loadfun " dictname ")\n"
                  "         (dictree--cell-plist cell))))\n")
               "   (dictree--cell-plist cell)))\n")
             " (dictree--trie " dictname "))\n")))


    ;; --- convert caches for writing to file ---
    ;; hash tables have no read syntax in older Emacsen, so we convert
    ;; them to alists for writing
    (unless (featurep 'hashtable-print-readable)
      ;; convert lookup cache hash table to alist, if it exists
      (when (dictree--lookup-cache-threshold dict)
        (maphash
         (lambda (key val)
           (push
            (cons key
                  (cons (mapcar 'car (dictree--cache-results val))
                        (dictree--cache-maxnum val)))
            lookup-alist))
         (dictree--lookup-cache dict))
        ;; generate code to reconstruct the lookup hash table
        (setq hashcode
              (concat
               hashcode
               "(let ((lookup-cache (make-hash-table :test 'equal))\n"
               "      (trie (dictree--trie " dictname ")))\n"
               "  (mapc\n"
               "   (lambda (entry)\n"
               "     (puthash\n"
               "      (car entry)\n"
               "      (dictree--cache-create\n"
               "       (mapcar\n"
               "        (lambda (key)\n"
               "          (cons key (trie-member trie key)))\n"
               "        (dictree--cache-results (cdr entry)))\n"
               "       (dictree--cache-maxnum (cdr entry)))\n"
               "      lookup-cache))\n"
               "   (dictree--lookup-cache " dictname "))\n"
               "  (setf (dictree--lookup-cache " dictname ")\n"
               "        lookup-cache))\n")))

      ;; convert query caches, if they exist
      (dolist (cache-details
               '((dictree--complete-cache-threshold
                  complete-alist dictree--complete-cache)
                 (dictree--complete-ranked-cache-threshold
                  complete-ranked-alist dictree--complete-ranked-cache)
                 (dictree--regexp-cache-threshold
                  regexp-alist dictree--regexp-cache)
                 (dictree--regexp-ranked-cache-threshold
                  regexp-ranked-alist dictree--regexp-ranked-cache)))
        (when (funcall (nth 0 cache-details) dict)
          ;; convert hash table to alist
          (set (nth 1 cache-details)
               (let (alist)
                 (maphash
                  (lambda (key val)
                    (push
                     (cons key
                           (cons
                            (mapcar 'car (dictree--cache-results val))
                            (dictree--cache-maxnum val)))
                     alist))
                  (funcall (nth 2 cache-details) dict))
                 alist))
          ;; generate code to reconstruct hash table from alist
          (setq
           hashcode
           (concat
            hashcode
            "(let ((cache (make-hash-table :test 'equal))\n"
            "      (trie (dictree--trie " dictname ")))\n"
            "  (mapc\n"
            "   (lambda (entry)\n"
            "     (puthash\n"
            "      (car entry)\n"
            "      (dictree--cache-create\n"
            "       (mapcar\n"
            "        (lambda (key)\n"
            "          (cons key\n"
            "                (trie-member\n"
            "                 trie (if (stringp key) key (car key)))))\n"
            "        (dictree--cache-results (cdr entry)))\n"
            "       (dictree--cache-maxnum (cdr entry)))\n"
            "      cache))\n"
            "   (" (symbol-name (nth 2 cache-details)) " " dictname "))\n"
            "  (setf (" (symbol-name (nth 2 cache-details)) " "
                      dictname ")\n"
            "        cache))\n")))))


    ;; --- write to file ---
    ;; generate the structure to save
    (setq tmpdict (dictree--copy dict))
    (setf (dictree--trie tmpdict) tmptrie
          (dictree--name tmpdict) dictname
          (dictree--filename tmpdict) filename
          (dictree--modified tmpdict) nil
          (dictree--meta-dict-list tmpdict) nil)
    (unless (featurep 'hashtable-print-readable)
      (setf (dictree--lookup-cache tmpdict) lookup-alist
            (dictree--complete-cache tmpdict) complete-alist
            (dictree--complete-ranked-cache tmpdict) complete-ranked-alist
            (dictree--regexp-cache tmpdict) regexp-alist
            (dictree--regexp-ranked-cache tmpdict) regexp-ranked-alist))

    ;; write lisp code that generates the dictionary object
    (let ((print-circle t) (print-level nil) (print-length nil))
      (insert "(eval-when-compile (require 'cl))\n")
      (insert "(require 'dict-tree)\n")
      (insert "(defvar " dictname " nil \"Dictionary " dictname ".\")\n")
      (insert "(setq " dictname " " (prin1-to-string tmpdict) ")\n")
      (when hashcode (insert hashcode))
      (insert "(unless (memq " dictname " dictree-loaded-list)\n"
              "  (push " dictname " dictree-loaded-list))\n"))))



(defun dictree--write-meta-dict-code (dict dictname filename)
  ;; Write code for meta-dictionary DICT to current buffer, giving it
  ;; the name DICTNAME and file FILENAME.
  (let (hashcode tmpdict lookup-alist
        complete-alist complete-ranked-alist
        regexp-alist regexp-ranked-alist)

    ;; --- convert caches for writing to file ---
    ;; hash tables have no read syntax in older Emacsen, so we convert
    ;; them to alists for writing
    (unless (featurep 'hashtable-print-readable)
      ;; convert lookup cache hash table to an alist, if it exists
      (when (dictree--meta-dict-lookup-cache-threshold dict)
        (maphash (lambda (key val)
                   (push (cons key (mapcar 'car val)) lookup-alist))
                 (dictree--meta-dict-lookup-cache dict))
        ;; generate code to reconstruct the lookup hash table
        (setq hashcode
              (concat
               hashcode
               "(let ((cache (make-hash-table :test 'equal)))\n"
               "  (mapc (lambda (entry)\n"
               "    (puthash (car entry) (cdr entry) cache))\n"
               "    (dictree--meta-dict-lookup-cache " dictname "))\n"
               "  (setf (dictree--meta-dict-lookup-cache " dictname ")\n"
               "        cache))\n")))

      ;; convert query caches, if they exist
      (dolist (cache-details
               '((dictree--meta-dict-complete-cache-threshold
                  complete-alist
                  dictree--meta-dict-complete-cache)
                 (dictree--meta-dict-complete-ranked-cache-threshold
                  complete-ranked-alist
                  dictree--meta-dict-complete-ranked-cache)
                 (dictree--meta-dict-regexp-cache-threshold
                  regexp-alist
                  dictree--meta-dict-regexp-cache)
                 (dictree--meta-dict-regexp-ranked-cache-threshold
                  regexp-ranked-alist
                  dictree--meta-dict-regexp-ranked-cache)))
        (when (funcall (nth 0 cache-details) dict)
          ;; convert hash table to alist
          (set (nth 1 cache-details)
               (let (alist)
                 (maphash
                  (lambda (key val) (push (cons key val) alist))
                  (funcall (nth 2 cache-details) dict))
                 alist))
          ;; generate code to reconstruct hash table from alist
          (setq
           hashcode
           (concat
            hashcode
            "(let ((cache (make-hash-table :test 'equal)))\n"
            "  (mapc (lambda (entry)\n"
            "    (puthash (car entry) (cdr entry) cache))\n"
            "    (" (symbol-name (nth 2 cache-details)) " "
                    dictname "))\n"
            "  (setf (" (symbol-name (nth 2 cache-details)) " "
                        dictname ")\n"
            "        cache))\n")))))


    ;; --- write to file ---
    ;; generate the structure to save
    (setq tmpdict (dictree--meta-dict-copy dict))
    (setf (dictree--meta-dict-name tmpdict) dictname
          (dictree--meta-dict-filename tmpdict) filename
          (dictree--meta-dict-modified tmpdict) nil
          (dictree--meta-dict-meta-dict-list tmpdict) nil
          (dictree--meta-dict-dictlist tmpdict)
            (mapcar (lambda (dic) (intern (dictree-name dic)))
                    (dictree--meta-dict-dictlist dict)))
    (unless (featurep 'hashtable-print-readable)
      (setf (dictree--meta-dict-lookup-cache tmpdict) lookup-alist
            (dictree--meta-dict-complete-cache tmpdict) complete-alist
            (dictree--meta-dict-complete-ranked-cache tmpdict)
              complete-ranked-alist
            (dictree--meta-dict-regexp-cache tmpdict) regexp-alist
            (dictree--meta-dict-regexp-ranked-cache tmpdict)
              regexp-ranked-alist))

    ;; write lisp code that generates the dictionary object
    (let ((print-circle t) (print-level nil) (print-length nil))
      (insert "(eval-when-compile (require 'cl))\n"
              "(require 'dict-tree)\n")
      (mapc
       (lambda (dic)
         (insert "(unless (dictree-load \"" (dictree-filename dic) "\")\n"
                 "        (error \"Failed to load dictionary \\\""
                 (dictree-name dic) "\\\" required by meta-dict \\\""
                 dictname "\\\"\"))\n"))
       (dictree--meta-dict-dictlist dict))
      (insert "(defvar " dictname " nil \"Dictionary " dictname ".\")\n"
              "(setq " dictname " " (prin1-to-string tmpdict) ")\n"
              "(setf (dictree--meta-dict-dictlist " dictname ")\n"
              "      (mapcar 'eval (dictree--meta-dict-dictlist "
                                    dictname ")))\n")
      (when hashcode (insert hashcode))
      (insert "(unless (memq " dictname " dictree-loaded-list)"
              " (push " dictname " dictree-loaded-list))\n"))))



;; ----------------------------------------------------------------
;;                Dumping and restoring contents

(defun dictree-populate-from-file
  (dict file
   &optional insert-function key-loadfun data-loadfun plist-loadfun
   balance)
  "Populate dictionary DICT from the key list in file FILE.

Each line of FILE should contain a key, either a string
\(delimited by \"\), a vector, or a list. (Use the escape
sequence \\\" to include a \" in a string.) If a line does not
contain a key, it is silently ignored.

Each line can optionally include data and a property list (in
that order) to be associated with the key. If present, these
should separated from each other and the key by whitespace.

INSERT-FUNCTION, KEY-LOAD-FUNCTION, DATA-LOAD-FUNCTION and
PLIST-LOAD-FUNCTION override the corresponding default functions
for DICT (see `dictree-create').

Interactively, DICT and FILE are read from the mini-buffer.


Technicalities:

The key, data and property list are read as lisp expressions
using `read'. The keys will be read from FILE in order, unless
BALANCE is non-nil, in which case they are read from the median
element outwards (which can help ensure efficient data structures
are created when using a trie that is not self-balancing, see
`dictree-create')."
  (interactive (list (read-dict "Dictionary: ")
                     (read-file-name "File to populate from: "
                                     nil "" t)))

  (if (and (called-interactively-p 'any) (string= file ""))
      (message "No file specified; dictionary %s NOT populated"
               (dictree-name dict))

    (unless (dictree--meta-dict-p dict)
      (unless key-loadfun
        (setq key-loadfun (dictree--key-loadfun dict)))
      (unless data-loadfun
        (setq data-loadfun (dictree--data-loadfun dict)))
      (unless plist-loadfun
        (setq plist-loadfun (dictree--plist-loadfun dict))))

    (save-excursion
      (let ((buff (find-file-noselect file)))
        (set-buffer buff)

        ;; insert the keys starting from the median to ensure a
        ;; reasonably well-balanced tree
        (let* ((lines (count-lines (point-min) (point-max)))
               (midpt (+ (/ lines 2) (mod lines 2)))
               entry)
          (message "Inserting keys in %s...(1 of %d)"
                   (dictree-name dict) lines)
          ;; insert the median key and set the dictionary's modified
          ;; flag
          (if balance
              (dictree--goto-line midpt)
            (goto-char (point-min)))
          (when (setq entry
                      (condition-case nil
                          (dictree--read-line
                           dict key-loadfun data-loadfun
                           plist-loadfun)
                        (error (error "Error reading line %d of %s"
                                      midpt file))))
            (dictree-insert dict (car entry) (nth 1 entry)
                            insert-function)
            (setf (dictree--cell-plist
                   (dictree--lookup dict (car entry) nil))
                  (nth 2 entry)))
          ;; insert keys successively further away from the median in
          ;; both directions
          (dotimes (i (1- (if balance midpt lines)))
            (if balance
                (dictree--goto-line (+ midpt i 1))
              (forward-line 1))
            (when (setq entry
                        (condition-case nil
                            (dictree--read-line
                             dict key-loadfun data-loadfun
                             plist-loadfun)
                          (error (error "Error reading line %d of %s"
                                        (+ midpt i 1) file))))
              (dictree-insert dict (car entry) (nth 1 entry)
                              insert-function)
              (setf (dictree--cell-plist
                     (dictree--lookup dict (car entry) nil))
                    (nth 2 entry)))
            (when (= 49 (mod i 50))
              (message "Inserting keys in %s...(%d of %d)"
                       (dictree-name dict)
                       (if balance (+ (* 2 i) 2) i)
                       lines))
            (when balance
              (dictree--goto-line (- midpt i 1))
              (when (setq entry
                          (condition-case nil
                              (dictree--read-line
                               dict key-loadfun data-loadfun
                               plist-loadfun)
                            (error (error "Error reading line %d of %s"
                                          (- midpt i 1) file))))
                (dictree-insert dict (car entry)
                                (nth 1 entry) insert-function)
                (setf
                 (dictree--cell-plist
                  (dictree--lookup dict (car entry) nil))
                 (nth 2 entry)))))

          ;; if inserting from mid-point out, and file contains an even
          ;; number of keys, we still have to add the last one
          (when (and balance (= 0 (mod lines 2)))
            (dictree--goto-line lines)
            (when (setq entry
                        (condition-case nil
                            (dictree--read-line
                             dict key-loadfun data-loadfun
                             plist-loadfun)
                          (error (error "Error reading line %d of %s"
                                        lines file))))
              (dictree-insert dict (car entry) (nth 1 entry)
                              insert-function)
              (setf (dictree--cell-plist
                     (dictree--lookup dict (car entry) nil))
                    (nth 2 entry))))

          (message "Inserting keys in %s...done" (dictree-name dict)))
        (kill-buffer buff)))))



(defun dictree--read-line
  (dict &optional key-loadfun data-loadfun plist-loadfun)
  ;; Return a list containing the key, data (if any, otherwise nil) and
  ;; property list (ditto) at the current line of the current buffer,
  ;; for dictionary DICT.
  (save-excursion
    (let (key data plist)
      ;; read key
      (beginning-of-line)
      (when (setq key (read (current-buffer)))
        (when key-loadfun (setq key (funcall key-loadfun key)))
        ;; if there's anything after the key, use it as data
        (unless (eq (line-end-position) (point))
          (setq data (read (current-buffer))))
        (when data-loadfun (setq data (funcall data-loadfun data)))
        ;; if there's anything after the data, use is as the property
        ;; list
        (unless (eq (line-end-position) (point))
          (setq plist (read (current-buffer))))
        (when plist-loadfun (funcall plist-loadfun plist))
        ;; return the key and data
        (list key data plist)))))



(defun dictree-dump-to-buffer (dict &optional buffer type)
  "Dump keys and their associated data
from dictionary DICT to BUFFER, in the same format as that used
by `dictree-populate-from-file'. If BUFFER exists, data will be
appended to the end of it. Otherwise, a new buffer will be
created. If BUFFER is omitted, the current buffer is used.

TYPE determines the type of sequence to use to represent the
keys, and should be one of 'string, 'vector or 'list. The default
is 'vector.

Note that if the data does not have a read syntax, the dumped
data can not be used to recreate the dictionary using
`dictree-populate-from-file'.

Interactively, DICT and BUFFER are read from the mini-buffer,
TYPE is always 'string."
  (interactive (list (read-dict "Dictionary: ")
                     (read-buffer
                      "Buffer to dump to (defaults to current): "
                      (buffer-name (current-buffer)))
                     'string))

  ;; select the buffer, creating it if necessary
  (if buffer
      (setq buffer (get-buffer-create buffer))
    (setq buffer (current-buffer)))
  (set-buffer buffer)

  ;; move point to end of buffer and make sure it's at start of new line
  (goto-char (point-max))
  (unless (= (point) (line-beginning-position))
    (insert "\n"))

  ;; dump keys
  (message "Dumping keys from %s to %s..."
           (dictree-name dict) (buffer-name buffer))
  (let ((count 0) (dictsize (dictree-size dict)))
    (message "Dumping keys from %s to %s...(key 1 of %d)"
             (dictree-name dict) (buffer-name buffer) dictsize)

    ;; map dump function over dictionary
    (dictree--mapc
     (lambda (key data plist)
       (when (= 99 (mod count 100))
         (message "Dumping keys from %s to %s...(key %d of %d)"
                  (dictree-name dict) (buffer-name buffer)
                  (1+ count) dictsize))
       (insert (prin1-to-string
                (funcall (or (dictree--key-savefun dict) 'identity)
                         key)))
       (when (setq data
                   (funcall (or (dictree--data-savefun dict) 'identity)
                            data))
         (insert " " (prin1-to-string data)))
       (when (setq plist
                   (funcall (or (dictree--plist-savefun dict) 'identity)
                            plist))
         (unless data (insert " nil"))
         (insert " " (prin1-to-string plist)))
       (insert "\n")
       (setq count (1+ count)))
     dict type)  ; dictree-mapc target

    (message "Dumping keys from %s to %s...done"
             (dictree-name dict) (buffer-name buffer)))
  (switch-to-buffer buffer))



(defun dictree-dump-to-file (dict filename &optional type overwrite)
  "Dump keys and their associated data
from dictionary DICT to a text file FILENAME, in the same format
as that used by `dictree-populate-from-file'. Prompts to overwrite
FILENAME if it already exists, unless OVERWRITE is non-nil.

TYPE determines the type of sequence to use to represent the
keys, and should be one of 'string, 'vector or 'list. The default
is 'vector.

Note that if the data does not have a read syntax and no , the dumped
data can not be used to recreate the dictionary using
`dictree-populate-from-file'.

Interactively, DICT and FILE are read from the mini-buffer,
OVERWRITE is the prefix argument, and TYPE is always 'string."
  (interactive (list (read-dict "Dictionary: ")
                     (read-file-name "File to dump to: " nil "")))

  (if (and (called-interactively-p 'any) (string= filename ""))
      (message "Dictionary %s NOT dumped" (dictree-name dict))

    ;; check if file exists, and prompt to overwrite it if necessary
    (if (and (file-exists-p filename)
             (not overwrite)
             (not (y-or-n-p
                   (format "File %s already exists. Overwrite? "
                           filename))))
        (message "Key dump cancelled")

      (let (buff)
        ;; create temporary buffer, dump keys to it, and save to
        ;; FILENAME
        (setq buff (generate-new-buffer filename))
        (save-window-excursion
          (dictree-dump-to-buffer dict buff type)
          (write-file filename))
        (kill-buffer buff)))))




;; ----------------------------------------------------------------
;;                     Minibuffer completion

(defvar dictree-history nil
  "History list for commands that read a dictionary name.")

(defvar dictree-loaded-history nil
  "History list for commands that read a loaded dictionary name.")


;;;###autoload
(defun read-dict
  (prompt &optional default dictlist allow-unloaded allow-unmatched)
  "Read the name of a dictionary with completion, and return it.

Prompt with PROMPT. By default, return DEFAULT. If DICTLIST is
supplied, only complete on dictionaries in that list.

If ALLOW-UNLOADED is non-nil, also complete on the names of
unloaded dictionaries (actually, on any Elisp file in the current
`load-path' restricted to subdirectories of your home directory
whose file name starts with \"dict-\"). If an unloaded dictionary
is read, the name of the Elisp file will be returned, without
extension, suitable for passing to `load-library'."

  (let (dictname paths)
    ;; when allowing unloaded dictionaries...
    (when allow-unloaded
      ;; get paths in load-path that are subdirectories of home
      ;; directory
      (dolist (d load-path)
        (when (eq (aref d 0) ?~) (push d paths)))
      ;; gather names of all Elisp libraries in this restricted
      ;; load-path
      (dolist (f (all-completions
                  "" (apply-partially 'locate-file-completion-table
                                      paths (get-load-suffixes))))
        (when (and (null (file-name-directory f))
                   (and (> (length f) 5)
                        (string= (substring f 0 5) "dict-"))
                   (null (file-name-extension f))
                   (not (member (file-name-sans-extension f) dictname)))
          (push (file-name-sans-extension f) dictname))))
    ;; gather names of loaded dictionaries
    (mapc (lambda (dict)
            (unless (or (null (dictree-name dict))
                        (member (dictree-name dict) dictname))
              (push (list (dictree-name dict)) dictname)))
          (or dictlist dictree-loaded-list))
    ;; do completing-read
    (setq dictname (completing-read
                    prompt
                    (if allow-unmatched
                        (completion-table-in-turn
                         dictname 'read-file-name-internal)
                      dictname)
                    nil (not allow-unmatched) nil
                    (if allow-unloaded
                        'dictree-history
                      'dictree-loaded-history)
                    (and (dictree-p default) (dictree-name default))))
    ;; return dictionary
    (cond
     ;; if user typed a file name, return that
     ((and allow-unmatched (file-regular-p dictname)) dictname)
     ;; if user selected a loaded dictionary, return dict itself
     ((condition-case nil
          (dictree-p (eval (intern-soft dictname)))
        (void-variable nil))
      (eval (intern-soft dictname)))
     ;; if user selected an unloaded dictionary, return dict name
     ((and allow-unloaded (stringp dictname)) dictname)
     ;; if DEFAULT was specified, return that
     (default default)
     ;; should never get here!
     (t (error "Unknown error reading dictionary")))
    ))



;; ----------------------------------------------------------------
;;            Pretty-print dictionaries during edebug

;; We advise the `edebug-prin1' and `edebug-prin1-to-string' functions
;; (actually, aliases) so that they print "#<dict-tree NAME>" instead of
;; the full print form for dictionaries.
;;
;; This is because, if left to its own devices, edebug hangs for ages
;; whilst printing large dictionaries, and you either have to wait for a
;; *very* long time for it to finish, or kill Emacs entirely. (Even C-g
;; C-g fails!)
;;
;; We do this also for lists of dictionaries, since those occur quite
;; often, but not for other sequence types or deeper nested structures,
;; to keep the implementation as simple as possible.
;;
;; Since the print form of a dictionary is practically incomprehensible
;; anyway, we don't lose much by doing this. If you *really* want to
;; print dictionaries in full whilst edebugging, despite this warning,
;; disable the advice.
;;
;; FIXME: Should use `cedet-edebug-prin1-extensions' instead of advice
;;        when `cedet-edebug' is loaded, though I believe this still
;;        works in that case.


(eval-when-compile
  (require 'edebug)
  (require 'advice))


(defun dictree--edebug-pretty-print (object)
  (cond
   ((dictree-p object)
    (concat "#<dict-tree \"" (dictree-name object) "\">"))
   ((null object) "nil")
   ((let ((dlist object) (test t))
      (while (or (dictree-p (car-safe dlist))
                 (and dlist (setq test nil)))
        (setq dlist (cdr dlist)))
      test)
    (concat "(" (mapconcat (lambda (d)
                             (concat "#<dict-tree \""
                                     (dictree-name d) "\">"))
                           object " ") ")"))
   ;; ((vectorp object)
   ;;  (let ((pretty "[") (len (length object)))
   ;;    (dotimes (i (1- len))
   ;;   (setq pretty
   ;;         (concat pretty
   ;;                 (if (trie-p (aref object i))
   ;;                     "#<trie>" (prin1-to-string (aref object i))) " ")))
   ;;    (concat pretty
   ;;         (if (trie-p (aref object (1- len)))
   ;;             "#<trie>" (prin1-to-string (aref object (1- len))))
   ;;         "]")))
   ))


(when (fboundp 'ad-define-subr-args)
  (ad-define-subr-args 'edebug-prin1 '(object &optional printcharfun)))

(defadvice edebug-prin1
  (around dictree activate compile preactivate)
  (let ((pretty (dictree--edebug-pretty-print object)))
    (if pretty
        (progn
          (prin1 pretty printcharfun)
          (setq ad-return-value pretty))
    ad-do-it)))


(when (fboundp 'ad-define-subr-args)
  (ad-define-subr-args 'edebug-prin1-to-string '(object &optional noescape)))

(defadvice edebug-prin1-to-string
  (around dictree activate compile preactivate)
  (let ((pretty (dictree--edebug-pretty-print object)))
    (if pretty
        (setq ad-return-value pretty)
      ad-do-it)))



(provide 'dict-tree)

;;; dict-tree.el ends here