The spatial-trees Reference Manual

Table of Contents

The spatial-trees Reference Manual

This is the spatial-trees Reference Manual, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:36:50 2018 GMT+0.

1 Introduction

This code was written by Christophe Rhodes, and the following description was taken from cliki.net.

spatial-trees

spatial-trees is a set of dynamic index data structures for spatially-extended data. The flavors provided are, as of the 0.1 release (on 2004-12-03):

• R-trees, as in R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING, Antonin Guttman, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1984.

• Greene-trees, as in An Implementation and Performance Analysis of Spatial Data Access Methods, Diane Greene, Proc. 5th IEEE Int. Conf. on Data Engineering, 1989.

• R*-trees, as in The R*-tree: An Efficient and Robust Access Method for Points and Rectangles, Beckmann, Kriegel, Schneider and Seeger, Proc. ACM Int. Conf. on Management of Data, 1990

• X-trees, as in The X-tree: An Index Structure for High-Dimensional Data, Berchtold, Keim and Kriegel, Proc. 22th Int. Conf. on Very Large Databases, 1996

Future work planned includes performance enhancements, incorporation of more index structures, and some work on supporting more optimal indexing when the entire set of data is known at index creation time; for more details, see the TODO file in the binary distribution.

The code is licensed BSD-style, and is intended to be similar in spirit to Nathan Froyd's TREES Library.

Currently quicklisp-loadable.

Here are some instructions:

• Read the API first
• For Tutorial, see tutorial.lisp
• For Testing, run (asdf:test-system :spatial-trees).
• In order to test a visual inspector, run (asdf:load-system :spatial-trees-viz) and the mcclim-based visualizer will show up.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 spatial-trees

Source

spatial-trees.asd (file)

Components

• base (module)
• tree-impls (module)
• licence (file)
• todo (file)

3 Modules

Modules are listed depth-first from the system components tree.

3.1 spatial-trees/base

Parent

spatial-trees (system)

Location

Components

• package.lisp (file)
• basedefs.lisp (file)
• rectangles.lisp (file)

3.2 spatial-trees/tree-impls

Dependency

base (module)

Parent

spatial-trees (system)

Location

Components

• r-trees.lisp (file)
• greene-trees.lisp (file)
• rstar-trees.lisp (file)
• rplus-trees.lisp (file)
• x-trees.lisp (file)

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

4.1 Lisp

4.1.1 spatial-trees.asd

Location

spatial-trees.asd

Systems

spatial-trees (system)

4.1.2 spatial-trees/base/package.lisp

Parent

base (module)

Location

package.lisp

Packages

• spatial-trees-impl
• rectangles
• spatial-trees-protocol
• spatial-trees

4.1.3 spatial-trees/base/basedefs.lisp

Dependency

package.lisp (file)

Parent

base (module)

Location

basedefs.lisp

Exported Definitions

• children (method)
• (setf children) (method)
• choose-leaf (generic function)
• choose-leaf (method)
• delete (generic function)
• delete (method)
• insert (generic function)
• insert (method)
• make-spatial-tree (generic function)
• records (method)
• (setf records) (method)
• rectfun (method)
• root-node (method)
• (setf root-node) (method)
• search (generic function)
• search (method)
• spatial-tree (class)
• spatial-tree-leaf-node (class)
• spatial-tree-node (class)
• split-node (generic function)
• split-node (method)

Internal Definitions

• check (macro)
• check-consistency (generic function)
• define-protocol-function (macro)
• internal-error (condition)
• max-per-node (method)
• min-per-node (method)
• parent (method)
• (setf parent) (method)
• protocol-error (condition)
• protocol-error-function (method)
• protocol-error-tree (method)

4.1.4 spatial-trees/base/rectangles.lisp

Dependency

package.lisp (file)

Parent

base (module)

Location

rectangles.lisp

Exported Definitions

• area (generic function)
• area (method)
• highs (function)
• intersection (generic function)
• intersection (method)
• intersectp (generic function)
• intersectp (method)
• lows (function)
• make-rectangle (function)
• minimum-bound (generic function)
• minimum-bound (method)
• rectangle (structure)

