documentation for trie

;;unoptimized trie
(defstruct (tr-node (:conc-name nil))
;; conc-name nil means that tr-node is not the leader of this struct
;; we will not use tr-node-val but rather val directly
  val
  (children (list)))
(defun tr-lookup (key root)
 "go through vector, at the end extract value of root
  but before that save the cdr of the current
  element of the key vector mapped to the
  car of the root's children, as in the child itself,
  the cdr in this case being the link to the next node
  that the child has, then save that link to the
  next recursive section of the tree into the root, in
  root trie-lookup search-within from-root
  the root's children become the current root"
;; dovector dotimes+aref
  (rtl:dovec (ch key
              ;; when iteration terminates normally
              ;; we have found the node we were looking for
              (val root) ;; run the val command which calls the defstruct
			  ;;apply that to the root of the tree
			  ;;this one function is called when the dovec is done
              )
			  #|
(if-it (foo)
	(bar it))
(let ((it (foo)))
  (if it
    (bar it)))
	btw this it is saved in a variable called i
	(rtl:assoc1 'a '((a . 1)))
	1 (1 bit, #x1, #o1, #b1)
	T
    |#
    (rtl:if-it (rtl:assoc1 ch (children root)) ;;assoc1=(o cdr assoc)
	;; save the cdr of the ch in it
	;; this yeilds nextnode
	;; yeah chilren has a next node
	;; children root is a list of cons cells
	;;((childrenlist. nextnode) (children . nextnode))
	;; moves root to the child node
               (setf root rtl:it)
               (return))))

(defun tr-add (key val root)
  (let ((i 0))
  (rtl:dovec (ch key)
      ;; dont do anything at the end
      (rtl:if-it (rtl:assoc1 ch (children root))
	  ;; save the root children's next link towards the next tr-node
                 (progn(setf root rtl:it)
				 ;; increment i if we keep finding a child with next node
				 ;; or we have have the child in the children's root
				 ;; i.e. the current child is not of root
				 (incf i))
                 (return)))
				 ;; if we have all children already parented
    (if (= i (length key))
        ;; something has already being stored at key -
        ;; so we signal a continuable error that
        ;; gives the user two options: overwrite or abort
        (cerror "Assign a new value"
                "There was already a value at key: ~A" (val root))
				;; our root already has keys
				;; if it doesn't have keys
				;; iterate with the keys that are not
				;; found in
				;; ((child1 . next)(child2. next))
        (rtl:dovec (ch (rtl:slice key i))
		;; iterate over the children that are not of root
		;; make a new child which is a struct with val and children
		;; this brcomes a new root
          (let ((child (make-tr-node)))
            ;; push the current childless element onto the children of root
            (push (cons ch child) (children root))
            (setf root child))))
			;; root becomes the strucure with val and children
    (setf (val root) val)))
CL-USER> (defparameter *trie* (make-tr-node))
*TRIE*
CL-USER> *trie*
#S(TR-NODE :VAL NIL :CHILDREN NIL)
For the sake of brevity, we won’t define a special print-function for our trie and will
use a default one. In a real setting, though, it is highly advisable:
CL-USER> (tr-lookup "word" *trie*)
NIL
CL-USER> (tr-add "word" 42 *trie*)
42
CL-USER> *trie*
#S(TR-NODE
   :VAL NIL
   :CHILDREN
   ((#\w
     . #S(TR-NODE
          :VAL NIL
          :CHILDREN
		            ((#\o
            . #S(TR-NODE
                 :VAL NIL
                 :CHILDREN
                 ((#\r
                   . #S(TR-NODE
                        :VAL NIL
                        :CHILDREN
                        ((#\d
                          . #S(TR-NODE
                               :VAL 42
                               :CHILDREN NIL)))))))))))))
CL-USER> (tr-lookup "word" *trie*)
42
CL-USER> (tr-add "word" :foo *trie*)
There was already a value at key: 42
   [Condition of type SIMPLE-ERROR]
Restarts:
 0: [CONTINUE] Assign a new value
 1: [RETRY] Retry SLIME REPL evaluation request.
 2: [*ABORT] Return to SLIME's top level.
 3: [ABORT] abort thread (#<THREAD "repl-thread" RUNNING>)
Backtrace:
  0: (TR-ADD "word" :FOO #S(TR-NODE :VAL 42 :CHILDREN NIL))
  1: (SB-INT:SIMPLE-EVAL-IN-LEXENV (TR-ADD "word" :FOO *TRIE*) #<NULL-
LEXENV>)
  2: (EVAL (TR-ADD "word" :FOO *TRIE*))
 --more--
;;; Take the restart 0
:FOO
CL-USER> (tr-add "we" :baz *trie*)
:BAZ
CL-USER> *trie*

#S(TR-NODE
   :VAL NIL
   :CHILDREN
   ((#\w
     . #S(TR-NODE
          :VAL NIL
          :CHILDREN
          ((#\e . #S(TR-NODE
                     :VAL :BAZ
                     :CHILDREN NIL))
           (#\o . #S(TR-NODE
                     :VAL NIL
                     :CHILDREN
                     ((#\r
                       . #S(TR-NODE
                            :VAL NIL
                            :CHILDREN
                            ((#\k
                              . #S(TR-NODE
                                   :VAL :BAR
                                   :CHILDREN NIL))
                             (#\d
                              . #S(TR-NODE
                                   :VAL :FOO
                                   :CHILDREN NIL)))))))))))))