[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Emacs-diffs] map c3acb32: New library map.el similar to seq.el but for
|
From: |
Nicolas Petton |
|
Subject: |
[Emacs-diffs] map c3acb32: New library map.el similar to seq.el but for mapping data structures. |
|
Date: |
Sat, 18 Apr 2015 14:28:44 +0000 |
branch: map
commit c3acb3258df5fc0987fdd233062632ed030923d9
Author: Nicolas Petton <address@hidden>
Commit: Nicolas Petton <address@hidden>
New library map.el similar to seq.el but for mapping data structures.
* test/automated/map-test.el: New file.
* lisp/emacs-lisp/map.el: New file.
---
lisp/emacs-lisp/map.el | 270 ++++++++++++++++++++++++++++++++++++
test/automated/map-test.el | 324 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 594 insertions(+), 0 deletions(-)
diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el
new file mode 100644
index 0000000..fec0634
--- /dev/null
+++ b/lisp/emacs-lisp/map.el
@@ -0,0 +1,270 @@
+;;; map.el --- Map manipulation functions -*- lexical-binding: t; -*-
+
+;; Copyright (C) 2015 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <address@hidden>
+;; Keywords: convenience, map, hash-table, alist, array
+;; Version: 1.0
+;; Package: map
+
+;; Maintainer: address@hidden
+
+;; This file is part of GNU 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 this program. If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; map.el provides map-manipulation functions that work on alists,
+;; hash-table and arrays. All functions are prefixed with "map-".
+;;
+;; Functions taking a predicate or iterating over a map using a
+;; function take the function as their first argument. All other
+;; functions take the map as their first argument.
+
+;; TODO:
+;; - Add support for char-tables
+;; - Maybe add support for gv?
+;; - See if we can integrate text-properties
+;; - A macro similar to let-alist but working on any type of map could
+;; be really useful
+
+;;; Code:
+
+(require 'seq)
+
+(defun map-elt (map key &optional default)
+ "Perform a lookup in MAP of KEY and return its associated value.
+If KEY is not found, return DEFAULT which defaults to nil.
+
+If MAP is a list, `assoc' is used to lookup KEY."
+ (map--dispatch map
+ :list (or (cdr (assoc key map)) default)
+ :hash-table (gethash key map default)
+ :array (or (ignore-errors (elt map key)) default)))
+
+(defmacro map-put (map key value)
+ "In MAP, associate KEY with VALUE and return MAP.
+If KEY is already present in MAP, replace its value with VALUE."
+ (declare (debug t))
+ `(progn
+ (map--dispatch (m ,map m)
+ :list (setq ,map (cons (cons ,key ,value) m))
+ :hash-table (puthash ,key ,value m)
+ :array (aset m ,key ,value))))
+
+(defmacro map-delete (map key)
+ "In MAP, delete the key KEY if present and return MAP.
+If MAP is an array, store nil at the index KEY."
+ (declare (debug t))
+ `(progn
+ (map--dispatch (m ,map m)
+ :list (setq ,map (map--delete-alist m ,key))
+ :hash-table (remhash ,key m)
+ :array (aset m ,key nil))))
+
+(defun map-nested-elt (map keys &optional default)
+ "Travserse MAP using KEYS and return the looked up value or DEFAULT if nil.
+Map can be a nested map composed of alists, hash-tables and arrays."
+ (or (seq-reduce (lambda (acc key)
+ (when (map-p acc)
+ (map-elt acc key)))
+ keys
+ map)
+ default))
+
+(defun map-keys (map)
+ "Return the list of keys in MAP."
+ (map-apply (lambda (key value) key) map))
+
+(defun map-values (map)
+ "Return the list of values in MAP."
+ (map-apply (lambda (key value) value) map))
+
+(defun map-pairs (map)
+ "Return the elements of MAP as key/value association lists."
+ (map-apply (lambda (key value)
+ (cons key value))
+ map))
+
+(defun map-length (map)
+ "Return the length of MAP."
+ (length (map-keys map)))
+
+(defun map-copy (map)
+ "Return a copy of MAP."
+ (map--dispatch map
+ :list (seq-copy map)
+ :hash-table (copy-hash-table map)
+ :array (seq-copy map)))
+
+(defun map-apply (function map)
+ "Return the result of applying FUNCTION to each element of MAP.
+FUNCTION is called with two arguments, the key and the value."
+ (funcall (map--dispatch map
+ :list #'map--apply-alist
+ :hash-table #'map--apply-hash-table
+ :array #'map--apply-array)
+ function
+ map))
+
+(defun map-keys-apply (function map)
+ "Return the result of applying FUNCTION to each key of MAP."
+ (map-apply (lambda (key val)
+ (funcall function key))
+ map))
+
+(defun map-values-apply (function map)
+ "Return the result of applying FUNCTION to each value of MAP."
+ (map-apply (lambda (key val)
+ (funcall function val))
+ map))
+
+(defun map-filter (pred map)
+ "Return an alist of the key/val pairs of which (PRED key val) is non-nil in
MAP."
+ (delq nil (map-apply (lambda (key val)
+ (if (funcall pred key val)
+ (cons key val)
+ nil))
+ map)))
+
+(defun map-remove (pred map)
+ "Return an alist of the key/val pairs of which (PRED key val) is nil in MAP."
+ (map-filter (lambda (key val) (not (funcall pred key val)))
+ map))
+
+(defun map-p (map)
+ "Return non-nil if MAP is a map (list, hash-table or array)."
+ (or (listp map)
+ (hash-table-p map)
+ (arrayp map)))
+
+(defun map-empty-p (map)
+ "Return non-nil is MAP is empty.
+MAP can be a list, hash-table or array."
+ (null (map-keys map)))
+
+(defun map-contains-key-p (map key &optional testfn)
+ "Return non-nil if MAP contain the key KEY, nil otherwise.
+Equality is defined by TESTFN if non-nil or by `equal' if nil.
+MAP can be a list, hash-table or array."
+ (seq-contains-p (map-keys map) key testfn))
+
+(defun map-some-p (pred map)
+ "Return any key/value pair for which (PRED key val) is non-nil is MAP."
+ (catch 'map--break
+ (map-apply (lambda (key value)
+ (when (funcall pred key value)
+ (throw 'map--break (cons key value))))
+ map)
+ nil))
+
+(defun map-every-p (pred map)
+ "Return non-nil if (PRED key val) is non-nil for all elements of the map
MAP."
+ (catch 'map--break
+ (map-apply (lambda (key value)
+ (or (funcall pred key value)
+ (throw 'map--break nil)))
+ map)
+ t))
+
+(defun map-merge (type &rest maps)
+ "Merge into a map of type TYPE all the key/value pairs in the maps MAPS."
+ (let (result)
+ (while maps
+ (map-apply (lambda (key value)
+ (map-put result key value))
+ (pop maps)))
+ (map-into result type)))
+
+(defun map-into (map type)
+ "Convert the map MAP into a map of type TYPE.
+TYPE can be one of the following symbols: list or hash-table."
+ (pcase type
+ (`list (map-pairs map))
+ (`hash-table (map--into-hash-table map))))
+
+(defmacro map--dispatch (spec &rest args)
+ "Evaluate one of the provided forms depending on the type of MAP.
+
+SPEC can be a map or a list of the form (VAR MAP [RESULT]).
+ARGS should have the form [TYPE FORM]...
+
+The following keyword types are meaningful: `:list',
+`:hash-table' and `array'.
+
+An error is thrown if MAP is neither a list, hash-table or array.
+
+Return RESULT if non-nil or the result of evaluation of the
+form.
+
+\(fn (VAR MAP [RESULT]) &rest ARGS)"
+ (declare (debug t) (indent 1))
+ (unless (listp spec)
+ (setq spec `(,spec ,spec)))
+ (let ((map-var (car spec))
+ (result-var (make-symbol "result")))
+ `(let ((,map-var ,(cadr spec))
+ ,result-var)
+ (setq ,result-var
+ (cond ((listp ,map-var) ,(plist-get args :list))
+ ((hash-table-p ,map-var) ,(plist-get args :hash-table))
+ ((arrayp ,map-var) ,(plist-get args :array))
+ (t (error "Unsupported map: %s" ,map-var))))
+ ,@(when (cddr spec)
+ `((setq ,result-var ,@(cddr spec))))
+ ,result-var)))
+
+(defun map--apply-alist (function map)
+ "Private function used to apply FUNCTION over MAP, MAP being an alist."
+ (seq-map (lambda (pair)
+ (funcall function
+ (car pair)
+ (cdr pair)))
+ map))
+
+(defun map--apply-hash-table (function map)
+ "Private function used to apply FUNCTION over MAP, MAP being a hash-table."
+ (let (result)
+ (maphash (lambda (key value)
+ (push (funcall function key value) result))
+ map)
+ (nreverse result)))
+
+(defun map--apply-array (function map)
+ "Private function used to apply FUNCTION over MAP, MAP being an array."
+ (let ((index 0))
+ (seq-map (lambda (elt)
+ (prog1
+ (funcall function index elt)
+ (setq index (1+ index))))
+ map)))
+
+(defun map--delete-alist (map key)
+ "Return MAP with KEY removed."
+ (seq-remove (lambda (pair)
+ (equal key (car pair)))
+ map))
+
+(defun map--into-hash-table (map)
+ "Convert MAP into a hash-table."
+ (let ((ht (make-hash-table :size (map-length map)
+ :test 'equal)))
+ (map-apply (lambda (key value)
+ (map-put ht key value))
+ map)
+ ht))
+
+(provide 'map)
+;;; map.el ends here
diff --git a/test/automated/map-test.el b/test/automated/map-test.el
new file mode 100644
index 0000000..8a12be8
--- /dev/null
+++ b/test/automated/map-test.el
@@ -0,0 +1,324 @@
+;;; map-tests.el --- Tests for map.el
+
+;; Copyright (C) 2015 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <address@hidden>
+;; Maintainer: address@hidden
+
+;; This file is part of GNU 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:
+
+;; Tests for map.el
+
+;;; Code:
+
+(require 'ert)
+(require 'map)
+
+(defmacro with-maps-do (alist-name vec-name ht-name &rest body)
+ (declare (indent 3))
+ `(let ((,alist-name '((a . 2)
+ (b . 3)
+ (c . 4)))
+ (,vec-name (make-vector 3 nil))
+ (,ht-name (make-hash-table)))
+ (aset ,vec-name 0 'a)
+ (aset ,vec-name 1 'b)
+ (aset ,vec-name 2 'c)
+ (puthash 'a 2 ,ht-name)
+ (puthash 'b 3 ,ht-name)
+ (puthash 'c 4 ,ht-name)
+ (progn
+ ,@body)))
+
+(ert-deftest test-map-elt ()
+ (with-maps-do alist vec ht
+ (assert (= 2 (map-elt alist 'a)))
+ (assert (= 3 (map-elt alist 'b)))
+ (assert (= 4 (map-elt alist 'c)))
+ (assert (null (map-elt alist 'd)))
+ (assert (= 2 (map-elt ht 'a)))
+ (assert (= 3 (map-elt ht 'b)))
+ (assert (= 4 (map-elt ht 'c)))
+ (assert (null (map-elt ht 'd)))
+ (assert (eq 'a (map-elt vec 0)))
+ (assert (eq 'b (map-elt vec 1)))
+ (assert (eq 'c (map-elt vec 2)))
+ (assert (null (map-elt vec 3)))))
+
+(ert-deftest test-map-elt-default ()
+ (with-maps-do alist vec ht
+ (assert (= 5 (map-elt alist 'd 5)))
+ (assert (= 5 (map-elt vec 4 5)))
+ (assert (= 5 (map-elt ht 'd 5)))))
+
+(ert-deftest test-map-put ()
+ (with-maps-do alist vec ht
+ (map-put alist 'd 4)
+ (assert (= (map-elt alist 'd) 4))
+ (map-put alist 'd 5)
+ (assert (= (map-elt alist 'd) 5))
+ (map-put ht 'd 4)
+ (assert (= (map-elt ht 'd) 4))
+ (map-put ht 'd 5)
+ (assert (= (map-elt ht 'd) 5))
+ (map-put vec 0 'd)
+ (assert (eq (map-elt vec 0) 'd))
+ (should-error (map-put vec 4 'd))))
+
+(ert-deftest test-map-put-literal ()
+ (assert (= (map-elt (map-put [1 2 3] 1 4) 1)
+ 4))
+ (assert (= (map-elt (map-put (make-hash-table) 'a 2) 'a)
+ 2))
+ (should-error (map-put '((a . 1)) 'b 2))
+ (should-error (map-put '() 'a 1)))
+
+(ert-deftest test-map-put-return-value ()
+ (let ((ht (make-hash-table)))
+ (assert (eq (map-put ht 'a 'hello) ht))))
+
+(ert-deftest test-map-delete ()
+ (with-maps-do alist vec ht
+ (map-delete alist 'a)
+ (assert (null (map-elt alist 'a)))
+ (map-delete ht 'a)
+ (assert (null (map-elt ht 'a)))
+ (map-delete vec 2)
+ (assert (null (map-elt vec 2)))))
+
+(ert-deftest test-map-delete-return-value ()
+ (let ((ht (make-hash-table)))
+ (assert (eq (map-delete ht 'a) ht))))
+
+(ert-deftest test-map-nested-elt ()
+ (let ((vec [a b [c d [e f]]]))
+ (assert (eq (map-nested-elt vec '(2 2 0)) 'e)))
+ (let ((alist '((a . 1)
+ (b . ((c . 2)
+ (d . 3)
+ (e . ((f . 4)
+ (g . 5))))))))
+ (assert (eq (map-nested-elt alist '(b e f))
+ 4)))
+ (let ((ht (make-hash-table)))
+ (map-put ht 'a 1)
+ (map-put ht 'b (make-hash-table))
+ (map-put (map-elt ht 'b) 'c 2)
+ (assert (eq (map-nested-elt ht '(b c))
+ 2))))
+
+(ert-deftest test-map-nested-elt-default ()
+ (let ((vec [a b [c d]]))
+ (assert (null (map-nested-elt vec '(2 3))))
+ (assert (null (map-nested-elt vec '(2 1 1))))
+ (assert (= 4 (map-nested-elt vec '(2 1 1) 4)))))
+
+(ert-deftest test-map-p ()
+ (assert (map-p nil))
+ (assert (map-p '((a . b) (c . d))))
+ (assert (map-p '(a b c d)))
+ (assert (map-p []))
+ (assert (map-p [1 2 3]))
+ (assert (map-p (make-hash-table)))
+ (assert (map-p "hello"))
+ (with-maps-do alist vec ht
+ (assert (map-p alist))
+ (assert (map-p vec))
+ (assert (map-p ht))
+ (assert (not (map-p 1)))
+ (assert (not (map-p 'hello)))))
+
+(ert-deftest test-map-keys ()
+ (with-maps-do alist vec ht
+ (assert (equal (map-keys alist) '(a b c)))
+ (assert (equal (map-keys vec) '(0 1 2)))
+ (assert (equal (map-keys ht) '(a b c)))))
+
+(ert-deftest test-map-values ()
+ (with-maps-do alist vec ht
+ (assert (equal (map-values alist) '(2 3 4)))
+ (assert (equal (map-values vec) '(a b c)))
+ (assert (equal (map-values ht) '(2 3 4)))))
+
+(ert-deftest test-map-pairs ()
+ (with-maps-do alist vec ht
+ (assert (equal (map-pairs alist) alist))
+ (assert (equal (map-pairs vec) '((0 . a)
+ (1 . b)
+ (2 . c))))
+ (assert (equal (map-pairs ht) alist))))
+
+(ert-deftest test-map-length ()
+ (let ((ht (make-hash-table)))
+ (puthash 'a 1 ht)
+ (puthash 'b 2 ht)
+ (puthash 'c 3 ht)
+ (puthash 'd 4 ht)
+ (assert (= 0 (map-length nil)))
+ (assert (= 0 (map-length [])))
+ (assert (= 0 (map-length (make-hash-table))))
+ (assert (= 5 (map-length [0 1 2 3 4])))
+ (assert (= 2 (map-length '((a . 1) (b . 2)))))
+ (assert (= 4 (map-length ht)))))
+
+(ert-deftest test-map-copy ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist vec ht))
+ (let ((copy (map-copy map)))
+ (assert (equal (map-keys map) (map-keys copy)))
+ (assert (equal (map-values map) (map-values copy)))
+ (assert (not (eq map copy)))))))
+
+(ert-deftest test-map-apply ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist ht))
+ (assert (equal (map-apply (lambda (k v) (cons (symbol-name k) v))
+ map)
+ '(("a" . 2) ("b" . 3) ("c" . 4)))))
+ (assert (equal (map-apply (lambda (k v) (cons (1+ k) v))
+ vec)
+ '((1 . a)
+ (2 . b)
+ (3 . c))))))
+
+(ert-deftest test-map-keys-apply ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist ht))
+ (assert (equal (map-keys-apply (lambda (k) (symbol-name k))
+ map)
+ '("a" "b" "c"))))
+ (assert (equal (map-keys-apply (lambda (k) (1+ k))
+ vec)
+ '(1 2 3)))))
+
+(ert-deftest test-map-values-apply ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist ht))
+ (assert (equal (map-values-apply (lambda (v) (1+ v))
+ map)
+ '(3 4 5))))
+ (assert (equal (map-values-apply (lambda (v) (symbol-name v))
+ vec)
+ '("a" "b" "c")))))
+
+(ert-deftest test-map-filter ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist ht))
+ (assert (equal (map-keys (map-filter (lambda (k v)
+ (<= 3 v))
+ map))
+ '(b c)))
+ (assert (null (map-filter (lambda (k v)
+ (eq 'd k))
+ map))))
+ (assert (null (map-filter (lambda (k v)
+ (eq 3 v))
+ [1 2 4 5])))
+ (assert (equal (map-filter (lambda (k v)
+ (eq 3 k))
+ [1 2 4 5])
+ '((3 . 5))))))
+
+(ert-deftest test-map-remove ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist ht))
+ (assert (equal (map-keys (map-remove (lambda (k v)
+ (<= 3 v))
+ map))
+ '(a)))
+ (assert (equal (map-keys (map-remove (lambda (k v)
+ (eq 'd k))
+ map))
+ (map-keys map))))
+ (assert (equal (map-remove (lambda (k v)
+ (eq 3 v))
+ [1 2 4 5])
+ '((0 . 1)
+ (1 . 2)
+ (2 . 4)
+ (3 . 5))))
+ (assert (null (map-remove (lambda (k v)
+ (>= k 0))
+ [1 2 4 5])))))
+
+(ert-deftest test-map-empty-p ()
+ (assert (map-empty-p nil))
+ (assert (not (map-empty-p '((a . b) (c . d)))))
+ (assert (map-empty-p []))
+ (assert (not (map-empty-p [1 2 3])))
+ (assert (map-empty-p (make-hash-table)))
+ (assert (not (map-empty-p "hello")))
+ (assert (map-empty-p "")))
+
+(ert-deftest test-map-contains-key-p ()
+ (assert (map-contains-key-p '((a . 1) (b . 2)) 'a))
+ (assert (not (map-contains-key-p '((a . 1) (b . 2)) 'c)))
+ (assert (map-contains-key-p '(("a" . 1)) "a"))
+ (assert (not (map-contains-key-p '(("a" . 1)) "a" #'eq)))
+ (assert (map-contains-key-p [a b c] 2))
+ (assert (not (map-contains-key-p [a b c] 3))))
+
+(ert-deftest test-map-some-p ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist ht))
+ (assert (equal (map-some-p (lambda (k v)
+ (eq 'a k))
+ map)
+ (cons 'a 2)))
+ (assert (not (map-some-p (lambda (k v)
+ (eq 'd k))
+ map))))
+ (assert (equal (map-some-p (lambda (k v)
+ (> k 1))
+ vec)
+ (cons 2 'c)))
+ (assert (not (map-some-p (lambda (k v)
+ (> k 3))
+ vec)))))
+
+(ert-deftest test-map-every-p ()
+ (with-maps-do alist vec ht
+ (dolist (map (list alist ht vec))
+ (assert (map-every-p (lambda (k v)
+ k)
+ map))
+ (assert (not (map-every-p (lambda (k v)
+ nil)
+ map))))
+ (assert (map-every-p (lambda (k v)
+ (>= k 0))
+ vec))
+ (assert (not (map-every-p (lambda (k v)
+ (> k 3))
+ vec)))))
+
+(ert-deftest test-map-into ()
+ (with-maps-do alist vec ht
+ (assert (hash-table-p (map-into alist 'hash-table)))
+ (assert (equal (map-into (map-into alist 'hash-table) 'list)
+ alist))
+ (assert (listp (map-into ht 'list)))
+ (assert (equal (map-keys (map-into (map-into ht 'list) 'hash-table))
+ (map-keys ht)))
+ (assert (equal (map-values (map-into (map-into ht 'list) 'hash-table))
+ (map-values ht)))
+ (assert (null (map-into nil 'list)))
+ (assert (map-empty-p (map-into nil 'hash-table)))))
+
+(provide 'map-tests)
+;;; map-tests.el ends here