1 ;;; map.el --- Map manipulation functions -*- lexical-binding: t; -*-
3 ;; Copyright (C) 2015 Free Software Foundation, Inc.
5 ;; Author: Nicolas Petton <nicolas@petton.fr>
6 ;; Keywords: convenience, map, hash-table, alist, array
10 ;; Maintainer: emacs-devel@gnu.org
12 ;; This file is part of GNU Emacs.
14 ;; GNU Emacs is free software: you can redistribute it and/or modify
15 ;; it under the terms of the GNU General Public License as published by
16 ;; the Free Software Foundation, either version 3 of the License, or
17 ;; (at your option) any later version.
19 ;; GNU Emacs is distributed in the hope that it will be useful,
20 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
21 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 ;; GNU General Public License for more details.
24 ;; You should have received a copy of the GNU General Public License
25 ;; along with this program. If not, see <http://www.gnu.org/licenses/>.
29 ;; map.el provides map-manipulation functions that work on alists,
30 ;; hash-table and arrays. All functions are prefixed with "map-".
32 ;; Functions taking a predicate or iterating over a map using a
33 ;; function take the function as their first argument. All other
34 ;; functions take the map as their first argument.
37 ;; - Add support for char-tables
38 ;; - Maybe add support for gv?
39 ;; - See if we can integrate text-properties
40 ;; - A macro similar to let-alist but working on any type of map could
47 (defun map-elt (map key &optional default)
48 "Perform a lookup in MAP of KEY and return its associated value.
49 If KEY is not found, return DEFAULT which defaults to nil.
51 If MAP is a list, `equal' is used to lookup KEY."
53 :list (or (cdr (assoc key map)) default)
54 :hash-table (gethash key map default)
55 :array (map--elt-array map key default)))
57 (defmacro map-put (map key value)
58 "In MAP, associate KEY with VALUE and return MAP.
59 If KEY is already present in MAP, replace the associated value
63 (map--dispatch (m ,map m)
64 :list (setq ,map (cons (cons ,key ,value) m))
65 :hash-table (puthash ,key ,value m)
66 :array (aset m ,key ,value))))
68 (defmacro map-delete (map key)
69 "In MAP, delete the key KEY if present and return MAP.
70 If MAP is an array, store nil at the index KEY."
73 (map--dispatch (m ,map m)
74 :list (setq ,map (map--delete-alist m ,key))
75 :hash-table (remhash ,key m)
76 :array (map--delete-array m ,key))))
78 (defun map-nested-elt (map keys &optional default)
79 "Travserse MAP using KEYS and return the looked up value or DEFAULT if nil.
80 Map can be a nested map composed of alists, hash-tables and arrays."
81 (or (seq-reduce (lambda (acc key)
89 "Return the list of keys in MAP."
90 (map-apply (lambda (key _) key) map))
92 (defun map-values (map)
93 "Return the list of values in MAP."
94 (map-apply (lambda (_ value) value) map))
96 (defun map-pairs (map)
97 "Return the elements of MAP as key/value association lists."
98 (map-apply (lambda (key value)
102 (defun map-length (map)
103 "Return the length of MAP."
104 (length (map-keys map)))
106 (defun map-copy (map)
107 "Return a copy of MAP."
110 :hash-table (copy-hash-table map)
111 :array (seq-copy map)))
113 (defun map-apply (function map)
114 "Return the result of applying FUNCTION to each element of MAP.
115 FUNCTION is called with two arguments, the key and the value."
116 (funcall (map--dispatch map
117 :list #'map--apply-alist
118 :hash-table #'map--apply-hash-table
119 :array #'map--apply-array)
123 (defun map-keys-apply (function map)
124 "Return the result of applying FUNCTION to each key of MAP."
125 (map-apply (lambda (key _)
126 (funcall function key))
129 (defun map-values-apply (function map)
130 "Return the result of applying FUNCTION to each value of MAP."
131 (map-apply (lambda (_ val)
132 (funcall function val))
135 (defun map-filter (pred map)
136 "Return an alist of the key/val pairs of which (PRED key val) is non-nil in MAP."
137 (delq nil (map-apply (lambda (key val)
138 (if (funcall pred key val)
143 (defun map-remove (pred map)
144 "Return an alist of the key/val pairs of which (PRED key val) is nil in MAP."
145 (map-filter (lambda (key val) (not (funcall pred key val)))
149 "Return non-nil if MAP is a map (list, hash-table or array)."
154 (defun map-empty-p (map)
155 "Return non-nil is MAP is empty.
156 MAP can be a list, hash-table or array."
157 (null (map-keys map)))
159 (defun map-contains-key-p (map key &optional testfn)
160 "Return non-nil if MAP contain the key KEY, nil otherwise.
161 Equality is defined by TESTFN if non-nil or by `equal' if nil.
162 MAP can be a list, hash-table or array."
163 (seq-contains-p (map-keys map) key testfn))
165 (defun map-some-p (pred map)
166 "Return any key/value pair for which (PRED key val) is non-nil is MAP."
168 (map-apply (lambda (key value)
169 (when (funcall pred key value)
170 (throw 'map--break (cons key value))))
174 (defun map-every-p (pred map)
175 "Return non-nil if (PRED key val) is non-nil for all elements of the map MAP."
177 (map-apply (lambda (key value)
178 (or (funcall pred key value)
179 (throw 'map--break nil)))
183 (defun map-merge (type &rest maps)
184 "Merge into a map of type TYPE all the key/value pairs in the maps MAPS."
187 (map-apply (lambda (key value)
188 (map-put result key value))
190 (map-into result type)))
192 (defun map-into (map type)
193 "Convert the map MAP into a map of type TYPE.
194 TYPE can be one of the following symbols: list or hash-table."
196 (`list (map-pairs map))
197 (`hash-table (map--into-hash-table map))
198 (t (error "Not a map type name: %S" type))))
200 (defmacro map--dispatch (spec &rest args)
201 "Evaluate one of the provided forms depending on the type of MAP.
203 SPEC can be a map or a list of the form (VAR MAP [RESULT]).
204 ARGS should have the form [TYPE FORM]...
206 The following keyword types are meaningful: `:list',
207 `:hash-table' and `array'.
209 An error is thrown if MAP is neither a list, hash-table nor array.
211 Return RESULT if non-nil or the result of evaluation of the
214 \(fn (VAR MAP [RESULT]) &rest ARGS)"
215 (declare (debug t) (indent 1))
217 (setq spec `(,spec ,spec)))
218 (let ((map-var (car spec))
219 (result-var (make-symbol "result")))
220 `(let ((,map-var ,(cadr spec))
223 (cond ((listp ,map-var) ,(plist-get args :list))
224 ((hash-table-p ,map-var) ,(plist-get args :hash-table))
225 ((arrayp ,map-var) ,(plist-get args :array))
226 (t (error "Unsupported map: %s" ,map-var))))
228 `((setq ,result-var ,@(cddr spec))))
231 (defun map--apply-alist (function map)
232 "Private function used to apply FUNCTION over MAP, MAP being an alist."
233 (seq-map (lambda (pair)
239 (defun map--apply-hash-table (function map)
240 "Private function used to apply FUNCTION over MAP, MAP being a hash-table."
242 (maphash (lambda (key value)
243 (push (funcall function key value) result))
247 (defun map--apply-array (function map)
248 "Private function used to apply FUNCTION over MAP, MAP being an array."
250 (seq-map (lambda (elt)
252 (funcall function index elt)
253 (setq index (1+ index))))
256 (defun map--elt-array (map key &optional default)
257 "Return the element of the arary MAP at the index KEY, or DEFAULT if nil."
258 (let ((len (seq-length map)))
264 (defun map--delete-alist (map key)
265 "Return MAP with KEY removed."
266 (seq-remove (lambda (pair)
267 (equal key (car pair)))
270 (defun map--delete-array (map key)
271 "Set nil in the array MAP at the index KEY if present and return MAP."
272 (let ((len (seq-length map)))
278 (defun map--into-hash-table (map)
279 "Convert MAP into a hash-table."
280 (let ((ht (make-hash-table :size (map-length map)
282 (map-apply (lambda (key value)
283 (map-put ht key value))