[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]

Arc de Triomphe clipart (2486 bytes)

TowerEiffel Booch Components


Written by Tower Technology Corporation.

tbooch.zip (400,811 bytes)


Quick Links:


Overview

The Eiffel Booch Components provide support for a wide variety of common container classes as well as powerful tools for interacting with these containers and their contents.

The TowerEiffel Booch Components are carefully designed classes that provide a complete collection of efficient and adaptable domain-independent data structures and algorithms. This class library was designed with several goals in mind:

Completeness
The library provides classes for many of the basic data structures and algorithms required in the production of quality software. Additionally, for each kind of structure, the library provides a family of classes, united by a shared interface but each employing a different representation, so that developers can select the ones with the time and space characteristics most appropriate to their application.
Adaptability
The library works on all platforms supported by TowerEiffel. Most classes and features will work (possibly after minor adjustments) with Eiffel compilers from competing vendors.
Efficiency
Our goal was to provide easily assembled components (efficient in compilation resources) that impose minimal run time and memory overhead (efficient in execution resources) and that are more reliable than hand-built mechanisms (efficient in developer resources).
Safety
Each class is designed to be type-safe, so that static assumptions about the behavior of a class may be enforced by the compilation system. Also, assertions have been used throughout the library to provide the user with the benefits of Design-By-Contract.
Ease of use
A clear and consistent organization makes it easy to identify and select appropriate forms of each structure and tool.
Extensibility
It is possible for developers to independently add new data structures and algorithms while preserving the architectural integrity of the library.

The TowerEiffel Booch Components represent the combination of Booch's object-oriented analysis and design approach with the ideas and techniques for OO software development introduced by Eiffel, particularly Design-by-Contract.

Having evolved from the Ada and C++ versions which are in use in over 500 organizations in the U.S., Europe, and the Pacific Rim, the TowerEiffel Booch Components are a mature library. The Eiffel version is more than a simple port from C++. Rather, it was carefully redesigned to take advantage of Eiffel's unique features.

This latest version of the components was altered to be more self-consistent as well as consistent with the Eiffel Kernel Libraries that are available from a variety of Eiffel vendors. They are well positioned to be compatible with the forthcoming Eiffel Kernel Library Standard from NICE, the Nonprofit International Consortium for Eiffel.

Class Summaries

Data Structures

Most data structure classes come in at two or three variants (_D: dynamic, _B: bounded, _U: unbounded). Each data structure returns the appropriate type of iterators (and sometimes also cursors) via its iterator and cursor features.

