1 {\rtf1\ansi \deff4\deflang1033{\fonttbl{\f4\froman\fcharset0\fprq2 Times New Roman;}{\f5\fswiss\fcharset0\fprq2 Arial;}{\f11\fmodern\fcharset0\fprq1 Courier New;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;
\r
2 \red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;
\r
3 \red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}{\stylesheet{\widctlpar \f4\fs20 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\*\cs15 \additive\f11\fs18 \sbasedon10 UCase symbol;}{\*\cs16 \additive\i \sbasedon10
\r
4 Desired;}}{\info{\operator Kirill M. Katsnelson}{\creatim\yr1998\mo4\dy3\hr19\min6}{\revtim\yr1998\mo4\dy3\hr23\min9}{\version3}{\edmins2}{\nofpages4}{\nofwords770}{\nofchars4389}{\*\company MERA}{\vern57431}}\widowctrl\ftnbj\aenddoc\formshade \fet0
\r
5 \sectd \linex0\endnhere {\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang
\r
6 {\pntxta )}}{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\r
7 \pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \widctlpar \f4\fs20 {\b\f5\fs28 Introduction
\r
9 \par \tab \tab The OO-Browser Graphical Interface
\r
11 \par \tab This program demonstrates a dynamic tree-drawing
\r
12 \par \tab algorithm developed by Sven Moen. The algorithm is
\r
13 \par \tab published in "IEEE Software", July 1990, pp. 21-28.
\r
14 \par \tab If you desire more information than the description
\r
15 \par \tab given below, see the above-referenced article.
\r
17 \par \tab A number of the features mentioned herein are not
\r
18 \par \tab included in this version of the program.
\r
20 \par }{\b\f5\fs28 Algorithm
\r
22 \par \tab Unlike other algorithms, Moen's algorithm uses an
\r
23 \par \tab explicit representation of node and subtree contours
\r
24 \par \tab and it stores each contour as a polygon.
\r
26 \par \tab Trees with nodes of any polygonal shape can be drawn
\r
27 \par \tab compactly, and the data structure supports insert and
\r
28 \par \tab delete operations on subtrees. The results are tidy
\r
29 \par \tab trees and efficient relayouts when the tree changes.
\r
31 \par \tab In the Layout step, the tree is traversed in depth-first
\r
32 \par \tab fashion until the leaf nodes are reached. The contour
\r
33 \par \tab of each leaf node is formed by creating a linked list of
\r
34 \par \tab lines that wrap around the node's shape. This is the
\r
35 \par \tab LayoutLeaf step. As the return trip is made back to the
\r
36 \par \tab root, the contour of each interior node is formed by
\r
37 \par \tab joining the individual contours of each child. This Join
\r
38 \par \tab step involves a Merge step where the offset between
\r
39 \par \tab two neighboring contours is computed to avoid overlap.
\r
40 \par \tab Since the width of each subtree contour is known at
\r
41 \par \tab each step, each interior node is centered over its
\r
42 \par \tab children, and the subtree contour is extended to include
\r
43 \par \tab the interior node. This is the AttachParent step.
\r
45 \par \tab In a dynamic update operation (insert or delete), the
\r
46 \par \tab algorithm reuses the contours not influenced by the
\r
47 \par \tab change and updates them efficiently. When a given
\r
48 \par \tab node changes, subtree contours at higher levels must
\r
49 \par \tab be disassembled before the change. This is called
\r
50 \par \tab the Unzip step, which call RuboutLeaf, Split, and
\r
51 \par \tab DetachParent, all inverses of LayoutLeaf, Join, and
\r
52 \par \tab AttachParent, respectively. After the change is made,
\r
53 \par \tab the Zip step reassembles the contours by again calling
\r
54 \par \tab Layout, Join, and AttachParent.
\r
56 \par }{\b\f5\fs28 User Interface
\r
58 \par \tab This program offers an interactive environment for
\r
59 \par \tab creating and updating trees of arbitrary size. Trees
\r
60 \par \tab can be loaded from a file or created on-the-fly. You
\r
61 \par \tab can also save trees, and specify various layout and
\r
62 \par \tab animation options. Each feature is associated with
\r
63 \par \tab a menu item which is explained in the next section.
\r
65 \par \tab When invoking the program, you may specify a single
\r
66 \par \tab argument indicating the name of a tree file. This file
\r
67 \par \tab will be loaded upon startup. If you start the program
\r
68 \par \tab without arguments, the canvas will be blank.
\r
70 \par }{\b\f5\fs28 Tree Menu}{\f5
\r
72 \par \tab New Tree...\tab Create a new tree. You specify
\r
73 \par \tab \tab \tab a new root, and the existing tree,
\r
74 \par \tab \tab \tab if any, is deleted.
\r
76 \par \tab Load Tree...\tab Load a tree specification file.
\r
77 \par \tab \tab \tab (see the File Format section)
\r
79 \par \tab Save Tree...\tab Save a tree specification file.
\r
80 \par \tab \tab \tab (see the File Format section)
\r
82 \par \tab Quit\tab \tab Exits the program.
\r
84 \par }{\b\f5\fs28 Layout Menu}{\f5
\r
86 \par \tab Layout Spacing...
\r
87 \par \tab \tab \tab Displays a dialog that allows you
\r
88 \par \tab \tab \tab to change the spacing between nodes
\r
89 \par \tab \tab \tab on the same level and the spacing
\r
90 \par \tab \tab \tab between levels.
\r
92 \par \tab Align Nodes on Level
\r
93 \par \tab \tab \tab Adds a constraint to the layout
\r
94 \par \tab \tab \tab algorithm that forces all nodes
\r
95 \par \tab \tab \tab on the same level to have the same
\r
96 \par \tab \tab \tab x-position. This leads to truncation
\r
97 \par \tab \tab \tab of nodes if necessary. The maximum
\r
98 \par \tab \tab \tab node width is controlled by the
\r
99 \par \tab \tab \tab Level Spacing. By default, this is
\r
100 \par \tab \tab \tab disabled.
\r
102 \par }{\b\f5\fs28 Node Menu}{\f5
\r
104 \par \tab This popup menu is invoked by pressing and holding
\r
105 \par \tab the left mouse button on a node. This menu offers
\r
106 \par \tab several actions that can be performed on nodes.
\r
108 \par \tab Add Child\tab Add a child to the node. The new child
\r
109 \par \tab \tab \tab is added after the bottommost child.
\r
111 \par \tab Add Sibling Before
\r
112 \par \tab \tab \tab Add a sibling before this node.
\r
114 \par \tab Add Sibling After
\r
115 \par \tab \tab \tab Add a sibling after this node.
\r
117 \par \tab Collapse Node\tab Collapses or expands the subtree
\r
118 \par \tab Expand Node\tab beginning at the specified node.
\r
119 \par \tab \tab \tab This operation is similar to a
\r
120 \par \tab \tab \tab Delete operation, except that the
\r
121 \par \tab \tab \tab subtree is preserved so that you
\r
122 \par \tab \tab \tab can display it again. Collapsed
\r
123 \par \tab \tab \tab nodes are marked with a gray box.
\r
125 \par \tab Delete Node\tab Delete the subtree beginning at the
\r
126 \par \tab \tab \tab specified node.
\r
128 \par }{\b\f5\fs28 Tree File Format}{\f5
\r
130 \par \tab If you wish to load a file, you can load a file created
\r
131 \par \tab by the OO-Browser with the \{C-c d\}, (br-xbr) command.
\r
133 \par \tab Node labels are sequences of characters delimited by
\r
134 \par \tab newlines or end-of-file.
\r
136 \par \tab Files must begin with an OO-Browser Environment path
\r
137 \par \tab name. The next line must be a label, which indicates the
\r
138 \par \tab root node. Optionally, lists containing labels may
\r
139 \par \tab follow. Each child label is indented two spaces more
\r
140 \par \tab its parent. Lists of labels are nested to produce trees.
\r
142 \par \tab For example, a three-level binary tree is as follows:
\r
144 \par \tab \tab ^^c++-^^~/OOBR
\r
145 \par \tab \tab root node level1
\r
146 \par \tab \tab level2-1
\r
147 \par \tab \tab level3-1
\r
148 \par \tab \tab level3-2
\r
149 \par \tab \tab level2-2
\r
150 \par \tab \tab level3-3
\r
151 \par \tab \tab level3-4
\r
153 \par }{\b\f5\fs28 Help}{\f5
\r
155 \par \tab If you are reading this, chances are that you found the
\r
156 \par \tab Help button on the menubar.
\r
158 \par }{\b\f5\fs28 Author}{\f5
\r
160 \par \tab This program was written by Mark L. Stern during
\r
161 \par \tab the summer of 1990. It was redone by Bob Weiner for
\r
162 \par \tab use with the OO-Browser.
\r
164 \par \tab Stephan Zachwieja contributed the double-buffering
\r
165 \par \tab code used for smooth animations in this program.
\r
167 \par \tab The other authors have permitted Bob Weiner to distribute
\r
168 \par \tab the code freely as part of the OO-Browser.
\r
projects / packages / blob