Maintainer
Tower Technology Corporation
Description
The TowerEiffel 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.
Status
Unmaintained. Tower Technology Corporation no longer exists.
Categories
Versions
Links
Details
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
The Quick Tour diagram (below) 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);
Quick Tour of the Data Structures / TEBC
Supported compilers
Licensing
