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

## TowerEiffel Booch Components |

Written by Tower Technology Corporation.

- 10 December 1996.
- TowerEiffel 2.x.
- Copyright freeware.

tbooch.zip (400,811 bytes)

Quick Links:

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 *Tower**Eiffel* 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
*Tower**Eiffel*. 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 *Tower**Eiffel* 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 *Tower**Eiffel* 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.

**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
*Tower**Eiffel*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.

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 *Tower**Eiffel*
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 *Tower**Eiffel* 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 *Tower**Eiffel* 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);

*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:

- 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.
- 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.
- 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**

- 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.
- 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.
- 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).
- 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 Corporation1501 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:

- the general design of the Booch Components which belongs to Grady Booch and Wizard Software;
- the name "Booch Components" belongs to Rational Software Corporation and Grady Booch of Wizard Software.

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 ]