cl-treemaps
cl-treemaps is a lightweight and fast implementation of binary trees. The current version only features red black trees. The interface is similar to the one of Common Lisp Hash Maps and is therefore very easy to understand and use. See the README for further details. The package is only tested with SBCL.

The sourcecode is hosted on github (github.com/sake/cl-treemaps). Tarballs can also be found there.

This package does not implement the Treemapping method for displaying tree-structured data by using nested rectangles.

Quick assessment (2023-03-19)

  • Compiles without warnings in CCL.
  • Fails the test due to type declaration.

? (require :cl-treemaps)
:CL-TREEMAPS
NIL
? (require :cl-treemaps-test)
:CL-TREEMAPS-TEST
NIL
? (asdf:test-system :cl-treemaps-test)
; Warning: Deprecated recursive use of (ASDF/OPERATE:OPERATE 'ASDF/LISP-ACTION:LOAD-OP '(#1="cl-treemaps-test"))
; While executing: #<STANDARD-METHOD ASDF/PLAN:RECORD-DEPENDENCY (NULL T T)>, in process listener(1).
XXXX
 Did 4 checks.
    Pass: 0 ( 0%)
    Skip: 0 ( 0%)
    Fail: 4 (100%)

 Failure Details:
 --------------------------------
 COUNT-TREE []:
      Unexpected Error: #<CCL::BAD-SLOT-TYPE-FROM-INITFORM #x210133025D>
The value NIL, derived from the initform NIL, can not be used to set the value of the slot CL-TREEMAPS::DATA
in #<REDBLACK-TREE-MAP #x210133033D>, because it is not of type CL-TREEMAPS::REDBLACK-NODE. ..
 --------------------------------
 --------------------------------
 FILL-TREE []:
      Unexpected Error: #<CCL::BAD-SLOT-TYPE-FROM-INITFORM #x21012D19CD>
The value NIL, derived from the initform NIL, can not be used to set the value of the slot CL-TREEMAPS::DATA
in #<REDBLACK-TREE-MAP #x21012D1AAD>, because it is not of type CL-TREEMAPS::REDBLACK-NODE. ..
 --------------------------------
 --------------------------------
 SPLIT-MERGE-TREE []:
      Unexpected Error: #<CCL::BAD-SLOT-TYPE-FROM-INITFORM #x2101239E9D>
The value NIL, derived from the initform NIL, can not be used to set the value of the slot CL-TREEMAPS::DATA
in #<REDBLACK-TREE-MAP #x2101239F7D>, because it is not of type CL-TREEMAPS::REDBLACK-NODE. ..
 --------------------------------
 --------------------------------
 TREE-ITERATOR []:
      Unexpected Error: #<CCL::BAD-SLOT-TYPE-FROM-INITFORM #x2101367C0D>
The value NIL, derived from the initform NIL, can not be used to set the value of the slot CL-TREEMAPS::DATA
in #<REDBLACK-TREE-MAP #x2101367FDD>, because it is not of type CL-TREEMAPS::REDBLACK-NODE. ..
 --------------------------------

The slot in question is defined at line 28 of redblack.lisp.


Topics: data structure