ain@j.cc.purdue.edu (Patrick White) (06/26/88)
Submitted by: enea!kuling!jonasf@uunet.uu.net (Jonas Flygare)
Summary: Demo for visualizing binary trees.
Poster Boy: Patrick White (ain@j.cc.purdue.edu)
Archive Name: sources/amiga/volume5/sort.sh.Z
uncompiled.
NOTES:
Didn't compile it since it if Lattice source... don't know if it works
since I only got sources.
-- Pat White (co-moderator comp.sources/binaries.amiga)
ARPA/UUCP: j.cc.purdue.edu!ain BITNET: PATWHITE@PURCCVM PHONE: (317) 743-8421
U.S. Mail: 320 Brown St. apt. 406, West Lafayette, IN 47906
========================================
: This is a shar archive. Extract with sh, not csh.
: This archive ends with exit, so do not worry about trailing junk.
echo 'Extracting sort.doc'
sed 's/^X//' > sort.doc << '+ END-OF-FILE sort.doc'
XHere is a small program I wrote to demonstrate binary sorting for a friend
Xwho just could not visualize a binary tree being built up....
XI used the code in Programmer's Guide to the Amiga as a skeleton on which
Xto build the rest. The program is real simple, and modifying it to show
Xbinary searching too is real simple. (Left as an exercise for the reader..)
XAnyhow, I don't recommend any experienced programmers to download this,
Xsince it is trivial, but to those who want an easy-to-read example
Xshowing some basics about algorithms it might be useful.
X(I *know* I have used parts of the example code in the book, but
X i hope no-one will sue me for that.. ;-)
XSuggested litterature:
X
X
XRobert A. Peck:
X
XProgrammers Guide to the Amiga (But be prepared that there are quite
Xa lot of typos (i have 1:st edition..))
X
X
XDonald E. Knuth:
X
XFundamental Algorithms.
XSorting and Searching.
XSeminumerical Algorithms.
X
XCompiled with Lattice 4.0.
XI do not take any responsibility for my part of the code, but if you should
Xuse it when you write SuperLisp/ProLog for the Amiga, I would appre-
Xciate a copy.. ;-)
XJust in case You wonder who I am:
XJonas Flygare
XVaktargatan 32 F:621
X754 22 Uppsala
XSweden
X
XEmail: jonasf@kuling.UUCP or jonasf@kuling.uu.se if you got domains.
+ END-OF-FILE sort.doc
chmod 'u=rw,g=rw,o=r' 'sort.doc'
echo ' -rw-rw-r-- 1 jonasf 1164 Mar 13 02:27 sort.doc (as sent)'
echo -n ' '
/bin/ls -l sort.doc
echo 'Extracting sort.c'
sed 's/^X//' > sort.c << '+ END-OF-FILE sort.c'
X#include <exec/types.h> /* Yes, we actually need all these*/
X#include <intuition/intuition.h> /* header files.... */
X#include <graphics/gfxmacros.h>
X#include <math.h>
X#include <stdlib.h> /* for malloc */
X#include <string.h> /* for stcd_i */
X
X#define NORMALFLAGS (WINDOWSIZING | WINDOWDRAG | WINDOWCLOSE | WINDOWDEPTH)
X
X#include "WBwindow.h" /* Window definitions */
X#include "event.c" /* Handle events */
X
Xstruct Window *w; /* Argh! Global variables.. */
Xstruct RastPort *rport; /* But I'll look the other way */
Xint sortnumber; /* today.. */
X
Xextern struct Window *OpenWindow(); /* I copied this straight out of */
Xint GfxBase; /* the book.. */
Xint IntuitionBase;
X
Xmain(argc, argv) /* Added optional argument */
Xint argc; /* which should be an integer */
Xchar *argv[]; /* No error check, so beware */
X{
X struct IntuiMessage *msg;
X LONG result;
X if (argc > 1){ /* Decide wether user typed */
X stcd_i(argv[1], &sortnumber); /* optional arg or not */
X }
X else
X sortnumber=1000; /* default = 1000 */
X
X /* Open libraries, windows, etc.. */
X
X GfxBase = OpenLibrary("graphics.library", 0);
X if(GfxBase == 0)
X {
X printf("Error occured opening Graphics..\n");
X exit(10);
X }
X IntuitionBase = OpenLibrary("intuition.library", 0);
X if(IntuitionBase == 0)
X {
X printf("Error occured opening Intuition..\n");
X exit(15);
X }
X
X w = OpenWindow(&myWindow); /* defined in window.h.. */
X if (w == 0)
X {
X printf("This window couldn't be opened..\n");
X exit(20);
X }
X
X /* Done that, now what? Oh, yes, locate RastPort.. */
X
X rport = w->RPort;
X
X redraw(); /* Ok, all done, draw my graphics. */
X
X WaitPort(w->UserPort);
X /* Wait for messages on port */ /* Thanks Peck.. ;-) */
X
X while(1) /* until doomsday */
X /* (Which soon might be here.. ) */
X {
X msg = (struct IntuiMessage *)GetMsg(w->UserPort);
X handleit:
X result = HandleEvent(msg->Class); /* event1.c */
X if(result == 0) /* Got CLOSEWINDOW */
X break;
X msg = (struct IntuiMessage *)GetMsg(w->UserPort);
X
X if(msg != 0)
X goto handleit;
X }
X /* The above code handles some messages for handling the window */
X /* Swiped from the book */
X CloseWindow(w); /* Doomsday! */
X CloseLibrary(IntuitionBase); /* Close business and go home. */
X CloseLibrary(GfxBase); /* Or something like that.. */
X}
X
X /* Node used in my binary tree. Contains a value and */
X /* two pointers. */
X
Xtypedef struct stree {
X int value;
X struct stree *right;
X struct stree *left;
X } mtree, *mtreep;
X
X /* This shouldn't really be handled like this.. No need to redraw*/
X /* window when moved.. */
Xredraw()
X{
X void gsort();
X mtreep stree;
X int sx=320, sy=1, dist=150, rval, i;
X unsigned seed;
X seed=45;
X stree=(mtreep)malloc(sizeof(mtree)); /* Create first node */
X stree->right=stree->left=NULL; /* init pointers */
X stree->value=rand()%(sortnumber/2); /* get starting value */
X for (i=0;i<sortnumber; i++) /* create all other values*/
X {
X rval=rand()%(sortnumber/2);
X gsort(stree, rval, sx, sy, dist); /* insert into tree */
X }
X}
X
Xvoid gsort(tree, value, x, y, dist)
Xmtreep tree;
Xint value;
Xint x;
Xint y;
Xint dist;
X{
Xif (y>200) return; /* Check against bounds */
Xif (value==tree->value) return; /* No action if match */
Xif ((x<1)||(x>639)) return; /* hit borders */
Xif (tree->value<value) /* insert to left? */
X{
X if (tree->left==NULL) /* shall I *insert* it??? */
X { /* yes */
X tree->left=(mtreep)malloc(sizeof(mtree)); /* create node */
X tree->left->value=value; /* put value there*/
X tree->left->left=tree->left->right=NULL; /* init pointers*/
X Move(rport, x, y); /* display */
X Draw(rport, x-dist, y+10);
X }
X else
X gsort(tree->left, value, x-dist, y+10, dist/2); /* recurse down*/
X } /* left branch */
X else
X {
X if (tree->right==NULL) /* Same for right*/
X { /* side..*/
X tree->right=(mtreep)malloc(sizeof(mtree));
X tree->right->value=value;
X tree->right->left=tree->right->right=NULL;
X Move(rport, x, y);
X Draw(rport, x+dist, y+10);
X
X }
X else
X gsort(tree->right, value, x+dist, y+10, dist/2);
X }
X}
+ END-OF-FILE sort.c
chmod 'u=rw,g=rw,o=r' 'sort.c'
echo ' -rw-rw-r-- 1 jonasf 3985 Mar 13 02:21 sort.c (as sent)'
echo -n ' '
/bin/ls -l sort.c
echo 'Extracting WBwindow.h'
sed 's/^X//' > WBwindow.h << '+ END-OF-FILE WBwindow.h'
Xstruct NewWindow myWindow =
X{
X 0, /* Leftedge for window. Measure: pixels */
X 0, /* Topedge for window, Measure: lines. */
X 640,255, /* Width, Height.. */
X -1, /* detailpen color */
X -1, /* Blockpen color */
X (CLOSEWINDOW|NEWSIZE|REFRESHWINDOW),
X (SMART_REFRESH|NORMALFLAGS|GIMMEZEROZERO),
X NULL, /* Firstgadget, none here */
X NULL, /* Checkmark, none here. */
X "Binary Sorting", /* Window Title.. */
X NULL, /* Pointer to screen if NOT WorkBench window */
X NULL, /* Pointer to bitmap if superbitmap. */
X 10,10, /* Minimum width, height. */
X 640, 255, /* Maximum height, width.. */
X WBENCHSCREEN /* Type of screen. */
X };
X/* Change 255 to 200 if not PAL AMIGA's... */
+ END-OF-FILE WBwindow.h
chmod 'u=rw,g=rw,o=r' 'WBwindow.h'
echo ' -rw-rw-r-- 1 jonasf 670 Mar 13 02:21 WBwindow.h (as sent)'
echo -n ' '
/bin/ls -l WBwindow.h
echo 'Extracting event.c'
sed 's/^X//' > event.c << '+ END-OF-FILE event.c'
X/* Event1.c */
X
XHandleEvent(class)
X LONG class;
X{
X switch(class)
X {
X case CLOSEWINDOW:
X return(0);
X /* Peck, you put a break here.. Can never reach it..*/
X case NEWSIZE:
X case REFRESHWINDOW:
X /* redraw not needed here.. */
X break;
X default:
X break;
X }
X return(1);
X}
+ END-OF-FILE event.c
chmod 'u=rw,g=rw,o=r' 'event.c'
echo ' -rw-rw-r-- 1 jonasf 233 Mar 13 02:21 event.c (as sent)'
echo -n ' '
/bin/ls -l event.c
exit 0