# shell archive created by dwjones on Mon Apr 1 03:57:14 PM CDT 2024 # To install this software on a UNIX compatable system (Linux or MacOS): # 1) create a directory (e.g. with the shell command mkdir project) # 2) change to that directory (e.g. with the command cd project), # 3) direct the remainder of this text to sh (e.g. sh < ../thisfile). # This will make sh create files in the new directory; it will do # nothing else (if you're paranoid, you should scan the following text # to verify this before you follow these directions). Then read README # in the new directory for additional instructions. # On other systems, extract files from this file using a text editor. # Each file is bracketed between two lines of xxxx. # The first line of xxxx contains a cat command giving the file name. cat > README <<\xxxxxxxxxx README FOR DEMO STACK ABSTRACTION WITH MULTIPLE POLYMORPHIC INSTANCES ===================================================================== this project will demonstrate a stack to show how big programs can be managed where the programs in question use polymorphic classes. TO BUILD THE PROJECT -------------------- The shell command `make demo` builds and runs a polymorphic stack demo program. All the demo does is output hello world, but it does so by pushing pieces on two different stacks and then popping and printing them. See `Makefile` for details on the relationships between the files included here See `.h` header files for the interface specifications for each stack class or subclass. FILES ----- * `README` -- this file * `Makefile` -- input to `make` for building this code distribution * `main.a` -- a main program to demonstrate * `stack.h` -- interface for abstract stack class (no implementation) * `arraystack.h` -- interface for array stack subclass * `arraystack.a` -- implementation of array stack subclass * `liststack.a` -- interface for linked list stack subclass * `liststack.h` -- implementation of linked list stack subclass AUTHORS ------- Douglas W. Jones and students from CS:2630 at the U of Iowa KNOWN BUGS ---------- The array-stack constructor would be more useful if it took a parameter, the size of the stack to be constructed. If this was done, each different array stack would have a different capacity. Ideally, class stack should define STACKERROR, an exception, and abuse of stacks should throw this exception. We have not talked about exception handling yet, so exception conditions are not tested and none are thrown. As a consequence, there is no checking for stack overflow. For array stacks, this can occur if the limit for each stack is exceeded. For list stacks, it occurs if the heap fills so that Malloc returns NULL. With this code, stack overflow will either produce nonsense results or lead to a bus trap. And, there is no checking for stack underflow. Popping from an empty stack will either return nonsense or cause a bus trap. xxxxxxxxxx cat > Makefile <<\xxxxxxxxxx # Makefile for the project demonstrating a stack with multiple instances # Author: Douglas W. Jones # Make uses sh, not bash, so we need to install the hawk and hawklink commands; # these definitions are lifted from the aliases in .bashrc # (If you try to use this makefile on a different system, you will need # to change the file names to where hawk and hawklink are installed there.) smal=~dwjones/bin/smal32 -P 45 -U ~dwjones/lib/hawk hawklink=~dwjones/bin/hawklink hawk=~dwjones/bin/hawk ########## # primary make target stackdemo.o: main.o arraystack.o liststack.o $(hawklink) -o stackdemo main.o arraystack.o liststack.o ########## # secondary make targets # the main program uses two different stack abstractions main.o: main.a stack.h arraystack.h liststack.h $(smal) main.a # class stack cannot be instantiated and has no code, so no make rules # class arraystack, a subclass of stack arraystack.o: arraystack.a stack.h arraystack.h $(smal) arraystack.a # class liststack, a subclass of stack liststack.o: liststack.a stack.h liststack.h $(smal) liststack.a ########## # Make utilities # demonsrate the program demo: stackdemo.o $(hawk) stackdemo.o # remove object and listing files clean: rm -f *.o *.l # create a shell archive of the project liststack=liststack.h liststack.a arraystack=arraystack.h arraystack.a stacks=stack.h $(arraystack) $(liststack) stackdemo.shar: README Makefile main.a $(stacks) shar README Makefile main.a $(stacks) > stackdemo.shar xxxxxxxxxx cat > main.a <<\xxxxxxxxxx TITLE "main.a by Douglas Jones -- exerciser for array and list stacks" ; A recursion-free solution to MP4 using several stacks. ; The stacks hold trees that have yet to be plotted on the screen. ; NOTE: There is no recursion here, it's all done with loops and stacks USE "hawk.h" USE "stdio.h" USE "stack.h" USE "arraystack.h" USE "liststack.h" INT MAIN S MAIN ; activation record for MAIN ;RETAD = 0 ARSIZE = 4 MAIN: STORES R1,R2 ADDSI R2,ARSIZE ; ============== ; -- A, make some stacks LIL R1,NEWARRAYSTACK JSRS R1,R1 ; -- stack for sizes of trees MOVE R13,R3 ; sizestack = newarraystack() LIL R1,NEWLISTSTACK JSRS R1,R1 ; -- stack for x coordinates MOVE R14,R3 ; xstack = newliststack() LIL R1,NEWLISTSTACK JSRS R1,R1 ; -- stack for y coordinates MOVE R15,R3 ; ystack = newliststack() ; here R13 = sizestack ; R14 = xstack ; R14 = ystack ; -- these stacks describe pending trees ; ============== ; -- B, get tree size from screen size LIL R3,TERMINFO LOAD R4,R3,TERMCOLS ; -- get termcols LOAD R5,R3,TERMROWS ; -- get termrows ; -- problem 1, what size fits? LIS R3,1 ; size = 1 ; here R3 = size ; -- size is always a power of 2 ; R4 = termcols ; R5 = termrows ; R6 = height then width ; R13,14,15 = stacks for size,x,y SIZELP: ; for (;;) { MOVESL R6,R3,1 ADDSI R6,-1 ; height = 2*size - 1 CMP R5,R6 BLT SIZEQT ; if (termrows < height) break SL R6,1 ; width = 2*height CMP R4,R6 BLT SIZEQT ; if (termcols < width) break SL R3,1 ; size = size * 2 BR SIZELP SIZEQT: ; } ; -- we computed one size too large SRU R3,1 ; -- parameter size = size/2 SR R4,1 ; -- parameter x = termcols/2 SR R5,1 ; -- parameter y = termrows/2 - size + 1 ; ============== ; -- C, schedule first tree to print ; here R3 = size ; -- size of the tree ; R4 = termcols ; -- x location of tree center ; R5 = termrows ; -- y location of gree center ; R13,14,15 = stacks for size,x,y MOVE R8,R4 MOVE R9,R5 ; -- move x and y temporarily MOVE R4,R3 ; -- parameter size MOVE R3,R13 ; -- parameter sizestack LOAD R1,R3,PUSH JSRS R1,R1 ; sizestack->push( sizestack, size ) MOVE R4,R8 ; -- parameter x MOVE R3,R14 ; -- parameter xstack LOAD R1,R3,PUSH JSRS R1,R1 ; xstack->push( xstack, x ) MOVE R4,R9 ; -- parameter y MOVE R3,R15 ; -- parameter ystack LOAD R1,R3,PUSH JSRS R1,R1 ; ystack->push( ystack, x ) ; ============== ; -- D, plot trees till stack is empty PLOTLOOP: ; for (;;) { ; here R13 = sizestack ; R14 = xstack ; R15 = ystack MOVE R3,R13 ; -- parameter sizestack LOAD R1,R3,EMPTY JSRS R1,R1 TESTR R3 BZR PLOTQUIT ; if (sizestack->empty(sizestack)) brk MOVE R3,R14 ; -- parameter xstack LOAD R1,R3,EMPTY JSRS R1,R1 TESTR R3 BZR PLOTQUIT ; if (xstack->empty( xstack )) break MOVE R3,R15 ; -- parameter ystack LOAD R1,R3,EMPTY JSRS R1,R1 TESTR R3 BZR PLOTQUIT ; if (ystack->empty( ystack )) break ; -- if any stack was empty we quit MOVE R3,R13 ; -- parameter sizestack LOAD R1,R3,POP JSRS R1,R1 ; MOVE R8,R3 ; size = sizestack->pop( sizestack ) MOVE R3,R14 ; -- parameter xstack LOAD R1,R3,POP JSRS R1,R1 MOVE R9,R3 ; x = sizestack->pop( xstack ) MOVE R3,R15 ; -- parameter ystack LOAD R1,R3,POP JSRS R1,R1 MOVE R10,R3 ; y = sizestack->pop( ystack ) ; here R8 = size ; R9 = x ; R10 = y ; -- characteristics of one tree ; R13,14,15 = stacks for size,x,y TESTR R8 BZS NOTREE ; if (size >= 1) { ; -- push left subtree attributes MOVE R3,R13 ; -- parameter sizestack MOVE R4,R8 ; SR R4,1 ; -- parameter size/2 LOAD R1,R3,PUSH JSRS R1,R1 ; sizestack->push( sizestack, size/2 ) MOVE R3,R14 ; -- parameter xstack MOVE R4,R9 SUB R4,R4,R8 ; -- parameter x - size LOAD R1,R3,PUSH JSRS R1,R1 ; xstack->push( xstack, x - size ) MOVE R3,R15 ; -- parameter ystack MOVE R4,R8 SR R4,1 ADD R4,R10,R4 ; -- parameter y + size/2 LOAD R1,R3,PUSH JSRS R1,R1 ; ystack->push( ystack, y + size/2 ) ; -- push right subtree attributes MOVE R3,R13 ; -- parameter sizestack MOVE R4,R8 ; SR R4,1 ; -- parameter size/2 LOAD R1,R3,PUSH JSRS R1,R1 ; sizestack->push(sizestack,size/2) MOVE R3,R14 ; -- parameter xstack MOVE R4,R9 ADD R4,R4,R8 ; -- parameter x + size LOAD R1,R3,PUSH JSRS R1,R1 ; xstack->push( xstack, x + size ) MOVE R3,R15 ; -- parameter ystack MOVE R4,R8 SR R4,1 ADD R4,R10,R4 ; -- parameter y + size/2 LOAD R1,R3,PUSH JSRS R1,R1 ; ystack->push( ystack, y + size/2 ) PLOTBRANCH: ; do { -- output size rows of /\ ; here R8 = size ; R9 = x ; R10 = y ; -- characteristics of one tree ; R13,14,15 = stacks for size,x,y MOVE R3,R9 SUB R3,R3,R8 ; -- parameter x - size MOVE R4,R10 ; -- parameter y LIL R1,PUTAT JSRS R1,R1 ; putat( x - size, y ) LIS R3,'/' ; -- parameter LIL R1,PUTCHAR JSRS R1,R1 ; putchar( '/' ) MOVE R3,R9 ADD R3,R3,R8 ADDSI R3,-1 ; -- parameter x + size - 1 MOVE R4,R10 ; -- parameter y LIL R1,PUTAT JSRS R1,R1 ; putat( x + size - 1, y - 1 ) LIS R3,'\' ; -- parameter LIL R1,PUTCHAR JSRS R1,R1 ; putchar( '\' ) ADDSI R10,-1 ; y = y - 1 -- move up ADDSI R8,-1 ; size = size - 1 BGT PLOTBRANCH ; } while (size > 0) NOTREE = PLOTLOOP ; } BR PLOTLOOP ; } PLOTQUIT: ; -- assert, some stack was empty ; ============== ; -- E, test that all stacks are empty MOVE R3,R13 ; -- parameter sizestack LOAD R1,R3,EMPTY JSRS R1,R1 TESTR R3 BZS PLOTBUG ; if (!sizestack->empty(sizestack) MOVE R3,R14 ; -- parameter xstack LOAD R1,R3,EMPTY JSRS R1,R1 TESTR R3 BZS PLOTBUG ; || !xstack->empty(xstack) MOVE R3,R15 ; -- parameter ystack LOAD R1,R3,EMPTY JSRS R1,R1 TESTR R3 BZR PLOTOK ; || (ystack->empty(xstack)) { PLOTBUG: LEA R3,STACKBUG LIL R1,PUTS JSRS R1,R1 ; puts( "stacks not all empty" ) PLOTOK: ; } ADDSI R2,-ARSIZE LOADS PC,R2 ; return STACKBUG: ASCII "stacks not all empty",0 END xxxxxxxxxx cat > stack.h <<\xxxxxxxxxx ; stack.h by Douglas W. Jones -- generic abstract stack interface ; an abstract class -- that is, it cannot be instantiated. ; subclasses of stack each will provide a constructor. ; see the subclass .h file for documentation ; All instances of stack have the following fields: EMPTY = 0 ; pointer to the empty method of this stack ; given nothing ; returns R3 -- zero if not empty, nonzero if empty ; may use R4-R7 PUSH = 4 ; pointer to the pop method of this stack ; given R3 -- stack to push on ; R4 -- word to push ; returns nothing ; may use R3-R7 POP = 8 ; pointer to the pop method of this stack ; given R3 -- stack to push on ; returns R3 -- a word popped from the stack ; may use R4-R7 ; each subclass may define other fields ; the total size of a stack object depends on which subclass it comes from xxxxxxxxxx cat > arraystack.h <<\xxxxxxxxxx ; arraystack.h by Douglas W. Jones -- array stack interface" ; an implementation of class stack using an array with a stack pointer ; each subclass of stack provides a constructor. EXT NEWARRAYSTACK ; given nothing ; returns R3 -- pointer to a new array stack instance ; may use R4-R7 ; the remainder of the interface definition is found in stack.h ; nothing is revealed here about the internal details of the implementation xxxxxxxxxx cat > arraystack.a <<\xxxxxxxxxx TITLE "arraystack.a by Douglas W. Jones -- array stack implementation" USE "hawk.h" USE "stdlib.h" USE "stack.h" ; the code here implements the stack interface ; configuration constants STACKSIZE= 10 ; stack size for this implementation, in words ; each stack object is a structure with 2 fields: ; All instances of stack have the following fields: ;EMPTY = 0 ; pointer to the empty method, see stack.h ;PUSH = 4 ; pointer to the push method, see stack.h ;POP = 8 ; pointer to the pop method, see stack.h ; additional fields defined for arraystack objects SP = 12 ; the stack pointer, address of first free word STACK = 16 ; first word of an array of stacksize words OBJSIZE = STACK + (STACKSIZE << 2) ;========== INT NEWARRAYSTACK; construct a new stack object, see arraystack.h ; given nothing ; returns R3 -- pointer to an initialized stack object ; wipes out R3-R7 ; AR for NEWARRAYSTACK ;RETAD = 0 ARSIZE = 4 NEWARRAYSTACK: STORES R1,R2 ADDSI R2,ARSIZE ; -- first, allocate a new stack object LIS R3,OBJSIZE ; -- parameter LIL R1,MALLOC JSRS R1,R1 ; retval = malloc( stacksize * 4 ) ; -- second, initialize the new object ; -- start with the method pointers LEA R4,ASEMPTY STORE R4,R3,EMPTY ; retval->empty = asempty -- the empty method LEA R4,ASPUSH STORE R4,R3,PUSH ; retval->push = aspush -- the push method LEA R4,ASPOP STORE R4,R3,POP ; retval->pop = aspop -- the pop method ; -- finish by making this new stack empty LEA R4,R3,STACK STORE R4,R3,SP ; retval->sp = &(retval->stack) ADDSI R2,-ARSIZE LOADS PC,R2 ; return retval ;========== ; ASEMPTY ; test to see if a stack is empty ASEMPTY: ; given R3 -- s, a stack to test ; returns R3 -- zero if not empty, nonzero if empty ; may use R4-R7 LEA R4,R3,STACK ; -- &(s->stack) LOAD R5,R3,SP ; -- s->sp SUB R3,R4,R5 ; temp = &(s->stack) - s->sp ; -- here, temp = 0 if empty, we want opposite BZS ASEZERO LIS R3,-1 ; -- tricky code: if it was nonzero, make it -1 ASEZERO: NOT R3 ; retval = (temp == 0) JUMPS R1 ; return retval ;========== ; ASPUSH ; push a word on the stack ; given R3 -- s, stack to push on ; R4 -- word to push ; returns nothing ; wipes out R3-R6 ASPUSH: LEA R5,R3,SP ; -- address of stack->mysp LOADS R6,R5 ; -- value of stack->mysp STORES R4,R6 ; *(s->mysp) = word to push ADDSI R6,4 ; s->mysp ++ STORES R6,R5 ; -- put s->mysp back JUMPS R1 ; return ;========== ; ASPOP ; pop a word from the stack ; given R3 -- s, stack to push on ; returns R3 -- a word popped from the stack ; wipes out R4-R6 ASPOP: LEA R5,R3,SP ; -- address of stack->mysp LOADS R6,R5 ; -- value of stack->mysp ADDSI R6,-4 ; s->mysp -- LOADS R3,R6 ; retval = *(s->mysp) STORES R6,R5 ; -- put s->mysp back JUMPS R1 ; return retval END xxxxxxxxxx cat > liststack.h <<\xxxxxxxxxx ; liststack.h by Douglas W. Jones -- linked list stack interface ; an implementation of class stack using a linked list ; each subclass of stack provides a constructor. EXT NEWLISTSTACK ; given nothing ; returns R3 -- pointer to a new list stack instance ; may use R4-R7 ; the remainder of the interface definition is found in stack.h ; nothing is revealed here about the internal details of the implementation xxxxxxxxxx cat > liststack.a <<\xxxxxxxxxx TITLE "liststack.a by YOUR NAME HERE -- linked list stacks" ; your code here! END xxxxxxxxxx