Internal Definitions

• %intersect/1d-p (function)
• %intersection/1d (function)
• %make-rectangle (function)
• bound< (function)
• bound<= (function)
• bound= (function)
• boundmax (function)
• boundmin (function)
• copy-rectangle (function)
• rectangle-infinite (condition)
• rectangle-infinite-rectangle (method)
• rectangle-p (function)

4.1.5 spatial-trees/tree-impls/r-trees.lisp

Parent

tree-impls (module)

Location

r-trees.lisp

Exported Definitions

• bounding-rectangle (function)
• choose-leaf (method)
• delete (method)
• insert (method)
• leaf-node-entry (structure)
• make-spatial-tree (method)
• mbr (generic function)
• mbr (method)
• mbr (method)
• search (method)
• search (method)
• split-node (method)

Internal Definitions

• adjust-tree (generic function)
• adjust-tree (method)
• condense-tree (function)
• copy-leaf-node-entry (function)
• d (function)
• find-leaf (function)
• leaf-node-entry-datum (function)
• (setf leaf-node-entry-datum) (function)
• leaf-node-entry-p (function)
• leaf-node-entry-rectangle (function)
• (setf leaf-node-entry-rectangle) (function)
• make-leaf-node-entry (function)
• make-node-like (function)
• minimum-bound-of (function)
• pick-next (function)
• pick-seeds (function)
• r-tree (class)

4.1.6 spatial-trees/tree-impls/greene-trees.lisp

Dependency

r-trees.lisp (file)

Parent

tree-impls (module)

Location

greene-trees.lisp

Exported Definitions

• make-spatial-tree (method)
• split-node (method)

Internal Definitions

• choose-axis (function)
• distribute (function)
• greene-tree (class)

4.1.7 spatial-trees/tree-impls/rstar-trees.lisp

Dependency

r-trees.lisp (file)

Parent

tree-impls (module)

Location

rstar-trees.lisp

Exported Definitions

• choose-leaf (method)
• insert (method)
• make-spatial-tree (method)
• split-node (method)

Internal Definitions

• %insert (function)
• *data-rectangle* (special variable)
• *overflowed-levels* (special variable)
• choose-split-axis (function)
• choose-split-index (function)
• choose-subtree (function)
• height (function)
• margin (function)
• overflow-treatment (function)
• overlap (function)
• r*-tree (class)
• reinsert (function)
• removed-number (method)
• (setf removed-number) (method)

4.1.8 spatial-trees/tree-impls/rplus-trees.lisp

Dependency

r-trees.lisp (file)

Parent

tree-impls (module)

Location

rplus-trees.lisp

Exported Definitions

• delete (method)
• insert (method)
• make-spatial-tree (method)
• make-spatial-tree (method)
• search (method)
• split-node (method)

Internal Definitions

• cost (function)
• fill-factor (method)
• (setf fill-factor) (method)
• generate-partition-rectangles (function)
• r+-tree (class)
• split-node-by (function)
• unlink-node (function)

4.1.9 spatial-trees/tree-impls/x-trees.lisp

Dependencies

• r-trees.lisp (file)
• rstar-trees.lisp (file)

Parent

tree-impls (module)

Location

x-trees.lisp

Exported Definitions

• insert (method)
• make-spatial-tree (method)
• split-node (method)

Internal Definitions

• *split* (special variable)
• adjust-tree (method)
• check-consistency (method)
• find-cons-with-leaf (function)
• leaves-of-split-tree (function)
• max-overlap (method)
• split-tree (method)
• (setf split-tree) (method)
• split-tree-from-set (function)
• x-tree (class)
• x-tree-leaf-supernode (class)
• x-tree-node (class)
• x-tree-supernode (class)

4.2 Other

4.2.1 spatial-trees/LICENCE

Parent

spatial-trees (system)

Location

LICENCE

4.2.2 spatial-trees/TODO

Parent

spatial-trees (system)

