On this page:
token-tree%
new
get-root
search!
node?
node-token-length
node-token-data
node-left-subtree-length
node-left
node-right
insert-first!
insert-last!
insert-last-spec!

7 Splay Tree for Tokenization

 (require syntax-color/token-tree)
  package: syntax-color-lib

class

token-tree% : class?

  superclass: object%

A splay-tree class specifically geared for the task of on-the-fly tokenization. Instead of keying nodes on values, each node has a length, and they are found by finding a node that follows a certain total length of preceding nodes.
FIXME: many methods are not yet documented.

constructor

(new token-tree% [len len] [data data])

  (is-a?/c token-tree%)
  len : (or/c exact-nonnegative-integer? fasle/c)
  data : any/c
Creates a token tree with a single element.

method

(send a-token-tree get-root)  (or/c node? #f)

Returns the root node in the tree.

method

(send a-token-tree search! key-position)  void?

  key-position : natural-number/c
Splays, setting the root node to be the closest node to offset key-position (i.e., making the total length of the left tree at least key-position, if possible).

procedure

(node? v)  boolean?

  v : any/c

procedure

(node-token-length n)  natural-number/c

  n : node?

procedure

(node-token-data n)  any/c

  n : node?

procedure

(node-left-subtree-length n)  natural-number/c

  n : node?

procedure

(node-left n)  (or/c node? #f)

  n : node?

procedure

(node-right n)  (or/c node? #f)

  n : node?
Functions for working with nodes in a token-tree%.

procedure

(insert-first! tree1 tree2)  void?

  tree1 : (is-a?/c token-tree%)
  tree2 : (is-a?/c token-tree%)
Inserts tree1 into tree2 as the first thing, setting tree2’s root to #f.

procedure

(insert-last! tree1 tree2)  void?

  tree1 : (is-a?/c token-tree%)
  tree2 : (is-a?/c token-tree%)
Inserts tree1 into tree2 as the last thing, setting tree2’s root to #f.

procedure

(insert-last-spec! tree n v)  void?

  tree : (is-a?/c token-tree%)
  n : natural-number/c
  v : any/c
Same as
(insert-last! tree
              (new token-tree%
                   [length n]
                   [data v]))

This optimization is important for the colorer.