Leftist Trees
leftist-tree
leftist-tree?
leftist-tree-empty?
leftist-tree-count
leftist-tree-add
leftist-tree-add-all
leftist-tree-min
leftist-tree-remove-min
leftist-tree->list
in-leftist-tree
7.0

Leftist Trees

Jon Zeppieri <[email protected]>

 (require data/leftist-tree) package: leftist-tree

Leftist trees are immutable priority queues.

procedure

(leftist-tree <=? [xs])  leftist-tree?

  <=? : (-> any/c any/c any/c)
  xs : sequence? = '()
Makes a new tree containing the elements of xs, ordered by <=?.

Examples:
> (define empty-tree-of-strings (leftist-tree string<=?))
> (define non-empty-tree-of-strings (leftist-tree string<=? '("once" "upon" "a" "time")))
> empty-tree-of-strings

#<leftist-tree [empty]>

> non-empty-tree-of-strings

#<leftist-tree [count=4; min="a"]>

procedure

(leftist-tree? x)  boolean?

  x : any/c
Returns #t if x is a leftist tree, #f otherwise.

Examples:
> (leftist-tree? (leftist-tree <=))

#t

> (leftist-tree? "I can haz treaz?")

#f

procedure

(leftist-tree-empty? t)  leftist-tree?

  t : leftist-tree?
Returns #t if t is empty, #f otherwise.

Examples:
> (define t (leftist-tree string<=?))
> (leftist-tree-empty? t)

#t

> (leftist-tree-empty? (leftist-tree-add t "κατέβην χθὲς εἰς Πειραιᾶ μετὰ Γλαύκωνος τοῦ Ἀρίστωνος..."))

#f

Returns the number of elements in t.

Examples:
> (define t (leftist-tree string<=?))
> (leftist-tree-count t)

0

> (leftist-tree-count (leftist-tree-add-all t (enum->list string/e 10)))

10

procedure

(leftist-tree-add t x)  leftist-tree?

  t : leftist-tree?
  x : any/c
Functionally extends t by adding x and returns the extended tree.

Examples:
> (define empty (leftist-tree string<=?))
> (define non-empty (leftist-tree-add empty "Hello world!"))

procedure

(leftist-tree-add-all t xs)  leftist-tree?

  t : leftist-tree?
  xs : sequence?
Functionally extends t by adding all elements of the sequence xs and returns the extended tree.

Examples:
> (define empty (leftist-tree string<=?))
> (define words '("some pig!" "terrific" "radiant" "humble"))
> (leftist-tree-add-all empty words)

#<leftist-tree [count=4; min="humble"]>

procedure

(leftist-tree-min t)  any/c

  t : leftist-tree?
Returns the least element in t according to the tree’s ordering. If the tree is empty, an exception is raised.

Examples:
> (define empty (leftist-tree string<=?))
> (define words '("some pig!" "terrific" "radiant" "humble"))
> (leftist-tree-min (leftist-tree-add-all empty words))

"humble"

Functionally removes the least element in t and returns the fresh tree.

Examples:
> (define empty (leftist-tree string<=?))
> (define words '("some pig!" "terrific" "radiant" "humble"))
> (define full (leftist-tree-add-all empty words))
> (leftist-tree-count full)

4

> (leftist-tree-count (leftist-tree-remove-min full))

3

procedure

(leftist-tree->list t)  (listof any/c)

  t : leftist-tree?
Returns an ordered list of the elements of t.

Examples:
> (define empty (leftist-tree string<=?))
> (define words '("some pig!" "terrific" "radiant" "humble"))
> (define full (leftist-tree-add-all empty words))
> (leftist-tree->list full)

'("humble" "radiant" "some pig!" "terrific")

procedure

(in-leftist-tree t)  sequence?

  t : leftist-tree?
Returns a sequence that generates the elements of t in order.

Examples:
> (define empty (leftist-tree string<=?))
> (define words '("some pig!" "terrific" "radiant" "humble"))
> (define full (leftist-tree-add-all empty words))
> (for ([word (in-leftist-tree full)])
    (displayln word))

humble

radiant

some pig!

terrific