Location

TODO

5 Packages

Packages are listed by definition order.

5.1 spatial-trees-impl

Source

package.lisp (file)

Use List

• rectangles
• spatial-trees-protocol
• spatial-trees
• common-lisp

Exported Definitions

• leaf-node-entry (structure)
• mbr (generic function)
• mbr (method)
• mbr (method)
• rectfun (generic function)
• rectfun (method)

Internal Definitions

• %insert (function)
• %intersect/1d-p (function)
• %intersection/1d (function)
• %make-rectangle (function)
• *data-rectangle* (special variable)
• *overflowed-levels* (special variable)
• *split* (special variable)
• adjust-tree (generic function)
• adjust-tree (method)
• adjust-tree (method)
• bound< (function)
• bound<= (function)
• bound= (function)
• boundmax (function)
• boundmin (function)
• check (macro)
• check-consistency (generic function)
• check-consistency (method)
• choose-axis (function)
• choose-split-axis (function)
• choose-split-index (function)
• choose-subtree (function)
• condense-tree (function)
• copy-leaf-node-entry (function)
• copy-rectangle (function)
• cost (function)
• d (function)
• define-protocol-function (macro)
• distribute (function)
• fill-factor (generic function)
• fill-factor (method)
• (setf fill-factor) (method)
• (setf fill-factor) (generic function)
• find-cons-with-leaf (function)
• find-leaf (function)
• generate-partition-rectangles (function)
• greene-tree (class)
• height (function)
• internal-error (condition)
• leaf-node-entry-datum (function)
• (setf leaf-node-entry-datum) (function)
• leaf-node-entry-p (function)
• leaf-node-entry-rectangle (function)
• (setf leaf-node-entry-rectangle) (function)
• leaves-of-split-tree (function)
• make-leaf-node-entry (function)
• make-node-like (function)
• margin (function)
• max-overlap (generic function)
• max-overlap (method)
• max-per-node (generic function)
• max-per-node (method)
• min-per-node (generic function)
• min-per-node (method)
• minimum-bound-of (function)
• overflow-treatment (function)
• overlap (function)
• parent (generic function)
• parent (method)
• (setf parent) (method)
• (setf parent) (generic function)
• pick-next (function)
• pick-seeds (function)
• protocol-error (condition)
• protocol-error-function (generic function)
• protocol-error-function (method)
• protocol-error-tree (generic function)
• protocol-error-tree (method)
• r*-tree (class)
• r+-tree (class)
• r-tree (class)
• rectangle-infinite (condition)
• rectangle-infinite-rectangle (generic function)
• rectangle-infinite-rectangle (method)
• rectangle-p (function)
• reinsert (function)
• removed-number (generic function)
• removed-number (method)
• (setf removed-number) (method)
• (setf removed-number) (generic function)
• split-node-by (function)
• split-tree (generic function)
• split-tree (method)
• (setf split-tree) (method)
• (setf split-tree) (generic function)
• split-tree-from-set (function)
• unlink-node (function)
• x-tree (class)
• x-tree-leaf-supernode (class)
• x-tree-node (class)
• x-tree-supernode (class)

5.2 rectangles

Source

package.lisp (file)

Use List

common-lisp

Used By List

spatial-trees-impl

Exported Definitions

• area (generic function)
• area (method)
• highs (function)
• intersection (generic function)
• intersection (method)
• intersectp (generic function)
• intersectp (method)
• lows (function)
• make-rectangle (function)
• minimum-bound (generic function)
• minimum-bound (method)
• rectangle (structure)

5.3 spatial-trees-protocol

Source

package.lisp (file)

Use List

• spatial-trees
• common-lisp

Used By List

spatial-trees-impl

Exported Definitions

