callahan@gondor.cs.psu.edu (Paul B. Callahan) (11/02/88)
The follow shar file contains the code for NeWS window program that allows
the user to "edit" binary search trees. It is contained in the files
treeedit.c, and treeedit.cps. The executable csh file cctreeedit will
compile it into treeedit if your system is configured in the same way
as the one I used.
The editor is easy to use.
The default initial tree is just a single node.
The left mouse button causes a tree rotation on the edge
going into a node, if it is clicked directly on the node.
If it is clicked far away, it allows gradual movement of
the current node.
The middle mouse button is used to select the node it is
clicked on as the current node.
The right button causes insertion of a node in a place
determined by the x coordinate of the mouse location.
Finally, the screen button DELETE deletes the current node.
When the window is zapped, the c program outputs an RPN
expression for the tree to stdout.
This sort of expression can also be input as the current
tree using the -i option.
Have fun, and reply with any feedback or suggestions.
-----------------------cut here----------------------
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
# cctreeedit
# treeedit.c
# treeedit.cps
# This archive created: Mon Oct 31 21:05:54 1988
export PATH; PATH=/bin:/usr/bin:$PATH
if test -f 'cctreeedit'
then
echo shar: "will not over-write existing file 'cctreeedit'"
else
cat << \SHAR_EOF > 'cctreeedit'
cps treeedit.cps
cc -o treeedit treeedit.c /usr/NeWS/lib/libcps.a -I/usr/NeWS/include
SHAR_EOF
chmod +x 'cctreeedit'
fi
if test -f 'treeedit.c'
then
echo shar: "will not over-write existing file 'treeedit.c'"
else
cat << \SHAR_EOF > 'treeedit.c'
#include <stdio.h>
#include "treeedit.h"
#define MaxNodes 1000
#define MaxCol 1
#define MaxRow 1
struct bst {
struct bst *left;
struct bst *right;
int rank;
int depth;
};
typedef struct bst * item;
item stack[MaxNodes];
int StackPtr;
initstack() {StackPtr=0;}
push(node)
item node;
{
if (StackPtr>=MaxNodes) {
printf("Stack Overflow\n");
exit(1);
}
else stack[StackPtr++]=node;
}
pop(node)
item *node;
{
if (StackPtr==0) {
printf("Stack Underflow\n");
exit(1);
}
else *node=stack[--StackPtr];
}
construct() {
struct bst *node,*nodel,*noder;
char c;
while ((c=getchar())!='\n') {
node=(struct bst *) malloc(sizeof(struct bst));
node->left=NULL;
node->right=NULL;
if (c=='.') {
push(node);
}
else if (c=='l') {
pop(&nodel);
node->left=nodel;
push(node);
}
else if (c=='r') {
pop(&noder);
node->right=noder;
push(node);
}
else {
pop(&noder);
node->right=noder;
pop(&nodel);
node->left=nodel;
push(node);
}
}
}
findxy(root,rank,depth,maxdepth)
struct bst *root;
int *rank,depth,*maxdepth;
{
if (root!=NULL) {
if (depth>*maxdepth) *maxdepth=depth;
findxy(root->left,rank,depth+1,maxdepth);
root->rank=*rank;
root->depth=depth;
(*rank)++;
findxy(root->right,rank,depth+1,maxdepth);
}
}
draw(id,root)
struct bst *root;
int id;
{
cps_drawnode(id,root->rank,root->depth);
if (root->left!=NULL) {
cps_drawedge(id,
root->rank,root->depth,
root->left->rank,root->left->depth);
draw(id,root->left);
}
if (root->right!=NULL) {
cps_drawedge(id,
root->rank,root->depth,
root->right->rank,root->right->depth);
draw(id,root->right);
}
}
postout(root)
struct bst *root;
{
int typenode;
static char nodechar[]=".rlb";
typenode=0;
if (root->left!=NULL) {
postout(root->left);
typenode+=2;
}
if (root->right!=NULL) {
postout(root->right);
typenode++;
}
printf("%c",nodechar[typenode]);
}
main(argc,argv)
char **argv;
{
char c;
struct bst *root;
int maxdepth, rank;
struct bst *rotabout,*newrot,*tempnode,*next,*parent;
struct bst **insplace;
int id,cnum;
int opt,done,x,rotx,tempx;
float geomx;
if (ps_open_PostScript()==0) {
fprintf(stderr,"No NeWS is bad news\n");
exit(1);
}
ps_flush_PostScript();
opt=0;
while (--argc>0) opt=((++argv)[0][0]=='-');
if (!opt) {
root=(struct bst *) malloc(sizeof(struct bst));
root->left=NULL;
root->right=NULL;
}
else if (argv[0][1]=='i') {
done=0;
while (!done) {
initstack();
construct();
pop(&root);
if (StackPtr>0) printf("Not a tree\n"); else done=1;
}
}
else {
fprintf(stderr,"invalid option %c\n",argv[0]);
exit(-1);
}
rotabout=root;
rank=0;
maxdepth=0;
findxy(root,&rank,0,&maxdepth);
cps_initwindow(rank-1,maxdepth,rotabout->rank,rotabout->depth);
while (!psio_error(PostScriptInput)) {
if (cps_damage(&id)) {
draw(id,root);
cps_Wcirc(id,rotabout->rank,rotabout->depth);
cps_exit(id);
}
else if (cps_rightbutton(&id,&geomx)) {
insplace=&root;
while ((*insplace)!=NULL) {
if ((float) ((*insplace)->rank) > geomx)
insplace=&((*insplace)->left);
else insplace=&((*insplace)->right);
}
*insplace=(struct bst *) malloc(sizeof(struct bst));
(*insplace)->left=NULL;
(*insplace)->right=NULL;
rank=0;
maxdepth=0;
findxy(root,&rank,0,&maxdepth);
cps_clearandrescale(id,rank-1,maxdepth);
cps_exit(id);
}
else if (cps_midbutton(&id,&geomx)) {
x = (int) (geomx+0.5);
rotx=rotabout->rank;
next=root;
while (next!=NULL) {
tempnode=next;
tempx=tempnode->rank;
if ((tempx > x) && (tempx > rotx)) next=tempnode->left;
else if ((tempx < x) && (tempx < rotx)) next=tempnode->right;
else next=NULL;
}
while (rotabout!=tempnode) {
cps_Bcirc(id,rotabout->rank,rotabout->depth);
pop(&rotabout);
cps_Wcirc(id,rotabout->rank,rotabout->depth);
}
while (rotabout->rank!=x) {
cps_Bcirc(id,rotabout->rank,rotabout->depth);
push(rotabout);
if (rotabout->rank>x) rotabout=rotabout->left;
else rotabout=rotabout->right;
cps_Wcirc(id,rotabout->rank,rotabout->depth);
}
cps_exit(id);
}
else if (cps_delbutton(&id)) {
if ((root->left!=NULL) || (root->right!=NULL))
switch((rotabout->left!=NULL)*2+(rotabout->right!=NULL)) {
case 0:
pop(&tempnode);
if (tempnode->left==rotabout) tempnode->left=NULL;
else tempnode->right=NULL;
break;
case 1:
if (root==rotabout) root=rotabout->right;
else {
pop(&tempnode);
if (tempnode->left==rotabout) tempnode->left=rotabout->right;
else tempnode->right=rotabout->right;
}
break;
case 2:
if (root==rotabout) root=rotabout->left;
else {
pop(&tempnode);
if (tempnode->left==rotabout) tempnode->left=rotabout->left;
else tempnode->right=rotabout->left;
}
break;
case 3:
parent=rotabout;
tempnode=parent->left;
if (tempnode->right==NULL) parent->left=tempnode->left;
else {
while (tempnode->right!=NULL) {
parent=tempnode;
tempnode=parent->right;
}
parent->right=tempnode->left;
}
break;
}
initstack();
rotabout=root;
maxdepth=0;
rank=0;
findxy(root,&rank,0,&maxdepth);
cps_clearandrescale(id,rank-1,maxdepth);
cps_exit(id);
}
else if (cps_get_comm(&id,&cnum)) {
switch(cnum) {
case 0:
if (StackPtr>0) {
cps_Bcirc(id,rotabout->rank,rotabout->depth);
pop(&rotabout);
cps_Wcirc(id,rotabout->rank,rotabout->depth);
}
break;
case 1:
if ((rotabout->left)!=NULL) {
push(rotabout);
cps_Bcirc(id,rotabout->rank,rotabout->depth);
rotabout=rotabout->left;
cps_Wcirc(id,rotabout->rank,rotabout->depth);
}
break;
case 2:
if ((rotabout->right)!=NULL) {
push(rotabout);
cps_Bcirc(id,rotabout->rank,rotabout->depth);
rotabout=rotabout->right;
cps_Wcirc(id,rotabout->rank,rotabout->depth);
}
break;
case 3:
if (StackPtr>0) {
pop(&newrot);
if (StackPtr==0) root=rotabout;
else {
pop(&tempnode);
push(tempnode);
if ((tempnode->right)==newrot) tempnode->right=rotabout;
else tempnode->left=rotabout;
}
if (newrot->left==rotabout) {
newrot->left=rotabout->right;
rotabout->right=newrot;
}
else {
newrot->right=rotabout->left;
rotabout->left=newrot;
}
rank=0;
maxdepth=0;
findxy(root,&rank,0,&maxdepth);
cps_clearandrescale(id,rank-1,maxdepth);
}
break;
}
cps_exit(id);
}
else if (cps_done() || psio_eof(PostScriptInput)) break;
}
postout(root);
printf("\n");
}
SHAR_EOF
fi
if test -f 'treeedit.cps'
then
echo shar: "will not over-write existing file 'treeedit.cps'"
else
cat << \SHAR_EOF > 'treeedit.cps'
#define LMB_TAG 1
#define DAMAGE_TAG 2
#define DONE_TAG 3
#define MMB_TAG 4
#define RMB_TAG 5
#define DELB_TAG 6
cdef cps_initwindow(int sx,int sy,int xrot,int yrot)
systemdict /Item known not { (NeWS/liteitem.ps) run } if
/LMB /LeftMouseButton def
/MMB /MiddleMouseButton def
/RMB /RightMouseButton def
yrot xrot
userdict begin /xrot exch def /yrot exch def end
/downeventinterest {/DownTransition ClientCanvas eventmgrinterest} def
/startinput {
/ButtonMgr[
LMB {LMB_TAG getdirection} downeventinterest
MMB {MMB_TAG getgeomx} downeventinterest
RMB {RMB_TAG getgeomx} downeventinterest
]forkeventmgr store
} def
/repair {
DAMAGE_TAG tagprint
uniquecid dup typedprint
[exch cidinterest] forkeventmgr
waitprocess pop
} def
/makescale {
/y exch def /x exch def
4 2 roll pop pop
y 0.5 add div exch
x 1.5 add div exch scale
0.01 setlinewidth
0 y 0.5 add translate
1 -1 scale
0.75 0.25 translate
} def
/TreeWindow DefaultWindow
dictbegin
/ScaleX sx def
/ScaleY sy def
/DelButtonHeight 45 def
/DelButtonWidth 60 def
/FrameLabel (Tree) def
/ButtonMgr null def
dictend
classbegin
/CreateClientCanvas {
/CreateClientCanvas super send
/items 1 dict dup begin
/DelButton (Delete) {DELB_TAG screenbutton} FrameCanvas
DelButtonWidth 0 /new ButtonItem send
dup /ItemBorderColor 0 0 0 rgbcolor put
def
end def
/itemmgr items forkitems def
} def
/RescaleCanvas {
/ScaleY exch def
/ScaleX exch def
setcanvas
[1 0 0 1 0 0] setmatrix
0 exch translate
initclip clippath pathbbox
ScaleX ScaleY makescale
currentcanvas reshapecanvas
} def
/ShapeClientCanvas {
gsave
/ShapeClientCanvas super send
currentcanvas
FrameCanvas setcanvas
FrameWidth 2 div
DelButtonWidth 2 div sub
BorderBottom 5 add /move
window /items get /DelButton get send
setcanvas
grestore
} def
/PaintClient { 1 fillcanvas
repair
/paint items /DelButton get send
} def
/PaintIcon { 0.75 0.498 0.196 rgbcolor fillcanvas
repair } def
/flipiconic {
/flipiconic super send
Iconic? IconCanvas /Retained get and {/paint self send} if
} def
/move {
Iconic? {IconHeight sub} if
/move super send
} def
/DestroyClient {
itemmgr killprocess
ButtonMgr killprocess
DONE_TAG tagprint
} def
/ForkFrameEventMgr{
/ForkFrameEventMgr super send
startinput
} def
/ClientPath {
4 copy
rectpath
DelButtonHeight sub
0 DelButtonHeight translate
ScaleX ScaleY
makescale
} def
/IconPath {
4 copy
rectpath
ScaleX ScaleY
makescale
} def
classend def
/window framebuffer /new TreeWindow send def
/reshapefromuser window send
/map window send
/getdirection {
ClientCanvas setcanvas
tagprint uniquecid dup typedprint
exch
begin
YLocation userdict /yrot get sub dup mul
XLocation userdict /xrot get sub 3 div dup mul add 0.09 lt
{3}
{YLocation userdict /yrot get gt
{XLocation userdict /xrot get lt {1} {2} ifelse}
{0} ifelse} ifelse
end
typedprint
[exch cidinterest] forkeventmgr
waitprocess pop
} def
/getgeomx {
ClientCanvas setcanvas
tagprint uniquecid dup typedprint
exch
begin
XLocation
end
typedprint
[exch cidinterest] forkeventmgr
waitprocess pop
} def
/screenbutton {
window begin
ClientCanvas setcanvas
tagprint uniquecid dup typedprint
[exch cidinterest] forkeventmgr
waitprocess pop
end
} def
cdef cps_get_comm(int id, int cnum) => LMB_TAG(id,cnum)
cdef cps_midbutton(int id, float geomx) => MMB_TAG(id,geomx)
cdef cps_rightbutton(int id, float geomx) => RMB_TAG(id,geomx)
cdef cps_delbutton(int id) => DELB_TAG(id)
cdef cps_damage(int id) => DAMAGE_TAG(id)
cdef cps_done() => DONE_TAG()
cdef cps_exit(int id)
id {exit} sendcidevent
cdef cps_clearandrescale(int id, int sx, int sy)
id {
DelButtonHeight ClientCanvas sx sy /RescaleCanvas window send
0 IconCanvas sx sy /RescaleCanvas window send
ClientCanvas setcanvas
gsave
[1 0 0 1 0 0] setmatrix
initclip clippath pathbbox
0 DelButtonHeight translate
DelButtonHeight sub
rectpath 1 setgray fill
grestore
repair
pause} sendcidevent
cdef cps_drawedge(int id, int x1, int y1, int x2, int y2)
id {
x1 y1 moveto x2 y2 lineto 0 setgray stroke
pause} sendcidevent
cdef cps_drawnode(int id, int x,int y)
id {
gsave x y translate 3 1 scale
0 0 0.25 0 360 arc 0 setgray fill grestore
pause} sendcidevent
cdef cps_Wcirc(int id,int x,int y)
id {
gsave x y translate 3 1 scale
0 0 0.1 0 360 arc 1 setgray fill grestore
userdict begin
/xrot x def
/yrot y def
end
pause} sendcidevent
cdef cps_Bcirc(int id,int x,int y)
id {
gsave x y translate 3 1 scale
0 0 0.1 0 360 arc 0 setgray fill grestore
pause} sendcidevent
SHAR_EOF
fi
exit 0
# End of shell archive