BC_AVL_TREE
A balanced binary tree following the algorithm of Adelson-Velskii and Landis.
BC_AVL_TREE_INORDER_ITERATOR
A iterator which traverses a BC_AVL_TREE in in-order traversal.
BC_AVL_TREE_PREORDER_ITERATOR
An iterator which traverses a BC_AVL_TREE in pre-order traversal.
BC_BAG, BC_BAG_D, BC_BAG_U
Collections of items which, unlike a BC_SET, may contain duplicate items.
BC_BAG_ITERATOR
An iterator which traverses BC_BAGs.
BC_BINARY_TREE
A structurally sharable binary tree.
BC_BINARY_TREE_ITERATOR
An iterator which traverses BC_BINARY_TREEs.
BC_CHARACTER_STRING
A character string that is also a BC_INDEXED (and can therefore be manipulated by the various Booch tools).
BC_DEQUE, BC_DEQUE_B, BC_DEQUE_D, BC_DEQUE_U
Sequences of items in which items may be added and removed from either end of the sequence.
BC_DIRECTED_ARC
An arc in a BC_DIRECTED_GRAPH. Not intended to be manipulated directly by users: use BC_DIRECTED_GRAPH.
BC_DIRECTED_GRAPH
A vertex in a graph with any number of in-bound and and out-bound arcs. Cycles are permitted.
BC_DIRECTED_GRAPH_ITERATOR
An iterator that visits each vertex in a BC_DIRECTED_GRAPH.
BC_DIRECTED_VERTEX
A vertex in a graph with any number of in-bound and and out-bound arcs. Cycles are permitted. Not intended to be manipulated directly by users: use BC_DIRECTED_GRAPH.
BC_DIRECTED_VERTEX_ITERATOR
An iterator that visits each vertex in a BC_DIRECTED_GRAPH.
BC_LIST, BC_LIST_B, BC_LIST_D, BC_LIST_U
Sequences of items.
BC_MAP, BC_MAP_D, BC_MAP_U
Collections of key/value pairs where `=' is used to determine if keys are equivalent.
BC_MAP_ITERATOR
An iterator which traverses BC_MAPs.
BC_MULTIWAY_TREE
A tree where a node may have any number of child nodes.
BC_MULTIWAY_TREE_ITERATOR
An iterator that visits each node in a BC_MULTIWAY_TREE.
BC_ORDERED_LIST
Lists in which items are sorted as they are added (based on the ordering given by a BC_COMPARATOR). Concrete descendents are BC_ORDERED_LIST_B, BC_ORDERED_LIST_D, and BC_ORDERED_LIST_U.
BC_ORDERED_QUEUE
Queues in which items are sorted as they are added (based on the ordering given by a BC_COMPARATOR). Concrete descendents are BC_ORDERED_QUEUE_B, BC_ORDERED_QUEUE_D and BC_ORDERED_QUEUE_U.
BC_QUEUE
Sequences of items in which items may be added to one end and removed from the opposite end of the sequence. Concrete descendent are BC_QUEUE_B, BC_QUEUE_D and BC_QUEUE_U.
BC_RING
Sequences in which items may be added and removed from the top of a circular structure. Since this structure has no beginning or ending, a client can mark one particular item to designate a point of reference in the structure. Concrete descendent are BC_RING_B, BC_RING_D and BC_RING_U.
BC_SET, BC_SET_D, BC_SET_U
Collections of items which, unlike a BC_BAG, may not contain duplicate items. `=' is used to determine if items are equivalent.
BC_SET_ITERATOR
An iterator which traverses BC_SETs.
BC_STACK
Sequences of items in which items may be added and removed from one end. Concrete descendents are BC_STACK_B, BC_STACK_D and BC_STACK_U.
BC_UNDIRECTED_ARC
An arc in a BC_UNDIRECTED_GRAPH. Not intended to be manipulated directly by users: use BC_UNDIRECTED_GRAPH.
BC_UNDIRECTED_GRAPH
A vertex in a graph with any number of arcs. Cycles are permitted.
BC_UNDIRECTED_GRAPH_ITERATOR
An iterator that visits each vertex in a BC_UNDIRECTED_GRAPH.
BC_UNDIRECTED_VERTEX
A vertex in a graph with any number of arcs. Cycles are permitted. Not intended to be manipulated directly by users: use BC_UNDIRECTED_GRAPH.
BC_UNDIRECTED_VERTEX_ITERATOR
An iterator that visits each vertex in a BC_UNDIRECTED_GRAPH.
IE_BAG_D, IE_BAG_U
BC_BAGs which use is_equal to determine whether keys are equivalent.
IE_MAP_D, IE_MAP_U
BC_MAPs which use is_equal to determine whether keys are equivalent.
IE_SET_D, IE_SET_U
BC_SETs which use is_equal to determine whether items are equivalent.

Agents (or Tools)

