aboutsummaryrefslogtreecommitdiff
path: root/emacs/.emacs.d/lisp/my/my-algo.el
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