From: Yuchen Pei <id@ypei.org>
To: Emacs Devel mailing list <emacs-devel@gnu.org>
Subject: Use radix-tree for string arrays
Date: Wed, 05 Jul 2023 23:01:45 +1000 [thread overview]
Message-ID: <871qhmh5qe.fsf@ypei.org> (raw)
[-- Attachment #1: Type: text/plain, Size: 338 bytes --]
Hello,
In implementing a command to convert a list of urls to a radix tree
based on path components, I made a slight generalization to
radix-tree.el to take a comparison function, see attached diff and
functions utilising the generalised radix tree.
I'll be happy to spend more time on a patch if there's interest in
incorporating it.
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: radix-tree.diff --]
[-- Type: text/x-patch, Size: 4162 bytes --]
@@ -1,6 +1,6 @@
;;; radix-tree.el --- A simple library of radix trees -*- lexical-binding: t; -*-
-;; Copyright (C) 2016-2023 Free Software Foundation, Inc.
+;; Copyright (C) 2016-2022 Free Software Foundation, Inc.
;; Author: Stefan Monnier <monnier@iro.umontreal.ca>
;; Keywords:
@@ -22,6 +22,11 @@
;;; Commentary:
+;; NOTE: This is a modified version of radix-tree that comes builtin
+;; with emacs. It allows different compare functions and type. One use
+;; is to build a radix tree of list of string, e.g. from a filesystem
+;; hierarchy.
+
;; There are many different options for how to represent radix trees
;; in Elisp. Here I chose a very simple one. A radix-tree can be either:
;; - a node, of the form ((PREFIX . PTREE) . RTREE) where PREFIX is a string
@@ -41,12 +46,14 @@
;; data structure harder to read (by a human) when printed out.
;;; Code:
+(defvar radix-tree-compare-function 'compare-strings)
+(defvar radix-tree-type 'string)
(defun radix-tree--insert (tree key val i)
(pcase tree
(`((,prefix . ,ptree) . ,rtree)
(let* ((ni (+ i (length prefix)))
- (cmp (compare-strings prefix nil nil key i ni)))
+ (cmp (funcall radix-tree-compare-function prefix nil nil key i ni)))
(if (eq t cmp)
(let ((nptree (radix-tree--insert ptree key val ni)))
`((,prefix . ,nptree) . ,rtree))
@@ -71,12 +78,13 @@
(pcase tree
(`((,prefix . ,ptree) . ,rtree)
(let* ((ni (+ i (length prefix)))
- (cmp (compare-strings prefix nil nil key i ni)))
+ (cmp (funcall radix-tree-compare-function prefix nil nil key i ni)))
(if (eq t cmp)
(pcase (radix-tree--remove ptree key ni)
('nil rtree)
(`((,pprefix . ,pptree))
- `((,(concat prefix pprefix) . ,pptree) . ,rtree))
+ `((,(seq-concatenate radix-tree-type prefix pprefix) . ,pptree) .
+ ,rtree))
(nptree `((,prefix . ,nptree) . ,rtree)))
(let ((n (if (< cmp 0) (- -1 cmp) (- cmp 1))))
(if (zerop n)
@@ -91,7 +99,7 @@
(pcase tree
(`((,prefix . ,ptree) . ,rtree)
(let* ((ni (+ i (length prefix)))
- (cmp (compare-strings prefix nil nil string i ni)))
+ (cmp (funcall radix-tree-compare-function prefix nil nil string i ni)))
(if (eq t cmp)
(radix-tree--lookup ptree string ni)
(let ((n (if (< cmp 0) (- -1 cmp) (- cmp 1))))
@@ -109,7 +117,7 @@
;; (pcase tree
;; (`((,prefix . ,ptree) . ,rtree)
;; (let* ((ni (+ i (length prefix)))
-;; (cmp (compare-strings prefix nil nil string i ni))
+;; (cmp (funcall radix-tree-compare-function prefix nil nil string i ni))
;; ;; FIXME: We could compute nrtree more efficiently
;; ;; whenever cmp is not -1 or 1.
;; (nrtree (radix-tree--trim rtree string i)))
@@ -130,7 +138,7 @@
(pcase tree
(`((,prefix . ,ptree) . ,rtree)
(let* ((ni (+ i (length prefix)))
- (cmp (compare-strings prefix nil nil string i ni))
+ (cmp (funcall radix-tree-compare-function prefix nil nil string i ni))
;; FIXME: We could compute prefixes more efficiently
;; whenever cmp is not -1 or 1.
(prefixes (radix-tree--prefixes rtree string i prefixes)))
@@ -149,7 +157,7 @@
(pcase tree
(`((,prefix . ,ptree) . ,rtree)
(let* ((ni (+ i (length prefix)))
- (cmp (compare-strings prefix nil nil string i ni)))
+ (cmp (funcall radix-tree-compare-function prefix nil nil string i ni)))
(if (eq t cmp)
(radix-tree--subtree ptree string ni)
(let ((n (if (< cmp 0) (- -1 cmp) (- cmp 1))))
@@ -222,7 +230,7 @@
(radix-tree-iter-subtrees
tree
(lambda (p s)
- (let ((nprefix (concat prefix p)))
+ (let ((nprefix (seq-concatenate radix-tree-type prefix p)))
(pcase s
((radix-tree-leaf v) (funcall fun nprefix v))
(_ (radix-tree-iter-mappings s fun nprefix)))))))
Diff finished. Wed Jul 5 22:52:53 2023
[-- Attachment #3: Type: text/plain, Size: 1459 bytes --]
#+begin_src elisp
(require 'radix-tree)
(defun my-compare-string-arrays (xs1 start1 end1 xs2 start2 end2)
(let* ((i 0)
(s1 (or start1 0))
(e1 (or end1 (length xs1)))
(s2 (or start2 0))
(e2 (or end2 (length xs2)))
(l1 (- e1 s1))
(l2 (- e2 s2))
(cmp t))
(while (and (< i l1) (< i l2) (eq t cmp))
(setq cmp (compare-strings (elt xs1 (+ s1 i)) nil nil
(elt xs2 (+ s2 i)) nil nil))
(setq i (1+ i)))
(cond ((and (numberp cmp) (< cmp 0)) (- i))
((and (numberp cmp) (> cmp 0)) i)
((= l1 l2) t)
((< l1 l2) (- i))
(t i))))
(defun my-radix-tree-from-list ()
(goto-char (point-min))
(let ((result radix-tree-empty)
(radix-tree-compare-function 'my-compare-string-arrays))
(while (not (eobp))
(let ((line (vconcat
(split-string
(buffer-substring-no-properties
(point)
(progn (forward-line 1) (1- (point))))
"/"))))
(setq result
(radix-tree-insert result line t))))
result))
(defun my-kill-radix-tree-from-list ()
(interactive)
(let ((max-lisp-eval-depth 8000))
(kill-new (pp (my-radix-tree-from-list)))))
#+end_src
Best,
Yuchen
--
PGP Key: 47F9 D050 1E11 8879 9040 4941 2126 7E93 EF86 DFD0
<https://ypei.org/assets/ypei-pubkey.txt>
next reply other threads:[~2023-07-05 13:01 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-07-05 13:01 Yuchen Pei [this message]
2023-07-05 16:47 ` Use radix-tree for string arrays Philip Kaludercic
2023-07-05 22:15 ` Yuchen Pei
2023-07-06 18:50 ` Philip Kaludercic
2023-07-07 10:35 ` Yuchen Pei
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=871qhmh5qe.fsf@ypei.org \
--to=id@ypei.org \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).