Figure
1 Nodes are allocated as multiples of
fundamental display units
Graphs are effective and widely used abstractions for organizing and visualizing information. They are particularly useful in CASE and re-engineering tools for diagramming program structures, logic, and data. However, developing software tools for efficiently generating, displaying, and editing graphs via a user-friendly GUI is not a trivial task.
The goal of this project was to design and implement a generic, portable, and efficient software abstraction for displaying and transforming graphical objects through an easy-to-use window-oriented interface. To accomplish our goals we first designed and implemented a tree editor using a freeware C++ based windows environment called wxWindows. This editor was designed for speed and for conserving layout space on the display. The design contains several innovations to enhance its performance.
The performance of our editor has been found to be superior to similar editors and graph display packages available on the Internet. Additionally, by virtue of our using wxWindows, our editor can run on multiple platforms, such as Windows 3.1, Windows95/NT, and UNIX.
The second goal of our project was to generalize from the experience gained by developing the tree editor and design a more general-purpose editor capable of manipulating arbitrary graph objects. As a first step toward this goal we defined a Graph Editor Specification Language (GESL). GESL has some similarities with parser generators like YACC. Using an interpretive implementation of GESL, a designer can quickly prototype a new graph editor.
Future research and extensions of this work include writing editor specifications for a broad family of graph and diagram types found in computer science and program development applications to mature GESL and then to implement both an interpretive as well as a compiled version of this language.
The results of our current work will be available on a web site along with the source code for our tree editor.
The author wishes to thank Dr. David Workman for all the time and effort given in the preparation of this project. Dr. Workman spent many weekend hours and after business hours working with the author. Additionally, he helped correct and enhance the author's poor grammar on numerous drafts of each chapter.
The author would also like to thank the members of the research committee, Dr. Rebecca Parsons and Dr. Mostafa Bassiouni, for the time they gave to review this project.
Finally, the author would like to thank his wife, Tami, for being patient while he spent many hours on the computer away from her, and for supporting him all the time.
Number Page
Figure 1 Nodes are allocated as multiples of fundamental display units 7Figure 2 Comparison of simple and efficient covering polygon calculation. 8Figure 3 Object diagram of current architecture. 9Figure 4 Hard-coded tool environment. 10Figure 5 Opening screen 10Figure 6 Options available from opening screen 11Figure 7 Initial tree editor window 11Figure 8 Available menus in the tree editor window. 13Figure 9 Sample tree 14Figure 10 Nodes record size and shape of their subtree 15Figure 11 Example of vector values 16Figure 12 Tree traversal algorithm. 19Figure 13 Order in which nodes would be processed by traversal algorithm. 20Figure 14 Sample tree to search. 22Figure 15 Trace of steps followed for tree searching. 23Figure 16 Special symbols and link attributes of GESL. 30Figure 17 Components of GESL. 31Figure 18 Grammar driven tool environment. 32Figure 19 A simple precondition table 43Figure 20 Arc relations of the tree node. 50Figure 21 Size of executable for each platform. 54Figure 22 Time test execution for each platform. 54Figure 23 Sample tree for timing editing operations. 56Figure 24 Object diagram of current architecture. 63
Computer Aided Software Engineering (CASE) tools are intended to help the engineer manage and understand the complexity of large systems. However, one of the most limiting and inhibiting characteristics of current CASE tools is their lack of visual presentation and manipulation of program entities and their relationships. Diagrams that CASE tools should be capable of displaying include:
The popularity of windows-based work environments is largely due to the visual way they allow the user to manipulate programs, thus making them easier to understand.
One particular software development application that has need of visual trees and graphs is a software re-engineering and maintenance tool named REENEW[Wor95]. REENEW (REENgineering Environment and Workbench) is a project being developed by Dr. David Workman at the University of Central Florida in cooperation with Science Applications International Corporation. It is designed to create, analyze, and maintain collections of related software objects. Throughout its development, it has become obvious that REENEW would benefit from a large number of tree and graph diagrams to help the user organize and understand these software objects.
Specifically, REENEW needs to provide its users with control flow diagrams, data structure diagrams, program structure diagrams, and expression tree diagrams. My part in the REENEW project has been to produce a facility for the visual display and manipulation of these graphical structures as part of an X-windows Graphical User Interface (GUI). It became discernible to me that one multi-purpose diagramming tool, that could handle all of these diagrams, and perhaps others, would be much more expedient than writing new code for each type of diagram. Such a tool would have innumerable uses apart from this one application as well. To satisfy the requirements for REENEW, I began searching the Internet for packages that I could integrate directly into the tool environment.
Initially we searched the Internet for other graph and tree drawing widgets to use in REENEW. Each of the packages described below has some restriction or performance limitation, and none of them appear to be as flexible or powerful as we would need for REENEW.
For X-windows, two useful and freely available tree widgets are XmGraph and MTree. Douglas Young wrote MTree and it is relatively small and simple [You94]. Its shortcomings are that it is written exclusively for X-windows (in particular Motif), and more importantly, its algorithm is based on recursion. Recursive algorithms are simple to implement, but can become quite memory and time consuming once the tree becomes very large. Another, more powerful, widget is XmGraph. A team at the Hewlett-Packard Company wrote XmGraph [Mig90]. This widget is also built as a Motif widget. The authors acknowledge that performance really breaks down after 2,000 nodes if the nodes are gadgets, and much sooner if they are widgets. Performance falls even more rapidly if a large number of arcs are used. Two thousand nodes may seem like a large number, but it is quite small for many applications, particularly programs of industrial size.
A more promising program appears to be the ISI Grapher by Gabriel Robins [Rob88]. This program is built to be portable among Common-Lisp platforms; however, the lower level drawing functions must be re-written for every platform. Gabriel Robins claims the ISI Grapher can graph over 2,500 nodes or edges per minute, which he claims is an order of magnitude improvement over other systems, but slower than we would like. The layout algorithm of the ISI Grapher is linear relative to the size of the graph. A more recent discovery is VCG-Visualization of Compiler Graphs by Georg Sander [San94, San95]. This tool is not built to manipulate the graphs in any way except to change the views, but it appears very powerful for drawing graphs. However, our goal is to manipulate the graphs, so this tool was not sufficient either.
The search of the Internet for a graphing library was only marginally
successful. Many GUI libraries have been developed to facilitate
creation of windows environments, and provide some consistency
of their appearance. However, there are no such libraries for
graph GUIs. There are a number of packages available that will
allow the user to create visual graphs (some of which will be
discussed below). However, what is lacking is a general purpose,
robust, efficient widget for displaying and manipulating
diagrams. Due to the lack of any real capability for interactive
editing, we decided to design our own graph GUI library.
The goal of this project is to design and implement a generic, portable, and efficient abstraction for displaying and transforming graphical figures.
To accomplish our goals we first designed a hard-coded tree editor. I wrote the program using C++. I endeavored to give it a good object-oriented design so that its components could be easily subclassed to suit the user's needs. It was designed for speed at the price of memory requirements and contains many innovations to enhance its performance. To make it portable between platforms, I used a portable GUI toolkit called wxWindows.
wxWindows is a platform independent class library for C++ for providing a graphical user interface (GUI). Using this package for the development of this project allows it to run in the MS-Windows, Motif, and Open Look environments. In addition, Macintosh, OS/2, Xt, and even Curses ports are in progress that will give the project a wide usability base. The wxWindows package is being developed at the Artificial Intelligence Applications Institute at the University of Edinburgh by Julian Smart. wxWindows is available by anonymous ftp at ftp.aiai.ed.ac.uk. While the wxWindows package is completely usable in its current state, it is also currently in development, and each new release provides more useful features for this project[Sma95]. It is currently in release 1.66 and generally compiles and installs without any problems.
The design of the tree editor helped us pin down the interactions between nodes in a tree when constructing and editing it. The next step toward fulfilling our goals was to develop a grammatical-style specification language that abstractly defined these interactions. This language is named GESL (Graph Editor Specification Language).
Once GESL had been defined, the final step was to define the grammar rules necessary for tree and graph editing. For any visual graph representation there are two sets of grammar rules that must be defined; these are the graphical layout rules and the internal data structure rules.
The remainder of this paper is divided into two main sections. The first section describes the hard-coded tree editor. It gives an overview of its interface and describes in detail the innovations implemented to enhance performance. The second section describes grammar driven editors. It gives the Graph Editor Specification Language (GESL), and the grammar rules for a tree editor. At the end we will summarize our accomplishments and discuss possible future extensions to this work.
This chapter describes the hard-coded tree editor. The term hard-coded refers to the fact that we coded all the rules for editing the tree in the implementation language (C++). This is in contrast to the grammar driven approach described in chapter 4 where we read the rules for editing as data from a file. The tree editor demonstrates the data models and essential tree operations necessary to edit a graphical tree in an efficient and convenient manner, while conserving the display area consumed by the tree image.
The display and placement of nodes is based on an (x,y) coordinate system where the x axis is the vertical axis, and the y axis refers to the horizontal axis. Our editor lays out a tree with a horizontal orientation. Three rules determine the horizontal orientation. First, a parent node and its first child have the same vertical display origin (i.e., the tops of both nodes start at the same x coordinate). Second, all the children of the same parent have the same horizontal display origin (i.e., the left side of all the children starts at the same y coordinate). Third, images of two subtrees having the same parent do not overlap.
The image of every node in the tree is allocated in terms of one or more fundamental display units (FDUs). A FDU is a rectangle measuring h pixels in the horizontal dimension, and v pixels in the vertical dimension (see Figure 1). If you imagine a grid placed over the display screen, then each square in the grid is one FDU. Therefore, conserving the display area consumed by a given subtree means using the smallest number of FDUs that cover its image.
Figure
1 Nodes are allocated as multiples of
fundamental display unitsA natural way to define the display space allocated to a subtree is to bound the subtree by two horizontal lines, one at the top and one at the bottom of the subtree image. These two lines would define the boundaries for a simple covering polygon which covers all nodes in a subtree with the smallest rectangle of FDUs. The origin of the subtree root node corresponds to the upper-left corner of the rectangle. The lower-right corner of this rectangle is defined by the maximum x and y coordinates used by the subtree. An uncomplicated layout approach would then be to layout the next subtree below the covering polygon of the current subtree (shown in the left side of Figure 2). However, a more space efficient display would be to calculate a covering polygon which more closely approximates the shape of the subtrees. This can be accomplished by constructing the covering polygon from the covering polygons of each node in the subtree. Then calculate if the next subtree's covering polygon can fit inside the space left by the previous subtree's covering polygon and place it there if possible (shown in the right side of Figure 2).
Each node stores the shape of its covering polygon within itself with its origin starting at logical coordinate (0,0). This means subtree A starts at logical (0,0) and subtree B starts at logical (0,0), regardless of the actual (x,y) location. This allows easy manipulation of subtrees since recalculation of coordinate values is not necessary. This principle is important in defining the shape abstraction presented later.
The tree editor architecture is fairly small, and is illustrated in the object diagram in Figure 3. The object diagram uses a simple Rumbaugh notation[Rum91]. As you can see, there are only 14 classes, which are closely related to each other in some way or another.
Figure
3 Object diagram of current architecture.The control flow is a simple hierarchy. As shown in Figure 4, the user gives input to the GUI driver. The GUI manages a tree object that manages access to all of its nodes. The editing actions performed by the user are sent to the tree. The tree passes these actions on to the appropriate nodes. The nodes themselves contain all of the methods required to adjust their own geometry and local data structures according to the actions performed on them. The nodes then send messages to their immediate neighbors to adjust the entire tree.
Figure
4 Hard-coded tool environment.The user interface is very simple. When starting up the program, you are presented with the window in Figure 5. The menu items and toolbar buttons available on the opening screen allow you to open an editor window, get author and version through an information box, or exit the program. Figure 6 illustrates the available menus.
Figure
5 Opening screen
Clicking on the tree icon on the toolbar opens a tree editor window. Selecting the File menu followed by selecting the New option also opens the tree editor window. Figure 7 shows the initial tree editor window and editing toolbar.
Figure
7 Initial tree editor window
The toolbar provides the interface to toggle editing settings for creating new nodes, and pasting cut nodes. These settings are the shape of a new node, and the location a node or subtree should be placed relative to the currently selected node. The available node shapes are a rectangle, a rounded rectangle (corners are rounded off), and an ellipse. The size of the text contained by a node automatically adjusts the size of a node.
There are 5 options for inserting a new node, or pasting a subtree in the edit buffer. All editing operations, such as inserting a new node, are done relative to a selected node. The insertion location options are:
The first 4 are straightforward. The last option simply means that the node should be inserted in order relative to the other children of the selected node. The ordering is lexical based on the node title in the current version, although changing this ordering is quite simple. The ordering is determined by the overloading of the relational operations (<,>,==). These operations are currently defined to sort alphabetically by the node text, but the source code can be modified to sort on any node attribute.
The tree operations are given through 3 menus which are shown in Figure 8. Through the menu operations you can load and save trees; insert, cut, copy, and paste subtrees; and modify the selected node's attributes such as its text and shape. You can also refresh the tree, or recalculate all of the node placements in case the tree somehow becomes corrupted. This operation was added for debugging, but has been left in the interface as a safe-guard. By means of these various operations you can construct a tree such as the one shown in Figure 9. In Figure 9, the root node is currently selected which is indicated by having its shape emphasized. The editing operations (Insert, Cut, Copy, and Paste) are also accessible within the editor window by using the right mouse button.
Figure
9 Sample treeThe advantage of this tree editor over other tree editors we examined is speed when computing the placement of large numbers of nodes. The principal design feature that allows this is that each node knows the size and shape of the subtree below it. For example, in Figure 10, node A stores within itself the shape of the tree it forms (shaded area). Then, when adding or inserting a new node or subtree, such as B or C, the new node or subtree need only check with its upper sibling to determine it's placement. This avoids traversing the entire subtree of A.
Figure
10 Nodes record size and shape of their
subtreeThere are, of course, complications to this. For example, let's assume subtrees A and B are on the tree P, and we are adding subtree C. Node C cannot simply check node B for overlaps since subtree C extends beyond the horizontal extent of subtree B. Therefore, it must also check node A to find if it will cause any overlaps. Node C would not have to check any further than node A however, since subtree A extends horizontally at least as far as subtree C, and node A knows this internally.
The method by which the shape of the subtree is stored is by two vectors, the UpperVector and the LowerVector. Each vector has one element for each FDU (fundamental display unit) the subtree covers in the horizontal dimension. The default size of a FDU is 10 horizontal pixels by 10 vertical pixels. Therefore, if you have a node that is 30 pixels wide then that node (or subtree) is three FDUs wide. When defining its shape in a vector this node will require three vector elements in each vector. The size of the vector, three elements in this example, tells you that the node is three FDUs wide. The values in the vectors define the upper and lower extents of the node, or subtree.
A node's vectors are appended onto its parent's vectors to define its parent's subtree shape. Also included in these vectors is a vector element for each FDU of spacing between the nodes. Therefore, if a parent node is 3 FDUs wide, and its child is 3 FDUs wide, and they are separated by 1 FDU, the parent's vector needs to be at least 7 elements long. Figure 11 gives a sample of what these vectors look like for a simple tree.
Figure
11 Example of vector valuesThe size of the FDU is useful for balancing performance tradeoffs between accuracy, memory size, and calculation speed. The larger the FDU size, the fewer the number of vector elements needed to cover each node. This can save space for vector memory, and calculation time, but the accuracy and display efficiency of a tree layout will suffer as a result. On the other hand, a small FDU size will create very large vectors in memory and take longer to perform calculations, but the tree layout will be very exact, and efficient. This is an important design property to keep in mind.
One of the key abstractions developed to support our display method is the shape algebra. The shape algebra is, for the most part, ordinary vector algebra with a few modifications. The shape algebra is implemented in the Vector class which is given in the Program Reference in Appendix A. The modified or additional operations will be described here. The specific uses of these operations will be described in the Tree Editing section.
The most significant modification to standard vector algebra is that shape vectors of different lengths can be added and subtracted from each other. When performing addition, if the two vectors are of different lengths, the resulting vector is the length of the larger of the two being added. The data elements beyond the length of the smaller vector are simply the values of the larger vector. For example:
This is advantageous for adding together the shapes of two unlike sized subtrees. For subtraction, the resulting vector is the size of the smaller of the two vectors. For example:
The vector class also provides a few other convenient operations. One such operation permits the addition or subtraction of a scalar value to every element in the vector. For example:
This is helpful when dealing with logical offsets from sibling nodes. The remaining operations the shape algebra provides are:
The final two additional operations are the maximum and minimum vector operations. These operations will compare two vectors and return either the maximum or the minimum element at each location. Unequal length vectors can be compared. With unequal lengths, the resulting vector is always the length of the larger vector with the additional elements simply being the values of the larger vector. For example:
This is essential for building the final subtree shape vector as the calculations move down the siblings.
The traversal of a tree for a variety of purposes is accomplished by the algorithm diagrammed in Figure 12. The traversal algorithm is a member method of the node class and traverses the subtree that has the node as its root. It is implemented as an iterator, by which I mean that it takes a node method pointer as one of its parameters and calls that method on each node in the subtree. In this way it becomes a very useful method for a wide variety of tasks such as printing, drawing, or counting the nodes in a subtree.
Figure
12 Tree traversal algorithm.Figure 12 best explains the algorithm operation, but basically it functions as follows:
Figure 13 shows the order in which the traversal algorithm would process each node in a simple tree. Each subtree is fully processed before moving to a lower sibling subtree. Also, the processing of each node occurs the first time a node is encountered on the traversal down, and is bypassed on the traversal back up. For example, the node labeled "2" in Figure 13 is processed before moving to node "3", but is not processed again after node "4" is processed.
Figure
13 Order in which nodes would
be processed by traversal algorithm.The traversal algorithm is only used when every node in the subtree must be processed. For actions such as finding the node that was picked by a mouse click this would be a very slow method, and is therefore not used for such an action. Instead, the search algorithm described below is used.
Due to the fact that each node knows the shape of the subtree beneath it, finding a node when picked by a user can be accomplished very quickly. The process, in fact, is logarithmic in the number of tree nodes. Recall that each node stores two vectors defining the shape of the subtree beneath it, including itself. Also recall that each subtree defines this shape as if its own origin is at (0,0). Therefore, as long as the algorithm keeps track of the actual (x, y) coordinate it is currently at, finding the location of a node is very simple. The algorithm works like this:
To illustrate this algorithm, suppose we have the tree illustrated in Figure 14, and the user clicks the mouse at coordinates (135, 165) which is in node 6.
Figure
14 Sample tree to search.The algorithm would proceed as illustrated in Figure 15. The algorithm trace will be the same regardless of whether node 1 is actually the first node in the tree, or if it is simply a subtree of a larger tree. This is because each node behaves as if it is the root of the tree beneath it and logically starts at coordinate (0,0), regardless of its actual position.
| |||||
Keep in mind this was a very straightforward search and does not portray the speed advantage of this method. Assume the subtree of node 1 was very massive, and it did not contain the clicked coordinates. Furthermore, assume there exists a node 8 which is node 1's lower sibling and either it or its subtree contains the coordinates. In this case, with one pass of the algorithm we would circumvent all of node 1's subtree without visiting its children and move down to node 8. This is possible because of the upper and lower vectors and provides expedient tree searching.
The worst case scenario for this algorithm is a tree formed in one direction. Example worst case scenarios would be either a tree consisting of many siblings with no children and having the last sibling chosen, or a tree with many generations of single children with the last child chosen. In these cases every node in the tree is visited, however the search is still very fast as shown by example in Chapter 5.
At this point the advantage of storing shape vectors in each node for quick calculations should be clear. However, if these vectors cannot be updated efficiently when editing the tree, the enhanced performance gained by their existence will be negated by the extra time needed to maintain them. Therefore, maintaining the shape vectors is accomplished incrementally through the use of the three methods: Calculate_Node, Calculate_Level, and Set_Subtree_Bounds.
These three methods work together to quickly update the vectors affected by a change in the tree, while by-passing vectors that will not be altered by the change. Here is how they work.
This method is only called on the first child of a node. Its primary job is to initialize variables needed to check the rest of its lower siblings. The outline of its operation is as follows:
This method is called on every node in the level being computed by Calculate_Level. In brief, it updates the Yoffset of the current node, and updates the Cumulative_Vectors to be passed to either its lower sibling, or its parent. In detail, it is a bit messy. Here is the outline of its operation:
This method is called on the root of a subtree after its children have finished their computations via the Calculate_Level and Calculate_Node methods. It simply updates the node's vectors based on the Cumulative_Vectors passed to it from its subtree. Here are the details:
By the use of these three methods, any change in the tree can be quickly and efficiently propagated up the tree by calling the modified node's first sibling. At the same time, this algorithm only visits those node's that might be affected by the change, while leaving all others alone.
The worst case scenarios for this algorithm is again either a tree consisting of many siblings with no children, or a tree with many generations of single children. The worst case is again enacted when the the node at the farthest extremity is edited. Such an edit would cause the algorithm to visit every node. The worst case scenario has more affect on performance in this algorithm than with the selection algorithm, but it is still very minor as demonstrated in Chapter 5.
The algorithm used for reading trees from a saved file, and writing them out to a file has proved to be very important. This is because that same algorithm can also be used for subtree copying when performing a copy/paste operation and for deleting all of the nodes in the tree to free its memory. Before this algorithm was implemented, these operations were not possible to accomplish for various reasons.
The algorithm works quite simply. An array of node pointers is allocated large enough for all of the nodes. This size is easily obtained by asking the root node for the number of nodes in its subtree since each node stores within it the node count of its subtree. The traversal algorithm is then called to store a pointer to each node in the array. Once all of the nodes are stored in the array, we iterate over each node in that array finding first which array element stores the current node's parent and saving that number. Then we find which array element stores the current node's upper sibling, and store that number. This continues until we have determined each node's parent, upper sibling, lower sibling, first child, and last child in terms of a logical array index rather than an actual memory pointer.
For example, lets assume we have the tree given in the Tree Definition and Layout section (Figure 10). The array generated would look something like the table below:
| Index | Node | Parent | Usib | Lsib | First | Last |
| 1 | P | 0 | 0 | 0 | 2 | 4 |
| 2 | A | 1 | 0 | 3 | * | * |
| 3 | B | 1 | 2 | 4 | * | * |
| 4 | C | 1 | 3 | 0 | * | * |
This table is basically what is written to disk when saving a tree, and what is then read in when loading a tree. As mentioned, this is also used for copying subtrees. In this case, instead of starting the traversal at the root node, the traversal starts from the root of the subtree which becomes the first entry in the array. Before this table is written to disk, the number of nodes in the table is written to the file first to make loading easier.
When a saved tree is restored from disk, the number of nodes is first read in and an array of nodes is declared of that size. Then as each line of the table is read in from disk, the node pointers are filled in with the nodes at the indices given in the table.
It was also mentioned that this algorithm is used for deleting subtrees. Actually, only the first half of the algorithm is used in this way, that is, the storing of the pointers in the array. It is necessary to do this rather than using the traversal to delete a subtree since the traversal requires coming back up to parents after its subtree has been deleted to move to its sibling. However, since the traversal algorithm performs any action on the node the first time it visits it, the parent would have already been deleted. In contrast, by simply storing the pointers in the array, a simple pass down the array allows the deletion of the whole subtree.
The worst case scenarios for the previous two algorithms are also the worst case scenarios for this input algorithm. However, unlike the previous two algorithms, the input algorithm is more seriously affected than the others by the worst case. As before, data illustrating the affects of the worst case are given in Chapter 5. This algorithm is more affected by the worst case scenario since it involves more memory allocation and manipulation than the others. On the other hand, the affects of the worst case can be more easily overcome for this algorithm by modifying it to load nodes from the extremities first and work in toward the root node. This reduces a significant amount of calculations.
The C++ source code which implements all of the data structures and algorithms described in this chapter is given in Appendix A. The code for the entire hard-coded editor is not included in this paper since it is not necessary for understanding the principles discussed here. The entire source code and editor executables are available on-line. Details for obtaining all the source code is given in Chapter 5.
In the previous chapter a hard-coded editor was described. Recall that the term "hard-coded" referred to the fact that all editing functions and other editing details were coded strictly in C++. Furthermore, that editor was limited to creating and modifying only simple tree structures. This chapter describes a re-design of the previous hard-coded tree editor using a grammar driven (lex/yacc style) approach. A consequence of this new approach is that editors for a much larger class of graphs can be specified more easily and more succinctly using our Graph Editor Specification Language (GESL). A description of GESL will be given first. This will be followed by a GESL specification for the tree editor that was presented in Chapter 3. Data abstractions and key algorithms developed for the hard-coded tree editor are now "built-in", or primitive, features of GESL.
A directed graph is a finite nonempty set of points V and a set X of ordered pairs of distinct points for edges. The ordered pairs link one point in the set V to another point in the set directed from the first point to the second point. To specify a directed graph editor with the grammar-driven approach we define two fundamental types of objects, "graph" objects and "node" objects (see Figure 16). The graph object contains the set of points V which are represented by the node objects. These node objects are connected through various arc relations which encapsulate the edges in the set X. The graph object encapsulates all the information necessary to edit graphs and interact with the user interface. The node objects provide the building blocks from which to construct the graphs to be edited.
Figure
16 Special symbols and link attributes
of GESL.The graph object defines and maintains parts of a graph that are used explicitly or implicitly as operands of editor operations. The current selected node and the last cut subgraph are examples of these graph parts. Some of these special graph parts are defined as GESL primitives, while others can be defined by the editor designer. The built-in, or primitive, parts will be described in more detail in following sections.
The nodes maintain link attributes and geometry, or display, attributes. All of the link attributes of the node are defined by the designer. These attributes define the connections between nodes. The definitions of these link attributes determine the available links of a node and establish the structure of the graph. GESL expresses the links between nodes as 1-way and 2-way binary relationships. These relationships are the directed arcs, or edges, of a directed graph. The display attributes of a node are used to define and maintain the size, shape, and other visual properties of a node, or the groups of nodes in a subgraph. All of the display attributes are also defined by the designer.
Figure
17 Components of GESL.The structure of the GESL specification is divided into three sections (as shown in Figure 17). All of the parts and attributes of the graph and node objects compose the first of three sections of a complete GESL specification. The other two sections are composed of the rules for manipulating the graph. These rules can be divided into those dealing with editing the internal data structure of the graph, and those dealing with maintaining geometric attributes of the nodes when editing the graph. The first type of rules, the data structure abstraction rules, contain all the grammar rules necessary to maintain and transform the internal structure of a graph. These rules manipulate the link attributes of the nodes and manipulate the various graph parts. The second type of rules, the geometry or display abstraction rules, contain all the grammar rules necessary to display a graph to the user. These rules, for example, maintain the shape vectors (introduced in Chapter 3) that define the boundaries of a subgraph.
In an actual GESL specification there is no syntactic division between the two types of rules, but it is helpful to keep a logical division between the two when composing the rules. When written, the geometry abstraction rules look no more complicated than the data structure rules. However, they rely on the shape abstraction and other previously established principles to accomplish a great deal in a simple statement.
All of the grammar rules are read and translated by an interpreter. In the grammar driven environment the interpreter is placed between the GUI driver and the graph object, as shown in Figure 18. The event processing of the grammar driven environment flows in the following manner. The user gives some input to the GUI. If the input is some sort of command that the GUI can handle (such as a movement of the scrollbar), it is handled by the GUI and control is returned to the user. If the input is an editing command, then the command is passed to the interpreter. The interpreter determines what editing command was issued and reads the appropriate rule from the set of GESL grammar rules. The interpreter interprets the rule as described in the following sections and manipulates the graph accordingly. The graph then manipulates nodes as necessary. When the interpreter completes the processing of the rules, control is returned to the user. The mapping of editing commands to GESL grammar rules is accomplished by using the GESL rule labels as the tokens in the GUI menus.
Figure
18 Grammar driven tool environment.The basic format of a GESL grammar is as follows:
Grammar: graph_name( graph_arguments);
Special : special_nodes;
Links: link_attributes;
<graph variable and function declarations>;
Node node_type(node_links) is
<node variable and function declarations>;
end node_name;
<other node type declarations>
Invariants of node_type are
<invariant declarations>;
Rules of node_type are
<rule declarations>
end graph_name;
GESL has a fairly limited vocabulary of keywords, or reserved words. In the grammar, reserved words are written in boldface. Most of the reserved words are used to denote the various sections of the special graph symbol declarations. A formal BNF specification of GESL is given in Appendix B, and a sample GESL grammar for a tree will be given later. The reserved words in a GESL grammar are listed below with a simple explanation. More detail of most sections will be given later.
Grammar Denotes the beginning of a GESL grammar definition. It is followed by a colon, a name for the grammar, and the declaration of any arguments to be passed in when instantiating a graph of this type.
Special Denotes the special nodes declaration section. Symbols representing special nodes or graph parts are declared in this section. This section simply lists the user-defined special graph symbols. The predefined special nodes will be described in more detail later.
Links Denotes the link attributes declaration section. Link attributes represent the arcs linking one node to another.
Node Denotes the beginning of a node definition. Nodes are the building blocks of the graph. Multiple types of nodes can be defined for the grammar. The declarations of the node types contain all the attributes an instance node contains, such as a label or a shape. The node type declarations do not contain any linking information since links, or arcs, are declared in the Links section and their behavior is defined in the Rules section.
Invariants Denotes the invariant declaration section. Invariants can be defined for each type of node, and define conditions which must always be true after any editing operation is applied.
Rules Denotes the grammar rule declaration section. The rules define how the nodes are assembled together into a graph and how editor operations transform the graph structure and display.
Other miscellaneous reserved words include:
GESL provides seven primitive data types. The primitive types include:
Most of these types are commonly used in programming languages and need no explanation. The shape type is the shape abstraction described in Chapter 3 which is a predefined type in GESL. The point type is an (x,y) coordinate pair which is provided to make specifying locations on the graphical display easier. These coordinate pairs are used as discussed in Chapter 3.
The primitive types can be used for declaring attributes for the various node types and any global variables used by the graph. Variables used by the graph are declared where it says, "<graph variable and function declarations>" in the GESL template. Variable declarations take the simple form:
In addition to variables, external functions can also be declared. External functions can be declared for the whole graph object as well as for the various node types. External functions are C++ methods. These functions are necessary to encapsulate any object specific code that does not relate to the structure or geometry of the graph. An example of a common external function is the drawing routine for a node. The actual drawing of a node is specific to the GUI library being used, and is not involved with any graph structure calculations. The syntax to declare an external function is similar to that used in ADA:
GESL recognizes the common arithmetic operators, +, -, *, and /. In addition, it recognizes simple set notation and predicate operators such as , , , , and ~ . Set notation is used to provide special sets of rules called invariants which will be described later.
Miscellaneous separators are used in GESL, such as : ; ( ) [ ] ' .
Comments and whitespace (such as blanks, tabs, and line feeds) are ignored in GESL. Comments can be given with the two common styles:
/* This is a C-like comment
and can span several lines */
// This is a C++ style comment which ends at the end of the line
Case is significant in GESL and is used to differentiate various types of language tokens. The types of nodes must be declared in all lowercase. This is important to distinguish between a node type and a node name when parsing the rules. Also, variables and function names should be declared in lower case. Node variables declared in the rules must be single, uppercase, English alphabetic letters. Arc relations (or links) are written in both upper and lower case symbols from the Greek alphabet. For two-way arcs, upper and lower case symbols of the same letter denote an arc and its inverse.
GESL contains a number of built-in or primitive symbols for representing special nodes or graph parts. An example of a special node is the currently selected node. In the tree editor, only one node may be selected at any one time, but other types of graphs may require multiple selections. The graph object must also contain pointers to graph parts that have been cut or copied. These special pointers are always defined and maintained by the graph object. The selected, cut, and copied node pointers are represented in GESL by the symbols, $, , and ©, respectively.
One additional graph primitive symbol is the @ symbol which represents the node to which a given grammar rule applies. It is similar to the "this" pointer in C++, or the "self" variable in SmallTalk. This symbol is useful since, as will be described later, some rules require changing contexts to various other nodes in the graph in addition to the node currently selected by the user ($). Additional special node symbols (e.g. additional selected nodes) can be declared by the user. All of these special symbols are used by the interpreter when manipulating the graph.
In GESL, Greek letters are used to represent arc relations between nodes. These relations are directed arcs from one node to another and can be one-way or two-way relations. The syntax used to represent a relation from a node A to a node B is "ArelationB." For example, in our tree editor grammar, is used to represent the parent relationship. So to express that node B is the parent of node A, we would write "AB." The parent relationship is a one-way directed arc from the child to its parent. By convention, when a relationship is a two-way relationship, the upper and lowercase versions of the same symbol are used. So, if we say node A is the upper sibling of node B, then node B is the lower sibling of node A. We might denote this in the grammar as BA if and only if AB, where is a directed arc from B to A and is an arc directed from A to B. The binding of Greek letters to arc relations is declared by the user. One-way relation symbols are simply listed in the "Links" section of the GESL grammar. Two-way relations are also listed there, but have a two-way arrow () linking them. For example, the sibling relation just mentioned would be denoted as, "". By declaring the relations as a two-way relation an invariant is automatically defined. This invariant ensures that when one relation of a two-way relation is modified, the corresponding inverse relation is also modified. More details on invariants will be discussed later. The Greek symbols used for declaring arc relations have no significance in themselves, but are translated by the interpreter to the arc relation it represents. With the knowledge of these mappings, and the access to the node elements through methods provided by the nodes, the interpreter can manipulate the nodes according to the grammar rules as it interprets them.
As mentioned earlier, the interpreter manipulates node structure and data through a series of user-defined grammar rules. The grammar rules are boolean-valued functions that allow paramters to be passed in and can be called recursively. Rules are called on node objects as member functions and are evaluated from left to right. The rule syntax is given below (the complete grammar specification is given in Appendix B). Rules take the general form of a label followed by a series of preconditions followed by a series of rewritings and function calls.
The preconditions are collections of relationship expressions. These expressions can do several things. Most often they define an arc relation that must exist and, in the process, can bind node variables to the nodes that fulfill the given relationship. The node variables bound in the arc relations produce a context set of nodes that are visible during the duration of the rule. Preconditions can also define arc relations that may optionally exist, and if they do, node variables can be bound to the relationship. Finally, they can compare an arc relation to another expression with a boolean operator such as '=' and '', and can include boolean conditions that must hold for node attributes. The arc relations in a precondition can also be composed to construct more complex relationships. All of the preconditions, except optional preconditions, must be fulfilled in order for the rule to be executed. All rules return a boolean value of either true if all the preconditions were met and the rule was executed, or false if the preconditions did not hold and thus the rule was not executed. Rules with no preconditions are "context-free" and will execute unconditionally. Regardless of whether the rule is executed or if the preconditions fail and the rule is not executed, upon completion of evaluating the rule control is returned to the GUI, and thus the user. If the rule failed, a message should be displayed to the user stating so by the GUI.
The most common form of precondition is a declaration of an arc relation that must hold before the operation. These relations consist of a previously defined source node, an arc relation, and a target node. The basic syntax is:
The source node can either be a predefined node symbol (such as $, or @), or it can be a local node defined in the context set. The target node can also be a predefined node symbol, or it can be a locally defined node variable. All symbols used in the preconditions, whether predefined or locally defined, create a context set of variables which can be used throughout the rule.
Locally defined node variables are uppercase English alphabetic letters (A, B, C, etc.). Locally defined node variables are temporary variables which are visible and usable throughout the scope of the rule for which they are defined. These variables can be explicitly typed or implicitly typed. By default, local node variables are implicitly typed by the node instance to which they are bound by an arc relation. This is accomplished since all rules are called on some specific node (usually the selected node ($)). In this way, rules are very similar to member functions of a class in C++. To explicitly define a node variable to be of a certain type, the following syntax is used:
When used in a precondition, the ability to specify a particular type for a node variable provides a useful property for editing and constructing graphs. For example, an editor for control-flow diagrams might mandate that specific types of symbols follow others. This can easily be accomplished by specifying the only legal types in the relationship expression.
An example of the common precondition with a specified node type is:
This example would be translated to mean that the selected node ($) must be in relation a node A which is of type "treenode". Any other preconditions evaluated later in the rule can reference node A as a previously defined symbol in the context set.
As already mentioned, preconditions can also define arc relations that may optionally exist. If the relation does exist, then the node variables are bound as before. If not, they are bound to the "null node" denoted by ''. The syntax for this conditional arc relation is similar to the previous form, except that it uses a '?' operator when defining the relation. The general syntax is:
An example of a conditional precondition is:
This is similar to the previous example. It is translated to mean that the selected node ($) may or may not be in relation to a node A. If it does, that node is bound to the variable A. If not, A is bound to .
The final example precondition format is one that compares an arc relation to another expression with a boolean operator such as '=' and ''. The general format for this type of precondition is:
These preconditions are used to check if certain nodes are at certain locations. For example, if you want to check if a node A, defined from a previous arc relationship expression, is the same node that is in the relation to node B, and is also in relation to the selected node, this could be written as, "BA, $ = A."
Subexpressions can also be added to preconditions to check for certain conditions. Subexpressions are placed in parentheses after a defined node to check certain attributes of that node. Subexpressions contain a set of boolean conditions which must be true for the precondition to pass. The general syntax is:
For example, to define a precondition which binds A to the node in relation to the selected node and passes only if that node's size is greater than 50 would be written as, "$A(A.size > 50)".
These few types of arc relation preconditions can be composed to construct complex preconditions. A simple composition is to combine two relationship expressions which share a common node variable. For example, the preconditions "AB, BC" can be combined into a single precondition "ABC". Now assume that node B was not needed for anything later in the rule, but was merely defined to be a placeholder from which to find node C. In this case, the node variable B can simply be omitted from the expression. The resulting simplified precondition would be "AC".
There is no limit to the number of arc relations that can be used in an expression as a route from one node to another. For example, a more complex route to node C from node A might be, "AC". If any of the arc relations en route to node C do not exist, then the precondition would fail. Any nodes in a complex precondition can be defined to be of a certain type as well. For example, "Acircle:Bdiamond:C" would ensure that the node in relation to node A is of type "circle". The node in relation to node A would be bound to node variable B. The node in relation of B must be of type "diamond" and would be bound to node variable C.
The precondition expression can become even more interesting as more relations are composed. For example, "A?circle:B$" would translate to, "Find the node in relation to A. Then find the node in relation to the previously found node. If that node exists and is of type "circle" bind it to node variable B. Now, assuming node B exists, find the node at relation to it. This final node cannot be the selected node."
There is a shortcut for a special case of composed precondition relationships. If all the arc relations in a relationship are the same such as, "ABC…Z", a form of the distributive law can be used. This allows you to write the previous expression as, "[ABC…Z]." As always, this precondition can be composed with others as well.
Another helpful feature is the use of simple regular expressions over a declared collection of arc relations. For example, "A()*B" ()* denotes the reflexive-transitive closure of . Thus "A()*B" states that B is the most remote ancestor of A; that is, B would satisfy: if X such that BX and A()*B, B = A if X such that AX. If this expression was used in a tree structure and represented the parent relationship, then it would return the root node of the tree. Similarly, "A()+B" ()+ would be the transitive closure of (A()+B implies A B). In a tree structure this would follow one or more parent relationships of the selected node. This would be similar to the previous example except that it would fail if the selected node was the root node.
In addition to these regular expressions, simple mathematics can be applied to relationships. For example, "$*3" would follow three relationships of the selected node. In our tree example it would return the great-grandparent of the selected node.
There is one type of special precondition. This special precondition is a copy precondition. This precondition does not check any arc relations, but simply makes a copy of a node and binds it to a variable name. The syntax for this precondition is:
It is made a precondition so that the source node can be verified to exist, and the copy can be verified before execution of the rule.
With the various methods of creating and composing precondition expressions, almost any graph structure that must exist for a rule to be executed can be defined. Preconditions only define the way the graph must be structured before a rule is executed and only bind node variables to nodes that should already exist in the various locations of the graph.
Postconditions can do any combination of three things. The first thing they can do is rewrite relations among nodes defined in the precondition. Secondly, postconditions can assign new values to graph and node variables and their attributes. Finally, postconditions can call other rules to be executed. Postconditions can have boolean conditions associated with them for conditional execution of any of the three things they can do. The general syntax for the three types of postconditions are:
To understand how postconditions rewrite the relations of a precondition, we must first look at the implementation of the preconditions. The preconditions construct a table of all node variables used and all arc relations defined. For example, the precondition "ABC" would construct a table that looked like figure 19.
From this table note that B is in relation to node A, and that node C is in relation to node B. The postconditions effectively redefine the entries to this table. The basic syntax for this rewriting operation is simply:
For example, if we wanted to assign the selected node to be the node in relation to node A, the postcondition would be "A$". Translating this postcondition in terms of the table would be, "$ is the entry in row A, column ."
As with preconditions, these rewriting postconditions can also be composed. However, careful declaration of node variables in the preconditions can often remove the need for composing postconditions. With the previous example (precondition ABC) we may want to rewrite node C to be the selected node. This could be accompished with the postcondition, "A$". However, since node B was defined in the precondition, it would be more efficient to write the postcondition as, "B$".
Unlike preconditions which test if certain relations exist, postconditions mandate them. For example, "B$" would mandate that the selected node be placed in relation to node B regardless of whether or not was originally defined for B (which is uncertain at this time since it was not specified in the precondition).
The null node () symbol is used to destroy arc relations. Therefore, a postcondition of "B" eliminates any value stored in the relation of node B. The null node symbol can also be used in the boolean conditional of a postcondition.
In addition to rewriting relations, postconditions can also assign values to variables. Assignments take the general form:
Postcondition assignments are defined like assignment statements in most imperative languages. For example, if the graph object has a boolean variable named "graphflag", assigning a value of "false" to it would look like, "graphflag false".
The target variable of an assignment can also be an attribute of a node type. Access to a node attribute uses the dot notation:
Therefore assignment to a node's "width" would look like, "N.width 10".
The final type of action of a postcondition is to call another rule to be executed. The general syntax for calling a rule is:
Calling a rule works by executing the rule specified, passing in any arguments necessary, where the nodename specified becomes the node denoted by the @ symbol in the called rule. For example, to call the rule "RuleOne" on the selected node you would write, "$=>RuleOne()". This is similar to calling a member function of an object in C++. If no nodename is specified to call the rule on, the rule is called on the node currently specified by the @ symbol. In this case, the @ is implied making the call "RuleOne()" equivalent to "@=>RuleOne()".
In addition to calling other rules, external functions can also be called. External functions of nodes are accessed similarly to attributes. The syntax is:
So, to call the external function "draw" on the selected node you would write, "$.draw()".
The actions of postconditions may be conditionally executed. This is accomplished by placing a boolean condition in front of a set of postcondition actions. The general form for conditional execution is:
The conditions check some value with a boolean operator. For example, to check if the selected node is not null you would write, "$ ". Any boolean variables can be simply stated since they already evaluate to either "true" or "false". If all of the conditions listed are true, the set of postconditions listed within the parentheses are executed, otherwise they are not.
Within a GESL specification there are a special set of rules which can be defined called Invariants. Invariants are conditions which must always be true and are provided to eliminate the need for restating certain rewriting rules multiple times. These rules are checked and enforced after the entire postcondition has been evaluated and whenever the symbol '!' is encountered within the postcondition. An example of an invariant is when a node 'A' is declared to be the child of a node 'P'. You would always want 'A' to point back to 'P' as its parent, but it would become repetitive to always have to state both the child relationship and the parent relationship whenever one is changed. Therefore, an invariant is stated to accomplish this.
Some invariants are implicitly defined. Implicitly defined invariants result from declaring arc relations as a two-way relation. For example, if a node A has a lower sibling of node B, then node B's upper sibling is always node A. If the sibling relation is declared as a two-way relation, such as " ", then this inverse relationship will always be retained whenever either of the relations is modified.
Other invariants must be explicitly defined. For example, two sibling nodes must always have the same parent node. However, such a relationship is not a two-way relationship so it will not be implicitly defined. The general syntax is the same as first-order predicate calculus. A simplified version of this syntax looks like:
The pre- and postconditions of an invariant are more general than those defined for rewriting rules. They are not particular to specific nodes or a specific context but apply to any nodes that satisfy the preconditions. The bound variables range over the context set defined by a successful rule. They read as follows: "for all nodes that fulfill some preconditional situation, it follows that some postconditional situation must exist." The postconditions can be specific to the nodes listed in the preconditions, or they can use the symbols '' and '' to state that some other node exists, or no other node exists, which fulfills the postcondition.
For example, the invariant which maintains that two siblings must have the same parent is:
This invariant can be read as "For all nodes x and y, where x is the lower sibling of y, there exists a node p such that p is the parent of x and p is the parent of y." This invariant would ensure that if a new node B was inserted as the lower sibling of a node A, node B would automatically be assigned as its parent the parent of node A. Note, because of the two-way relations of sibling relations, this rule would also fix the parent relation of a node that was inserted as the upper sibling of another node.
In this section we present an example of a GESL specification for a tree editor. This will be followed by a brief explanation.
Grammar: Trees( integer Hunit := 10, // Size of horiz. FDU
integer Vunit := 10); // Size of vert. FDU
Special : none;
Links: , , ;
// is read "has first child"
// is read "has parent"
// is read "has upper sibling"
// is read "has lower sibling"
constant integer xpad := 1;
constant integer ypad := 1;
shape Sum_Upper, Sum_Lower;
Node tree(, , , ) is
shape upper, lower;
point location := (0,0);
boolean visible := true;
string label;
integer width, height, yoffset;
function draw() is separate;
end tree;
Invariants of tree are
(x,y)[ yx xy ];
(x,y)[ yx x];
(x,y)[ yx (p)(xp yp)];
(x) [ x x x];
Rules of Tree are
// Cut subtree to cut buffer
Cut(): [$PB, $?A, $?C
CA,
[A ](AC),
[B = $](PC),
$,
$,
P=>Calculate_Level()];
// Copy subtree to copy buffer ©
Copy(boolean:cut):
[S X, S?A, S?B
[cut](X, © X),
[A ](A=>Copy(false)),
[B ](B=>Copy(false))];
// Insert new node as the first child of the selected node
Insert_First_Child(node:N, boolean:isCut):
[$?A
[A ](NA),
$N,
[isCut]( ),
N=>Calculate_Level()];
// Insert new node as the last child of the selected node
Insert_Last_Child(node:N, boolean:isCut):
[$?A()*B
[A ](Insert_First_Child(N, isCut),
[A = ]( BN, [isCut]( ), $=>Calculate_Level() )];
// Insert new node as the upper sibling of the selected node
Insert_Upper_Sibling(node:N, boolean:isCut):
[$?A
[A ](NA)
$N,
[isCut]( ),
$=>Calculate_Level()];
// Insert new node as the lower sibling of the selected node
Insert_Lower_Sibling(node:N, boolean:isCut):
[$?A
[A ](NA),
$N,
[isCut]( ),
$=>Calculate_Level()];
// Beginning of display/geometry
rules
// Calculate Level
Calculate_Level():
[@?A, @?B
Sum_Upper @.upper,
Sum_Lower @.lower,
@.yoffset 0,
@.draw(),
[A ](A=>Calculate_Node()),
[A = , B ](B=>SetBounds())];
// Calculate Node
Calculate_Node():
[@?A, @?B
@.yoffset max(Sum_Lower - (Sum_Lower[0] + @.upper)),
Sum_Upper min(Sum_Upper, (Sum_Lower[0] + @.upper + @.yoffset)),
Sum_Lower max(Sum_Lower, (Sum_Lower[0] +
@.lower + @.yoffset)),
@.draw(),
[A ](A=>Calculate_Node()),
[A = , B ](B=>SetBounds())];
// Set subtree bounds
SetBounds():
[@?A
@.upper Shape(0, (width + xpad)) & Sum_Upper,
@.lower Shape((height + ypad), (width +
xpad)) & Sum_Lower,
[A ] (A=>CalculateLevel())];
end Tree;
Before we look at the grammar rules, we need to understand what the declarations mean at the beginning of the grammar. The two lines that may be confusing are:
The declaration of the special nodes means that this grammar is not declaring any special nodes beyond the ones supplied for all grammars, namely $, , ©, and @. Special nodes should be some unique, non-alphanumeric symbol. The links declared are the arc relationships between nodes this grammar will maintain. Any symbols are acceptable, and have no inherent meaning of their own. The symbol '' means that the relationships on either side of it are inverse relationships. The remaining declaration lines are simply variables we wish to use throughout the program.
The grammar defines a node of type "tree". To the tree node is assigned the arc relationships , , , . These relations are depicted in Figure 20.
Figure
20 Arc relations of the tree node.For trees there are several statements that are always true. These are the invariant rules. By establishing these rules we are able to simplify the normal grammar rules. The invariant rules are:
The first rule is interpreted as, "For all nodes x and y, if x is the first child of y, then y is the parent of x." The second rule means, "For all nodes x and y, if x is the first child of y, then x has no upper sibling" The third rule states, "For all nodes x and y, if x is the lower sibling of y, then there exists a node p such that p is the parent of x, and p is the parent of y. Finally, the fourth rules says, "For all nodes x, if x has no parent, then x has no upper and no lower sibling." By examining each rule, it is obvious that they are true. However, it is beneficial to state them as invariants which can check the correctness of each editing function when it applies, and simplify the editing rules.
One sample rule will be interpreted to ensure the reader can correctly interpret the rest of them. Look at the cut rule:
Cut(): $PB, $?A, $?C
C $,
[A ](AC),
[B = $](PC),
$,
$,
P=>Calculate_Level(); (38)
This rule would be interpreted in this manner. Bind the parent of the selected node to node variable P. Bind the first child of node P to the node variable B. If the selected node has an upper sibling, bind it to node variable A. If the selected node has a lower sibling, bind it to the node variable C. If any of the required relations (namely that of node P and node B) did not exist, this rule would fail to execute and would return a boolean value of false. Assuming the required relations existed, now perform the postcondition actions. Set the node in relation to C (C's upper sibling) to be the node in relation to the selected node ($'s upper sibling). If node A exists (i.e., the selected node had an upper sibling) then assign the lower sibling of node A to be the lower sibling of the selected node. If node B is the selected node (i.e., the selected node is the first child of its parent (node P)), then assign the first child of node P to be node C (which is the selected node's lower sibling). Next, destroy the parent relation of the selected node. Then assign the selected node to be the node in the cut buffer. Finally, call the rule "Calculate_Level" on the first child node of the node P. So put simply, this rule removes the selected node and adjusts the appropriate arc relations.
This chapter describes the steps necessary to install the source code for the hard-coded editor for compilation on other machines. A few speed benchmarks are given which are compared as closely as possible to other products mentioned earlier in the paper. Also a comparison is given of the size differences on different architectures.
One of the goals of this project was to make the tool described portable among various platforms. To do this the program was compiled for the following platforms:
The MS-Windows versions were compiled with Borland C++ and the Linux versions were compiled with the GNU C++ compiler (gcc). The same source code was used and compiled for each platform. Using MS-Windows and Linux as the two development platforms made it extremely convenient to use the same source code. This is because both operating system can be run on the same machine, and share the same disk space. At the same time, Linux provides a reliable representation of the standard UNIX environment which is much different from the MS-windows environment. This demonstrates the portability of the product. Surprisingly, even though the code was the same, the size of the executable varied significantly. The variance is evident even on the same operating system. Figure 21 shows the sizes for each platform.
While the variance in size of the executables is an interesting statistic, it is not nearly as important as the execution speed of the program. The rapid update of the display and quick manipulation of tree nodes is another one the goals of this project. To benchmark the program, I created of random tree of 2000 nodes. By the term random I mean that the tree consisted of some large branches and some small branches, some nodes had many siblings while others had none. This tree was then saved as a file, and read in to each of the different versions of the program. All executions were run on the same machine. The machine used was a 100Mhz Pentium with 16MB of main memory. The tree was read in and displayed 10 times and the average time was taken. The program itself gives the time taken to read and display a tree with detail to thousandths of a second for Linux and hundreths of a second for Windows. Figure 22 gives the results of the time tests.
The execution speeds compare favorably to other graph layout tools found during the research phase of the project. Due to various software requirements the other tools were not compiled on my machine, but the documentation for them contains a few benchmarks. For example, the ISI Grapher by Gabriel Robins was benchmarked at speeds up to 2,500 nodes per minute running on a Symbolics workstation[Rob88]. A much closer competitor is the VCG Tool by Georg Sander. The VCG Tool laid out a tree of 2047 nodes in 5.5 seconds [San94, San95]. This would seem about equal in performance, however it was run on a Sparc 10/30 with 32MB of main memory. Running Linux makes my machine as similar to the operating system of that architecture as I can make it, and even with an inferior CPU and less memory it outperforms the VCG Tool.
For further time testing of the editing operations I built a tree as shown in Figure 23. This tree is one of the worst case scenarios for the editor. As you can see, this tree is in a stepping pattern. There are four main stepping branches each based at a top node titled "Program". Each of these four branches consist of 500 nodes for a total of 2000 nodes. This is a hard setup for the editor because it creates nodes with large shape vectors and editing deep in the tree can cause a large amount of traversal. Also finding a selected node at the bottom of the tree requires traversing at least 500 nodes.
Figure
23 Sample tree for timing editing operations.Several benchmarks we run on this tree structure. Testing was done by cutting 1000 nodes, then pasting them back into the tree. Also, the time to load and redraw the tree was measured as well as the time to find a node at the bottom of the tree. To reduce the amount of result data, testing was only done on the 32-bit Windows version and the Linux Xt version of the program.
Finding a node in either version was a very insignificant amount of time. MS-Windows registered no time at all to select a node, while Linux averaged 0.003 seconds. Redrawing the entire tree (which performs no tree calculations) averages 2.62 seconds on MS-Windows and 1.0058 seconds on Linux.
The times for the editing operations are divided into calculation times and drawing times. The calculation time to cut 1000 nodes on Windows is 0.23 seconds and on Linux it is 0.0165 seconds. The calculation time to paste the nodes back into the tree takes 0.088 seconds on Windows and 0.0363 on Linux. The calculation times to cut and paste on both platforms can increase by around a tenth of a second depending on where in the tree the operation is performed. To adjust the display of the tree after a cut takes 1.477 seconds on Windows and 0.0363 on Linux while redrawing after a paste requires the full redrawing time given above (2.62 seconds or 1.0058 seconds).
All of these editing operation times are quite small for a tree of this size. Also the times measured in this bad case scenario did not vary significantly from the random tree first measured. The one significant change is the load time for this tree and the random tree. Due to the size of this tree large shape vectors are created; at the same time, due to the shape of this tree, many nodes must be traversed and checked as each new node is added to the end of the tree. These two factors result in a significant performance degradation when this tree of 2000 nodes is read compared to when the random tree of 2000 nodes was read. Now, instead of 5.13 seconds to load and draw the tree on Windows, it takes 36.0967 seconds to load the tree plus 2.62 seconds to draw it. On Linux it takes 27.8888 seconds to load the tree plus 1.0058 seconds to draw it instead of merely 2.811 to load and draw the tree as it did with the random tree.
There are a few optimizations that can be done which may improve some of these times. The load time might be reduced be restructuring the load procedure to start from the bottom of the tree and work up. In this way, instead of traversing all of the previously added nodes to fix their shape vectors as each new one is added, only the previously added node would need to be checked to construct the new node's shape vector. This should significantly reduce the load time of the tree. The draw time might also be improved. Currently each node draws itself and its connectors. As new nodes are added, the node connectors meet to form a single line. This method is very modular and easy to implement, but it results in numerous drawing function calls. A more optimized version might calculate when multiple drawing calls can be combined into a single call, and only make the single function call.
Installation of the binary versions of the editor is very straightforward. It does not require any DLLs or other types of libraries. Simply download the version which best fits your architecture, and run it.
Installation of the source code for compilation requires a little bit more work, but not a significant amount. The hardest part of the preparation for compiling the editor is building the wxWindows library for the platform your using. Compilation of the wxWindows library generally proceeds without any problems, however you may have difficulties if you use a compiler or operating system which is not popularly used by the wxWindows community. Information about wxWindows and the code for it can be obtained at:
Upon obtaining the wxWindows package appropriate for your development platform, unpack it. Unpacking it is simply by means of either unzipping it, or untaring it depending on the format downloaded. When extracting the source, make sure the subdirectories are created. For MS-Windows, once it is unpacked, choose the appropriate makefile for your platform and compiler and compile the library. The supported MS-Windows compilers are MS-Visual C++ and Borland C++. In addition, Watcom C++ and Symantic C++ are known to work as well. For UNIX, there is a shell script called "wxinstall" which can be run to build the library. GNU C++ is the primary supported Unix compiler, however compatible compilers such as Sun C++ and AT&T C++ are also known to work.
Once the wxWindows library is built, building the editor is simple. Two versions of the source code are available. The difference between these packages it whether or not the text of the source code contains both carriage returns (CR) and line feeds (LF) at the end of each line, or only carriage returns. DOS and Windows environments require both CR and LF. On the other hand, UNIX environments only require LFs. Other than this difference, and whether a makefile or a Borland IDE file is included, both source code packages contain the same information. Again, make sure the subdirectories are created when extracting the source. The wxWindows distribution contains a "samples" directory under which I made a subdirectory where this program was built. There is no reason it must be compiled in this location, but if it is built in a different location, be sure to modify the makefiles or Borland IDE files accordingly. Once the source is extracted, and the makefiles have been modified to point to the correct location of the wxWindows directory, building the executable should be fundamental.
The accomplishments of this research can be categorized between those dealing with the hard-coded implementation, and those dealing with the grammar-driven specification. The hard-coded implementation contributions are related to efficient algorithms and data abstractions, while the grammar-driven approach contributes a flexible means to construct various graph editors using the contributions of the hard-coded implementation.
The key data abstraction that resulted from this research is the shape abstraction. The contribution of the shape abstraction is not the data structure so much as how it is used. The shape abstraction allows the quick manipulation of graphs since the graph does not need to be traversed to determine the layout of the graph. This compares favorably to many other graph editors researched that must recurse into the graph to calculate layout.
The importance of the shape abstraction is realized when used in conjunction with two important algorithms. The first key algorithm is the algorithm dealing with tree editing. This is the algorithm used to recalculate the geometry of a graph when a node has been inserted or deleted. The shape abstraction allows the geometry recalculations to be accomplished quickly and efficiently. The second key algorithm is the algorithm dealing with finding a selected node. Because the shape abstraction encapsulates the knowledge of the area covered by the graph, large sections of a graph can quickly be discarded from consideration when searching for a node at a given coordinate. This makes searching very fast.
The primary contribution of the grammar-driven specification is a syntax for efficiently and concisely defining the operations of a graph editor. This syntax is powerful enough to handle any directed graph, yet has a compact syntax.
To provide easy access to all the information covered in this project, the entire project has been converted into HTML and made available on the World Wide Web. It is also available in its original MS-Word format and in Postscript. Additionally, all of the source code and executables for the hard-coded editor, as well as the proposal for this project and the defense presentation are available for downloading. All of these are available at:
The evident future direction of this project is to implement the grammar-driven editor. This involves implementing an interpreter which understands the grammar and can parse the grammar rules. Some syntactic changes to the GESL syntax must also be made since Greek letters and the many types of arrows used are not easily representable in ASCII editors. Implementing the interpreter also involves modifying the existing code to allow the node and tree (or graph) objects to be manipulated by the interpreter, rather than doing the work themselves. Additionally, to make the addition of new node shapes more flexible and abstract, the node objects should be modified to use the wxWindows Object Graphics Library (OGL).
The easiest first step for implementing the grammar-driven editor would be to make it execute the tree editor. Once the tree editor has been implemented, other graph editors should be easy to implement by constructing new grammars. Suggested graph editors to implement would be a control flow diagram editor, and an editor to represent language semantics. Implementation of these and other graph editors may result in additional syntax to handle special situations.
Figure
24 Object diagram of current architecture.The source given below is the code for the hard-coded tree editor. In order to prevent the size of this paper from becoming too excessive, only the key files are included. The key files are those which directly implement the algorithms discussed in this paper. The C++ classes included here are the base node class, the base tree class, and the shape abstraction class. All of the files used by the GUI, including the subclasses of the node and tree classes which include GUI specific operations, are not included. Also any auxilary files are not included.
//////////////////////////////////////////////////////////////////////
//
// Filename : node.h
//
// Description : This is the declaration for the Node class which
// provides all the basic structure information for
// all nodes. The Node class contains no actual
// data, just the pointers and things.
//
// Author : Steven Pothoven
//
// Advisor : Dr. David Workman
//
// Copyright : Copyright (c) 1995 Steven Pothoven &
// The University of Central Florida, Orlando, Florida.
// All rights reserved.
//
// Permission is hereby granted, without written
// agreement and without license or royalty fees,
// to use, copy, modify, and distribute this software
// and its documentation for any purpose, provided
// that the above copyright notice and the following
// two paragraphs appear in all copies of this
// software.
//
// IN NO EVENT SHALL STEVEN POTHOVEN BE LIABLE TO ANY
// PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL,
// OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF
// THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF STEVEN
// POTHOVEN HAS BEEN ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// STEVEN POTHOVEN SPECIFICALLY DISCLAIMS ANY
// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED
// HEREUNDER IS ON AN "AS IS" BASIS, AND STEVEN
// POTHOVEN HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
// SUPPORT, UPDATES, ENHANCEMENT, OR MODIFICATION.
//
// Date released :
//
//////////////////////////////////////////////////////////////////////
//
// Fix log :
//
//
//////////////////////////////////////////////////////////////////////
#ifndef NODE_HPP
#define
NODE_HPP
#ifndef MATH_H
#include <math.h>
#define MATH_H
#endif
#ifndef VECTOR_HPP
#include "vector.hpp"
#endif
#ifndef COMMONX_HPP
#include "commonx.hpp"
#endif
#ifndef GRAPHFIL_HPP
#include "graphfil.hpp"
#endif
// forward declaration
class
Node;
#ifndef TREE_HPP
#include "tree.hpp"
#endif
#ifndef __BORLANDC__
extern template class Vector<int>;
#endif
enum
Visibility {HIDDEN, VISIBLE}; // If node can be seen currently
or not
//------------------------------------------------------------
// Class declaration of generic tree nodes
//------------------------------------------------------------
class Node
{
public:
// PUBLIC
SERVICES ----------------------------------------
//
// Constructor (protected since only derived classes should use it)
//
Node(
Visibility theVisibility = VISIBLE
);
//
// Destructor
//
virtual ~Node(
void
);
//
// Calculate the locations for this nodes tree level
//
virtual void calculate_level(
void
);
//
// Check if coordinates are in the node
//
virtual int in_node(
float,
float
);
//
// check if coordinates are in node's children
//
virtual int in_children(
float,
float
);
//
// add a subtree to the current node
//
virtual void insert_subtree(
Node* theSubtree,
InsertMode theMode
);
//
// Remove current node and its subtree and return its pointer
//
virtual Node* remove_subtree(
void
);
//
// Set the size of the node (in units)
//
virtual void set_size(
int theWidth,
int theHeight
);
// Get the count of nodes in subtree (including self)
virtual int get_subtreeCount(
void
);
//
// Recalculate node size after some change
//
virtual void recalculate_size(
void
) {}
//
// Generic tree traversal algorithm
// Note: function passed in gets no arguments
//
virtual void traverse(
void (Node::*theFunction)(void)
);
//
// Generic tree traversal algorithm
// Note: function passed in gets 1 integer argument
//
virtual void traverse(
void (Node::*theFunction)(int),
int
);
//
// Generic tree traversal algorithm
// Note: function passed in gets 1 integer argument
//
virtual void traverse(
void (Node::*theFunction)(Node**),
Node**
);
//
// Generic tree traversal algorithm
// Note: function passed in gets 2 integer arguments
//
virtual void traverse(
void (Node::*theFunction)(int, int),
int,
int
);
// VIRTUAL SERVICES ----------------------------------------
//
// Print the node to stdout
//
virtual void print(
int,
int
);
//
// Draw the node on drawing context at specified coordinates
//
virtual void draw(
int theX,
int theY
) { itsLastX
= theX; itsLastY = theY; }
//
// Erase the node at the specified coordinates
//
virtual void erase(
int,
int
) {}
//
// Select a node
//
virtual void select(
void
) {}
//
// Deselect a node
//
virtual void deselect(
void
) {}
//
// Save the node to a file
//
virtual Node& operator>>(
GraphFile &theGraphFile
);
//
// Load the node to a file
//
virtual Node& operator<<(
GraphFile &theGraphFile
);
//
// Store the node pointers into an array for saving
//
virtual void store(
Node** theNodes
);
//
// Set the node's tree pointer
//
virtual void set_tree(
Tree *theTree
);
//
// Return the tree pointer
//
virtual Tree *tree(
void
);
//
// Set the nodes upper sibling
//
virtual void set_usib(
Node *theNode
);
//
// Set the nodes lower sibling
//
virtual void set_lsib(
Node *theNode
);
//
// Set the nodes lower sibling
//
virtual void set_parent(
Node *theNode
);
//
// Set the nodes lower sibling
//
virtual void set_firstChild(
Node *theNode
);
//
// Set the nodes lower sibling
//
virtual void set_lastChild(
Node *theNode
);
//
// Return the node's parent
//
virtual Node* parent(
void
);
//
// Return the node's upper sibling
//
virtual Node* usib(
void
);
//
// Return the node's lower sibling
//
virtual Node* lsib(
void
);
//
// Return the node's first child
//
virtual Node* firstChild(
void
);
//
// Return the node's last child
//
virtual Node* lastChild(
void
);
//
// Return the node's width (in units)
//
virtual int width(
void
);
//
// Return the node's height (in units)
//
virtual int height(
void
);
//
// Return the node's actual width (in pixels)
//
virtual int actual_width(
void
);
//
// Return the node's actual height (in pixels)
//
virtual int actual_height(
void
);
//
// Return the node's lower vector
//
virtual Vector<int> lower_vector(
void
);
//
// Return the node's Y offset from it's parent
//
virtual int yoffset(
void
);
//
// Set the node's visibility status (VISIBLE/INVISIBLE)
//
virtual void set_visibility(
Visibility theVisibility
);
// Friend functions ----------------------------------------
friend char operator<(
Node& theNode1,
Node& theNode2
) {
theNode1 = theNode1;
theNode2 = theNode2;
return 0;
}
friend char operator>(
Node& theNode1,
Node& theNode2
) {
theNode1 = theNode1;
theNode2 = theNode2;
return 0;
}
friend char operator==(
Node& theNode1,
Node& theNode2
) {
theNode1 = theNode1;
theNode2 = theNode2;
return 0;
}
friend char operator!=(
Node& theNode1,
Node& theNode2
) {
theNode1 = theNode1;
theNode2 = theNode2;
return 0;
}
// ATTRIBUTES
----------------------------------------
int
itsLastX,
itsLastY;
// last (x,y) coordinates node was drawn at
protected:
// Data & Services only visible to Node and it's subclasses
// ATTRIBUTES ----------------------------------------
Tree
*itsTree; // Pointer to tree it belongs to
Node
*itsParent, // Pointer to parent node
*itsUSIB, // Pointer to upper (or right) sibling
*itsLSIB, // Pointer to lower (or left) sibling
*itsFirstChild, // Pointer to first child
*itsLastChild; // Pointer to last child
int
itsYoffset, // Y offset from upper sibling
itsWidth, // Width of node
itsHeight, // Height of node
itsSubtreeCount; // Number of nodes in subtree
Vector<int>
itsUpperVector, // Upper bounds of subtree levels
itsLowerVector; // Lower bounds of subtree levels
Visibility
itsVisibility;
// If node is currently visibly or hidden
// SERVICES ----------------------------------------
//
// The the dimensions of the nodes subtree
//
virtual void set_subtree_bounds(
Vector<int>& theUpperVector,
Vector<int>& theLowerVector,
int theSubtreeCount
);
//
// Do subtree size calculations
//
virtual void calculate_node(
Vector<int>& theCumulativeUpperVector,
Vector<int>& theCumulativeLowerVector,
int theSubtreeCount
);
// Set the count of nodes in subtree (including self)
virtual void set_subtreeCount(
int
);
};
////////////////////////////////////////////////////////////////////////
// INLINE Methods
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
// Set the node's tree pointer
inline void Node::set_tree(
Tree *theTree
)
{
TRACEENTRY("set_tree");
itsTree = theTree;
TRACEEXIT;
}
////////////////////////////////////////////////////////////////////////
// Return the tree pointer
inline Tree* Node::tree(
void
)
{
TRACEENTRY("tree");
TRACEEXIT;
return itsTree;
}
////////////////////////////////////////////////////////////////////////
// Set the nodes upper sibling
inline void Node::set_usib(
Node *theNode
)
{
TRACEENTRY("set_usib");
itsUSIB = theNode;
TRACEEXIT;
}
////////////////////////////////////////////////////////////////////////
// Set the nodes lower sibling
inline void Node::set_lsib(
Node *theNode
)
{
TRACEENTRY("set_lsib");
itsLSIB = theNode;
TRACEEXIT;
}
////////////////////////////////////////////////////////////////////////
// Set the nodes first child
inline void Node::set_firstChild(
Node *theNode
)
{
TRACEENTRY("set_firstChild");
itsFirstChild = theNode;
TRACEEXIT;
}
////////////////////////////////////////////////////////////////////////
// Set the nodes last child
inline void Node::set_lastChild(
Node *theNode
)
{
TRACEENTRY("set_lastChild");
itsLastChild = theNode;
TRACEEXIT;
}
////////////////////////////////////////////////////////////////////////
// Set the nodes parent
inline void Node::set_parent(
Node *theNode
)
{
TRACEENTRY("set_parent");
itsParent = theNode;
TRACEEXIT;
}
////////////////////////////////////////////////////////////////////////
// Return the node's parent
inline Node* Node::parent(
void
)
{
TRACEENTRY("parent");
TRACEEXIT;
return itsParent;
}
////////////////////////////////////////////////////////////////////////
// Return the node's upper sibling
inline Node* Node::usib(
void
)
{
TRACEENTRY("usib");
TRACEEXIT;
return itsUSIB;
}
////////////////////////////////////////////////////////////////////////
// Return the node's lower sibling
inline Node* Node::lsib(
void
)
{
TRACEENTRY("lsib");
TRACEEXIT;
return itsLSIB;
}
////////////////////////////////////////////////////////////////////////
// Return the node's first child
inline Node* Node::firstChild(
void
)
{
TRACEENTRY("firstChild");
TRACEEXIT;
return itsFirstChild;
}
////////////////////////////////////////////////////////////////////////
// Return the node's last child
inline Node* Node::lastChild(
void
)
{
TRACEENTRY("lastChild");
TRACEEXIT;
return itsLastChild;
}
////////////////////////////////////////////////////////////////////////
// Return the node's width (in units)
inline int Node::width(
void
)
{
TRACEENTRY("width");
TRACEEXIT;
return itsWidth;
}
////////////////////////////////////////////////////////////////////////
// Return the node's height (in units)
inline int Node::height(
void
)
{
TRACEENTRY("height");
TRACEEXIT;
return itsHeight;
}
////////////////////////////////////////////////////////////////////////
// Return the node's lower vector
inline Vector<int> Node::lower_vector(
void
)
{
TRACEENTRY("lower_vector");
TRACEEXIT;
return itsLowerVector;
}
////////////////////////////////////////////////////////////////////////
// Return the node's Y offset from it's parent
inline int Node::yoffset(
void
)
{
TRACEENTRY("yoffset");
TRACEEXIT;
return itsYoffset;
}
////////////////////////////////////////////////////////////////////////
// Set the node's visibility status (VISIBLE/INVISIBLE)
inline void Node::set_visibility(
Visibility theVisibility
)
{
TRACEENTRY("set_visibility");
itsVisibility = theVisibility;
TRACEEXIT;
}
////////////////////////////////////////////////////////////////////////
// Return count of nodes in subtree (including self)
inline int Node::get_subtreeCount(
void
)
{
TRACEENTRY("get_subtreeCount");
TRACEEXIT;
return itsSubtreeCount;
}
////////////////////////////////////////////////////////////////////////
// Set count of nodes in subtree (including self)
inline void Node::set_subtreeCount(
int theSubtreeCount
)
{
TRACEENTRY("set_subtreeCount");
itsSubtreeCount = theSubtreeCount;
TRACEEXIT;
}
#endif
//////////////////////////////////////////////////////////////////////
//
// Filename : node.cc
//
// Description : This is the body for the node class. The node
// class is the base class for all node types used
// in any diagram managed by this editor.
// The node class handles all internal pointers and
// structure data for any tree.
//
// Author : Steven Pothoven
//
// Advisor : Dr. David Workman
//
// Copyright : Copyright (c) 1995 Steven Pothoven &
// The University of Central Florida, Orlando, Florida.
// All rights reserved.
//
// Permission is hereby granted, without written
// agreement and without license or royalty fees,
// to use, copy, modify, and distribute this software
// and its documentation for any purpose, provided
// that the above copyright notice and the following
// two paragraphs appear in all copies of this
// software.
//
// IN NO EVENT SHALL STEVEN POTHOVEN BE LIABLE TO ANY
// PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL,
// OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF
// THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF STEVEN
// POTHOVEN HAS BEEN ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// STEVEN POTHOVEN SPECIFICALLY DISCLAIMS ANY
// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED
// HEREUNDER IS ON AN "AS IS" BASIS, AND STEVEN
// POTHOVEN HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
// SUPPORT, UPDATES, ENHANCEMENT, OR MODIFICATION.
//
// Date released :
//
//////////////////////////////////////////////////////////////////////
//
// Fix log :
//
//
//////////////////////////////////////////////////////////////////////
#ifndef NODE_CPP
#define
NODE_CPP
#ifndef NODE_HPP
#include "node.hpp"
#endif
#ifndef STRING_H
#include <string.h>
#define STRING_H
#endif
#ifndef VECTOR_CPP
#include "vector.cpp"
#endif
#ifndef __BORLANDC__
template class Vector<int>;
#endif
// ----------------------------------------------------------------------
// This are the services provided for the Node class template
// ----------------------------------------------------------------------
//////////////////////////////////////////////////////////////////////
// Constructor
//////////////////////////////////////////////////////////////////////
Node::Node(
Visibility theVisibility
)
{
TRACEENTRY("Node");
set_tree(NULL);
set_parent(NULL);
set_usib(NULL);
set_lsib(NULL);
set_firstChild(NULL);
set_lastChild(NULL);
set_visibility(theVisibility);
set_subtreeCount(1);
itsYoffset = 0;
itsWidth = 0;
itsHeight = 0;
itsLastX = 0;
itsLastY = 0;
itsUpperVector
= itsLowerVector = vectorify(0,1);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Destructor
//////////////////////////////////////////////////////////////////////
Node::~Node(
void
)
{
TRACEENTRY("~Node");
if (tree() != NULL)
{
// construct an array of nodes in subtree
Node **nodeBuffer;
int
nodeCount = tree()->root()->get_subtreeCount();
nodeBuffer = new Node*[nodeCount + 1];
tree()->reset_node_count();
traverse(&Node::store,
nodeBuffer);
// delete all the nodes in subtree
for (int i = 2; i <= nodeCount; i++)
{
// first set all node's tree pointer to null to keep them
// from trying to build this buffer and deleting their subtrees
nodeBuffer[i]->set_tree(NULL);
// now delete the nodes
delete nodeBuffer[i];
}
delete nodeBuffer;
}
set_parent(NULL);
set_usib(NULL);
set_lsib(NULL);
set_firstChild(NULL);
set_lastChild(NULL);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
void Node::calculate_level(
void
)
{
TRACEENTRY("calculate_level");
Vector<int>
aCumulativeUpperVector,
aCumulativeLowerVector;
int
aSubtreeCount;
if (VISIBLE == itsVisibility)
{
aCumulativeUpperVector = itsUpperVector;
aCumulativeLowerVector = itsLowerVector;
aSubtreeCount = itsSubtreeCount;
itsYoffset = 0;
if (itsLSIB != NULL)
itsLSIB->calculate_node(aCumulativeUpperVector,
aCumulativeLowerVector,
aSubtreeCount);
else if (itsParent != NULL)
itsParent->set_subtree_bounds(aCumulativeUpperVector,
aCumulativeLowerVector,
aSubtreeCount);
}
else
if (itsLSIB != NULL)
itsLSIB->calculate_level();
else
// this condition should actually not be possible since you
// couldn't be editing this tree if all nodes are invisible
// but just to be thorough, I'll put it in here
if ((itsParent != NULL) &&
(itsParent->itsParent != NULL))
itsParent->itsParent->itsFirstChild->calculate_level();
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
void Node::calculate_node(
Vector<int>& theCumulativeUpperVector,
Vector<int>& theCumulativeLowerVector,
int theSubtreeCount
)
{
TRACEENTRY("calculate_node");
if (VISIBLE == itsVisibility)
{
itsYoffset = (theCumulativeLowerVector -
(itsUpperVector +
theCumulativeLowerVector[0])).max_element();
theCumulativeUpperVector = min(theCumulativeUpperVector,
(itsUpperVector +
theCumulativeLowerVector[0] +
itsYoffset));
theCumulativeLowerVector = max(theCumulativeLowerVector,
(itsLowerVector +
theCumulativeLowerVector[0] +
itsYoffset));
theSubtreeCount += itsSubtreeCount;
}
if (itsLSIB != NULL)
itsLSIB->calculate_node(theCumulativeUpperVector,
theCumulativeLowerVector,
theSubtreeCount);
else if (itsParent != NULL)
itsParent->set_subtree_bounds(theCumulativeUpperVector,
theCumulativeLowerVector,
theSubtreeCount);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
void Node::set_subtree_bounds(
Vector<int>& theCumulativeUpperVector,
Vector<int>& theCumulativeLowerVector,
int theSubtreeCount
)
{
TRACEENTRY("set_subtree_bounds");
itsUpperVector = vectorify(0, itsWidth + itsTree->hspacing()) &
theCumulativeUpperVector;
itsLowerVector = vectorify((itsHeight + itsTree->vspacing()),
itsWidth + itsTree->hspacing()) &
theCumulativeLowerVector;
// Set the subtree node count to number of nodes in subtree plus itself
set_subtreeCount(theSubtreeCount
+ 1);
if (itsParent != NULL)
itsParent->itsFirstChild->calculate_level();
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
int Node::in_node(
float theVirtualX,
float theVirtualY
)
{
TRACEENTRY("in_node");
int
rc;
if (((0 == floor(theVirtualX)) ||
(theVirtualX <= itsWidth)) &&
((0 == floor(theVirtualY)) ||
(theVirtualY <= itsHeight)))
{
TRACESTR("Found Node");
rc = 1;
}
else
{
TRACESTR("Not node");
rc = 0;
}
TRACEEXIT;
return rc;
}
//////////////////////////////////////////////////////////////////////
int Node::in_children(
float theVirtualX,
float theVirtualY
)
{
TRACEENTRY("in_children");
int
rc;
if (((theVirtualX - itsWidth - itsTree->hspacing()) >= 0) &&
((theVirtualX - itsWidth - itsTree->hspacing()) <=
(itsLowerVector.length() - 1)) &&
((itsLowerVector.length() - 1) >= floor(theVirtualX)) &&
(theVirtualY <= (itsLowerVector[(int)floor(theVirtualX)])))
{
TRACESTR("In children");
rc = 1;
}
else
{
TRACESTR("Not in children");
rc = 0;
}
TRACEEXIT;
return rc;
}
//////////////////////////////////////////////////////////////////////
// inserts nodes into tree in a sorted order
// (sorting provided by "<" service of TreeNode, so to make
// insert always prepend, or always append modify "<" to always
// return either false or true accordingly)
//////////////////////////////////////////////////////////////////////
void Node::insert_subtree(
Node* theNode,
InsertMode theMode
)
{
TRACEENTRY("insert_subtree");
Node *current
= NULL;
switch(theMode)
{
case USIB:
theNode->itsParent = itsParent;
current = this;
break;
case LSIB:
theNode->itsParent = itsParent;
current = itsLSIB;
break;
case FIRSTCHILD:
theNode->itsParent = this;
current = itsFirstChild;
break;
case LASTCHILD:
theNode->itsParent = this;
current = NULL;
break;
case ORDEREDCHILD:
theNode->itsParent = this;
for(current = itsFirstChild;
(current != NULL) && (*current < *theNode);
current = current->itsLSIB)
;
break;
}
if (NULL == current) // either itsFirstChild child or adding to end
{
// append theNode
theNode->itsUSIB = theNode->itsParent->itsLastChild;
if (theNode->itsParent->itsFirstChild != NULL)
theNode->itsParent->itsLastChild->itsLSIB = theNode;
else
theNode->itsParent->itsFirstChild = theNode;
theNode->itsParent->itsLastChild = theNode;
theNode->itsParent->itsLastChild->itsLSIB = NULL;
}
else
{
if (current == theNode->itsParent->itsFirstChild)
{
// prepend theNode
theNode->itsLSIB = theNode->itsParent->itsFirstChild;
if (theNode->itsParent->itsFirstChild != NULL)
theNode->itsParent->itsFirstChild->itsUSIB = theNode;
else
theNode->itsParent->itsLastChild = theNode;
theNode->itsParent->itsFirstChild = theNode;
theNode->itsParent->itsFirstChild->itsUSIB = NULL;
}
else
{
// set the prior node's itsLSIB pointer to new node
current->itsUSIB->itsLSIB = theNode;
// set new node's usib pointer to prior node
theNode->itsUSIB = current->itsUSIB;
// set current node's usib pointer to new node
current->itsUSIB = theNode;
// set new node's itsLSIB pointer to current node
theNode->itsLSIB = current;
}
}
// if this is a subtree, rather than a single node, recalulcate
// its vectors
if (theNode->itsFirstChild != NULL)
theNode->itsFirstChild->calculate_level();
// else set its vectors and re-calculate rest of tree
else
{
theNode->itsUpperVector = vectorify(0, theNode->itsWidth +
theNode->itsTree->hspacing());
theNode->itsLowerVector = vectorify(theNode->itsHeight +
theNode->itsTree->vspacing(),
theNode->itsWidth +
theNode->itsTree->hspacing());
theNode->itsParent->itsFirstChild->calculate_level();
}
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// removes the specifed node from the tree and returns a pointer to it
// rather than deleting it
//////////////////////////////////////////////////////////////////////
Node* Node::remove_subtree(
void
)
{
TRACEENTRY("remove_subtree");
Node *saved_node
= this;
if (itsParent != NULL)
{
if (NULL == itsUSIB)
itsParent->itsFirstChild = itsLSIB;
else
itsUSIB->itsLSIB
= itsLSIB;
if (NULL == itsLSIB)
itsParent->itsLastChild = itsUSIB;
else
itsLSIB->itsUSIB
= itsUSIB;
itsUSIB = NULL;
itsLSIB
= NULL;
if (itsParent->itsFirstChild != NULL)
{
itsParent->itsFirstChild->calculate_level();
}
else
{
// Reset itsParent's vectors
itsParent->itsUpperVector = vectorify
(0, itsParent->itsWidth) &
vectorify(0,
itsTree->hspacing());
itsParent->itsLowerVector = vectorify
((itsHeight + itsTree->vspacing()),
itsParent->itsWidth) &
vectorify(0,
itsTree->hspacing());
// if the itsParent is not the root node
if (NULL != itsParent->itsParent)
{
// For some reason Borland 4.51 gets confused if you do this
// all on one line, so I had to make a tempPtr to get the
// right node, then call the method on that node.
Node *tempPtr = itsParent->itsParent->itsFirstChild;
tempPtr->calculate_level();
}
}
}
else
{
itsTree->set_root(NULL);
}
TRACEEXIT;
return saved_node;
}
//////////////////////////////////////////////////////////////////////
// set the width and height of the node
//////////////////////////////////////////////////////////////////////
void Node::set_size(
int theWidth,
int theHeight
)
{
TRACEENTRY("set_size");
if (itsTree)
{
itsUpperVector = vectorify(0, (theWidth + itsTree->hspacing())) &
itsUpperVector.all_but_first
(itsWidth + itsTree->hspacing());
itsLowerVector = vectorify(theHeight,
(theWidth + itsTree->hspacing())) &
itsLowerVector.all_but_first
(itsWidth + itsTree->hspacing());
}
else
{
itsUpperVector = vectorify(0, theWidth) &
itsUpperVector.all_but_first(itsWidth);
itsLowerVector = vectorify(theHeight, theWidth) &
itsLowerVector.all_but_first(itsWidth);
}
itsWidth = theWidth;
itsHeight = theHeight;
TRACEINT(itsWidth);
TRACEINT(itsHeight);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Print the Node
//////////////////////////////////////////////////////////////////////
void Node::print(
int theX,
int theY
)
{
TRACEENTRY("print");
char
*spacing;
if (NULL == (spacing = (char *)malloc(theX)))
TRACESTR("Out
of Memory");
itsLastX = theX;
itsLastY = theY;
memset(spacing, ' ', theX);
theX >
0
? spacing[theX-1]
= '\0'
: *spacing = '\0';
if (VISIBLE == itsVisibility)
cout << spacing << (const char*)"VISIBLE Node\n";
else
cout << spacing << (const char*)"HIDDEN Node\n";
cout << spacing << (const char*)"(x,y): " << theX << (const char*)", " << theY << endl;
cout << spacing << (const char*)"Y-offset: " << itsYoffset << endl;
cout << spacing << (const char*)"itsWidth: " << itsWidth << endl;
cout << spacing << (const char*)"itsHeight: " << itsHeight << endl;
cout << spacing << (const char*)"UpperBounds: " << itsUpperVector << endl;
cout << spacing << (const char*)"LowerBounds: " << itsLowerVector << (const char*)"\n-----\n\n";
free(spacing);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Save the Node
//////////////////////////////////////////////////////////////////////
Node& Node::operator>>(
GraphFile &theGraphFile
)
{
TRACEENTRY("operator>>");
theGraphFile << itsWidth << DELIMITER;
theGraphFile << itsHeight << DELIMITER;
theGraphFile
<< itsVisibility << DELIMITER;
TRACEEXIT;
return *this;
}
//////////////////////////////////////////////////////////////////////
// Load the Node
//////////////////////////////////////////////////////////////////////
Node& Node::operator<<(
GraphFile &theGraphFile
)
{
TRACEENTRY("operator<<");
int visibilityValue,
aWidth,
aHeight;
theGraphFile >> aWidth;
theGraphFile >> aHeight;
theGraphFile >> visibilityValue;
set_size(aWidth, aHeight);
set_visibility((Visibility)visibilityValue);
TRACEEXIT;
return *this;
}
//////////////////////////////////////////////////////////////////////
// Traverse entire tree and do operation passed in to each node
// This version accepts no arguments to function passed in
// and does not keep track of the current X and Y possition of node
//////////////////////////////////////////////////////////////////////
void Node::traverse(
void (Node::*theFunction)()
)
{
TRACEENTRY("traverse");
Node *N = this;
int
Continue = 1;
while(Continue)
{
(N->*theFunction)();
// Process Node
if (NULL == N->itsFirstChild)
{
while((Continue) && ((NULL == N->itsLSIB) || (N == this)))
{
if ((NULL == N->itsParent) || (N == this))
Continue = 0;
else
N = N->itsParent;
}
N = N->itsLSIB;
}
else
N = N->itsFirstChild;
}
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Traverse entire tree and do operation passed in to each node
// This version accepts one integer argument to function passed in
// and does not keeps track of the x,y possition of the current node
//////////////////////////////////////////////////////////////////////
void Node::traverse(
void (Node::*theFunction)(int),
int theValue
)
{
TRACEENTRY("traverse");
Node *N = this;
int
Continue = 1;
while(Continue)
{
(N->*theFunction)(theValue);
// Process Node
if (NULL == N->itsFirstChild)
{
while((Continue) && ((NULL == N->itsLSIB) || (N == this)))
{
if ((NULL == N->itsParent) || (N == this))
Continue = 0;
else
N = N->itsParent;
}
N = N->itsLSIB;
}
else
N = N->itsFirstChild;
}
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Traverse entire tree and do operation passed in to each node
// This version accepts two integer arguments to function passed in
// which are the X,Y coordinates of the current node
//////////////////////////////////////////////////////////////////////
void Node::traverse(
void (Node::*theFunction)(int, int),
int theX,
int theY
)
{
TRACEENTRY("traverse");
Node *N = this;
int Continue = 1;
int UnitSize;
int
Hspacing;
UnitSize = (itsTree != NULL) ? itsTree->unit_size() : 1;
Hspacing
= (itsTree != NULL) ? itsTree->hspacing() : 0;
while(Continue)
{
(N->*theFunction)(theX,theY); // Process Node
// if there are no children
if (NULL == N->itsFirstChild)
{
while((Continue) && ((NULL == N->itsLSIB) || (N == this)))
{
if ((NULL == N->itsParent) || (N == this))
Continue = 0;
else
{
// Go back to the itsParent and set x,y to it's values
N = N->itsParent;
theX = N->itsLastX;
theY = N->itsLastY;
}
}
if(Continue)
{
// go to Lower Sibling and calculate it's y.
theY += N->itsLowerVector[0] * UnitSize;
N = N->itsLSIB;
theY += N->itsYoffset * UnitSize;
}
}
// if this node has children, change X to location after
// current node, and go to that node
else
{
theX += (N->itsWidth + Hspacing) * UnitSize;
N = N->itsFirstChild;
}
}
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Traverse entire tree and do operation passed in to each node
// This version accepts one integer argument to function passed in
// and does not keeps track of the x,y possition of the current node
//////////////////////////////////////////////////////////////////////
void Node::traverse(
void (Node::*theFunction)(Node**),
Node** theValue
)
{
TRACEENTRY("traverse");
Node *N = this;
int
Continue = 1;
while(Continue)
{
(N->*theFunction)(theValue);
// Process Node
if (NULL == N->itsFirstChild)
{
while((Continue) && ((NULL == N->itsLSIB) || (N == this)))
{
if ((NULL == N->itsParent) || (N == this))
Continue = 0;
else
N = N->itsParent;
}
N = N->itsLSIB;
}
else
N = N->itsFirstChild;
}
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Return the node's actual width (in pixels)
//////////////////////////////////////////////////////////////////////
int Node::actual_width(
void
)
{
TRACEENTRY("actual_width");
TRACEEXIT;
return ((itsTree != NULL) ? itsWidth * itsTree->unit_size() : itsWidth);
}
//////////////////////////////////////////////////////////////////////
// Return the node's actual height (in pixels)
//////////////////////////////////////////////////////////////////////
int Node::actual_height(
void
)
{
TRACEENTRY("actual_height");
TRACEEXIT;
return ((itsTree != NULL) ? itsHeight * itsTree->unit_size() : itsHeight);
}
//////////////////////////////////////////////////////////////////////
// Store itself in the node array for saving puposes
//////////////////////////////////////////////////////////////////////
void Node::store(
Node** theNodes
)
{
TRACEENTRY("store");
if (itsTree != NULL)
{
itsTree->increment_node_count();
theNodes[itsTree->get_node_count()] = this;
}
TRACEEXIT;
}
#endif
//////////////////////////////////////////////////////////////////////
//
// Filename : tree.h
//
// Description : This is the declaration for the tree class. The
// Tree object provides a container and access point
// for all the nodes used in a diagram.
//
// Author : Steven Pothoven
//
// Advisor : Dr. David Workman
//
// Copyright : Copyright (c) 1995 Steven Pothoven &
// The University of Central Florida, Orlando, Florida.
// All rights reserved.
//
// Permission is hereby granted, without written
// agreement and without license or royalty fees,
// to use, copy, modify, and distribute this software
// and its documentation for any purpose, provided
// that the above copyright notice and the following
// two paragraphs appear in all copies of this
// software.
//
// IN NO EVENT SHALL STEVEN POTHOVEN BE LIABLE TO ANY
// PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL,
// OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF
// THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF STEVEN
// POTHOVEN HAS BEEN ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// STEVEN POTHOVEN SPECIFICALLY DISCLAIMS ANY
// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED
// HEREUNDER IS ON AN "AS IS" BASIS, AND STEVEN
// POTHOVEN HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
// SUPPORT, UPDATES, ENHANCEMENT, OR MODIFICATION.
//
// Date released :
//
//////////////////////////////////////////////////////////////////////
//
// Fix log :
//
//
//////////////////////////////////////////////////////////////////////
#ifndef TREE_HPP
#define
TREE_HPP
#include
<stdio.h>
#ifndef COMMONX_HPP
#include "commonx.hpp"
#endif
#ifndef GRAPHFIL_HPP
#include"graphfil.hpp"
#endif
enum InsertMode {
USIB, // Insert as UpperSibling
LSIB, // Insert as LowerSibling
FIRSTCHILD, // Insert as FirstChild
LASTCHILD, // Insert as LastChild
ORDEREDCHILD
}; // Insert as Ordered Child
class
Tree;
#ifndef NODE_HPP
#include "node.hpp"
#endif
//------------------------------------------------------------
// This is the class declaration for the Tree object
// which contains only the root nodes for the tree structure
//------------------------------------------------------------
class Tree
{
public:
//
// Constructor
//
Tree(
int theHspacing = DEFAULT_SPACING,
int theVspacing = DEFAULT_SPACING,
int theUnitSize = UNIT_SIZE
);
//
// Destructor
//
virtual ~Tree(
void
);
//
// Initialize the tree to initial state
//
virtual void Initialize(
void
);
//
// Find the node at the given coordinates
//
virtual Node* select_node(
float theX,
float theY
);
//
// Cut selected node
//
virtual Node* cut_selected(
void
);
//
// Add a subtree to selected node
//
virtual void add_subtree(
Node* theNode
);
//
// Recalculate positions
//
virtual void recalulcate_position(
void
);
//
// Print the tree
//
virtual void print(
void
);
//
// Draw the tree
//
virtual void draw(
void
) {};
//
// Save the tree
//
virtual Tree& operator>>(
GraphFile& theGraphFile
);
//
// Load the tree
//
virtual Tree& operator<<(
GraphFile& theGraphFile
);
//
// Copy the selected subtree
//
virtual void copy(
Node *theSelectedNode,
GraphFile& theGraphFile
);
//
// Paste a subtree
//
virtual void paste(
GraphFile& theGraphFile
);
//
// Store the tree to a file
//
virtual void store(
Node *theStartNode,
GraphFile& theGraphFile
);
//
// Load the tre from a file
//
virtual Node* load(
GraphFile& theGraphFile
);
//
// Return pointer to root node
//
virtual Node* root(
void
);
//
// Return pointer to selected node
//
virtual Node* selected_node(
void
);
//
// Set root node
//
virtual void set_root(
Node* theRoot
);
//
// Return current Horizontal spacing (in units)
//
virtual int hspacing(
void
);
//
// Return current Vertical spacing (in Units)
//
virtual int vspacing(
void
);
//
// Return current Horizontal spacing (in pixels)
//
virtual int actual_hspacing(
void
);
//
// Return current Vertical spacing (in pixels)
//
virtual int actual_vspacing(
void
);
//
// Return current size of a unit
//
virtual int unit_size(
void
);
//
// Increment node counter
// This is used by nodes for saving themselves
//
virtual void increment_node_count(
void
);
//
// Return node count
//
virtual long get_node_count(
void
);
//
// Reset node counter to 0
//
virtual void reset_node_count(
void
);
//
// Set shape for new nodes
//
virtual void set_shape(
int theShape
);
//
// Return current shape of new nodes
//
virtual int get_shape(
void
);
//
// Set insertion mode
//
virtual void set_insertion_mode(
InsertMode theMode
);
protected:
// Root node of tree
Node *itsRoot;
// Currently selected node
Node *itsSelectedNode;
// Unit size
int
itsUnitSize;
// Horizontal spacing of tree levels
int
itsHspacing;
// Vertical spacing of tree levels
int
itsVspacing;
// X coordinate of first root node
int
itsStartX;
// Y coordinate of first root node
int
itsStartY;
// Number of nodes in tree
long
itsNodeCount;
// Array of nodes for saving and copying
Node **itsNodeBuffer;
// Current shape of new nodes
int
itsNodeShape;
// Current mode for node insertion
InsertMode itsInsertionMode;
};
// Inline services ----------------------------------------
//////////////////////////////////////////////////////////////////////
inline Node* Tree::root(
void
)
{
TRACEENTRY("root");
TRACEEXIT;
return itsRoot;
}
//////////////////////////////////////////////////////////////////////
inline Node* Tree::selected_node(
void
)
{
TRACEENTRY("selected_node");
TRACEEXIT;
return itsSelectedNode;
}
//////////////////////////////////////////////////////////////////////
inline int Tree::hspacing(
void
)
{
TRACEENTRY("hspacing");
TRACEINT(itsHspacing);
TRACEEXIT;
return itsHspacing;
}
//////////////////////////////////////////////////////////////////////
inline int Tree::vspacing(
void
)
{
TRACEENTRY("vspacing");
TRACEINT(itsVspacing);
TRACEEXIT;
return itsVspacing;
}
//////////////////////////////////////////////////////////////////////
inline int Tree::actual_hspacing(
void
)
{
TRACEENTRY("actual_hspacing");
TRACEINT(itsHspacing * itsUnitSize);
TRACEEXIT;
return (itsHspacing * itsUnitSize);
}
//////////////////////////////////////////////////////////////////////
inline int Tree::actual_vspacing(
void
)
{
TRACEENTRY("actual_vspacing");
TRACEINT(itsVspacing * itsUnitSize);
TRACEEXIT;
return (itsVspacing * itsUnitSize);
}
//////////////////////////////////////////////////////////////////////
inline int Tree::unit_size(
void
)
{
TRACEENTRY("unit_size");
TRACEINT(itsUnitSize);
TRACEEXIT;
return itsUnitSize;
}
//////////////////////////////////////////////////////////////////////
// Increment node counter
// This is used by nodes for saving themselves
//
//////////////////////////////////////////////////////////////////////
inline void Tree::increment_node_count(
void
)
{
TRACEENTRY("increment_node_count");
itsNodeCount++;
TRACEINT(itsNodeCount);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Return node count
//
//////////////////////////////////////////////////////////////////////
inline long Tree::get_node_count(
void
)
{
TRACEENTRY("get_node_count");
TRACEEXIT;
return itsNodeCount;
}
//////////////////////////////////////////////////////////////////////
// Reset node counter to 0
//
//////////////////////////////////////////////////////////////////////
inline void Tree::reset_node_count(
void
)
{
TRACEENTRY("reset_node_count");
itsNodeCount = 0;
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Set the shape of newly inserted nodes
//
//////////////////////////////////////////////////////////////////////
inline void Tree::set_shape(
int theShape
)
{
TRACEENTRY("set_shape");
itsNodeShape = theShape;
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Get the shape of newly inserted nodes
//
//////////////////////////////////////////////////////////////////////
inline int Tree::get_shape(
void
)
{
TRACEENTRY("get_shape");
TRACEEXIT;
return itsNodeShape;
}
//////////////////////////////////////////////////////////////////////
// Set the insertion mode for of newly inserted nodes
//
//////////////////////////////////////////////////////////////////////
inline void Tree::set_insertion_mode(
InsertMode theMode
)
{
TRACEENTRY("set_insertion_mode");
itsInsertionMode = theMode;
TRACEEXIT;
}
#endif
//////////////////////////////////////////////////////////////////////
//
// Filename : tree.cc
//
// Description : This is the body for the tree class. The tree
// class provides the container for all the nodes in
// use, and the access point to them.
//
// Author : Steven Pothoven
//
// Advisor : Dr. David Workman
//
// Copyright : Copyright (c) 1995 Steven Pothoven &
// The University of Central Florida, Orlando, Florida.
// All rights reserved.
//
// Permission is hereby granted, without written
// agreement and without license or royalty fees,
// to use, copy, modify, and distribute this software
// and its documentation for any purpose, provided
// that the above copyright notice and the following
// two paragraphs appear in all copies of this
// software.
//
// IN NO EVENT SHALL STEVEN POTHOVEN BE LIABLE TO ANY
// PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL,
// OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF
// THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF STEVEN
// POTHOVEN HAS BEEN ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// STEVEN POTHOVEN SPECIFICALLY DISCLAIMS ANY
// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED
// HEREUNDER IS ON AN "AS IS" BASIS, AND STEVEN
// POTHOVEN HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
// SUPPORT, UPDATES, ENHANCEMENT, OR MODIFICATION.
//
// Date released :
//
//////////////////////////////////////////////////////////////////////
//
// Fix log :
//
//
//////////////////////////////////////////////////////////////////////
#ifndef TREE_CPP
#define
TREE_CPP
#ifndef TREE_HPP
#include "tree.hpp"
#endif
//////////////////////////////////////////////////////////////////////
//
// Constructor
//
//////////////////////////////////////////////////////////////////////
Tree::Tree(
int theHspacing,
int theVspacing,
int theUnitSize
)
{
TRACEENTRY("Tree");
itsHspacing = theHspacing;
itsVspacing = theVspacing;
itsUnitSize = theUnitSize;
itsInsertionMode = ORDEREDCHILD;
set_shape(0);
set_root(NULL);
Initialize();
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Destructor
//////////////////////////////////////////////////////////////////////
Tree::~Tree(
void
)
{
TRACEENTRY("~Tree");
delete
itsRoot;
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Initializer
//////////////////////////////////////////////////////////////////////
void Tree::Initialize(
void
)
{
TRACEENTRY("Initialize");
delete itsRoot;
itsStartX = 0;
itsStartY = 0;
itsSelectedNode = NULL;
reset_node_count();
set_root(NULL);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
void Tree::print(
void
)
{
TRACEENTRY("print");
itsRoot->traverse(&Node::print, itsStartX, itsStartY);
cout <<
(const
char*)"----------------------------------------\n\n";
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
/*
void Tree::draw(
void
)
{
TRACEENTRY("draw");
itsRoot->traverse(&Node::draw,
itsStartX, itsStartY);
TRACEEXIT;
}
*/
//////////////////////////////////////////////////////////////////////
void Tree::recalulcate_position(
void
)
{
TRACEENTRY("recalculate_position");
if ((itsSelectedNode != NULL) &&
(itsSelectedNode->parent() != NULL))
itsSelectedNode->parent()->firstChild()->calculate_level();
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
void Tree::set_root(
Node* theRoot
)
{
TRACEENTRY("set_root");
itsRoot = theRoot;
if (itsRoot)
itsRoot->set_tree(this);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Find the node at the given X,Y coorindates
//////////////////////////////////////////////////////////////////////
Node* Tree::select_node(
float theX,
float theY
)
{
TRACEENTRY("select_node");
float virtualX;
float virtualY;
int Continue = 1;
Node *currentNode
= itsRoot;
virtualX = theX / itsUnitSize;
virtualY = theY / itsUnitSize;
if (itsSelectedNode)
{
itsSelectedNode->deselect();
itsSelectedNode = NULL;
}
while ((NULL == itsSelectedNode) && (Continue))
{
// check if coordinates are in current node
if (currentNode->in_node(virtualX, virtualY))
itsSelectedNode
= currentNode;
// checks to see if coordinates are
// in the current node's subtree
else if (currentNode->in_children(virtualX, virtualY))
{
virtualX -= currentNode->width() + itsHspacing;
currentNode = currentNode->firstChild();
}
// if there is an lsib, go to it
else if (NULL != currentNode->lsib())
{
virtualY -= currentNode->height() + itsVspacing;
currentNode = currentNode->lsib();
virtualY -= currentNode->yoffset();
}
// coordinates selected do not belong to any node in tree
else
{
Continue = 0;
TRACESTR("Not found");
}
}
if (itsSelectedNode)
itsSelectedNode->select();
TRACEEXIT;
return itsSelectedNode;
}
//////////////////////////////////////////////////////////////////////
// cut selected node, and return a pointer to it
//////////////////////////////////////////////////////////////////////
Node* Tree::cut_selected(
void
)
{
TRACEENTRY("cut_selected");
Node *temp;
if (itsSelectedNode != NULL)
itsSelectedNode->remove_subtree();
temp = itsSelectedNode;
itsSelectedNode
= NULL;
TRACEEXIT;
return temp;
}
//////////////////////////////////////////////////////////////////////
// Add a Subtree (N) to the Parent located at (x,y)
//////////////////////////////////////////////////////////////////////
void Tree::add_subtree(
Node* theNode
)
{
TRACEENTRY("add_subtree");
if (itsSelectedNode != NULL)
{
theNode->set_tree(this);
itsSelectedNode->insert_subtree(theNode, itsInsertionMode);
}
else
{
TRACESTR("Parent does not exist\n");
}
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Save the tree
//////////////////////////////////////////////////////////////////////
Tree& Tree::operator>>(
GraphFile& theGraphFile
)
{
TRACEENTRY("operator>>");
store(itsRoot,
theGraphFile);
TRACEEXIT;
return *this;
}
//////////////////////////////////////////////////////////////////////
// Copy a subtree
//////////////////////////////////////////////////////////////////////
void Tree::copy(
Node *theSelectedNode,
GraphFile& theGraphFile
)
{
TRACEENTRY("copy");
Node *originalParent;
Node *originalUSIB;
Node *originalLSIB;
originalParent = theSelectedNode->parent();
originalUSIB = theSelectedNode->usib();
originalLSIB
= theSelectedNode->lsib();
theSelectedNode->set_parent(NULL);
theSelectedNode->set_usib(NULL);
theSelectedNode->set_lsib(NULL);
store(theSelectedNode,
theGraphFile);
theSelectedNode->set_parent(originalParent);
theSelectedNode->set_usib(originalUSIB);
theSelectedNode->set_lsib(originalLSIB);
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Store a subtree to a file
//////////////////////////////////////////////////////////////////////
void Tree::store(
Node *theStartNode,
GraphFile& theGraphFile
)
{
TRACEENTRY("store");
itsNodeCount = theStartNode->get_subtreeCount();
theGraphFile << itsNodeCount << DELIMITER;
theGraphFile << itsUnitSize << DELIMITER;
theGraphFile << itsHspacing << DELIMITER;
theGraphFile << itsVspacing << DELIMITER;
theGraphFile << itsStartX << DELIMITER;
theGraphFile
<< itsStartY << endl;
itsNodeBuffer
= new
Node*[itsNodeCount + 1];
reset_node_count();
theStartNode->traverse(&Node::store,
itsNodeBuffer);
for (int i = 1, j; i <= itsNodeCount; i++)
{
theGraphFile
<< i << DELIMITER;
if (itsNodeBuffer[i]->parent() != NULL)
{
j = 1;
while ((itsNodeBuffer[i]->parent() != itsNodeBuffer[j]) &&
(j <= itsNodeCount))
j++;
theGraphFile << j << DELIMITER;
}
else
theGraphFile
<< 0
<< DELIMITER;
if (itsNodeBuffer[i]->usib() != NULL)
{
j = 1;
while ((itsNodeBuffer[i]->usib() != itsNodeBuffer[j]) &&
(j <= itsNodeCount))
j++;
theGraphFile << j << DELIMITER;
}
else
theGraphFile
<< 0
<< DELIMITER;
if (itsNodeBuffer[i]->lsib() != NULL)
{
j = 1;
while ((itsNodeBuffer[i]->lsib() != itsNodeBuffer[j]) &&
(j <= itsNodeCount))
j++;
theGraphFile << j << DELIMITER;
}
else
theGraphFile
<< 0
<< DELIMITER;
if (itsNodeBuffer[i]->firstChild() != NULL)
{
j = 1;
while ((itsNodeBuffer[i]->firstChild() != itsNodeBuffer[j]) &&
(j <= itsNodeCount))
j++;
theGraphFile << j << DELIMITER;
}
else
theGraphFile
<< 0
<< DELIMITER;
if (itsNodeBuffer[i]->lastChild() != NULL)
{
j = 1;
while ((itsNodeBuffer[i]->lastChild() != itsNodeBuffer[j]) &&
(j <= itsNodeCount))
j++;
theGraphFile << j << DELIMITER;
}
else
theGraphFile
<< 0
<< DELIMITER;
*itsNodeBuffer[i] >> theGraphFile;
theGraphFile << endl;
}
delete
itsNodeBuffer;
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Load the tree
//////////////////////////////////////////////////////////////////////
Tree& Tree::operator<<(
GraphFile& theGraphFile
)
{
TRACEENTRY("operator<<");
itsRoot =
load(theGraphFile);
TRACEEXIT;
return *this;
}
//////////////////////////////////////////////////////////////////////
// Paste a subtreev
//////////////////////////////////////////////////////////////////////
void Tree::paste(
GraphFile& theGraphFile
)
{
TRACEENTRY("paste");
add_subtree(load(theGraphFile));
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
// Load the tree
//////////////////////////////////////////////////////////////////////
Node* Tree::load(
GraphFile& theGraphFile
)
{
TRACEENTRY("load");
int anInt; // Dummy value
int i; // a temporary index
char junk[255];
Node *aNodePointer;
theGraphFile >> itsNodeCount;
theGraphFile >> itsUnitSize;
theGraphFile >> itsHspacing;
theGraphFile >> itsVspacing;
theGraphFile >> itsStartX;
theGraphFile
>> itsStartY;
itsNodeBuffer = new Node*[itsNodeCount + 1];
itsNodeBuffer[0]
= NULL; // make sure place 0 is a NULL and not garbage
for (i = 1; i <= itsNodeCount; i++)
{
itsNodeBuffer[i] = new Node();
itsNodeBuffer[i]->set_tree(this);
// Burn past pointer references until all nodes are made
theGraphFile >> anInt >> anInt >> anInt >> anInt >> anInt >> anInt;
*itsNodeBuffer[i] << theGraphFile;
}
theGraphFile.seekp(0); // Move back to the beginning of file
theGraphFile.getline(junk,255);
for (i = 1; i <= itsNodeCount; i++)
{
theGraphFile >> anInt; // Node's own index, unnessesary
theGraphFile >> anInt; // Node's parent index
itsNodeBuffer[i]->set_parent(itsNodeBuffer[anInt]);
theGraphFile >> anInt; // Node's upper sibling
itsNodeBuffer[i]->set_usib(itsNodeBuffer[anInt]);
theGraphFile >> anInt; // Node's lower sibling
itsNodeBuffer[i]->set_lsib(itsNodeBuffer[anInt]);
theGraphFile >> anInt; // Node's first child
itsNodeBuffer[i]->set_firstChild(itsNodeBuffer[anInt]);
theGraphFile >> anInt; // Node's last child
itsNodeBuffer[i]->set_lastChild(itsNodeBuffer[anInt]);
theGraphFile.getline(junk, 255); // move to next line
if (NULL == itsNodeBuffer[i]->lsib()) // attempt to optimize calcs
itsNodeBuffer[i]->recalculate_size();
}
aNodePointer= itsNodeBuffer[1];
delete
itsNodeBuffer;
TRACEEXIT;
return aNodePointer;
}
#endif
//////////////////////////////////////////////////////////////////////
//
// Filename : vector.h
//
// Description : This is the declaration of the vector object
// which is defines many standard, and some
// specialized, operations used by the Node class
//
// Author : Steven Pothoven
//
// Advisor : Dr. David Workman
//
// Copyright : Copyright (c) 1995 Steven Pothoven &
// The University of Central Florida, Orlando, Florida.
// All rights reserved.
//
// Permission is hereby granted, without written
// agreement and without license or royalty fees,
// to use, copy, modify, and distribute this software
// and its documentation for any purpose, provided
// that the above copyright notice and the following
// two paragraphs appear in all copies of this
// software.
//
// IN NO EVENT SHALL STEVEN POTHOVEN BE LIABLE TO ANY
// PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL,
// OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF
// THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF STEVEN
// POTHOVEN HAS BEEN ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// STEVEN POTHOVEN SPECIFICALLY DISCLAIMS ANY
// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED
// HEREUNDER IS ON AN "AS IS" BASIS, AND STEVEN
// POTHOVEN HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
// SUPPORT, UPDATES, ENHANCEMENT, OR MODIFICATION.
//
// Date released :
//
//////////////////////////////////////////////////////////////////////
//
// Fix log :
//
//
//////////////////////////////////////////////////////////////////////
#ifndef VECTOR_HPP
#define
VECTOR_HPP
#ifdef __BORLANDC__
#include <fstream.h>
#else
#include <stream.h>
#endif
#include <stdlib.h>
#include
<stdio.h>
#ifndef COMMONX_HPP
#include "commonx.hpp"
#endif
template<class Velement> class Vector
{
public:
//
// Constructors
//
Vector(
void
);
Vector(
int theSize
);
Vector(
const Vector<Velement> &theVector
);
//
// Destructor
//
~Vector(
void
);
//
// Assignment of Vectors
//
Vector<Velement>& operator=(
const Vector<Velement> &theVector
);
//
// Add/Assign Velement to each vector element
//
Vector<Velement>& operator+=(
Velement theElement
);
//
// Subtract/Assign Velement from each vector element
//
Vector<Velement>& operator-=(
Velement theElement
);
//
// Return vector element at location
//
Velement& operator[](
int theIndex
) const;
//
// Add element to end of vector
//
int add_element(
const Velement theElement
);
//
// Remove last vector element
//
int remove_element(
void
);
//
// Return vector[n..length]
//
Vector<Velement> all_but_first(
int theStart
);
//
// Return largest element in vector
//
Velement max_element(
void
);
//
// Return length of Vecctor
//
int length(
void
) const;
// A few
friends
//
// enable cout for vectors
//
friend ostream& operator<<(
ostream &theStream,
const Vector<Velement> &theVector
);
//
// enable cin for vectors
//
friend istream& operator>>(
istream &theStream,
Vector<Velement> &theVector
);
//
// comparison of two vectors
//
friend int operator==(
const Vector<Velement> &theVector1,
const Vector<Velement> &theVector2
);
//
// add two vectors
//
friend Vector<Velement> operator+(
const Vector<Velement> &theVector1,
const Vector<Velement> &theVector2
);
//
// subtract two vectors
friend Vector<Velement> operator-(
const Vector<Velement> &theVector1,
const Vector<Velement> &theVector2
);
//
// multiply two vectors
//
friend Vector<Velement> operator*(
const Vector<Velement> &theVector1,
const Vector<Velement> &theVector2
);
//
// divide two vectors
//
friend Vector<Velement> operator/(
const Vector<Velement> &theVector1,
const Vector<Velement> &theVector2
);
//
// CONCATENATE two vectors
//
friend Vector<Velement> operator&(
const Vector<Velement> &theVector1,
const Vector<Velement> &theVector2
);
//
// add a value to each vector element
//
friend Vector<Velement> operator+(
const Vector<Velement> &theVector,
const Velement theElement
);
//
// subtract a value from each vector elem
//
friend Vector<Velement> operator-(
const Vector<Velement> &theVector,
const Velement theElement
);
//
// return vector of n copies of Velement
//
friend Vector<Velement> vectorify(
Velement theElement,
int theSize
);
//
// returns a vector of smallest values
//
#undef min
friend Vector<Velement> min(
Vector<Velement> &theVector1,
Vector<Velement> &theVector2
);
//
// returns a vector of largest values
//
#undef max
friend Vector<Velement> max(
Vector<Velement> &theVector1,
Vector<Velement> &theVector2
);
private:
// Pointer to Vector
Velement
*itsVectorPtr;
// Length of Vector
int itsLength;
};
// Inline Methods ------------------------------------
//////////////////////////////////////////////////////////////////////
template<class Velement>
inline Vector<Velement>::Vector(
void
)
{
TRACEENTRY("Vector");
itsVectorPtr = NULL;
itsLength
= 0;
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
inline Vector<Velement>::~Vector(
void
)
{
TRACEENTRY("~Vector");
itsLength = 0;
delete
itsVectorPtr;
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
inline int Vector<Velement>::length(
void
) const
{
TRACEENTRY("length");
TRACEINT(itsLength);
TRACEEXIT;
return itsLength;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
inline Velement& Vector<Velement>::operator[](
int theIndex
) const
{
TRACEENTRY("operator[]");
if ((theIndex < 0) || (theIndex > (itsLength - 1)))
{
perror("Vector: range violation\n");
if (theIndex > (itsLength - 1))
perror("Vector index exceeds it's maximum\n");
else
perror("Vector index is negative\n");
exit(-1);
}
TRACEEXIT;
return itsVectorPtr[theIndex];
}
#endif
//////////////////////////////////////////////////////////////////////
//
// Filename : vector.cc
//
// Description : This is the body of the vector class which defines
// some normal and some specialized vector operations
// used by the Node class
//
// Author : Steven Pothoven
//
// Advisor : Dr. David Workman
//
// Copyright : Copyright (c) 1995 Steven Pothoven &
// The University of Central Florida, Orlando, Florida.
// All rights reserved.
//
// Permission is hereby granted, without written
// agreement and without license or royalty fees,
// to use, copy, modify, and distribute this software
// and its documentation for any purpose, provided
// that the above copyright notice and the following
// two paragraphs appear in all copies of this
// software.
//
// IN NO EVENT SHALL STEVEN POTHOVEN BE LIABLE TO ANY
// PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL,
// OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF
// THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF STEVEN
// POTHOVEN HAS BEEN ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// STEVEN POTHOVEN SPECIFICALLY DISCLAIMS ANY
// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED
// HEREUNDER IS ON AN "AS IS" BASIS, AND STEVEN
// POTHOVEN HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
// SUPPORT, UPDATES, ENHANCEMENT, OR MODIFICATION.
//
// Date released :
//
//////////////////////////////////////////////////////////////////////
//
// Fix log :
//
//
//////////////////////////////////////////////////////////////////////
#ifndef VECTOR_CPP
#define
VECTOR_CPP
#ifndef VECTOR_HPP
#include "vector.hpp"
#endif
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement>::Vector(
int theSize
)
{
TRACEENTRY("Vector");
if (theSize < 0)
theSize
= 0;
itsVectorPtr
= new
Velement[theSize]; // allocate Vector dynamically
if (itsVectorPtr) // if allocation successful
{
for (int i =0; i< theSize; i++)
itsVectorPtr[i] = 0;
itsLength = theSize; // store length
}
else
{
perror("Insufficient memory to allocate Vector");
exit (-1);
}
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement>::Vector(
const Vector<Velement>& theVector
)
{
TRACEENTRY("Vector");
itsLength = theVector.length();
itsVectorPtr
= new
Velement[itsLength];
for (int i = 0; i < itsLength; i++)
itsVectorPtr[i]
= theVector[i];
TRACEEXIT;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement>& Vector<Velement>::operator=(
const Vector<Velement>& theVector
)
{
TRACEENTRY("operator=");
if (this != &theVector)
{
if (itsLength != theVector.length())
{
itsLength = theVector.length();
delete itsVectorPtr;
itsVectorPtr = new Velement[itsLength];
}
for (int i = 0; i < itsLength; i++)
itsVectorPtr[i] = theVector[i];
}
TRACEEXIT;
return *this;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
int operator==(
const Vector<Velement>& theVector1,
const Vector<Velement>& theVector2
)
{
TRACEENTRY("operator==");
if (theVector1.length() == theVector2.length())
{
for (int i = 0; i < theVector1.length(); i++)
if (theVector1[i] != theVector2[i])
{
TRACEEXIT;
return 0;
}
TRACEEXIT;
return 1;
}
else
{
TRACEEXIT;
return 0;
}
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> operator+(
const Vector<Velement>& theVector1,
const Vector<Velement>& theVector2
)
{
TRACEENTRY("operator+");
// Make return vector the size of larger vector if unequal
Vector<Velement>
Vector3((theVector1.length() >= theVector2.Length ?
theVector1.length() : theVector2.length()));
for (int i = 0; i < Vector3.length(); i++)
if (i >= theVector1.length())
Vector3[i] = theVector2[i];
else if (i >= theVector2.length())
Vector3[i] = theVector1[i];
else
Vector3[i]
= theVector1[i] + theVector2[i];
TRACEEXIT;
return Vector3;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> operator-(
const Vector<Velement>& theVector1,
const Vector<Velement>& theVector2
)
{
TRACEENTRY("operator-");
// Make return vector the size of smaller vector if unequal
Vector<Velement>
Vector3((theVector1.length() < theVector2.length() ?
theVector1.length() : theVector2.length()));
for (int i = 0; i < Vector3.length(); i++)
Vector3[i]
= theVector1[i] - theVector2[i];
TRACEEXIT;
return Vector3;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> operator*(
const Vector<Velement>& theVector1,
const Vector<Velement>& theVector2
)
{
TRACEENTRY("operator*");
Vector<Velement>
Vector3(theVector1.length());
if (theVector1.length() == theVector2.length())
for (int i = 0; i < theVector1.length(); i++)
Vector3[i]
= theVector1[i] * theVector2[i];
TRACEEXIT;
return Vector3;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> operator/(
const Vector<Velement>& V1,
const Vector<Velement>& V2
)
{
TRACEENTRY("operator/");
Vector<Velement>
V3(V1.Length);
if (V1.Length == V2.Length)
for (int i = 0; i < V1.Length; i++)
V3.VectorPtr[i]
= V1.VectorPtr[i] / V2.VectorPtr[i];
TRACEEXIT;
return V3;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> operator&(
const Vector<Velement>& theVector1,
const Vector<Velement>& theVector2
)
{
TRACEENTRY("operator&");
int
i; // A temporary index
Vector<Velement>
Vector3(theVector1.length() + theVector2.length());
for (i = 0; i < theVector1.length(); i++)
Vector3[i]
= theVector1[i];
for (i = 0; i < theVector2.length(); i++)
Vector3[theVector1.length()
+ i] = theVector2[i];
TRACEEXIT;
return Vector3;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> operator+(
const Vector<Velement>& theVector,
const Velement theElement
)
{
TRACEENTRY("operator+");
Vector<Velement>
Vector2(theVector.length());
for (int i = 0; i < theVector.length(); i++)
Vector2[i]
= theVector[i] + theElement;
TRACEEXIT;
return Vector2;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> operator-(
const Vector<Velement>& theVector,
const Velement theElement
)
{
TRACEENTRY("operator-");
Vector<Velement>
Vector2(theVector.length());
for (int i = 0; i < theVector.length(); i++)
Vector2[i]
= theVector[i] - theElement;
TRACEEXIT;
return Vector2;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement>& Vector<Velement>::operator+=(
Velement theElement
)
{
TRACEENTRY("operator+=");
for (int i = 0; i < itsLength; i++)
itsVectorPtr[i]
= itsVectorPtr[i] + theElement;
TRACEEXIT;
return *this;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement>& Vector<Velement>::operator-=(
Velement theElement
)
{
TRACEENTRY("operator-=");
for (int i = 0; i < itsLength; i++)
itsVectorPtr[i]
= itsVectorPtr[i] - theElement;
TRACEEXIT;
return *this;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> vectorify(
Velement theElement,
int theSize
)
{
TRACEENTRY("vectorify");
Vector<Velement>
Vector(theSize);
for(int i=0; i < theSize; i++)
Vector[i]
= theElement;
TRACEEXIT;
return Vector;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
ostream& operator<<(
ostream& theStream,
const Vector<Velement>& theVector
)
{
TRACEENTRY("operator<<");
for(int i = 0; i < theVector.length(); i++)
theStream
<< theVector[i] << '
';
TRACEEXIT;
return theStream;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
istream& operator>>(
istream& theStream,
Vector<Velement>& theVector
)
{
TRACEENTRY("operator>>");
for(int i = 0; i < theVector.length(); i++)
theStream
>> theVector[i];
TRACEEXIT;
return theStream;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
int Vector<Velement>::add_element(
const Velement theElement
)
{
TRACEENTRY("add_element");
Vector<Velement>
TempVector(itsLength);
TempVector = *this; // Save current vector;
delete itsVectorPtr; // delete current vector
itsVectorPtr
= new
Velement[++itsLength]; // expand current vector
if(itsVectorPtr) // if allocation was successful
{
for(int i = 0; i < itsLength; i++) // replace old values
itsVectorPtr[i]
= TempVector[i];
itsVectorPtr[itsLength - 1] = theElement; // a new value
TRACEEXIT;
return 1;
}
else
{
TRACEEXIT;
return 0;
}
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
int Vector<Velement>::remove_element(
void
)
{
TRACEENTRY("remove_element");
Vector<Velement> TempVector(itsLength);
TempVector = *this; // Save current vector;
delete itsVectorPtr; // delete current vector
itsVectorPtr
= new
Velement[--itsLength]; // shrink current vector
if(itsVectorPtr) // if allocation was successful
{
for(int i = 0; i < itsLength; i++) // replace old values
itsVectorPtr[i]
= TempVector[i];
TRACEEXIT;
return 1;
}
else
{
TRACEEXIT;
return 0;
}
}
//////////////////////////////////////////////////////////////////////
// all_but_first(n) returns the vector of all but the first n elements
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> Vector<Velement>::all_but_first(
int theStart
)
{
TRACEENTRY("all_but_first");
Vector<Velement> Vector(itsLength - theStart);
// if Length > n then copy elements n..Length-1
if (itsLength > theStart)
for (int i = theStart; i < itsLength; i++)
Vector[i
- theStart] = itsVectorPtr[i];
TRACEEXIT;
return Vector;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Velement Vector<Velement>::max_element(
void
)
{
TRACEENTRY("max_element");
Velement
max = itsVectorPtr[0];
for (int i = 1; i < itsLength; i++)
max =
(max >= itsVectorPtr[i] ? max : itsVectorPtr[i]);
TRACEEXIT;
return max;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> min(
Vector<Velement> &theVector1,
Vector<Velement> &theVector2
)
{
TRACEENTRY("min");
Vector<Velement>
Vector3(theVector1.length() > theVector2.length() ?
theVector1.length() : theVector2.length());
for (int i = 0; i < Vector3.length(); i++)
if (i >= theVector1.length())
Vector3[i] = theVector2[i];
else if (i >= theVector2.length())
Vector3[i] = theVector1[i];
else
Vector3[i] =
(theVector1[i] < theVector2[i] ?
theVector1[i] : theVector2[i]);
TRACEEXIT;
return Vector3;
}
//////////////////////////////////////////////////////////////////////
template<class Velement>
Vector<Velement> max(
Vector<Velement> &theVector1,
Vector<Velement> &theVector2
)
{
TRACEENTRY("max");
Vector<Velement>
Vector3(theVector1.length() > theVector2.length() ?
theVector1.length() : theVector2.length());
for (int i = 0; i < Vector3.length(); i++)
if (i >= theVector1.length())
Vector3[i] = theVector2[i];
else if (i >= theVector2.length())
Vector3[i] = theVector1[i];
else
Vector3[i] =
(theVector1[i] > theVector2[i] ?
theVector1[i] : theVector2[i]);
TRACEEXIT;
return Vector3;
}
#endif
The following is the grammar specification for GESL:
<Specification> <SpecHead><SpecBody><End>
<End> end IDENT;
<SpecHead> <SpecName><Declarations>
<SpecName> Grammar : IDENT<Params>; |
Grammar : IDENT;
<Params> ( <DeclStmts> )
<Declarations> <Specials><Links><DeclStmts><Nodes><Invariants>
<Specials> Special : <SpecialList>
<SpecialList> <NodeList>; |
none;
<IdentList> <IdentList>,IDENT |
IDENT
<NodeList> <NodeList>,NODENAME |
NODENAME
<RelationList> <RelationList>,RELATIONNAME |
RELATIONNAME
<Links> Links : <LinkList>
<LinkList> <LinkIdents>;
<LinkIdents> <LinkIdents>, <LinkIdent> |
<LinkIdent>
<LinkIdent> RELATIONNAME |
RELATIONNAME RELATIONNAME
<DeclStmts> <DeclStmts>;<DeclStmt> |
<DeclStmt>
<DeclStmt> <DeclType> <IdentList>; |
<DeclType> <IdentList> := VALUE; |
function IDENT<Params> is separate;
<DeclType> <Type> |
constant <Type>
<Type> boolean |
integer |
string |
float |
shape |
vector |
point |
*<Type>
<Nodes> <NodeHeader><DeclStmts><End>
<NodeHeader> Node IDENT(<RelationList>) is
<Invariants> <InvariantHead><InvariantRules>
<InvariantHead> Invariants of IDENT are
<InvariantRules> <InvariantRules> <Invariant> |
<Invariant>
<Invariant> (<NodeList>)[<Implication>];
<Implication> <Relationship> <Relationship> |
<Relationship> ~(<Relationship>) |
<Relationship> <RelationGroup> |
<Relationship> ~(<RelationGroup>) |
<Relationship>
(<NodeList>):<RelationGroup>
<RelationGroup> (<Relationship> <Relationship>) |
(<Relationship> <Relationship>)
<Relationship> NODENAME <RelationExp> NODENAME
<RelationExp> RELATIONNAME |
( <RelationExp> ) |
<RelationExp> * |
<RelationExp> + |
<RelationExp> * VALUE |
<RelationExp> RELATIONNAME |
<RelationExp> NODENAME <RelationExp>
<SpecBody> <RuleHeader><RuleList>
<RuleHeader> Rules of IDENT are
<RuleList> <RuleList>;<Rule> |
<Rule>
<Rule> RULEIDENT<IdentList>:
[<Preconditions> <Postconditions>];
<Preconditions> <Preconditions>; <Precondition> |
<Precondition>
<Precondition> <PRelationship> |
<PRelationship>(BoolConds)
<BoolConds> <BoolConds>, <BoolCond> |
<BoolCond>
<BoolCond> <Expression> <BoolOp> <Expression>
<BoolOp> > | < | <= | >= | = |
<Postconditions> <Postconditions>; <Postcondition> |
<Postcondition>
<Postcondition> NODENAME RELATIONNAME NODENAME
<NamedNode> <NamedNode> |
<NamedNode> <Expression> |
NODENAME => RULEIDENT(RULEARGS) |
RULEIDENT(ARGS) |
NODENAME.EXTERNALFUNCTION(ARGS)
<PRelationship> <NodeExp> RELATIONNAME <NodeExp>
<NodeExp> ? RELATIONNAME <NodeExp>
<NodeExp> RELATIONNAME <NodeExp> <BoolOp> <NodeExp>
<NodeExp> <NodeExp>
<NodeExp> NODENAME |
<Type>:NODENAME |
<NodeExp> RELATIONNAME |
<NamedNode> NODENAME |
NODENAME.NODEATTIRBUTE
<Expression> <Expression> <Operation> <Expression> |
( <Expression> ) |
- <Expression> |
IDENT
<Operation> + |
- |
* |
/ |
^
[Mig90] Miguel, Luis and Doug Young, XmGraph, Hewlett-Packard Company, 1990. (Available at cae.wisc.edu in /hpux/X11/Toolkits/XmGraph-1.0).
[Rob88] Robins, Gabriel, The ISI Grapher: A Portable Tool for Displaying Graphs Pictorially, Multicomputer Vision, Levialdi, S., Chapter 12, Academic Press, London, 1988, pp. 185-202.
[Rum91] Rumbaugh, James, et. al., Object-Oriented Modeling and Design, Prentice Hall, New Jersey, 1991.
[San94] Sander, Georg, Graph Layout through the VCG Tool, Universität des Saarlandes, Germany, October 4, 1994. (Available by ftp at ftp.cs.uni-sb.de in /pub/graphics/vcg).
[San95] Sander, Georg, VCG, Visualization of Compiler Graphs, Universität des Saarlandes, Germany, February 9, 1995. (Available by ftp at ftp.cs.uni-sb.de in /pub/graphics/vcg).
[Sma95] Smart, Julian, User Manual for wxWindows 1.65: a Portable C++ GUI Toolkit, Artificial Intelligence Applications Institute, University of Edinburg, August 1995. (Available by ftp at ftp.aiai.ed.ac.uk in /pub/packages/wxwin, also at URL: http://web.ukonline.co.uk/julian.smart/wxwin).
[Work] Workman, David A., An Application of Path Grammars to the Design of a Tree Editor , University of Central Florida.
[Wor90] Workman, David A., On the Formal Specification of Graphical Languages Using Path Rewriting Systems , University of Central Florida, December 1990.
[Wor95] Workman, David A., REENEW: A REEngineering Environment and Workbench, Science Applications International Corporation and University of Central Florida, January 1995.
[You94] Young, Douglas, The X Windows System: Programming and Applications with Xt , Second OSF/Motif Edition, Prentice Hall, 1994. (Tree source code available at ftp.x.org as /contrib/widgets/motif/mtree.trz).