The Gobán Eiffel library (draft version)

Colm Ó Dúnlaing

February 22, 2006

Abstract

Contents

Introduction 1 Note on iterators and routine arguments 3 Heaps 2 Tuples 4 Tuple test bench 5 Search trees 6 Pattern matching 7 Examples 8

1 Introduction

The Gobán library is a small library of Eiffel classes implementing the most important data-structures: search trees, heaps, pattern-matching structures, graphs, and so on. It is intended that the library be small. In many algorithmic situations only a few data-structures are needed. In computational geometry the combinatorial needs are often satisfied with a heap and a search-tree, and the difficulties are mostly numerical. This library is therefore content with just a small set of data-structures. The intention is that they be easy to use. For ease of use, Eiffel is the best language available, superior to C, C++, and Java.

The basic element of our library is the tuple. A tuple is no more nor less than an ordered list. It can be implemented as a doubly-linked list, or in a red-black tree; and both these versions are available in the library. Exactly the same operations are supplied for both structures, and the implementation is fully hidden. The performance of the various operations differs. In fact, the list version of a tuple is superior to the tree version in all operations except when removing a sublist.

We have arranged, rather peculiarly, that binary trees should represent ordered list without needing to store keys (in sorted order) in these trees. Search trees are implemented as red-black tree lists augmented with various lookup operations.

Hash-tables are perhaps more useful than search trees, but these are already implemented in the SmartEiffel library, and there seemed no reason to revise them.

It has proved useful at times to have a pattern-matching function (for modifying identifiers in programs under development), and the library includes a TRIE (retrieval tree) data structure, suitable for searching for occurrences of several patterns simultaneously in a string.

A Heap (priority queue) structure is available. It differs from the basic version in one crucial respect: that heap entries are accessible through PLACE-like objects, in effect, through pointers. Although the most basic heap structure is used — the array implementation — heap entries cannot be accessed through array indices, since these indices are volatile: heap entries move around within the array. With the PLACE access scheme, it is possible to remove entries from the heap.

This leads us to mention a feature of the data-structures: whenever an object is added to a tuple, or heap, or whatever, a link is optionally returned whereby the entry can be accessed directly and removed if so wished. It seems necessary then that all links be reversible, so lists are doubly-linked, and binary trees include links to the parents. This requires extra space and time (every pointer update must be duplicated), but allows for flexibility and ease of use.

2 Heaps

It seems a good idea to include a heap structure in the library. There is one respect where one needs to go beyond the classical heap structure — to provide a means of direct access into the heap. Hence

type GBN_HEAP_PLACE.
class interface GBN_HEAP[G->COMPARABLE]
   -- Keys are stored in objects of type GBN_HEAP_PLACE.
   -- This allows keys to be accessed directly
   -- through their place.  Indexes into the data array,
   -- which are changeable, are kept private.
creation
   make
   build_heap (keys: ARRAY[G])
       -- linear time operation
feature
   count: INTEGER
   is_empty: BOOLEAN
   min: G
   has_place (p: GBN_HEAP_PLACE[G]): BOOLEAN
   delete_min
   remove (p: GBN_HEAP_PLACE[G])
   add (k: G; stored_at: GBN_BOX[GBN_HEAP_PLACE[G]])
      -- optionally returns the `place' stored_at

3 Note on iterators and routine arguments

(3.1) Iterators in the Gobán library. Over the years, there seem to have been changes in the way iterators are approached in Eiffel. In the Gobán library, we stick to earlier notation. Our iterators function the same way as those in the SmartEiffel library with some difference in keywords used. Usage of iterators must be as follows.

                         from
                           it := a . xxxiterator
                         until
                           it . finished
                         loop
                           ...
                           it . forth
                         end

As usual with iterators, the question arises about what happens when you add items to or remove them from a structure while iterating over the structure. There are two approaches: either make a copy of the structure before iteration, or make such changes illegal. Our iterators adopt the second (easier) option, with the use of semaphores. For this reason it is essential that iterators terminate cleanly. If using an iterator to search for something, you must not write

                        from
                          it := a . xxxiterator
                        until
                          found or it . finished
                        loop
                          ...
                          it . forth
                        end

This would leave an unresolved semaphore, and any further efforts to alter the structure would violate the require clauses. The correct way is

                         from
                           it := a . xxxiterator
                         until
                           it . finished
                         loop
                           ...
                           if found then
                             it . stop
                           else
                             it . forth
                           end
                         end

(3.2) Iteration ‘protectorates.’ When an iterator is live, it has a designated ‘protectorate’ which cannot support any update operation until the iterator terminates. A new feature of the Gobán library is that the protectorate may involve more than the structure which provides the iterator. For example, when iterating over the adjacency list of a graph node, all modifications to the graph structure must be inhibited, not just modifications to the list.

(3.3) Routine arguments. All arguments in Eiffel are call-by-value. Sometimes this makes programming clumsy. For example, to read a real number one writes

                           io . read_real
                           x := io . last_real

It would be more satisfying if one could tie the two statements together. A mechanism is possible in Eiffel. The simple class GBN_BOX provides such a mechanism.

One should add immediately that it is seldom worth the trouble.

class interface GBN_BOX[G]
   -- This class is intended for `call by result' parameter pasing