• children (generic function)
• children (method)
• (setf children) (method)
• (setf children) (generic function)
• choose-leaf (generic function)
• choose-leaf (method)
• choose-leaf (method)
• choose-leaf (method)
• records (generic function)
• records (method)
• (setf records) (method)
• (setf records) (generic function)
• root-node (generic function)
• root-node (method)
• (setf root-node) (method)
• (setf root-node) (generic function)
• spatial-tree (class)
• spatial-tree-leaf-node (class)
• spatial-tree-node (class)
• split-node (generic function)
• split-node (method)
• split-node (method)
• split-node (method)
• split-node (method)
• split-node (method)
• split-node (method)

5.4 spatial-trees

Source

package.lisp (file)

Use List

common-lisp

Used By List

• spatial-trees-impl
• spatial-trees-protocol

Exported Definitions

• bounding-rectangle (function)
• delete (generic function)
• delete (method)
• delete (method)
• delete (method)
• insert (generic function)
• insert (method)
• insert (method)
• insert (method)
• insert (method)
• insert (method)
• make-spatial-tree (generic function)
• make-spatial-tree (method)
• make-spatial-tree (method)
• make-spatial-tree (method)
• make-spatial-tree (method)
• make-spatial-tree (method)
• make-spatial-tree (method)
• search (generic function)
• search (method)
• search (method)
• search (method)
• search (method)

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

6.1 Exported definitions

6.1.1 Functions

Function: bounding-rectangle TREE

Package

spatial-trees

Source

r-trees.lisp (file)

Function: highs INSTANCE

Package

rectangles

Source

rectangles.lisp (file)

Function: lows INSTANCE

Package

rectangles

Source

rectangles.lisp (file)

Function: make-rectangle &key LOWS HIGHS

Package

rectangles

Source

rectangles.lisp (file)

6.1.2 Generic functions

Generic Function: area OBJECT

Package

rectangles

Source

rectangles.lisp (file)

Methods

Method: area (R rectangle)

Generic Function: children OBJECT

Generic Function: (setf children) NEW-VALUE OBJECT

Package

spatial-trees-protocol

Methods

Method: children (SPATIAL-TREE-NODE spatial-tree-node)

automatically generated reader method

Source

basedefs.lisp (file)

Method: (setf children) NEW-VALUE (SPATIAL-TREE-NODE spatial-tree-node)

automatically generated writer method

Source

basedefs.lisp (file)

Generic Function: choose-leaf R TREE

Package

spatial-trees-protocol

Source

basedefs.lisp (file)

Methods

Method: choose-leaf R (TREE r*-tree)

Source

rstar-trees.lisp (file)

Method: choose-leaf R (TREE r-tree)

Source

r-trees.lisp (file)

Method: choose-leaf R (TREE spatial-tree)

Generic Function: delete OBJECT TREE

Package

spatial-trees

Source

basedefs.lisp (file)

Methods

Method: delete R (TREE r+-tree)

Source

rplus-trees.lisp (file)

Method: delete R (TREE r-tree)

Source

r-trees.lisp (file)

Method: delete OBJECT (TREE spatial-tree)

Generic Function: insert OBJECT TREE

Package

spatial-trees

Source

basedefs.lisp (file)

Methods

Method: insert O (TREE x-tree)

Source

x-trees.lisp (file)

Method: insert R (TREE r+-tree)

Source

rplus-trees.lisp (file)

Method: insert R (TREE r*-tree)

Source

rstar-trees.lisp (file)

Method: insert R (TREE r-tree)

Source

r-trees.lisp (file)

Method: insert OBJECT (TREE spatial-tree)

Generic Function: intersection ONE TWO

Package

rectangles

Source

rectangles.lisp (file)

Methods

Method: intersection (R1 rectangle) (R2 rectangle)

Generic Function: intersectp ONE TWO

Package

rectangles

Source

rectangles.lisp (file)

Methods

Method: intersectp (R1 rectangle) (R2 rectangle)

Generic Function: make-spatial-tree KIND &rest INITARGS &key &allow-other-keys

Package

spatial-trees

Source

basedefs.lisp (file)

Methods

Method: make-spatial-tree (KIND (eql x)) &rest INITARGS

Source

x-trees.lisp (file)

Method: make-spatial-tree (KIND (eql r+)) &rest INITARGS

Source

