changelog shortlog graph tags branches changeset files revisions annotate raw help

Mercurial > core / lisp/lib/obj/tree/node.lisp

changeset 698: 96958d3eb5b0
parent: d7aa08025537
author: Richard Westhaver <ellis@rwest.io>
date: Fri, 04 Oct 2024 22:04:59 -0400
permissions: -rw-r--r--
description: fixes 
     1 ;;; lib/obj/tree/node.lisp --- Tree Nodes
     2 
     3 ;; SBCL provides excellent support for the ANSI CL built-in types such
     4 ;; as vector/array, list, hash-table. We don't need to provide much in
     5 ;; terms of additional support for these. There are some internal SBCL
     6 ;; collections such as RBTREE, AVLTREE and BROTHERTREE which we expose here
     7 ;; and provide additional support for.
     8 
     9 ;;; Code:
    10 (in-package :obj/tree)
    11 
    12 (deftype keytype () 'sb-vm:word)
    13 
    14 (defstruct (tree-node (:copier nil)
    15                  (:constructor make-node (key)))
    16   (key 0 :type keytype))
    17 
    18 (defstruct (unary-node (:include tree-node))
    19   (child nil :type t))
    20 
    21 (defstruct (binary-node (:include tree-node)
    22                        (:copier nil)
    23                        (:constructor make-binary-node (key left right)))
    24   left right)
    25 
    26 ;; temporary nodes eliminated when a tree is compiled
    27 (defstruct (ternary-node (:include binary-node)
    28                          (:copier nil)
    29                          (:constructor make-ternary-node (left key1 middle key2 right)))
    30   key1 middle key2)
    31 
    32 (defstruct (avl-node (:include tree-node)
    33                      (:copier nil)
    34                      (:constructor make-avl-node (key data left right)))
    35   data left right)
    36