blob: f3e8bc85d67b277b7ffbc40f657c8da18fdb1bb5 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
;;; my-algo.el -- Algorithms related exentions for emacs core -*- lexical-binding: t -*-
;; Copyright (C) 2023 Free Software Foundation.
;; Author: Yuchen Pei <id@ypei.org>
;; Package-Requires: ((emacs "28.2"))
;; This file is part of dotfiles.
;; dotfiles is free software: you can redistribute it and/or modify it under
;; the terms of the GNU Affero General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;; dotfiles 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 Affero General
;; Public License for more details.
;; You should have received a copy of the GNU Affero General Public
;; License along with dotfiles. If not, see <https://www.gnu.org/licenses/>.
;;; Commentary:
;; Algorithms and data structure.
;;; Code:
;;; radix tree with string array
(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)))))
(provide 'my-algo)
;;; my-algo.el ends here
|
