[ 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 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.
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.
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);
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 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:
- 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 ]