BC_ANY_EXCEPT
A class of BC_TOKEN which matches any item except those contained in the all_items collection.
BC_BINARY_FINDER
A BC_FINDER that searches a collection using a binary search.
BC_BINARY_INSERTION_SORTER
A BC_SORTER that uses a binary insertion sort.
BC_BM_MATCHER
A BC_PATTERN_MATCHER using the Boyer Moore algorithm.
BC_BUBBLE_SORTER
A BC_SORTER that uses a bubble sort.
BC_EXPRESSION
A regular expression to be used by a BC_EXPRESSION_MATCHER.
BC_EXPRESSION_MATCHER
A pattern matcher that finds `regular expressions' of items (not just character strings).
BC_FILTER
Iterates along a structure and applies a BC_FILTER_PROCESSOR. Filters are different than transformers in that a filter processor can look ahead or back in the collection, while a transformer processor can only examine one item at a time.
BC_FILTER_PROCESSOR
A class which implements the transform process for a BC_FILTER.
BC_FINDER
An abstract tool for finding items in a collection. See BC_SEQUENTIAL_FINDER and BC_BINARY_FINDER.
BC_HEAP_SORTER
A BC_SORTER that uses a heap sort.
BC_LITERAL
The class of BC_TOKENs which match only items equal to those contained in the all_items collection.
BC_PATTERN_MATCHER
An agent that searches other structures for a sequence of items, returning an index into the structure where the pattern is next found.
BC_QUICK_SORTER
A BC_SORTER that uses a quick sort.
BC_REJECTOR
A selective iterator which visits only those items not rejected by its BC_VALIDATOR.
BC_SELECTOR
A selective iterator which visits only those items selected by its BC_VALIDATOR.
BC_SEQUENTIAL_FINDER
A BC_FINDER that searches a collection sequentially.
BC_SHAKER_SORTER
A BC_SORTER that uses a shaker sort.
BC_SHELL_SORTER
A BC_SORTER that uses a shell sort.
BC_SIMPLE_MATCHER
A BC_PATTERN_MATCHER which sequentially steps through the collection looking for a match.
BC_SORTER
A sorting agent that uses a BC_COMPARATOR to sort an indexed collection.
BC_STRAIGHT_INSERTION_SORTER
A BC_SORTER that uses a straight insertion sort.
BC_STRAIGHT_SELECTION_SORTER
A BC_SORTER that uses a straight selection sort.
BC_TRANSFORMER
Iterates along a structure and applies a BC_TRANSFORMER_PROCESSOR. Filters are different than transformers in that a filter processor can look ahead or back in the collection, while a transformer processor can only examine one item at a time.
BC_TRANSFORMER_PROCESSOR
A class which implements the transform process for a BC_TRANSFORMER.
BC_WILDCARD
A class of BC_TOKEN which matches any item.

Support classes

The support classes are low-level classes used to implement the data structures and tools classes:

BC_ABSTRACT_DICTIONARY
An abstract collection of key/value pairs.
BC_ABSTRACT_DICTIONARY_ITERATOR
An iterator for traversing BC_ABSTRACT_DICTIONARYs.
BC_AVL_NODE
Nodes of a BC_AVL_TREE.
BC_BINARY_NODE
Nodes of a BC_BINARY_TREE.
BC_BOUND
A primitive collection with a constant capacity.
BC_COMPARABLE_PAIR
A key/value pair where the key is COMPARABLE.
BC_COMPARATOR
An agent which compares the ordering of two objects (the objects themselves do not need to be COMPARABLE).
BC_COMPARE_BY_COMPARABLE
A BC_COMPARATOR which compares two COMPARABLE's and uses that as the ordering criteria.
BC_CONTAINER
An abstract container.
BC_CURSOR
An iterator which can be moved backwards and forwards and even to arbitrary indexes.
BC_DICTIONARY, BC_DICTIONARY_D, BC_DICTIONARY_U
A collection of key/value pairs. See also BC_BAG, BC_MAP, BC_SET and BC_HASH_TABLE.
BC_DICTIONARY_ITERATOR
An iterator for traversing BC_DICTIONARYs.
BC_DOUBLE_NODE
A node which holds an item and a link to the previous and next node.
BC_DYNAMIC
A primitive collection whose capacity grows in chunks.
BC_EQUALITY_JUDGE
An agent which determines whether two items are `equal'. See BC_JUDGE_BY_IS_EQUAL and BC_JUDGE_BY_REFERENCE.
BC_HASH_TABLE, BC_HASH_TABLE_D, BC_HASH_TABLE_U
A collection of key/value pairs. See BC_DICTIONARY and BC_BAG, BC_MAP and BC_SET.
BC_HASH_TABLE_ITERATOR
An iterator for traversing BC_HASH_TABLEs.
BC_INDEXED
An abstract collection in which items can be accessed by an index.
BC_ITERATED
An abstract collection in which items can be visited by using an iterator. All data structure classes in the TowerEiffel Booch Components inherit from BC_ITERATED.
BC_ITERATOR
An abstract notion of an iterator.
BC_JUDGE_BY_IS_EQUAL
An agent which determines whether two items are equal by using is_equal.
BC_JUDGE_BY_REFERENCE
An agent which determines whether two items are equal by using the `=' operator.
BC_MULTIWAY_NODE
A node in a BC_MULTIWAY_TREE.
BC_NODE
An abstract node which holds an item.
BC_PAIR
A key/value pair.
BC_READER
An abstract tool that can read the contents of the collection it is processing.
BC_TESTER
An abstract base class for implementing test drivers.
BC_TOKEN
An abstract notion of a token (for using in BC_PATTERN_MATCHERs).
BC_TRIPLE
A key/value1/value2 tuple.
BC_UNBOUND
A primitive collection which uses a linked list for each node.
BC_VALIDATOR
An abstract notion of a validator (used for the selective iterators BC_REJECTOR and BC_SELECTOR).
BC_WRITER
An abstract tool that can modify the contents of the collection it is processing.

Data Structure Forms

Nearly every data structure comes in dynamic, unbound and bound forms.

Dynamic
The dynamic form uses a resizable array as the underlying mechanism. Use this form when access to the structure is mostly random and not too much resizing or insertion and deletion into the interior of the structure takes place. When in doubt, use the dynamic form.
Unbound
The unbound form uses a linked list as its underlying mechanism. Unbound data structures are appropriate for structures that do a lot of insertion and deletion other than to the front or back of the structure.
Bound
The bound form uses a fixed-size array for its mechanism. It is almost never appropriate because it has almost the same performance characteristics as Dynamic, but with the dangers of fixed size.

The data structure name indicates which of the forms is utilized. For example, BC_BAG_D is Dynamic, BC_BAG_U is Unbound, and BC_BAG_B is Bound. The deferred class BC_BAG is the common abstract ancestor of these classes. You cannot create instances of BC_BAG. You must choose a concrete descendent.

One of the most powerful aspects of the TowerEiffel Booch Components is that you can create new low-level forms and easily create new versions of the various high-level data structures to utilize your custom form. (Creating your own low-level form requires advanced knowledge of and experience with the TowerEiffel Booch Components, so this is not a good initial project.)

Quick Tour of the Data Structures

Quick Tour of the Data Structures displays the inheritance graph for the Booch Components data structures. All of the classes with a dotted rectangle are generic. The classes marked with a triangle are abstract (i.e. deferred.) Most of these classes have concrete descendents that correspond to the forms discussed in the previous section.

When viewed in terms of inheritance, the data structures of the TowerEiffel Booch Components come in three basic flavors -- simple, iterated and indexed. The simple classes are support classes. Of these, BC_PAIR and BC_CURSOR are the ones that you will probably use the most. The others are used by the data structures classes and you will rarely, if ever, need to use them directly.

The classes that descend from BC_ITERATED are full-fledged container style classes that are used to hold and manage multiple items. All concrete classes that are derived from BC_ITERATED can return an iterator. The class named BC_ABSTRACT_DICTIONARY and its descendents BC_DICTIONARY and BC_HASH_TABLE, are support classes that are used to implement the various versions of BC_BAG, BC_MAP and BC_SET. (We urge you to consider utilizing BC_BAG, BC_MAP and BC_SET in preference to BC_DICTIONARY and BC_HASH_TABLE because they are somewhat simpler to use and much simpler to subclass.)

The classes that descend from BC_INDEXED provide BC_CURSORs which are descendents of BC_ITERATOR that can traverse both backwards and forwards over the elements being contained. BC_CHAR_STRING is a descendent of both BC_INDEXED and class STRING from the Eiffel Kernel cluster. It allows you to treat character strings as collections of characters.

The class BC_CONTAINER is the parent of the three low-level form classes mentioned earlier. (We urge you to utilize BC_RING, BC_STACK, BC_LIST, BC_ORDERED_LIST, BC_QUEUE, BC_ORDERED_QUEUE or BC_DEQUE instead of BC_BOUND, BC_UNBOUND or BC_DYNAMIC.)

There are some high level operations for adding the elements of one iterated data structure to another iterated structure. These operations can save you a lot of effort when you need to transform a group of objects from one form into another. For example, reversing a queue can be done as follows:

my_stack.copy_contents_of(my_queue);
my_queue.copy_contents_of(my_stack);

Licensing

License and Disclaimer Of Warranties for the TowerEiffel Booch Components

Definitions

TEBC
TowerEiffel Booch Components, includes the source code and any compiled or encoded version of the source code.
TOWER
Tower Technology Corporation
USER
Anyone who obtains access to the TowerEiffel Booch Components Source Code and who follows the dictates of this license agreement.

License

Tower hereby grants to any USER: (1) an irrevocable royalty-free, worldwide, non-exclusive license to use, execute, reproduce, display, and distribute copies of the TEBC; and (2) the right to authorize others to do any of the foregoing.

The only limitations to this licence are:

  1. modifications to the TEBC Source Code may not be distributed directly by any party other than Tower; Tower will accept any modifications (including modifications that allow the TEBC to be used with Eiffel compilers other than those from Tower) and apply such modifications that are deemed as acceptable by Tower and an advisory group chosen by Tower that includes registered USERS of the TEBC.
  2. the TEBC source code may not be resold for profit. It may be included with shareware, freeware and Eiffel software collections as long as it is accompanied by this license and the source code entirely matches an officially released version of the TEBC Source Code not more than 4 (four) months older than the most recently released version of the TEBC.
  3. an unmodified copy of this LICENSE AND DISCLAIMER and the attached SUPPORT POLICY must accompany any reproduction and/or redistribution of the TEBC.

Tower requests, but does not require, that USERs who make direct use of the TEBC shall attribute Tower for the use of the TEBC in a manner or manners deemed as appropriate by the USER.

Disclaimer of Warranties

  1. The TowerEiffel Booch Components Source Code is provided "as is" to any USER. USER assumes responsibility for determining the suitability of the TEBC for its use and for results obtained. TOWER makes no warranty that any errors have been eliminated from the TEBC or that they can be eliminated by USER. TOWER shall not be obliged to provide any free support maintenance or other aid to USER or its licensees with respect to the TowerEiffel Booch Components. TOWER shall not be responsible for losses of any kind resulting from use of the TEBC including (without limitation) any liability for business expense, machine downtime, or damages caused to USER or third parties by any deficiency, defect, error, or malfunction.
  2. TOWER DISCLAIMS ALL WARRANTIES, EXPRESSED OR IMPLIED, ARISING OUT OF OR RELATING TO THE TowerEiffel BOOCH COMPONENTS OR ANY USE THEREOF, INCLUDING (WITHOUT LIMITATION) ANY WARRANTY WHATSOEVER AS TO THE FITNESS FOR A PARTICULAR USE OR THE MERCHANTABILITY OF THE TEBC.
  3. In no event shall TOWER be liable to USER or third parties licensed by USER for any indirect, special, incidental, or consequential damages (including lost profits).
  4. TOWER has no knowledge of any conditions that would impair its right to license the TowerEiffel Booch Components. Notwithstanding the foregoing, TOWER does not make any warranties or representations that the TEBC are free of claims by third parties of patent, copyright infringement or the like, nor does TOWER assume any liability in respect of any such infringement of rights of third parties due to USER's operation under this license.

Support Policy

Tower intends to support the TEBC in a professional manner such that they can be employed for projects that require a high degree of reliability. To this end, Tower will appoint an advisory group of volunteer registered TEBC USERS to help oversee the continued evolution of the TEBC. Together with the help of the advisory group, Tower will release periodic updates and extensions to the TEBC.

All TowerEiffel customers should note that support for the TEBC is included implicitly with any maintenance and support contract for TowerEiffel. USERS who do not have current support and maintenance contracts for TowerEiffel can purchase support for the TEBC. Contact Tower for details.

Any USER can register as an official user of the TEBC. This entitles a USER to be considered as a potential volunteer for the TEBC advisory group and/or to receive email messages when updates to the TEBC are posted or released. See the distribution for details of how to register.

If you have additional questions, please contact Tower by Fax or email as shown above or by mail or phone at:

Tower Technology Corporation
1501 W. Koenig Lane
Austin, TX 78756 USA
Tel (512) 452-9455

Additional Notes

If the TowerEiffel Booch Components are delivered as a part of an Eiffel source code framework developed by a USER, then the TEBC can either be embedded in the framework (in the same manner that the TEBC are distributed along with the TowerEiffel clusters) whereupon this file must appear in the top-level directory of the distribution, or else the TEBC it can be distributed as a completely separate distribution in the exact same manner that Tower makes the TEBC available as a separate ftp-able distribution on the Tower web-site. Tower's policy to control modifications is aimed at preventing version confusion as might occur if distribution rights were entirely unencumbered (which they are not.) This policy also prevents third parties from making incidental changes and then claiming ownership of the sources which is also not allowed.

Tower intends to support the use of the TEBC for as many Eiffel compilers as possible and certainly for all current and planned versions of TowerEiffel. This process will be driven by the needs of the Eiffel community as expressed by the volunteer advisory group, so we invite USERS to get involved and help steer this process.

The TowerEiffel Booch Components were originally developed by Tower Technology Corporation with the permission of Rational Software Corporation and Grady Booch of Wizard Software. Tower owns all rights to the TowerEiffel Booch Components except for:

Translation of this code to another language without the permission of Rational Software Corporation and Wizard Software is not allowed. In particular, Rouge Wave Software owns the rights to the C++ Booch Components and a rewrite of the TowerEiffel Booch Components in C++ is not permitted.


[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]