creation
   make
       ensure
          empty: is_empty
feature(s) from GBN_BOX
   is_empty: BOOLEAN
   wipe_out
       ensure
          empty: is_empty
   put (x: G)

   ensure
       nonempty: not is_empty;
       has_x: item = x
item: G
   require
       nonempty: not is_empty
end of GBN_BOX[G]

For example, the GBN_HEAP feature add has the following signature

 add ( k : G; stored_at : GBN_BOX [ GBN_HEAP_PLACE [G,H] ] )

This adds the key k to the heap. It creates a ‘heap place’ p at which the key is stored, and which can carry other data associated with the key. If the argument stored_at is passed as a non-Void object, the routine stores p in the ‘box’ stored_at. Thus the routine can pass data back to the caller. Otherwise it would be necessary to provide a feature ‘last_place’ associated with the heap, indicating the place most recently added to the heap.

The cost of this mechanism is that a box needs to be created and accessed by the calling routine. Because of this the mechanism should be used sparingly.

4 Tuples

A tuple is a finite ordered list. In the Gobán scheme, the most primitive kind of tuple is a readonly tuple, which cannot be modified in any way (except for hidden iterator semaphores). This is a deferred class. Objects of this class cannot be created, but they can be assigned.

deferred class interface GBN_ROTUPLE[G]
-- This class has all the read-only properties of a tuple. An
-- object of this type can inspect and traverse the tuple, but
-- not alter it.
feature
count: INTEGER
is_empty: BOOLEAN
has_place (p: GBN_PLACE): BOOLEAN
first_place: GBN_PLACE
last_place: like first_place
rank (p: like first_place): INTEGER
nth_after (n: INTEGER; p: like first_place): like first_place
nth_before (n: INTEGER; p: like first_place): like first_place
nth_place (n: INTEGER): like first_place
pred (p: like first_place): like first_place

succ (p: like first_place): like first_place
cyclic_pred (p: like first_place): like first_place
cyclic_succ (p: like first_place): like first_place
place_lesseq (p, q: like first_place): BOOLEAN
item (p: like first_place): G
infix "@" (p: like first_place): G
top: G
first_item: G
last_item: G
protecting: GBN_PROTECTED
iterator: GBN_TUPLE_ITERATOR[G]
reverse_iterator: like iterator
cyclic_iterator (start_at, stop_after: like first_place): like iterator
reverse_cyclic_iterator (start_at, stop_after: like first_place):
          like iterator
printout (f: OUTPUT_STREAM)
end of deferred GBN_ROTUPLE[G]

The GBN_TUPLE class is also deferred, inheriting all read-only tuple features and including

deferred class interface GBN_TUPLE[G]
feature
replica: like Current
wipe_out
add_first (x: G)
push (x: G)
add_last (x: G)
add_before (x: G; p: like first_place)
add_after (x: G; p: like first_place)
pop
remove_first
remove_last
remove (p: like first_place)
absorb_prefix (other: like Current)
absorb_suffix (other: like Current)
absorb_before (other: like Current; p: like first_place)
absorb_after (other: like Current; p: like first_place)
cyclic_remove (p, q: like first_place; subtuple: GBN_BOX[like Current])
end of deferred GBN_TUPLE[G]

There are three effective classes inheriting from GBN_TUPLE: GBN_DLIST (doubly-linked list), GBN_BTLIST (binary tree), GBN_RBTLIST (red-black tree).

The doubly-linked list is superior in efficiency to the red-black tree in most respects; nth_after, cyclic_remove, etcetera are proportional to the size of the sublist examined, but the others are little more than constant-time operations. The has_place operation makes use of a union-find structure to identify the list currently containing the given place, so it runs in time O(α(r)) where α is the inverse Ackermann function and r is the current number of lists in existence.

In a red-black tree, has_place works by searching up to the root, O(log n) where n is the current size of the tree containing the place.

5 Tuple test bench

Because binary trees and lists are both treated as kinds of tuples, it becomes possible to subject them to randomised tests. A test bench program has been written which takes four or five arguments. The first argument is GBN_DLIST, GBN_BTLIST, or GBN_RBTLIST, indicating the kind of lists to be generated.