rplus-trees.lisp (file)

Method: make-spatial-tree (KIND (eql r+)) &rest INITARGS around

Source

rplus-trees.lisp (file)

Method: make-spatial-tree (KIND (eql r*)) &rest INITARGS

Source

rstar-trees.lisp (file)

Method: make-spatial-tree (KIND (eql greene)) &rest INITARGS

Source

greene-trees.lisp (file)

Method: make-spatial-tree (KIND (eql r)) &rest INITARGS

Source

r-trees.lisp (file)

Generic Function: mbr THING TREE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Methods

Method: mbr (O leaf-node-entry) (TREE spatial-tree)

Method: mbr (N spatial-tree-node) (TREE spatial-tree)

Generic Function: minimum-bound ONE TWO

Package

rectangles

Source

rectangles.lisp (file)

Methods

Method: minimum-bound (R1 rectangle) (R2 rectangle)

Generic Function: records OBJECT

Generic Function: (setf records) NEW-VALUE OBJECT

Package

spatial-trees-protocol

Methods

Method: records (SPATIAL-TREE-LEAF-NODE spatial-tree-leaf-node)

automatically generated reader method

Source

basedefs.lisp (file)

Method: (setf records) NEW-VALUE (SPATIAL-TREE-LEAF-NODE spatial-tree-leaf-node)

automatically generated writer method

Source

basedefs.lisp (file)

Generic Function: rectfun OBJECT

Package

spatial-trees-impl

Methods

Method: rectfun (SPATIAL-TREE spatial-tree)

automatically generated reader method

Source

basedefs.lisp (file)

Generic Function: root-node OBJECT

Generic Function: (setf root-node) NEW-VALUE OBJECT

Package

spatial-trees-protocol

Methods

Method: root-node (SPATIAL-TREE spatial-tree)

automatically generated reader method

Source

basedefs.lisp (file)

Method: (setf root-node) NEW-VALUE (SPATIAL-TREE spatial-tree)

automatically generated writer method

Source

basedefs.lisp (file)

Generic Function: search OBJECT TREE

Package

spatial-trees

Source

basedefs.lisp (file)

Methods

Method: search (R rectangle) (TREE r+-tree) around

Source

rplus-trees.lisp (file)

Method: search (R rectangle) (TREE r-tree)

Source

r-trees.lisp (file)

Method: search O (TREE r-tree)

Source

r-trees.lisp (file)

Method: search OBJECT (TREE spatial-tree)

Generic Function: split-node TREE NEW NODE

Package

spatial-trees-protocol

Source

basedefs.lisp (file)

Methods

Method: split-node (TREE x-tree) NEW NODE

Source

x-trees.lisp (file)

Method: split-node (TREE r+-tree) NEW NODE

Source

rplus-trees.lisp (file)

Method: split-node (TREE r*-tree) NEW NODE

Source

rstar-trees.lisp (file)

Method: split-node (TREE greene-tree) NEW NODE

Source

greene-trees.lisp (file)

Method: split-node (TREE r-tree) NEW NODE

Source

r-trees.lisp (file)

Method: split-node (TREE spatial-tree) NEW NODE

6.1.3 Structures

Structure: leaf-node-entry ()

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

mbr (method)

Direct slots

Slot: rectangle

Readers

leaf-node-entry-rectangle (function)

Writers

(setf leaf-node-entry-rectangle) (function)

Slot: datum

Readers

leaf-node-entry-datum (function)

Writers

(setf leaf-node-entry-datum) (function)

Structure: rectangle ()

Package

rectangles

Source

rectangles.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

• search (method)
• search (method)
• area (method)
• minimum-bound (method)
• intersection (method)
• intersectp (method)
• print-object (method)

Direct slots

Slot: lows

Readers

lows (function)

Writers

(setf lows) (function)

Slot: highs

Readers

highs (function)

Writers

(setf highs) (function)

6.1.4 Classes

Class: spatial-tree ()

Package

spatial-trees-protocol

Source

basedefs.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

r-tree (class)

Direct methods

