;;; map.el --- Map manipulation functions -*- lexical-binding: t; -*-
-;; Copyright (C) 2015 Free Software Foundation, Inc.
+;; Copyright (C) 2015-2016 Free Software Foundation, Inc.
;; Author: Nicolas Petton <nicolas@petton.fr>
;; Keywords: convenience, map, hash-table, alist, array
-;; Version: 1.0
+;; Version: 1.1
;; Package: map
;; Maintainer: emacs-devel@gnu.org
;;; Code:
(require 'seq)
+(eval-when-compile (require 'cl-lib))
(pcase-defmacro map (&rest args)
"Build a `pcase' pattern matching map elements.
-The `pcase' pattern will match each element of PATTERN against
-the corresponding elements of the map.
+ARGS is a list of elements to be matched in the map.
-Extra elements of the map are ignored if fewer ARGS are
-given, and the match does not fail.
+Each element of ARGS can be of the form (KEY PAT), in which case KEY is
+evaluated and searched for in the map. The match fails if for any KEY
+found in the map, the corresponding PAT doesn't match the value
+associated to the KEY.
-ARGS can be a list of the form (KEY PAT), in which case KEY in an
-unquoted form.
+Each element can also be a SYMBOL, which is an abbreviation of a (KEY
+PAT) tuple of the form (\\='SYMBOL SYMBOL).
-ARGS can also be a list of symbols, which stands for ('SYMBOL
-SYMBOL)."
+Keys in ARGS not found in the map are ignored, and the match doesn't
+fail."
`(and (pred mapp)
,@(map--make-pcase-bindings args)))
default)))
(defmacro map-put (map key value)
- "Associate KEY with VALUE in MAP and return MAP.
+ "Associate KEY with VALUE in MAP and return VALUE.
If KEY is already present in MAP, replace the associated value
with VALUE.
MAP can be a list, hash-table or array."
- (macroexp-let2 nil map map
- `(progn
- (setf (map-elt ,map ,key) ,value)
- ,map)))
+ `(setf (map-elt ,map ,key) ,value))
-(defmacro map-delete (map key)
+(defun map-delete (map key)
"Delete KEY from MAP and return MAP.
No error is signaled if KEY is not a key of MAP. If MAP is an
array, store nil at the index KEY.
MAP can be a list, hash-table or array."
- (declare (debug t))
- (gv-letplace (mgetter msetter) `(gv-delay-error ,map)
- (macroexp-let2 nil key key
- `(if (not (listp ,mgetter))
- (map--delete ,mgetter ,key)
- ;; The alist case is special, since it can't be handled by the
- ;; map--delete function.
- (setf (alist-get ,key (gv-synthetic-place ,mgetter ,msetter)
- nil t)
- nil)
- ,mgetter))))
+ (map--dispatch map
+ :list (setf (alist-get key map nil t) nil)
+ :hash-table (remhash key map)
+ :array (and (>= key 0)
+ (<= key (seq-length map))
+ (aset map key nil)))
+ map)
(defun map-nested-elt (map keys &optional default)
"Traverse MAP using KEYS and return the looked up value or DEFAULT if nil.
function
map))
+(defun map-do (function map)
+ "Apply FUNCTION to each element of MAP and return nil.
+FUNCTION.is called with two arguments, the key and the value."
+ (funcall (map--dispatch map
+ :list #'map--do-alist
+ :hash-table #'maphash
+ :array #'map--do-array)
+ function
+ map))
+
(defun map-keys-apply (function map)
"Return the result of applying FUNCTION to each key of MAP.
"Merge into a map of type TYPE all the key/value pairs in MAPS.
MAP can be a list, hash-table or array."
- (let (result)
+ (let ((result (map-into (pop maps) type)))
(while maps
+ ;; FIXME: When `type' is `list', we get an O(N^2) behavior.
+ ;; For small tables, this is fine, but for large tables, we
+ ;; should probably use a hash-table internally which we convert
+ ;; to an alist in the end.
(map-apply (lambda (key value)
- (setf (map-elt result key) value))
- (pop maps)))
- (map-into result type)))
+ (setf (map-elt result key) value))
+ (pop maps)))
+ result))
(defun map-merge-with (type function &rest maps)
"Merge into a map of type TYPE all the key/value pairs in MAPS.
When two maps contain the same key, call FUNCTION on the two
values and use the value returned by it.
MAP can be a list, hash-table or array."
- (let (result)
+ (let ((result (map-into (pop maps) type))
+ (not-found (cons nil nil)))
(while maps
(map-apply (lambda (key value)
- (setf (map-elt result key)
- (if (map-contains-key result key)
- (funcall function (map-elt result key) value)
- value)))
- (pop maps)))
- (map-into result type)))
+ (cl-callf (lambda (old)
+ (if (eq old not-found)
+ value
+ (funcall function old value)))
+ (map-elt result key not-found)))
+ (pop maps)))
+ result))
(defun map-into (map type)
"Convert the map MAP into a map of type TYPE.
(cdr pair)))
map))
-(defun map--delete (map key)
- (map--dispatch map
- :list (error "No place to remove the mapping for %S" key)
- :hash-table (remhash key map)
- :array (and (>= key 0)
- (<= key (seq-length map))
- (aset map key nil)))
- map)
-
(defun map--apply-hash-table (function map)
"Private function used to apply FUNCTION over MAP, MAP being a hash-table."
(let (result)
(setq index (1+ index))))
map)))
+(defun map--do-alist (function alist)
+ "Private function used to iterate over ALIST using FUNCTION."
+ (seq-do (lambda (pair)
+ (funcall function
+ (car pair)
+ (cdr pair)))
+ alist))
+
+(defun map--do-array (function array)
+ "Private function usde to iterate over ARRAY using FUNCTION."
+ (seq-do-indexed (lambda (elt index)
+ (funcall function index elt))
+ array))
+
(defun map--into-hash-table (map)
"Convert MAP into a hash-table."
(let ((ht (make-hash-table :size (map-length map)