The program works with a random pool of tuples, of which one specifies the number, and the maximal size (size is allotted randomly). Then one specifies a required number of random operations to be performed on this pool. Finally, one can specify a seed for the random number generator.

If the last three or four arguments are the same, the same pool will be generated and processed in the same way. Hence one can compare dlists, binary trees, and red-black trees for essentially identical outputs. Not identical, since red-black structures are checked at the end.

6 Search trees

A red-black search-tree is implemented as a red-black list augmented with a few operations. Hence one has

class interface GBN_RBST[G->COMPARABLE]
creation
   make
feature
   the_tuple: GBN_ROTUPLE[G]
   location (k: G): like last_node
   has_place (p: GBN_PLACE): BOOLEAN
   has_key (k: G): BOOLEAN
   add (x: G)
   glb (x: G): like last_node
   lub (x: G): like last_node
   absorb (other: like Current)
   remove_place (p: like last_node)
   remove_subtree (k1, k2: G; subtree: GBN_BOX[like Current])
end of GBN_RBST[G->COMPARABLE]

A keyed red-black search tree behaves identically, except that keyed pairs are stored. This allows one to store data associated with the keys.

class interface GBN_KEYED_RBST[G->COMPARABLE,H]
feature .. generally same as above, but

the_tuple: GBN_ROTUPLE[GBN_KEYED_PAIR[G,H]]
end of GBN_KEYED_RBST[G->COMPARABLE,H]

7 Pattern matching

For pattern-matching, a GBN_TRIE class is available. This enables an Aho-Corasick search of a text string simultaneously for all the strings stored in the trie.

class GBN_TRIE
creation
make (list: ARRAY[STRING])
feature
start_of_match: INTEGER
length_of_match: INTEGER
index_of_match: INTEGER
match_found: BOOLEAN
text: STRING
install_text_string (s: STRING)
strings_and_indices: GBN_DLIST[GBN_PAIR[STRING,INTEGER]]
show_backlinks
find_match_overlapping
find_match
matching_string: STRING
lengthen_match

Also, for purposes of illusration, a more straightforward trie structure without pattern-matching capacity. The first structure only allows strings to be added on creation, because it is necessary to have all strings present when constructing the mutual overlap function.

class interface GBN_PLAIN_TRIE
-- just used to store strings, with
-- no pattern-matching capability.
creation
make
feature(s) from GBN_PLAIN_TRIE
index_of (s: STRING): INTEGER
insert (s: STRING; indx: INTEGER)
strings_and_indices: GBN_DLIST[GBN_PAIR[STRING,INTEGER]]
end of GBN_PLAIN_TRIE

8 Examples

The following code extracts words from a file, puts them in a heap, and prints them in sorted order.

from
!! words.make
until
words.last_word = Void
loop
words.get_word (file)
if words.last_word /= Void then
heap . add ( words.last_word, Void )
end
end
from
until
heap . is_empty
loop
io . put_string ( heap.min + "%N" )
heap . delete_min
end

The following does much the same, using a red-black search tree to store the words. Repetitions are not permitted.

!! tree.make
from
!! words.make
until
words.last_word = Void
loop
words.get_word (file)
if words.last_word /= Void then
if not tree.has_key (words.last_word) then
  tree . add ( words.last_word )
end
end
end
from
it := tree.the_tuple.iterator
until
it.finished
loop
io . put_string ( it.item + "%N" )
it . forth
end

The following does the same, except that a keyed red-black tree is used, and frequency counts are tallied.

!! tree.make
from
!! words . make
until
words . last_word = Void
loop
words . get_word (file)
if words . last_word /= Void then
  if not tree.has_key (words . last_word) then
     tree . add ( words . last_word )
  end
  node := tree.location ( words . last_word )
  pair := tree.the_tuple.item ( node )
  pair . put ( pair . item + 1 )
end
end
from
it := tree.the_tuple.iterator
until
it.finished
loop
io . put_string ( it.item.key + " occurs " )
io . put_integer ( it.item.item )
io . put_string ( " times%N" )
it . forth
end

The last example does the same using a trie. The trie associates an index with each word stored, and this can be used to maintain a tally count.

from
!! words . make
until
words . last_word = Void
loop
words . get_word (file)
if words . last_word /= Void then
  index := trie.index_of ( words.last_word )
  if index = 0 then
     count := count+1
     trie . insert ( words.last_word, count )
     index := count
  end
  if index > counts.upper then
     k := 0
  else
     k := counts . item ( index )
  end
  counts . force ( k+1, index )
end
end
list := trie . strings_and_indices
from
it := list . iterator
until
it.finished
loop
io . put_string ( it.item.item_1 + " occurs " )
io . put_integer ( counts . item ( it.item.item_2 ) )
io . put_string ( " times%N" )
it . forth
end