• mbr (method)
• mbr (method)
• split-node (method)
• choose-leaf (method)
• delete (method)
• insert (method)
• search (method)
• print-object (method)
• min-per-node (method)
• max-per-node (method)
• rectfun (method)
• root-node (method)
• root-node (method)

Direct slots

Slot: root-node

Initargs

:root-node

Readers

root-node (generic function)

Writers

(setf root-node) (generic function)

Slot: rectfun

Initargs

:rectfun

Readers

rectfun (generic function)

Slot: max-per-node

Initform

7

Readers

max-per-node (generic function)

Slot: min-per-node

Initform

3

Readers

min-per-node (generic function)

Class: spatial-tree-leaf-node ()

Package

spatial-trees-protocol

Source

basedefs.lisp (file)

Direct superclasses

spatial-tree-node (class)

Direct subclasses

x-tree-leaf-supernode (class)

Direct methods

• records (method)
• records (method)

Direct slots

Slot: children

Initargs

:records

Readers

records (generic function)

Writers

(setf records) (generic function)

Class: spatial-tree-node ()

Package

spatial-trees-protocol

Source

basedefs.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• spatial-tree-leaf-node (class)
• x-tree-node (class)

Direct methods

• mbr (method)
• print-object (method)
• parent (method)
• parent (method)
• children (method)
• children (method)

Direct slots

Slot: mbr

Initargs

:mbr

Slot: children

Initargs

:children

Readers

children (generic function)

Writers

(setf children) (generic function)

Slot: parent

Initargs

:parent

Readers

parent (generic function)

Writers

(setf parent) (generic function)

6.2 Internal definitions

6.2.1 Special variables

Special Variable: *data-rectangle*

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Special Variable: *overflowed-levels*

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Special Variable: *split*

Package

spatial-trees-impl

Source

x-trees.lisp (file)

6.2.2 Macros

Macro: check FORM CONTROL &rest ARGS

Package

spatial-trees-impl

Source

basedefs.lisp (file)

Macro: define-protocol-function NAME LAMBDA-LIST

Package

spatial-trees-impl

Source

basedefs.lisp (file)

6.2.3 Functions

Function: %insert THING TREE LEVEL

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: %intersect/1d-p L1 H1 L2 H2

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: %intersection/1d L1 H1 L2 H2

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: %make-rectangle LOWS HIGHS

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: bound< X Y

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: bound<= X Y

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: bound= X Y

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: boundmax X Y

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: boundmin X Y

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: choose-axis ENTRIES NODE TREE

Package

spatial-trees-impl

Source

greene-trees.lisp (file)

Function: choose-split-axis ENTRIES TREE

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: choose-split-index ENTRIES AXIS TREE

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: choose-subtree THING NODE LEVEL TREE

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: condense-tree NODE TREE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: copy-leaf-node-entry INSTANCE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: copy-rectangle INSTANCE

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: cost R1 R2

Package

spatial-trees-impl

Source

rplus-trees.lisp (file)

Function: d R1 R2 TREE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: distribute ENTRIES AXIS NODE NEW-NODE TREE

Package

spatial-trees-impl

Source

greene-trees.lisp (file)

Function: find-cons-with-leaf OBJECT CONSES

Package

spatial-trees-impl

Source

x-trees.lisp (file)

Function: find-leaf OBJ NODE TREE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: generate-partition-rectangles ENTRIES TREE

Package

spatial-trees-impl

Source

rplus-trees.lisp (file)

Function: height TREE

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: leaf-node-entry-datum INSTANCE

Function: (setf leaf-node-entry-datum) VALUE INSTANCE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: leaf-node-entry-p OBJECT

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: leaf-node-entry-rectangle INSTANCE

Function: (setf leaf-node-entry-rectangle) VALUE INSTANCE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: leaves-of-split-tree SPLIT-TREE

Package

spatial-trees-impl

Source

x-trees.lisp (file)

