This work was motivated by the similarity between many grouping and sequence problems we have encountered so far. The ADE classes were designed around this experience base to facilitate rapid application development and provide for easy maintainability and modification. In addition to having built-in constraint manipulation techniques and complex data structure navigation, the ADE class library allows user interfaces to be developed which will automatically adapt to additions, removals, and changes in the physical data attributes of the objects used in implementing the algorithms without any recompilation of the interfaces.
At its primary level, the ADE consists of a set of classes designed specifically for forming the foundation of large, industrial strength applications in which high performance search techniques and constraint manipulation are required. They provide the developer with the primitive operations necessary to implement many of the common requirements which we have found to be shared across large scheduling and planning problems such as: sequencing, grouping, navigation and constraint enforcement. In addition to this, all base classes and classes derived from them are persistent. This allows other applications, like graphical user interfaces, the ability to recreate an exact memory image of the application during any stage of its execution.
A developer utilizes the base classes of the library by deriving their own application specific classes from them. This is done by utilizing the ADE object specification language to describe all object names and attributes along with problem constraints. These scripts are then given to the ADE class code generator which generates proper C++ header and source files for implementing the objects that the developer described, along with additional classes for navigation of those specified objects. The code generator also creates source code for each constraint specified. These constraints will be compiled and linked into a shared library which will be dynamically loaded by the ADE library to perform constraint checking. This allows the developer to add, delete or modify constraint code without recompiling any of the application code. Finally, any non-ADE solution specific code, such as heuristics, is compiled and linked with the ADE generated library to create an executable.
This scheme allows for quick development and modification because the object specification language is very easy to understand and most changes can be seen merely by recompiling changed code and re-running the application. The end user can even alter constraint code after all development is finished and the system is installed. Also, the classes generated by the ADE are fully functional C++ classes that the developers can use as they would any class.
Once the solution application is developed, we can use the ADE browser to look at particular ADE objects. This is done by writing the objects out at some point during the execution of the solution application and then reading them in with the browser. The browser doesn't simply read in the object data, though. It actually instantiates the particular objects through a method we call dynamic construction. The newly instantiated object then reads its own information back in from the file created by the solution application. So all static class data along with member functions for the object is available to the browser and whenever the ADE object's attributes are changed, by modifying the object specification file for example, the browser will automatically know about them and be able to display them without any recoding or recompilation.
By using the browser, end users are able to view object attributes, types and descriptions. If the object is derived from a container type base class, (AdeSet, AdeSequence, AdeGroupManager), then all contained objects can be displayed. The user has the ability to alter what information is to be displayed for a particular object type and can define tables and graphs to better view the data. These modifications are saved in an options file which can be unique to every user.
The ability to alter the actual display of the browser and to define tables and graphs allows the developer quickly create a usable interface to the problem application's solutions. It also permits the end user to browse multiple object databases from entirely different solution applications during the same session.
In the same way that the ADE browser re-instantiates the objects of a problem, the developer can write any program to process the ADE object database file and use the objects. Any application for this might be an interface to the main plant database and/or computer control systems.
The ADE consists of a project editor, a code generator, and a generic GUI. The developer uses the project editor to define the objects and constraints in the application. The code generator translates this input into C++ classes. The generated code is linked with additional developer code. The solutions generated are in a form usable by the generic GUI.
Many of the objects defined in the ADE are of the type AdeObject. This is a C++ abstract base class that defines several pure virtual functions, specifically those required for runtime attribute information, persistence, and relational operators.
An object has some subset of its attributes that contribute to comparing its goodness to another object of the same type. Each attribute, in turn has a non-negative weight associated with it. We can arrange the attributes into an attribute vector and the weights into a weight vector. Given these two vectors, we can define several distinct comparison methods
Just having one relational operator, operator<()
defined is sufficient to determine whether an object is better than,
worse than, or is as good as another.
A < B is A < B
A > B is B < A
A == B is !( (A < B) || (B < A) )
In the examples that follow, assume that there are three objects, A, B, and C. The weights and the attribute vectors are
weights = [3 1 0 2] A = [ 2 1 7 2 ] B = [ 3 1 -1 4 ] C = [ 3 0 5 2 ]
To compare two objects using the single comparison method, we first form the inner product (called the score of the attribute vector and the weight vector for each element. Hence, for the single comparison method, each of the elements in the attribute vector must either be an arithmetic type or automatically convertible to an arithmetic type. The comparison between the two object is then just a comparison of these two scalar values.
score A = 11 score B = 18 score C = 11 A < B true A < C false B < A false B < C false C < A false C < B true
A priority comparison uses an evaluation order that depends on the weight vector. An attribute with a non-zero weight is enabled, and indicates the importance of the element. Comparisons are made in order of decreasing importance, the most important enabled attribute being compared first.
the evaluation order is [ 1 4 2 ] A < B true (2 < 3; stop) A < C true (2 < 3; stop) B < A false (3 < 2; stop) B < C false (3 < 3; 4 < 2; stop) C < A false (3 < 2; stop) C < B true (3 < 3; 2 < 4; stop)
Multiple comparisons are based on dominance. An object is better than another if it dominates the other object. An object is as good as another it neither dominates nor is dominated by the other object.
For an object to dominate another object, at least one of its attributes must be better than the corresponding attribute of the other attribute, and none of its attributes can be worse than the corresponding attribute of the other object. Thus, an object can have some set of attributes that are better than the corresponding attributes of another object, but if one attribute is worse, than neither object dominates the other.
A multiple comparison uses an enabled vector. A non-zero element in the enabled vector indicates that the attribute is considered in determining dominance.
the enabled vector is [1 1 0 1 ] B dominates A B dominates C A does not dominate C C does not dominate A A < B true B < A false A < C false C < A false B < C false C < B true
The possible comparison methods for an object are determined at compile time, and the particular comparison method from the set of enabled methods can be set at run time.
Base elements are the lowest level sequenceable elements. The developer, using the application development environment user interface, or by editing an ADE object specification file using a text editor, defines the properties of the base elements. The code generator uses this definition to generate appropriate C++ code for the class.
The characteristics and boundaries of groups of base elements are defined by group elements. Like the base elements, the group elements can have developer-defined attributes.
A group is usually built by specifying the group identifier and two base elements that define the endpoints of the group. A base element is said to be in the scope of a group if bit corresponding to the group is set in the base element's flags.
In addition to the standard behaviour of all ADE objects, groups have the following additional member functions
scopeElement and unScopeElement
reverse reverses the sense of the group I don't
know what this might be used for
cardinality returns the number of base elements in scope
idValue returns the group identifier
getType() returns "AdeGroup"
Note 1: Since an base element can be out of scope of
a group, it is the responsibility of the developer to check that a
particular element is actually in the group when, for example,
determining and setting properties about the group in the
selfEvaluate function.
Note 2: Forcing a base element out of scope has no effect on iterators currently pointing to the group. That is, whether an element is in scope of a group is only checked when an iterator moves.
In grouping and sequencing applications, inefficiency may result when there are several levels of grouping and it is necessary to operate simultaneously at different levels.
Unfortunately, standard collection classes (like the flat collections in the IBM class library or in Rogue Wave) make it difficult to do this easily. Sometimes sequences have to be unrolled from their groups in order to operate on them which is very expensive.
Consider the following multiply-grouped sequence
In this example there are 14 base elements. There are three possible groupings. The first grouping has three groups, the second has three also, and the third grouping has four groups. In the first group of the first grouping, we see that element 4 is ignored. The same is true of element 10 in the second group of the first grouping, elements 6 and 7 in the second group of the third grouping, and element 14 in the last group of the third grouping.
With standard collection classes that force one to implement strict hierarchies of elements, even though elements 5 and 6 are adjacent, there is no way to get to 6 from 5 except by going out to the containing and then getting the first element. When we are at 5 there can be no nextElement method that returns 6 because it is isolated by the hierarchical organization. There are some algorithms that require frequent jumps between groups like this.
Instead, it is arguably better to represent this hierarchical structure as a completely flat structure that somehow maintains the grouping information and is not confined by the notion of a strict hierarchy.
Since one of the primary operations on the sequences is sequential traversal (both forward and backward directions) the sequences of the should probably be some form of linked lists of elements.
Another frequent operation is destructive concatenation, in which two sequences are concatenated to form a third and the component sequences no longer exist.
In most collection class libraries, there is no notion of destructive concatenation, so to concatenate a sequence all elements must be copied and the component sequences destroyed, which is more expensive than it has to be.
Iterators are modeled loosely after the GNU C++ pseudo-index. An iterator for a sequence can iterate over any one of its groups or over its base elements. An iterator over a group only iterates over its base elements.
The setToFirst() and setToLast() members set the iterator to the first
and last element in the sequence, respectively. The next() and
previous() members set the iterator to the next and previous members,
respectively. The operators operator++() and operator--() overload
next() and previous(). When used as an boolean value, an iterator
returns true if the iterator is valid, and false
otherwise. The dereferencing operators return the object that the
iterator is currently pointing to.
An iterator group is a collection of related iterators that all move in lock-step. It is created with a specification of forward or backward traversal of the list. For example, if the sequence is undirected and the iterator group i is created in the backward direction, then gi = i.group1(); gi.first() will actually return the last group of the list and gi++ moves backward through the groups in the list
An iterator group simultaneously points to multiple groups. Because all iterators in an iterator groups move in lockstep there is no need for a function that returns the containing group for a base element or a the group with a common base element for a particular group.
The following example shows the initial situation of the iterator group for the example sequence.
If we increment the cursor for the base element element twice, it now points to element 3. The other iterators have not changed because we haven't changed groups in any grouping.
If we increment the cursor for the base element to element 4, we notice two things. First, the iterator for the second grouping becomes invalid, because element 4 was marked as ignored for the second group. Also, the iterator for the third grouping has changed from the first group in the grouping to the second.
Incrementing the base element iterator again to element 5 makes the iterator for the second grouping valid again.
Incrementing the base element iterator to element 6 forces a change of group in grouping 1, and invalidates the iterator for grouping 3 because element 6 is ignored for grouping 3.
Each object known to the ADE has to have an evaluator defined, although an evaluator might not do anything in particular. For a group object, the evaluator is called whenever there is a change to its contained base elements (an insertion or deletion for example) or when there is a concatenation of two sequences that results in some group element being merged. Additionally, evaluators can be invoked to update the state of an object that depends on global data.
In addition to sequences, set are required in grouping and sequencing applications to represent solutions. An AdeSet manages a collection of pointers to ADE objects. Its behavior is different depending on its state which is set when the object is created. The state consists of a bound and flags.
The bound indicates the maximum number of elements that can be contained. The bound defaults to zero indicating that the set is unbounded. Otherwise, the set is restricted to contain no more than bound elements, although it may contain as few as one element.
The first set of flags determine the memory management characteristics
If CloneOnAdd is set, the AdeObject is cloned and the pointer to
the clone is added to the set. Otherwise, the actual pointer is added
to the set. If CloneOnCopy is set, when the set is copied, each
individual object is cloned. Otherwise only the pointers to the
objects are copied. If DeleteOnDestroy is set, the set calls
delete on the objects when the set is destroyed.
The second set of flags relates to the relational behavior of the elements in the set.
If DoComparisons is enabled, the elements are compared for uniqueness. Otherwise no comparisons are done to ensure that the set is unique. If the NonDominated flag is set, the set tries to maintain a non-dominated set of elements. Otherwise, the set maintains the best elements.
The last flag, EvaluateOnAdd, determines whether the set invokes its self-evaluation function after an object has been added.
The current EBBSolution class specifies a behavior of a set of sequences of elements but it does not specify the implementation of the set, the sequences, or the elements.
The EbbAdeSolution is a template class inherited from the EbbSolution class. The template takes an AdeObject representing the link, an AdeSet representing the solution, an AdeSequence representing the sequences that make up the set, and an AdeIterator that iterates over the sequences.
The developer only needs to generate the initial solution (typically by adding singleton sequences to the set), enable the appropriate constraints, and invoke the search. A set of solutions will be returned. These solutions can be written to disk using the persistent object methods and then viewed with the browser.
The following diagram is an overview of how one might use the ADE for development of a grouping and sequencing application.
Assume that we have a set of elements, each of which has a non-zero length less than some fixed maximum length, and an identifier.
There exists a precedence constraint between any two elements, such
that a positive cost cost(a,b) is incurred when element
a follows item b. This cost can be infinite,
indicating that item a cannot follow item b
in a feasible solution.
The path cost of a sequence of elements is the sum of the cost between all adjacent pairs of the elements in the sequence. By this definition, the path cost of a one-element sequence is zero. The length of a sequence is the sum of the lengths of the elements.
Assume further that we have unlimited number of bins, each of which has the same fixed capacity. Our primary goal is to sequence the items into as few bins as possible. The secondary goal is to minimize the sum of the path costs of all sequenced bins.
This problem lends itself well to the grouping/sequencing abstraction. More...
To implement an application that solves this problem we make use of the ADE and the ADE to EBB Search bridge.
The base element has a length and identifier, both of which are
integer valued quantities. We define an AdeBase object
called (arbitrarily but appropriately) CbpElement.
There is only grouping in this application, the bin. We define a
AdeGroup called CbpBin
to represent the bin.
The bin only has one attribute, the length which is an
integer value. An auxilliary function, getUtilization is
provided as a convenience function to calculate the length of the bin
compared to the capacity of the bin.
The bin's evaluator determines the bin attributes. This code goes
through the base elements and sums the length and sets the
corresponding component in the length attribute.
Note that we don't define the cost of the sequence here because cost is a direction-dependent quantity in this problem and groupings are directionless. It is only the underlying sequence that has any sense of direction. Hence, the cost is calculated as a member of the sequence.
Since we are using the EBB search to generate solutions for this
problem, we must define an object that represents the "goodness" of
linking two yet unlinked sequences. In this case, the link is called
CbpLink and has a sole
attribute, the cost between the last element in the first sequence and
the first element in the second sequence.
Because links need to be compared, we must enable some comparison
protocols for the object. In this case we enable the
multiple and priority
protocols. Additionally, we have to indicate that the cost is a
comparable attribute. The cost is given negative polarity because we
consider higher costs to be "worse". Finally, if we do choose to
compare links with a weighted or priority comparison method, we assign
the arbitrary weight of one to the attribute. Had there been more
attributes, we could have assigned different weights to the different
attributes, thus giving them different importance in the comparison.
The globals are managed by a plain ADE object called CbpGlobals. By including the
header file CbpGlobals.h generated by the code generator,
these globals are made visible. The global parameters can be
conveniently initialized from a parameters files since all static
attributes can be read set using the readStatic function.
The sequence CbpSequence pulls together
all of the other pieces -- the link CbpLink, the base
element CbpElement, and the group CbpBin.
Sequences cannot have any member data, but they may have any number
of member functions and constraints. In this case, there are two
functions, getCost and getIdentifier. The
former sums the costs between adjacent elements and returns the
value. The latter simply returns the identifier of the first element,
which, in this formulation, has a one to one corresondence with and
uniquely identifies the sequence.
The constraints are represented and managed by an
AdeSeqenceConstraintManager object called CbpConstraint.
Each constraint checking code fragment for the base element has a unique name within the object specification file and it receives two iterators. The iterators are initialized and passed to the constraint, saving the developer some effort and reducing opportunities for creating bugs.
The code is wrapped to look like the appropriate function (passing in the two iterators with a name that is determined from the name of the constraint) stored in a file name that the developer selects, and compiled.
The first constraint, costCheck, pulls the
identity from the last element of the first sequence and
from the first element of the second sequence. It uses the cost matrix
in CbpGlobals to determine the cost and sets this into
the cost element of the link merit.
The second constraint, lengthCheck, pulls the
length from each sequence and determines whether the sum
of the length exceeds the global value BinCapacity.
In this formulation, a solution is simply a set of
CbpSequence objects. We declare the AdeSet
representing the solution, giving it the name CbpSolution.
Since the EBB search needs to make comparisons between solutions,
as with the link, we must enable comparison protocols for the
CbpSolution object. The attribute that serves as the sole
component of the comparison is the pathCost. The path
cost is set by the evaluator by summing the individual path cost of
each CbpSequence in the set. Again, the cost has
a negative polarity.
Two additional member functions are required by the EBB search,
tryToFix and isGoodEnough.
The main application starts all the pieces working together. It consists of configuring the initial solution (a set of elements, each of which is a sequence) and invoking the search.
To initialize the solution we need to generate the cost matrix and
the random quantity for each of the elements and place
them into the set of sequences of elements.
Any non-trivial makefile is always a bit mysterious. A makefile is generated for doing much of the work but a top-level makefile still needs to be written to link in any developer-defined code. The makefile given for this example could serve as a boilerplate example for other applications because they all tend to look fairly similar.
Luckily, all the work is done in the makefile. The developer needs
only to invoke it with make.
The resulting application is named cbp. The parameters
are set in the configuration file cbp.config in which one has control over
all the attributs in the CbpGlobals object.
When the code has finished running, an ADE persistent database file
called cbp_objectdump is created.
Invoke the browser by entering ade-browser and then
use the file dialog to load the persistent database file
cbp_objectdump.
The developer can define an arbitrary number of object code modules that implement constraint checks. Constraints optionally modify the state of an object passed by reference to the constraint, and return a boolean value indicating whether or not the constraint was satisfied.
The constraint code is dynamically linked so that only tiny pieces of code need to be recompiled, and without even relinking the application, the changes will be reflected. Dynamic linking also facilitates enabling and disabling of constraints.
Currently, constraints can be defined for both sets and sequences.
For a sequence, a constraint takes two iterator groups and an ADE
object as arguments. The constraint determines whether the sequence
represented by the first iterator group can be concatenated with the
sequence represented by the second iterator group to form a new
sequence. If the constraint is satisfied the constraint function
returns true, otherwise is returns false. If
the constraint is satisfied, the constraint function can optionally
modify attributes of the ADE object that was passed as the third
argument to give a more quantitative indication of the nature of the
constraint satisfaction.
For a set, a constraint takes an AdeSet, and two ADE
objects as arguments. The constraint determines whether the ADE object
specified as the second argument can be added to the set specified in
the first argument. If the constraint is satisfied the constraint
function returns true, otherwise is returns
false. Again, as in the case of sequence constraints, if
the constraint is satisfied, the constraint function can optionally
modify attributes of the ADE object that was passed as the third
argument to give a more quantitative indication of the nature of the
constraint satisfaction.
One important high level component of the ADE should be convolutional constraints for sequences. To implement general convolutional constraints requires requires some sort of structured language that operates over sequences and groups.
Given a sequence of elements, A, a general convolutional constraint over A consists of
The extent function and constraint constraint function C++ code fragments. The steps size is the name of the base element or a group.
There may be performance problems with this approach but we gain a lot by again concentrating the information in a small number of functions.
The regular structure of the ADE sequences and sets and rich information available from all ADE objects allows a fairly generic user interface that provides an intuitive way of browsing all the information about the objects in a grouping and sequencing application.
The GUI reads an ADE persistent object database which can contain any number of ADE objects. Depending on the type of the object (AdeObject, AdeSequence, or AdeSet) the format of the display is different.
The browser is invoked by simplifying issuing the
ade-browser command. From the browser, the database of
interest can be selected from menus. The browser is currently capable
of displaying sets, sequences, and plain objects.
Once the database has been selected an loaded, the browser displays the object contained in the database and their type.
Double clicking on an object name brings up more detail. A set of objects is represented by a set of buttons on a canvas. In this example, the set of solutions contained one element which itself it a set.
Double clicking on a set element shows more detail about the contents of the set. This solution was found to contain several sequences.
In this example, double clicking on the set element reveals the sequence details. The base elements of the sequence are represented by squares that run along the bottom of the window. Successive groups are indicated by rectangles. A rectangle which spans the same horizontal distances as a set of squares is a metaphor for a group that contains a range of base elements.
Double clicking on a group or base element button reveals information about the base or the group. In this case, we show information about a base element.
We can define graphs that display characteristics of sequences. Both line graphs and bar graphs can be configured.
The data contained in the graph is selectable from menus of the sequence, group, and base element attributes.
An example of a bar graph showing the weight of the base elements in the constrained bin packing example is shown below.
An object specification file is a method for generating C++ classes. The files are not intended to replace the need for writing C++, but rather to simplify and complement it. As such, the object specification file is not as general as C++ but allows some access to C++ constructs.
Arguably, some of the constructs in the ADE should really become language extensions, specifically, the run-time attribute inquiries and persistent objects. However, this effort is out of the scope of this project.
The syntax of object specification files is relatively straightforward. One object can be defined per specification file. Each object can have several attributes. An attribute may be either a function or a variable, and either static or automatic.
If a variable is declared with the name foo, the only
way to access it is via the generated const and non-const functions
getFoo() and the (non-const) function
setFoo(). A variable may be another ADE object. If the
variable is declared static, then there will be one instance that is
shared between all members of the class. In this case, the access is
still limited to the accessor and mutator functions but there is no
const version of getFoo(). All attributes not marked
as invisible are available to the browser.
A function can be any valid C++ function definition. They can be const or non-const, static or automatic. The functions have the same level of access as normal C++ member functions. Note, however, that only const functions that take no arguments are available to the browser.
Standard C/C++ comments are allowed anywhere in the object
specification file. Standard C/C++ #include directives
are also supported. They may anywhere before the declaration of the
object.
The syntax rules are given below.
object-specification-file:
include
comment
object-declaration
include:
#include<file-name>
#include"file-name"
file-name:
standard UNIX file naming rulesobject-declaration:
AdeObjectidentifier object-property-list { attribute-block }
AdeBaseidentifier object-property-list { attribute-block }
AdeGroupidentifier [identifier] object-property-list { attribute-block }
AdeSetidentifier [identifier] object-property-list { attribute-block }
AdeSequenceidentifier [identifier][identifier-list][identifier][identifier] object-property-list { function-attribute-block }
identifier:
variable name satisfying standard C/C++ naming rules
identifier-list:
identifier
identifier-list , identifier
attribute-block:
empty
attribute attribute-block
function-attribute-block:
empty
function-attribute function-attribute-block
attribute:
data-attribute
function-attribute
object-property:
description
single
multiple
priority
object-property-list:
empty
: object-property
object-property-list , object-property
attribute-property:
description
unit
default-value
default-weight
comparable
invisible
negative
attribute-property-list:
empty
: attribute-property
attribute-property-list , attribute-property
data-attribute:
c++-type name attribute-property-list;
function-attribute:
c++-type name ( arguments ) constness attribute-property-list { function body }
arguments:
standard C++ function argument declaration
constness:
empty
const
string:
standard C++ double-quote delimited character string
description:
descriptionstring;
default-weight:
weightarithmetic-expression
arithmetic-expression:
anything that resolves to a C++ arithmetic value
default-value:
valueexpression
unit:
unitstring
Further description of the keywords
description
The description specifies a character string that is associated with the object or attribute. It is intended for providing information which can be used by the generic GUI.
comparable
If an attribute is comparable, its weight and its value will be considered by all comparison methods.
negative
This polarity keyword indicates that smaller values of this attribute are better. Attributes are positive by default (larger values of the attribute are better) unless specified as negative.
single
This comparison method keyword indicates that the object is enabled for single comparisons. A single comparison uses the inner product of an object's comparable attributes and their weights as basis of comparison between two objects.
multiple
This comparison method keyword indicates that the object is enabled for multiple comparisons. A multiple comparison uses the object's comparable attributes to determine whether one object dominates another. A non-zero weight on an attribute indicates that the attribute is considered in the dominance determination.
priority
This comparison method keyword indicates that the object is enabled for priority comparisons. A priority comparison uses the inner product of an object's comparable attributes and their weights as basis of comparison between two objects.
value
If the attribute is intrinsic, it can have a default value.
weight
If the attribute is comparable, it can have a default weight.
unit
The unit specifies a character string that is associated with the attribute. It is intended for use with the generic GUI.
invisible
If the attribute is invisible, then it is assumed that either an
operator<<() is not defined or that it is impossible or
undesirable to display the attribute. Attributes are displayable
by default unless they are function attributes that either take
arguments, are non-const, or both.
#include
Pull source code into the generated files.
There are several restrictions to the function and data members that are managed by the ADE:
class, struct, union, typedef,
friend, public, private, protected, template, and virtual
are not supported
Because the ADE is strongly dependent on object persistence, each attribute must itself be an object that is either a base type or a derived type that minimally knows how to read and write itself.
Hence, instead of a pointer, one will often find oneself using a reference counted AdeObject.
The code generator operates on an object specification file to generate C++ source code which can be compiled and linked with the ADE libraries, the EBB search libraries, and developer code, to form an application.
The code generator usage is
ade-parser [options] filename
where the options are
-d debug mode -M generate dependencies -v show version information
For any ADE object named Abc123, the following
files are generated
Abc123.h
#include directives are copied into this file.
Depending on the object declaration, a class is generated that
derives from either AdeObject, AdeBase, AdeGroup, AdeSequence,
or AdeSet. In this class are declarations for
Abc123.C
Abc123.h.
Abc123DynCtor.C
Abc123DynCtor.make
Abc123, the dynamic
constructor DLL is called Abc123DynCtor.dll.
For an AdeSequenceConstraint or AdeSetConstraint object
named Abc123, the following file is generated
Abc123.C
For an AdeBase or AdeGroup object named Abc123,
the following files are also generated
Abc123-adegen.C
Abc123-adegen.h
For an AdeSequence object named Abc123, the
following additional files are generated
Abc123iterg-adegen.h
Abc123iterg-adegen.C
Abc123.make
A sequence of base elements such may be divided into n
groups of type k, where k is a level of
grouping. If j is the maximum number of groupings, then 1
<= k <= j.
An AdeIterator is constructed from two endpoints.
Given an iterator, one can use operator++() and
operator--() to walk up and down a chain of base elements
or groups.
This approach is fine for a single grouping, but when using iterators for multiple groupings simultaneously, there must be a mechanism for automatically incrementing and decrementing the iterator of a certain grouping when the movement of an iterator of another grouping goes over a boundary.
To implement this, we took the following approach: a group is nothing more than an iterator over a specified subsequence of base elements. Since iterators have a direction we do not need to be concerned about direction while traversing the sequence because it will be taken care of automatically. But we do need to worry about the base elements that fall on group boundaries because the movement of a high level group iterator may create a situation in which the new current base element has skipped over the boundaries of other containing groups. If this occurs, then the only way to properly restore the other containing groups' iterators is to have the new base element be able to say what contains it. So each boundary element has a vector of pointers to all of its containing groups. We call the process of resolving group pointers forward-patching and back-patching. For example
The base elements are {0,1,2,3,4,5}. The inner grouping has two groups, { a = {0,1,2}, b = {3,4,5} }. The outer grouping also has two groups, { A = {0,1,2,3}, B = {4,5} }. Each of the boundary base elements, namely {0,2,3,4,5} would have a vector of pointers to their containing groups. In this case, the first component of the vector would be a pointer to the inner grouping object (either a or b) and the second component would be pointer to the outer grouping object (either A or B).
The base elements that fall on the boundary of group A are 0 and 3. and both of these elements have a pointer to group A. Similarly, elements 4 and 5 have pointers to B, 0 and 2 have pointers to a, and 3 and 5 have pointers to b. These pointers were identified by forward patching.
To fill in the remaining components of the vector, element 2 points to A, and element 4 points to b. These pointers were obtained by back-patching because in each case, the element does not fall on the boundary of the group to which it points.
When a group level iterator is moved, we can adjust all other iterators within the group just by looking at the new base element and setting them. Each base element has a vector of grouping pointers. If the element is not a boundary element, then this vector is NULL, else this vector should have an entry for each grouping level.
When a new group is defined over a sequence, the two boundary elements of the group can have the entry in their group vector updated immediately (forward-patched) for the new group. However, it may be the case that by defining this new group we have split another grouping. In this case we will need to patch the non-overlapping boundary elements (back-patch) with the appropriate group pointers. Because it can't be done immediately, so we'll take care of it later.
The actual time when all back-patching is performed is when the an
iterator is moved to a boundary element whose group vector is only
partially full. At that time the AdeSequence will search
for the proper groupings to fill in the vector. This has the advantage
of not back-patching elements that the developer might not be
concerned about. Also, once an element in a sequence is back patched,
it won't need to be back-patched again.
Upon deletion of a boundary element from a sequence, all information contained within its group vector is copied to its adjacent element within the same group.
We define two abstract base classes, namely, AdeBase
and AdeGroup.
Solution-specific base element and groups are derived from these two classes. There can only be one base element class defined in a sequence. There can, however, be up to 255 distinct groupings. These base classes only provide a mechanism for chaining like objects together. This mechanism is invisible to derived classes and does not need to concern the developer.
The classes that are derived from AdeBase and
AdeGroup can have any number of methods and variables
that the developer wishes. They should also contain appropriate
construction and destruction methods. To avoid the complexity of
defining the classes by hand, it is recommended that the developer
uses the object specification language.
Here is an example of using the AdeBase and
AdeGroup classes.
class Element : public AdeBase
{
Element ( int a1, int a2 ) : attribute1(a1), attribute2(a2) {};
int attribute1;
int attribute2;
};
class Group1 : public AdeGroup
{
Group1 ( AdeBase *ep1, AdeBase *ep2 ) : AdeGroup(ep1,ep2) {};
float attribute1;
int attribute2;
};
class Group2 : public AdeGroup
{
Group2 ( BaseElement *ep1, BaseElement *ep2 ) : AdeGroup(ep1,ep2) {};
String attribute1;
float attribute2;
};
Groupings are defined by instantiating an object of the proper
group type by passing the constructor the two endpoints of the
group. An element within a group can be removed from the scope of that
group by using the unScopeElement method. Note, however,
that this does not physically remove the element from the group, it
merely tells the group to ignore it. This element can subsequently be
added back into the scope of the group by calling the
scopeElement method. A group must have at least one
element in its scope. If this last element is to be removed from the
group, then the group object needs to be removed from the sequence.
In order to encapsulate the actual base object sequencing for the
developer and also allow for correct iterator initialization and
manipulation, we define an abstract base class called
AdeSequence. This class provides method for adding and
deleting both base elements and groupings to/from the sequence, along
with protected methods for forward- and back-patching. To use the
AdeSequence, one must create a new class called in which methods for
solution-specific groupings of the base elements are defined. Again,
it is recommended that the developer uses the
object specification language and allow
the code generator to handle the complexity of defining the derived
classes.
The developer defines a new group on a sequence by first
instantiating and initializing the appropriate group object then
calling the addGroup method of the sequence. Likewise,
the developer can remove that grouping by calling the
removeGroup method of the sequence. Notice that this
scheme gives the developer a lot of freedom in declaring groups. For
example, the developer may declare two groups at the same level which
are non-disjoint, or the developer may leave gaps in the grouping of a
certain level. The only operation that the sequence object will deny
is defining a group on a boundary element that is already a boundary
element of another grouping at the same level. Therefore, it is
important that the developer ensure that the logic of the grouping
sequences is correct for the particular application.
A sequence can either be directed or undirected. If a sequence is directed, then this means that we can only traverse the base elements and groups in a single set direction. Whenever an iterator group is initialized via a directed sequence, the developer has no control over setting the traversal direction of the group. If a sequence is undirected, then it may be traversed starting from either endpoint. When an iterator group is instantiated via an undirected sequence, then the traversal direction will be set to the mode specified by the developer. The default direction will be forward traversal, meaning the direction in which the sequence was built.
class Sequence : public AdeSequence
{
void addGroup ( Group1 * ); // Add a group1 to sequence
void addGroup ( Group2 * ); // Add a group2 to sequence
void removeGroup ( Group1 * ); // Remove a group2 to sequence
void removeGroup ( Group2 * ); // Remove a group2 to sequence
};
int main ( void )
{
Element e1, e2, e3, e4, e5;
Sequence;
sequence.add ( &e1 );
sequence.add ( &e2 );
sequence.add ( &e3 );
sequence.add ( &e4 );
sequence.add ( &e5 );
sequence.addGroup ( new Group1(&e1, &e3) ); // G1 = {e1,e2,e3}
sequence.addGroup ( new Group1(&e4, &e5) ); // G1 = {e1,e2,e3}, {e4,e5}
sequence.addGroup ( new Group2(&e1, &e5) ); // G2 = {e1,e2,e3,e4,e5}
}
Elements that are appended or prepended to a sequence are set to be
not included within any group's scope. The developer must specifically
add new elements to group scope by calling scopeElement
method or by creating a new grouping which includes the element. An
element cannot be physically removed from a sequence until it has been
properly removed from the scope of all its containing
groups. Groupings may be added and removed from a sequence at any
time.
As described above, iterators are objects that walk up and down a
chain of base elements. Iterators may be moved by using pre and post
increment/decrement operators. The actual object being iterated over
can be dereferenced by operator*() and the data within the objects can
be manipulated by using operator->().
The abstract base class for iterators is called AdeIterator. This base class has an associated direction (forward or backward) which is set upon instantiation and dictates which way the iterator will move along the chain. There is also a boolean operator to test if an iterator is valid. An iterator becomes invalid when it has reached the final element in the chain along the direction which it has been moved. An iterator also becomes invalid if the current element is set to be ignored by the iterator. This happens, for example, when an element is removed from the scope of a group. In this case, however, the iterator is still able to be incremented and decremented. An iterator can be reset at any time back to either of its endpoints by using the setToFirst and setToLast methods.
The ADE will inherit from AdeIterator to define a specific iterator class for each group and base element object that is defined by the developer. These specific iterator classes will know the type of element that they iterate over, along with having a specific copy constructor and assignment operator to those element types.
class ElementIterator : public AdeIterator < Element >
{
ElementIterator ( Element *e1, Element *e2 );
ElementIterator &operator=( ElementIterator *Src );
};
class Group1Iterator : public AdeIterator < Group1 >
{
Group1Iterator ( Group1 *e1, Group1 *e2 );
Group1Iterator &operator=( Group1Iterator *Src );
};
class Group2Iterator : public AdeIterator < Group2 >
{
Group2Iterator ( Group2 *e1, Group2 *e2 );
Group2Iterator &operator=( Group2Iterator *Src );
};
int main ( void )
{
Element e1, e2, e3, e4, e5;
link(e1, e2);
link(e2, e3);
link(e3, e4);
link(e4, e5);
ElementIterator ei( &e1, &e5 );
while (ei) {
cout << "Height :" << ei -> height << endl;
cout << "Width : " << ei -> width << endl;
ei++;
}
}
An iterator group is a set of iterators that work together to iterate over a sequence. The group will consist of an iterator for each level of grouping in the sequence along with an iterator for the base elements of the sequence. The developer may utilize a specific iterator within the group by obtaining a reference to it via the appropriate group method. The iterators within a specific iterator group work together by propagating the movement of one of the iterators to any other iterator within the same group that may be affected by that movement. In other words, all iterators within a group move with respect to one another. Note, however, that multiple objects of the same iterator class will not have an effect on each other.
An iterator group is instantiated by passing the constructor a reference to an AdeSequence and an optional direction. From that point forward all iterator manipulations of that group will be done with respect to the appropriate direction of the group. The ADE will inherit from the abstract base class AdeIteratorGroup class to define a specific IteratorGroup class which will know how to set the iterators correctly with respect to the solution dependent groups.
It is important to note that if the sequence from which an iterator group was instantiated physically changes, then the iterator group will be left in an undefined state and needs to be reinitialized before using it. This can be done by calling the reInitialize method for each active iterator group.
class IteratorGroup : public AdeIteratorGroup
{
ElementIterator Element;
Group1Iterator Group1;
Group2Iterator Group2;
};
int main ( void )
{
IteratorGroup ig ( sequence );
ElementIterator &ei = ig.Element; // *ei = e1
Group1Iterator &g1i = ig.Group1; // *g1i = {e1,e2,e3}
Group2Iterator &g2i = ig.Group2; // *g2i = {e1,e2,e3,e4,e5}
g1i++; // *ei = e4
// *g1i = {e4,e5}
// *g2i = {e1,e2,e3,e4,e5}
ei--; // *ei = e3
// *g1i = {e1,e2,e3}
// *g2i = {e1,e2,e3,e4,e5}
}
An iterator group can also be initialized by passing the constructor a reference to another iterator group along with a group reference. This will have the effect of creating an iterator group which is frozen at the given group level. What this means is that any operation performed on an iterator of this group which moves outside of the current frozen group will invalidate all iterators. As with normal iterator groups, if the sequence should physically change while this iterator group is active, then the entire iterator group will be in an undefined state and will need to be reinitialized.
The class library has been designed to implement the scheme that is described above.
Imagine that we have to write a simple application suite. The application involves an algorithm that generates a few objects and writes them to a file. A graphical user interface application reads from the file and displays the generated objects.
The developer defines the objects, writes the algorithm, and the output function. These files are compiled and linked to form an application.
The application is run to generate an output database containing
several objects of class AppClass. The GUI must be
written to read the objects from the file and then display them.
With the ADE, the initial development of the application that
generates the object is very much simplified. The input and output of
the objects is performed using the built-in persistence (so
writeResults is a one-liner) and there is no
need to write a graphical user interface at all.
The objects are specified using the ADE object specification language which is parsed to generate C++ code which is compiled and linked with the rest of the application.
Now imagine that a change needs to be made such that the objects
generated have an additional property. We would like this property to
also be stored in the file and displayed. Without the ADE, the
following modifications need to be made. We must modify
application.h to add the attribute,
writeResults to output the new information, and any part
of the algorithm that is affected by the new attribute. For the GUI,
both readResults and the code that displays the attribute
must be updated.
With the ADE, however, only a single modification needs to be
made. The application still has to be compiled and linked. Because
persistence is built into the ADE objects, the input and output code
in writeResults is unchanged. And because of the run
time attribute inquiry capability, the objects themselves tell the
browser how to change what it displayed. Finally, any parts of the
algorithm that uses relational operators on objects of type
AppClass are unchanged.
Of course, this is an extremely trivial example but it shows the kind of reduction in development and maintenance time that can be achieved using the ADE.
The ADE is a synthesis of several standard object-oriented programming techniques (persistent objects and the abstract factory design pattern), a few non-standard techniques which arguably should be standard (run-time type and attribute inquiries) and some novel techniques specific to the domain of grouping and sequencing applications (configurable relational operators, smart iterators over multiply grouped sequences, and constraint manipulation).
The ADE is written in C++ and depends on the IBM Collection Class Library and on OSF/Motif. It currently runs only under AIX.
To obtain a copy of the ADE package, please contact us by sending mail to schedule@watson.ibm.com.