Function: radix-tree--insert

radix-tree--insert is a byte-compiled function defined in radix-tree.el.gz.

Signature

(radix-tree--insert TREE KEY VAL I)

Source Code

;; Defined in /usr/src/emacs/lisp/emacs-lisp/radix-tree.el.gz
;;; radix-tree.el --- A simple library of radix trees  -*- lexical-binding: t; -*-

;; Copyright (C) 2016-2022 Free Software Foundation, Inc.

;; Author: Stefan Monnier <monnier@iro.umontreal.ca>
;; Keywords:

;; 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 <https://www.gnu.org/licenses/>.

;;; Commentary:

;; 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
;;   meaning that everything that starts with PREFIX is in PTREE,
;;   and everything else in RTREE.  It also has the property that
;;   everything that starts with the first letter of PREFIX but not with
;;   that whole PREFIX is not in RTREE (i.e. is not in the tree at all).
;; - anything else is taken as the value to associate with the empty string.
;; So every node is basically an (improper) alist where each mapping applies
;; to a different leading letter.
;;
;; The main downside of this representation is that the lookup operation
;; is slower because each level of the tree is an alist rather than some kind
;; of array, so every level's lookup is O(N) rather than O(1).  We could easily
;; solve this by using char-tables instead of alists, but that would make every
;; level take up a lot more memory, and it would make the resulting
;; data structure harder to read (by a human) when printed out.

;;; Code:

(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)))
       (if (eq t cmp)
           (let ((nptree (radix-tree--insert ptree key val ni)))
             `((,prefix . ,nptree) . ,rtree))
         (let ((n (if (< cmp 0) (- -1 cmp) (- cmp 1))))
           (if (zerop n)
               (let ((nrtree (radix-tree--insert rtree key val i)))
                 `((,prefix . ,ptree) . ,nrtree))
             (let* ((nprefix (substring prefix 0 n))
                    (kprefix (substring key (+ i n)))
                    (pprefix (substring prefix n))
                    (ktree (if (equal kprefix "") val
                             `((,kprefix . ,val)))))
               `((,nprefix
                  . ((,pprefix . ,ptree) . ,ktree))
                 . ,rtree)))))))
    (_
     (if (= (length key) i) val
       (let ((prefix (substring key i)))
         `((,prefix . ,val) . ,tree))))))