Function: make-leaf-node-entry &key (RECTANGLE RECTANGLE) (DATUM DATUM)

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: make-node-like NODE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: margin RECTANGLE

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: minimum-bound-of OBJECTS TREE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: overflow-treatment THING TREE NODE LEVEL

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: overlap X OTHERS TREE

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: pick-next ENTRIES NODE NEW-NODE TREE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: pick-seeds ENTRIES TREE

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Function: rectangle-p OBJECT

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Function: reinsert THING TREE NODE LEVEL

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Function: split-node-by TREE NODE ENTRIES RONE RTWO

Package

spatial-trees-impl

Source

rplus-trees.lisp (file)

Function: split-tree-from-set SET SPLIT-TREE

Package

spatial-trees-impl

Source

x-trees.lisp (file)

Function: unlink-node NODE TREE

Package

spatial-trees-impl

Source

rplus-trees.lisp (file)

6.2.4 Generic functions

Generic Function: adjust-tree TREE NODE &optional NEW

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Methods

Method: adjust-tree (TREE x-tree) NODE &optional NEW

Source

x-trees.lisp (file)

Method: adjust-tree (TREE r-tree) NODE &optional NEW

Generic Function: check-consistency TREE

Package

spatial-trees-impl

Source

basedefs.lisp (file)

Method Combination

progn (short method combination)

Options: :most-specific-first

Methods

Method: check-consistency (TREE x-tree) progn

Source

x-trees.lisp (file)

Generic Function: fill-factor OBJECT

Generic Function: (setf fill-factor) NEW-VALUE OBJECT

Package

spatial-trees-impl

Methods

Method: fill-factor (R+-TREE r+-tree)

automatically generated reader method

Source

rplus-trees.lisp (file)

Method: (setf fill-factor) NEW-VALUE (R+-TREE r+-tree)

automatically generated writer method

Source

rplus-trees.lisp (file)

Generic Function: max-overlap OBJECT

Package

spatial-trees-impl

Methods

Method: max-overlap (X-TREE x-tree)

automatically generated reader method

Source

x-trees.lisp (file)

Generic Function: max-per-node OBJECT

Package

spatial-trees-impl

Methods

Method: max-per-node (SPATIAL-TREE spatial-tree)

automatically generated reader method

Source

basedefs.lisp (file)

Generic Function: min-per-node OBJECT

Package

spatial-trees-impl

Methods

Method: min-per-node (SPATIAL-TREE spatial-tree)

automatically generated reader method

Source

basedefs.lisp (file)

Generic Function: parent OBJECT

Generic Function: (setf parent) NEW-VALUE OBJECT

Package

spatial-trees-impl

Methods

Method: parent (SPATIAL-TREE-NODE spatial-tree-node)

automatically generated reader method

Source

basedefs.lisp (file)

Method: (setf parent) NEW-VALUE (SPATIAL-TREE-NODE spatial-tree-node)

automatically generated writer method

Source

basedefs.lisp (file)

Generic Function: protocol-error-function CONDITION

Package

spatial-trees-impl

Methods

Method: protocol-error-function (CONDITION protocol-error)

Source

basedefs.lisp (file)

Generic Function: protocol-error-tree CONDITION

Package

spatial-trees-impl

Methods

Method: protocol-error-tree (CONDITION protocol-error)

Source

basedefs.lisp (file)

Generic Function: rectangle-infinite-rectangle CONDITION

Package

spatial-trees-impl

Methods

Method: rectangle-infinite-rectangle (CONDITION rectangle-infinite)

Source

rectangles.lisp (file)

Generic Function: removed-number OBJECT

Generic Function: (setf removed-number) NEW-VALUE OBJECT

Package

spatial-trees-impl

Methods

Method: removed-number (R*-TREE r*-tree)

automatically generated reader method

Source

rstar-trees.lisp (file)

Method: (setf removed-number) NEW-VALUE (R*-TREE r*-tree)

automatically generated writer method

Source

rstar-trees.lisp (file)

Generic Function: split-tree OBJECT

Generic Function: (setf split-tree) NEW-VALUE OBJECT

Package

spatial-trees-impl

