;;; 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