Methods

Method: split-tree (X-TREE-NODE x-tree-node)

automatically generated reader method

Source

x-trees.lisp (file)

Method: (setf split-tree) NEW-VALUE (X-TREE-NODE x-tree-node)

automatically generated writer method

Source

x-trees.lisp (file)

6.2.5 Conditions

Condition: internal-error ()

Package

spatial-trees-impl

Source

basedefs.lisp (file)

Direct superclasses

simple-error (condition)

Condition: protocol-error ()

Package

spatial-trees-impl

Source

basedefs.lisp (file)

Direct superclasses

error (condition)

Direct methods

• protocol-error-tree (method)
• protocol-error-function (method)

Direct slots

Slot: function

Initargs

:function

Readers

protocol-error-function (generic function)

Slot: tree

Initargs

:tree

Readers

protocol-error-tree (generic function)

Condition: rectangle-infinite ()

Package

spatial-trees-impl

Source

rectangles.lisp (file)

Direct superclasses

error (condition)

Direct methods

rectangle-infinite-rectangle (method)

Direct slots

Slot: rectangle

Initargs

:rectangle

Readers

rectangle-infinite-rectangle (generic function)

6.2.6 Classes

Class: greene-tree ()

Package

spatial-trees-impl

Source

greene-trees.lisp (file)

Direct superclasses

r-tree (class)

Direct methods

split-node (method)

Class: r*-tree ()

Package

spatial-trees-impl

Source

rstar-trees.lisp (file)

Direct superclasses

r-tree (class)

Direct subclasses

x-tree (class)

Direct methods

• insert (method)
• split-node (method)
• choose-leaf (method)
• initialize-instance (method)
• removed-number (method)
• removed-number (method)

Direct slots

Slot: removed-number

Initargs

:removed-number

Readers

removed-number (generic function)

Writers

(setf removed-number) (generic function)

Class: r+-tree ()

Package

spatial-trees-impl

Source

rplus-trees.lisp (file)

Direct superclasses

r-tree (class)

Direct methods

• split-node (method)
• delete (method)
• insert (method)
• search (method)
• initialize-instance (method)
• fill-factor (method)
• fill-factor (method)

Direct slots

Slot: fill-factor

Initargs

:fill-factor

Readers

fill-factor (generic function)

Writers

(setf fill-factor) (generic function)

Class: r-tree ()

Package

spatial-trees-impl

Source

r-trees.lisp (file)

Direct superclasses

spatial-tree (class)

Direct subclasses

• greene-tree (class)
• r*-tree (class)
• r+-tree (class)

Direct methods

• split-node (method)
• delete (method)
• adjust-tree (method)
• insert (method)
• choose-leaf (method)
• search (method)
• search (method)

Class: x-tree ()

Package

spatial-trees-impl

Source

x-trees.lisp (file)

Direct superclasses

r*-tree (class)

Direct methods

• check-consistency (method)
• split-node (method)
• insert (method)
• adjust-tree (method)
• initialize-instance (method)
• max-overlap (method)

Direct slots

Slot: max-overlap

Initargs

:max-overlap

Readers

max-overlap (generic function)

Class: x-tree-leaf-supernode ()

Package

spatial-trees-impl

Source

x-trees.lisp (file)

Direct superclasses

• spatial-tree-leaf-node (class)
• x-tree-supernode (class)

Class: x-tree-node ()

Package

spatial-trees-impl

Source

x-trees.lisp (file)

Direct superclasses

spatial-tree-node (class)

Direct subclasses

x-tree-supernode (class)

Direct methods

• split-tree (method)
• split-tree (method)

Direct slots

Slot: split-tree

Initargs

:split-tree

Readers

split-tree (generic function)

Writers

(setf split-tree) (generic function)

Class: x-tree-supernode ()

Package

spatial-trees-impl

Source

x-trees.lisp (file)

Direct superclasses

x-tree-node (class)

Direct subclasses

x-tree-leaf-supernode (class)

Appendix A Indexes

A.1 Concepts

A.2 Functions