ProfitPress Mega CDROM2 Shareware Freeware (MSDOS)(1992)(Eng)

home *** CD-ROM | disk | FTP | other *** search

/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / PROG / PASCAL / PNL006.ZIP / PNL006.TXT < prev next >

Wrap

Text File | 1991-03-17 | 62.6 KB | 1,692 lines

//////// // // // // // /// // // // // //// // // //////// // // // // // // //// // // // /// // // // // /////// Pascal NewsLetter Issue #6 March, 1991 Editor: Pete Davis The Programmer's Forum BBS is the home of PNL. It can be reached in Washington, DC at (202)966-3647. Information is available through the following locations: FidoNet: Pete Davis@1:109/138 GEnie: P.DAVIS5 BitNet: HJ647C@GWUVM & UE356C@GWUVM InterNet: HJ647C@GWUVM.GWU.EDU or UE356C@GWUVM.GWU.EDU Uucp: Pete.Davis@f138.n109.z1.fidonet.org Table of Contents Introduction ................................ 3 (P.D.) Returning Structured Data Using TP Functions. 5 (B.M.) Displaying an Integer with Commas, Revisited. 10 (N.P.) Chess-Ter ................................... 13 (P.D.) Searching ................................... 19 (K.S.) For Beginners ............................... 21 (B.G.) Conclusion .................................. 26 (P.D.) Key: ---- P.D. - Pete Davis : Editor-in-Chief R.M. - Richard Morris : Editor-Over-The-Pond B.G. - Bob Gowans : Columnist B.M. - Bill Madison : Contributing Writer N.P. - Nathan Phillips : Contributing Writer K.S. - Kelly Schwarzhoff : Contributing Writer Introduction Well, it's been quite a while since PNL005 and I apologize for the delay. Many of you know why it took so long, and for those of you who don't, I will give you my excuse. First of all, since this is going to remain a free newsletter in the foreseeable future, I have to put my priorities in order. Since money isn't going to be my priority, school is. I have decided to add to my course load so that I can graduate a semester earlier than planned. This has resulted in the addition of two credits bringing my total to 17. Also, I decided (not wisely) to take a graduate course. The additional two credits and the graduate course have taken up an enormous amount of extra time. On top of this I also work 20-30 hours a week. These, combined with an attempt to maintain my social life (very hard with school and work) has left little time for keeping the newsletter coming out at a regular interval. Right now I am in my spring break which will allow me a little time to get this issue out. I hope to get started on PNL007 before summer, but I just can't be sure. If the first half of this semester is any indication, PNL007 won't come out until about a week after summer vacation begins. Also, getting the issues out over summer won't be as easy as last summer as I am going to be taking some classes over the summer and working almost full time. Well, that's my excuse. Don't get me wrong, I love doing the newsletter, and if I didn't have to worry about school and work I would certainly be working much harder on it. I would like to bring up some very good news, though. One of my professors, Ray Thomas, who was my professor for some of my first classes in programming, will be retiring soon. Professor Thomas taught me a lot of what I know and is directly or indirectly responsible for several articles that I have written. He has also been very supportive of the newsletter. He has told me that after his retirement (the end of this semester) he will be writing articles now and then for the newsletter. This is very good news to me and I think many of you will be pleased. The introduction and conclusion areas are sort of my areas to ramble on about things related to the newsletter as opposed to Pascal specific things. So, to that end, here are some things I want to talk about. First of all: I love getting comments and suggestions about the newsletter. (Not quite as much as getting articles, but the comments help a lot.) So, keep them coming. Also, I've been thinking about dividing the newsletter into sections. Maybe having a beginners, moderate and advanced level areas. I'd like to hear comments on this idea. Would it help you find the stuff you want a little quicker? I feel like I have a million things to talk about. It has been so long since my last issue, but I would probably bore many of you. I will just add a little about what you can expect from this issue and then let you go on to the good stuff. - 3 - This issue I will start my series on Chess-Ter, a chess game written by me and 5 others. It's not an artificial intelligence chess program, but one that two people can play. I present it for it's application to Pascal, not AI. The first two or three installments of this article aren't going to go very in-depth and will only get the surface of certain parts of the program. The idea being that you, the reader, will tell me what parts interest you and confuse you, then in later issues I will go back and cover things in a more in-depth fashion. Just because of the size of the program, it is going to take a long time cover the whole thing and I want to get the whole program out to you, the readers, as quickly as possible. Anyway, read the article for more information. Bill Madison presents a method of Returning Structured Data Using Pascal Functions. Also, we have Displaying an Integer with Commas, Revisited. This piece, by Nathan S. Phillips is a return to a procedure that appeared in issue #2 of the PNL. He goes into new ways of doing the same thing and showing the good and bad aspects of each method. This is a great lesson in program optimization. Kelly Schwarzhoff, a high school sophmore, shows some methods of searching. a list. And Bob Gowans, my faithful companion comes through again with another column in the For Beginners section. Richard Morris' article has been dis-continued temporarily. We hope to have it continued as soon as possible. Well, that's about it, hope you enjoy this issue. - 4 - Returning Structured Data Using Turbo Pascal Functions by Bill Madison W. G. Madison & Associates, Ltd. 8425 Greenbelt Road, #101 P. O. Box 898 Greenbelt, MD 20770 (301)552-7234 CIS 73240,342 ABSTRACT Turbo Pascal is, without question, the development language of choice for microcomputer applications in which portability is not an overriding issue (C addicts to the contrary notwithstanding). Turbo Pascal, or any dialect of Pascal for that matter, has several serious shortcomings. One of the more important among these is Pascal's inability to establish structured data types (with the sole exception of strings) as a function return. This effectively precludes the writing of many types of packages in a programmer-friendly manner. This article explores a technique for circumventing the problem by using the mechanism of functions having returns of type POINTER or a variant thereof. Examples are shown, drawn from a COMPLEX unit which has been designed, written, and used by myself. INTRODUCTION AND MOTIVATION I was recently given an assignment by a client which involved extensive manipulation of complex numbers. This was not the first time this had occurred. Tired of re-inventing the wheel every time it occurred, and equally tired of making interminable procedure calls to evaluate a simple expression, he decided that there had to be a better way. IF ONLY TURBO PASCAL WOULD PERMIT FUNCTIONS TO RETURN STRUCTURED DATA TYPES!!! The result turned out even better than expected; a design methodology emerged which, when implemented, would work equally well for ANY structured data type. With minor modification, it would even work well with data types in which,ideally, the size of the actual data to be manipulated could not be determined until execution time; e.g., matrices, long strings (i.e., strings whose length exceeds 255 characters). To refresh your memory, complex numbers, which will be used to develop this discussion, are numbers of the form R + (i*I), where i = sqrt(-1)). In a Pascal environment, this inherently represents a RECORD structure: type ComplexBaseType = record Re, - 5 - Im : real; end; {ComplexBaseType} Mathematical rules exist which define the four basic arithmetic operations with respect to the complex numbers. Given these rules, other rules have been derived such that, if an operation exists for conventional REAL numbers an analogous rule exists for the COMPLEX numbers. Thus, one may speak of powers and roots of complex numbers, their trigonometric functions, etc. In order to define these operations to Pascal, they would either need to be defined in the native compiler or the compiler would need to be syntax extensible. Then one would be able to write, for example, C := A + B; where A, B, C have been declared to be type ComplexBaseType. Yet it is impossible to expect that the plethora of unusual data types which one might devise could be compiled in native mode. Further, syntax extensibility is a compiler attribute not found (unfortunately) in commercially available compilers. (The most recent commercially available compiler having any form of syntactic extensibility which I have seen was the FORTRAN for the CDC 1604, built during the mid-1960's.) An alternative, therefore, would be to permit the user to write functions implementing desired operations, which would return arbitrary data types as function results. Were this language feature available, and assuming that functions to combine two complex numbers were declared function CAdd(A, B : ComplexBaseType) : ComplexBaseType; function CSub(A, B : ComplexBaseType) : ComplexBaseType; function CMul(A, B : ComplexBaseType) : ComplexBaseType; function CDiv(A, B : ComplexBaseType) : ComplexBaseType; one could write the equivalent of E := (A + B * C) / D as E := CDiv(CAdd(A, CMul(B, C)), D); Clumsy as this might appear at first, it is infinitely more readable (in my opinion) than declarations of procedure CAdd(A, B : ComplexBaseType; var C : ComplexBaseType); procedure CSub(A, B : ComplexBaseType; var C : ComplexBaseType); - 6 - procedure CMul(A, B : ComplexBaseType; var C : ComplexBaseType); procedure CDiv(A, B : ComplexBaseType; var C : ComplexBaseType); and an evaluation of the expression as CMul(B, C, Temp); CAdd(A, Temp, Temp); CDiv(Temp, D, E); especially as one attempts to evaluate more complex expressions. Of course, we are still not out of the woods, because Turbo Pascal can't return structured values from functions! ONE POSSIBLE SOLUTION Suppose, instead of working with ComplexBaseType as defined above, we work with type Complex = ^ComplexBaseType; and then in addition to declaring our variables var A, B, C, D, E : Complex; we declare the functions as function CAdd(A, B : Complex) : Complex; function CSub(A, B : Complex) : Complex; function CMul(A, B : Complex) : Complex; function CDiv(A, B : Complex) : Complex; then we can write the above expression evaluation as E^ := CDiv(CAdd(A, CMul(B, C)), D)^; which, as we can see, is just as readable and convenient as the original (with the minor inconvenience of requiring the "^" symbol on each side of the replacement operator. Note, however, that since all operations are being performed by nested function calls, the normal rules of operator precedence are not applicable. All "operators" are of equal precedence. It is therefore incumbent on the programmer to assure that any required operator dependency is properly managed. If this approach of using pointer-type functions is taken, an additional step must be included. Note that a variable of type Complex - 7 - is actually a pointer. Unless a pointer is initialized with something to point to, strange things will occur very quickly when the program is executed. Therefore, each variable, in addition to being declared must be initialized. Pointer variables suggest (but do not require) that the things pointed to must be on the heap. Assume that we accept the suggestion, and agree to store all Complex data on the heap. Further, assume a function CInit, declared as function CInit(A : Complex) : boolean; which will return FALSE if and only if there is insufficient contiguous space left on the heap. Then, prior to the first reference to any of the variables, we would have a sequence of instructions like if not CInit(A) then {Do error recovery}; if not CInit(B) then {Do error recovery}; if not CInit(C) then {Do error recovery}; if not CInit(D) then {Do error recovery}; if not CInit(E) then {Do error recovery}; One additional requirement must be met to use this approach effectively; specifically, the storage of intermediate results. When a value is returned from a function in Turbo Pascal, that value is stored on a stack and is popped off as required. The stack maintenance code is generated by the compiler, as part of the compilation process. However, when we take over a part of the compiler's functionality, as we are doing here, we must also assume responsibility for keeping track of the structured values being returned. This is necessitated by the fact that the function returns are pointers to the returned values, and not the values themselves! This is most conveniently done by establishing one or more ring buffers, again probably (but not necessarily) on the heap. The actual structured value is then stored in the ring buffer, and the return from the Pascal function becomes the pointer value pointing into the ring. The size (i.e., the number of elements) of the ring buffer determines the maximum complexity of the expression to be evaluated. Theoretically it would be possible to write expressions whose evaluation would require storage of any desired number of temporary results. A more serious threat, however, lies in the evaluation of recursive procedure or function calls, in which a stack (or ring) of any size could be quickly exhausted. CONCLUSION While no perfect solution exists for the easy manipulation of structured data types within the confines of any dialect of the PASCAL programming language, a methodology has been suggested which, when properly applied, can approach this ideal. - 8 - The use of Pascal functions which accept and return pointer values and allocate data storage on the heap provides a mechanism for effectively and relatively easily and readably manipulating data structures of any degree of complexity. A WORKING EXAMPLE Following is the code for a unit I wrote to implement COMPLEX arithmetic using Turbo Pascal, along with the code for a program used to test the unit. The code for both the unit and the test program is available on many BBSs under the name SHCMPLX1.ZIP. I have also used this basic technique to implement a unit for the manipulation of long strings (up to 65517 characters), without having to allocate the full maximum allowable length for each long string declared. The code for both the LongString unit and its test program is available on many BBSs under the name SHLNGST1.ZIP. {Editor's note: The file SHCMPLX1.ZIP is included with this PNL006.ZIP file and the code mentioned in the article is found there.} - 9 - Displaying an Integer with Commas, Revisited by Nathan S. Phillips In the second issue of the PNL, I discussed a recursive method of displaying an integer with commas (12345 -> 12,345). The recursive procedure provided as an example at that time has several problems. First, being recursive, stack space is used for storage of parameter values and calls. The program has to keep track of all local variable values used in the procedure so that they can be restored when the next call returns. It takes time to perform these housekeeping tasks. Although in this particular example these are not major concerns, you should bear them in mind when contemplating more complex recursive routines. The second problem with the procedure is that it is fairly cryptic; anyone attempting to revise or debug the code would probably spend several minutes figuring out how the blasted thing works in the first place. More than likely, the person would then choose to rewrite the entire procedure, resulting in more lost time. As with the first point, this is not a major problem with the particular routine being considered, but with a larger piece of code the amount of wasted time could add up very quickly. Finally, since the procedure does the output internally, you must position the cursor before calling the procedure; the number with commas is then simply 'spit out' at that location. This makes it very difficult to do formatting such as right justification, because you don't know in advance (without doing additional calculations) how long the number will be once the commas are included. Also, to get the output to go somewhere besides the display, you have to modify the procedure! Not good programming practice at all. If it returned a string, we could then put the string wherever we want to, and with a simple Length() call, we would know how long it is. Wouldn't it be nice if this were a non-recursive, easily modified function which took the number as a parameter and returned a string which was the number with commas included? Well, let's make it so: function NumWithCommas(theNum : longint) : string; var nwcStr, { the working string } tempStr { a temporary string } : string; begin { function NumWithCommas } nwcStr := ''; { initialize working string } while theNum >= 1000 do { as long as we need more commas } begin { while theNum } - 10 - Str(theNum mod 1000, tempStr); { put the last 3 digits } { of theNum in tempStr } while Length(tempStr) < 3 do { pad tempStr with } tempStr := '0' + tempStr; { '0's on the left } nwcStr := ',' + tempStr + nwcStr; { add comma & digits } { to working string } theNum := theNum div 1000; { discard the 3 digits } { we just took care of } end; { while theNum } Str(theNum,tempStr); { now theNum is less than 1,000 } NumWithCommas := tempStr + nwcStr; { put first digits } { at the beginning } end; { function NumWithCommas } This function has very little overhead, is easier to revise and debug, and is generally more useful. (Sidebar to technically inclined: I tested both forms of this routine using Turbo Profiler and found, to my surprise, that the non-recursive function version shown here is faster by a small amount. I was sure that the string operations it uses would make it considerably slower - any ideas what this isn't so? I forced this function to write the result before returning, so the 'output slowdown' should have been the same for both routines.) Now, how does one go about using this new function? Suppose you wish to inform the user of the number of bytes that the current directory is taking up on the hard disk. A typical method is: writeln(bytesUsed:1, ' bytes used for directory ',dirName); which produces: 1348857 bytes used for directory FOO With NumWithCommas, you can dress up the output very easily: writeln(NumWithCommas(bytesUsed),' bytes used for directory', dirName); which produces: 1,348,857 bytes used for directory FOO - 11 - But the old recursive procedure could do that! Why did we go to the trouble of rewriting it? Suppose there are several directories for which you want to display size information in column format. With the old DisplayWithCommas, you had to settle for: for i := 1 to numDirs do begin for j := 1 to 8-Length(dirName[i]) do write(' '); write(dirName[i],' - '); DisplayWithCommas(bytesUsed[i]); writeln(' bytes'); end; which produces: FOO - 1,348,857 bytes LABELS - 243,567 bytes UTIL - 16,344,059 bytes FAKEDIR - 1,024 bytes Now with NumWithCommas as a function, you can do this: for i := 1 to numDirs do begin for j := 1 to 8-Length(dirName[i]) do write(' '); write(dirName[i],' - '); wcStr := NumWithCommas(bytesUsed[i]); for j := 1 to 10-Length(wcStr) do write(' '); writeln(wcStr,' bytes'); end; producing: FOO - 1,348,857 bytes LABELS - 243,567 bytes UTIL - 16,344,059 bytes FAKEDIR - 1,024 bytes The combination of commas and formatting makes it very easy for the user to determine at a glance the relative magnitude of each value. And the easier your program is for the user, the more likely it is to be used (and, hopefully, paid for). - 12 - Chess-Ter By Pete Davis Well, I mentioned in a previous issue that I would do this article and, after a good deal of procrastination, I finally got started on it. Part of the delay is just due to the volume of the program itself. The code is broken into 8 units and comes to over 4800 lines of code. This sheer volume makes it a little difficult to handle in the newsletter. I have decided to break up the article into either two or three parts, initially. The two or three parts would be sort of a quick overview and between those two or three, the entire source code would be released. For example, in this issue, I plan on talking about the CHESSTER.PAS, GLOBALS.PAS, KB1.PAS and DRAW_PCS.PAS. I will only release the source code for those parts of the program with this issue. Then, in the next issue, I will release the source code to the other parts of the program I discuss and, if necessary, I will release anything remaining in the third part. I am doing a rather brief overview at first so that I can get out the different parts of the program quickly. After the entire program has been released, I will back-track and talk about some of the more technical aspects of the program and discuss ways of improving the code and so-forth. First, I suppose I should provide some sort of background on Chess-Ter. Last semester I took a class called Software Engineering. The main thrust of the class was putting together large projects. I've thought about concentrating on that issue in a series in the newsletter, but unless I get some requests, I'm going to hold off on that. Anyway, about two weeks into the semester we got our assignment, which was due at the end of the semester. The project was a Chess program that two people could play. This is not an AI chess program, it only lets two people play. The AI part is left for you, if you dare. Anyway, I got into a group of 5 other programmers who turned out to be very hard working. Good thing, because I'm not and without the push from the rest of the group, a project like this would not have been done by me. So, I would first like to name all the authors and point out their contributions: Mark Friedman - Did most of the chess pieces and the board. He also did the Handle Moves Request and Handle Take-Back Request. Jessica Chestnut - Did most of the checks for legal moves. (A very impressive feat for someone who had never played chess until a couple days before the project was completed.) Akiko Okamoto - Did the Load and Save games file handling. - 13 - John Loux - Wrote the main keyboard interface and the central procedure of the program. Paul Sternal - Wrote the Replay procedures that allow for game replays. and Me - I did the Check for Check and Check for Check-Mate procedures. I also did the intro screen and the screen interface. (With the exception of the board and pieces.) That about covers the intro to the project. There are a few things I'd like to bring up, though. First of all, the program is copyrighted and the source code is released not just from me, but from the entire group (collectively known as The Pascal Team). Also, I had considered cleaning the program up before writing this, but then it occurred to me that leaving in some of the problems might be useful in discussion of improvements for the program. I hope to bring some improvements into the program through future issues. Well, let's get started. First of all, I guess I should discuss the main program file, CHESSTER.PAS. Not a whole lot to discuss. It includes all the necessary units: Globals (discussed later), CRT, KB1 (discussed later), DOS, and Draw_Pcs. The screen is initialized, the game is initialized, the board is drawn, text displayed and finally Get_Keyboard is called, which is an iterative procedure that keeps going until the game is quit. Then the endprompt is shown. Not a whole lot in the main program. For large projects it's a good idea to keep the main program itself rather small. This helps to enforce the idea of modularity, or breaking your programs into smaller pieces. The first unit I want to discuss is GLOBALS. GLOBALS contained all the type definitions and procedures which were common throughout the program. I want to point out that this wasn't always the case. This was the desired result, but sometimes it turned out that a procedure we thought would be used globally, turned out only to be used one place, or vica-versa. The representation of our board was, of course, a key concern, but even more important was the current state of the game. We felt the best way for all the different procedures to share information was to create a variable type of Game_State. The Game_State had everything from a 2 dimensional array of all the pieces on the board to the current move number, whose move it was and what mode the game was playing in. (A short note about the modes. The game has a novice and expert mode. The novice mode allows the ability to take back moves and find out what all the legal moves for a given piece are.) The game state also kept various flags about current moves. Along with the game_state there is also a move history which keeps track of all the moves made. This is basically an array of the Move_Type. The Move_Type contains the pieces from and to locations, - 14 - the piece color, the piece_type, what kind of piece was taken, if any, and what the move type was (i.e. castle, check, mate, and other exceptional conditions). Although it is usually considered bad practice to keep global variables, in this case we found it necessary and sometimes it is. We kept several things global: The current game state, the current move, the move_history and the list of legal moves for the current moving piece. Now I'd like to get into the graphics a bit. Here is something that is mentioned in the Turbo manual and has turned out to be a very useful feature. Instead of having the BGI files we needed loaded at run-time, we decided to have them linked in at compile-time. This has several advantages: First of all, it keeps you from having to keep track of more than one file in the run-time program. It also saves a bit of trouble, I feel. In this program we used EGA mode. This was done mainly because that was the only graphics I had and since I did a lot of the graphics, I had to have it compatible with my system. So, here's how we handle the compile-time linking of BGI files. (I also did this with the Gothic character set included with TP.) Since we are working with EGA, used the EGAVGA.BGI file. I changed this to an object file using BINOBJ.EXE. I then typed, from the DOS prompt, with EGAVGA.BGI and BINOBJ.EXE in the current directory: BINOBJ EGAVGA.BGI EGAVGA.OBJ EGAVGA This turns the .BGI into a .OBJ and gives it a public name of EGAVGA (Don't worry about that last part, just stick to using the part of the filename before the period and you should be fine.) I followed this by doing the same thing to the gothic character set: BINOBJ GOTH.CHR GOTH.OBJ GOTH This turns the .CHR file into a .OBJ file also. Then in the GLOBALS procedure I link both of these .OBJ files into the main program as follows: procedure EGAVGA; external; { The procedure name must match the Public name given above. } {$L EGAVGA.OBJ} { the $L, above actually links it in. } procedure GOTH; external; { Just like above: } {$L GOTH.OBJ} - 15 - That's all there is to it. You now have the .BGI files linked in. Now, to actually use those .BGI routines you need to register them with TP. This is all done in the InitScrn procedure in the GLOBALS.PAS file. Some of the other important procedures included the Prompt procedure which put a line of text on the 23rd line of the screen. This was basically used to send some sort of message to the user. There was also a beep procedure that went well with the prompt procedure. Then a Query procedure was added, which worked just like the prompt procedure, but then read in a line of text from the user so that a response could be returned. Then there is the Error_Display procedure which is like Prompt, but in a different color to help grab the user's attention. The next thing on our list is the InitGame procedure. Basically this is called everytime you start a new game. This initializes all the conditions in the game and finds out whether the user want's expert or novice mode. Also initial positions for all the pieces are set. This should all be very straight forward. One thing you might notice in the InitGame procedure is the very beginning. The code starting with SetFillStyle(8, Blue) through OutTextXY(370,220,'(C) ... this is the opening screen. Using the simple Gothic font and some easy to use graphic procedures, Turbo Pascal let's you do some very nice opening screens. The Convert_Rank and Convert_File procedures were used to convert the board positions (A1-H8) to screen pixel positions. This was necessary since we were using a board that was 8x8 in concept, but actually several hundred pixels in length and height. The Display_Move_History updates the Move_History that is shown on the screen. Basically it's a list of all move made since the game began. This, again, is done in a fairly straight-forward way, except for one thing. I used the assignment: directvideo:= false; before doing any screen writes. This allows you to write text into a graphics screen. The show_text procedure, like the Display_Move_History turns directvideo off. All it really does is displays the text on the screen, other than the move_history. It is straight-forward and easy to follow. The next unit I want to cover is the Draw_Pcs unit. This one is very simple to follow. It was more of a tedious routine to put together than a complicated routine. Basically you sit and draw your pieces one line at a time and keep looking at them on the screen until they look good. In this case, the pieces were drawn by Mark Friedman, - 16 - who spent a lot of time drawing the pieces out. I would like to point out one improvement we encountered when writing this. Originally Mark wrote the procedure using for-do loops and the putpixel procedure to draw the pieces. This turned out to be very slow, so we ended up replacing all the putpixels and for-do loops with lineto procedures. This resulted in a huge time savings. You'll notice that the squares are still drawn using the putpixel routine. We left this that way for the visual effects it provides. That's really all there is to the Draw_Pcs. The last unit we will be discussing in this issue is the KB1 unit. This Get_Keyboard procedure at the end of the unit is the center-piece for the entire program. It is where the user's input is handled. It checks to make sure certain keystrokes are valid for the current mode. (Expert or Novice). It takes care of check-mate. Basically the routine is centered around a repeat-until loop that reads the keyboard input and then uses a case statement to process different requests from the user. Going back to the beginning of the unit we have the Arrow_Moves procedure. This reads in the keypad arrows and uses them for cursor movement in the game. It also checks to make sure the user stays on the board and doesn't try to roam off. Following that are two Beep routines (Beep2 & Beep4) These, looking back, probably belong in the Globals unit with Beep, but we will discuss that later when we talk about ways to improve the program. The Select_A_Piece procedure changes the color of a piece on the board after the user has selected that piece to be moved. Following that is DeSelect which then turns the piece back to it's previous color. The Check_Move_Piece procedure takes care of picking up and moving pieces on the board. IT calls the logic procedures(Legal_Move) to see if the moves are legal. We'll get involved in the logic part in a later issue. The Check_Legal_Piece checks to see if the piece the user has selected is a piece on his side. And the final procedure is the Handle_New_Game_Request which basically re-initializes the game state and board. Now, I know what you're thinking. You think I've shot through this program without a whole lot of explanation and you're right. I want to give you a quick overview of everything first and when we've covered the entire program I will back-track and go in-depth into parts we've only touched on now. - 17 - The entire program is very large and represents a lot of work done by six people. There are errors and the code is not perfect, but I believe that showing some of the mistakes we made can help prevent you from making the same ones. - 18 - Searching By Kelly Schwarzhoff Internet schwarzhoff@f103.n914.z8.rbbs-net.org Rbbs-Net 8:914/103 Fidonet 1:125/41 For anyone who is planning on taking a Pascal class there comes a time when he/she must make a search program. For me that happened two weeks ago in my high school AP Computer Science class. I had to make a program that would search for a certain inventory part and print out the inventory or "not found" if there are none. In the following examples I assume you're using the following type definitions: list=record id:integer; inv:integer; end; parts=array[1..5000] of list; I also assume you have defined variable a to be a variable of type parts (this is the raw data) and a variable count to be of type integer (this is how many different parts there actually are). Finally, I expect the id #'s to be pre-sorted from smallest to biggest (see PNL #3 for an excellent article on sorting). There are two main type of searches. The easiest way is a sequential sort that simply goes through the list and will search for a particular number. Although the sequential sort is nice and easy, it is extremely slow. Luckily for us there is a faster (and harder) way called a binary search. Binary search requires the data to be sorted in order of the item-type you are searching for. The procedure will set two variables (called b and z in the program) to be at each end of the parts array. It will then create a variable mid that will equal the middle of b and z ( (b+z) div 2). It will then check to see what the value of the id number of mid is (a[mid].id) and make an if then else if check. If the number is equal to the number you're looking for (a[mid].id=look) then you found it and it will return that number. If the mid is greater than the number then it is in the lower side of your list in which case you set the right hand side variable to right below mid. If the mid is less than the number then the number you're looking for is in the lower side of your list in which case you set the left-hand variable to right above mid. This continues until the two variables either collide or you find the variable. If the id # you're looking for is never found the function will return -1. For those of you who want the technical speeds of the searches, sequential is on average an O(N/2) search and binary is an O(log2 N) search. - 19 - If you have any questions feel free to contact me at the listed network addresses. {Editor's Note: Two files included with PNL006.ZIP are SEQUENT.PAS and BINARY.PAS. These are related to this article. A note about the author. Kelly Schwarzhoff is a sophmore in high school. I bring this up, mostly to point out that the articles in this newsletter are not written by PhDs in Computer Science. One of the most common compliments about the newsletter is that it's written by regular people like you and me, so go ahead and send in an article!} - 20 - For Beginners by Bob Gowans In this issue of PNL I thought we could develop a programming project based on the knowledge we have obtained from previous issues of PNL. As wordprocessors are familiar to us all I have decided to build our project around text manipulation. First, it will involve counting the number of words in a line of text. Second, calculating the length of a line of text. Both procedures are obviously simplified versions of those a commercial wordprocessor would make use of to invoke word wrap and set text between left and right margins, however the principle of problem solving, program design and program coding is the same whether the project is large or small. Before running to the nearest PC and hastily churning out the code for our project lets stop and think a while about program design and any constraints we may have to impose on the program. Program constraints will be given, bearing in mind the knowledge that has been obtained from the last five articles in the beginners column. Obviously there may be better ways to implement the program than the way suggested, but we must write the program within the confines of what we know. It is not unusual for programmers to have constraints placed upon them - for example financial constraints could influence the implementation of one design over another. Wordcount/Line length - A line of text is to be processed, each word is followed by a single space including the last word in the line. The line is processed to determine the total number of words. We can assume that the line of text is entered by the user from the keyboard and at least one word will be entered. The result, the total number of words in a line is printed to the screen. In addition a count of the total number of characters in the line, including spaces, is calculated. A line length is then calculated in inches based on an assumption that 10 characters will be one inch in length. The design for this process must involve a loop that scans the text, looking for the single space between the words, it must also involve a counter to keep track of the number of spaces. How will the loop be terminated? ie. as the line of text is scanned how will the program know it has reached the end of the line. We can make the decision that the end of the line will include a space then a special character, % (percent). Also,the loop must make a count of all the characters in the line, excluding the final space and the special end of line character (%). Pseudo-code 1. read in first character 2. initialize variables updated in loop - 21 - 3. loop while there are characters in the line of text 4. process characters 5. read in next character 6. loopend 7. calculate total number of words 8. calculate length of line of text 9. write out total number of words 10. write out length of text Assuming that the character to be processed is held in the variable called character, step 3 can be refined as follows : 3.1 loop while character <> percent sign The end of each word is marked by a space so if the character being processed is a space we can update a variable spacecount by 1, if the character being processed is anything else we update the variable lettercount by one. 4.1 if character = space 4.2 then 4.3 update spacecount by one 4.4 else 4.5 update lettercount by one 4.6 ifend The variables spacecount and lettercount are initialized in step 2 and are further refined below: 2.1 set spacecount to zero 2.2 set lettercount to zero Step 7 does not really need refining as the total number of spaces is equivalent to the total number of words in the line of text. When the loop is terminated spacecount will contain the value for the total number of words. For the sake of clarity we will write step 7 as follows: 7.1 set totalwords to spacecount Step 8 however, requires a bit more thought. The length of a line of text in inches is given by the total number of characters divided by 10. The total number of characters would be calculated by adding lettercount and spacecount minus one (the last space on the line is not counted). This would give the total number of characters including spaces. To complete the calculation the total number of characters is divided by 10 and the result printed out, in inches, to 2 decimal places. 8.1 set totalcharacters to lettercount + spacecount - 1 8.2 set linelength to totalcharacters/10 - 22 - The final design is as follows: 1. read in first character 2.1 set spacecount to 0 2.2 set lettercount to 0 3.1 loop while character <> percent sign 4.1 if character = space 4.2 then 4.3 update spacecount by one 4.4 else 4.5 update lettercount by one 4.6 ifend 5. read in next character 6. loopend 7.1 set wordcount to spacecount 8.1 set totalcharacters to lettercount + spacecount - 1 8.2 set linelength to totalcharacters/10 9.1 writeout 'Total words in text line = ',totalwords 10. writeout 'Length of line of text = ',linelength,' inches' Implementation of the design The Pascal coding of the design should not present any problems as we have covered most of the issues before. However I would like to introduce constants into this particular code. Constants are used to give a fixed value to an identifier. The system uses constants such as Boolean values or the set of integer values, these are internal constants set by the system. Constants can also be named by the user as illustrated: const interest_rate = 0.15; The Pascal reserved word CONST must come before the constant definition. Constant definitions are placed, in order of program sequence, before variable declarations as you will notice in the code below. Notice also that the assignment symbol for a constant is simply an equals (=) sign and not the Pascal assignment symbol (:=). The advantages of using named constants are that you can make your code a lot more readable if you use them wisely. When using constants it is useful to bear in mind the possibility of your program being updated. In the example above, the constant definition of interest_rate could be used in a program that calculates loan repayments. We all know too well how interest rates fluctuate so it is advantageous to declare interest rate as a constant. When it comes to updating the program, as a new interest rate is given, we simply have to change the constant definition line. All references to interest_rate in the program are then automatically updated, saving you a lot of work! - 23 - Constructing a data table for the design: IDENTIFIER DESCRIPTION TYPE space the space character ' ' constant line_end the percent character '%' constant cpi characters per inch constant character characters input by user char spacecount counter of space characters integer lettercount counter of letter characters integer total_chrs holds total number of letters and spaces integer total_words holds total number of words integer line_length length in inches of 10 characters real Here's the code to our design: program process_line; {By R.Gowans 7/2/91 - Manchester Polytechnic Didsbury} {Calculates number of words in a line of text as input by the user and outputs the result to the screen. Calculates line length given there are 10 characters per inch and outputs results to screen.} const space = ' '; line_end = '%'; cpi = 10; var character : char; spacecount,lettercount,total_chrs,total_words : integer; line_length : real; begin writeln('Input a line of text, each word must be followed by a'); writeln('space,the line must be terminated by a pct sign (%)'); writeln; write('Enter line > '); read(character); spacecount := 0; lettercount := 0; while character <> line_end do begin if character = space then spacecount := spacecount + 1 else lettercount := lettercount + 1; - 24 - read(character) end; total_words := spacecount; total_chrs := lettercount + spacecount - 1; line_length := total_chrs/cpi; writeln; writeln('Total words in text line = ',total_words); writeln; writeln('Length of line = ',line_length:4:2,' inches') end. You will have probably noticed that there are a lot of 'What if's???' about this program and if it has raised some questions in your mind, well that is the intention. Some of the questions I hope you may be asking yourself are: 1. What if the character read in is not a space, letter or a percent sign? 2. What if the first character is a percent symbol? 3. What if there is more than one space between the words? You can probably think of more questions which will reveal the weaknesses of this program and it is fitting to be critical in order to make the best possible,positive modifications to a program. I will leave you to think about the question of data checking, it is an essential part of any non-trivial program. Try predicting what the program will do when you enter unusual data then try it out! A word of warning - be sure you know how to break out of a program if you are attempting the unpredictable, the usual sequence on a PC is to hold down the CTRL key and press c or break. - 25 - Conclusion Well, that about wraps up this rather hastily assembled issue of the newsletter. I'm sorry for taking so long and I hope to be able to do another issue before summer, but I can't promise anything. Either way, I plan on trying to make up for it this summer by putting out 4 or 5 issues over the summer. I really need your help. The readers who contribute really make this happen and unless I receive articles from the user, it's going to take longer and longer between issues. Eventually, if I have to carry the load of writing the entire newsletter, it will fade away. I don't want to see that happen, so please try to help out. Try to set aside a few hours on a weekend and put something together for us here. I'm still not too sure about what's in-store for the next issue. I haven't really thought about it too much. I will do more on Chess- Ter and surely Bob will be back with For Beginners. I hope to have Richard back writing his articles on Graphics in TP. I haven't published anything about TP6.0 because frankly, I haven't had a chance to use it myself, yet, and I haven't received anything from my readers on it, so if there are those of you that have gotten familiar with TP6.0, I'd sure like to see some reviews. Oh well, enough begging on my part. I'll leave the rest up to you guys. I'm off to complete what is left of my vacation. Hope you enjoyed the issue and I'll write to you in the next issue. _Pete Davis - 26 - The Pascal NewsLetter is Copyrighted by Pete Davis. Articles submitted by others are the property of the authors and are used with permission. They may not be treated seperately from this newsletter without the author's permission and thus maintain all distribution rules of the newsletter as a whole. It may be freely distributed in un-modified form, but no charge whatsoever may be incurred on the recipient. All code is provided 'as-is' with no guarantees whatsoever. The Pascal NewsLetter can be obtained from the following locations: GEnie : General Electric Network for Information Exchange. It is located in the IBMPC filelist. Simtel : Internet address: 26.2.0.74 or Simtel20.ARPA It is located in the <MSDOS.PASCAL> directory. Programmer's Forum : This is the home of the PNL. Each issue can be found in the PNL directory from the main area. The number is on the title page. If you would like to receive back issues of PNL directly from me, send a diskette and $2.00 for shipping. Don't forget to include your address. Send your order to: Peter Davis 4851 Brandywine St. NW Washington, DC 20016 If you are a SysOp that will regularly carry PNL and would like to have your bulletin board listed as such, here, send me a message either by postal mail or at one of the electronic addresses given on the title page, with your bulletin board's name, phone number, and your name. - 27 - The Pascal NewsLetter Distribution List BBS | Fidonet Address | Phone # --------------------------+----------------------+--------------- The Bored | 1:397/3 | (512) 303-0471 Classic City BBS | 1:370/10 | (404) 548-0726 Thieve's World BBS | 1:106/805 | (713) 463-8053 Hippocampus BBS | 1:141/205 | (203) 484-4621 Rogers State College | 1:170/711 | (918) 341-8982 The Foxtrot BBS | 1:272/26 | (914) 567-1814 Turbo City BBS | 1:208/2 | (209) 599-7435 Austin IEMUG/MIDI BBS | 1:382/14 | (512) 258-0626 Laser Publishers | 1:170/403 | (918) 438-2749 Fargo RBBS-PC | 1:10/8 | (701) 293-5973 Momentary Lapse of Reason | | (704) 327-6361 The Demon's Den | | (508) 433-2702 The Cannibal Cafe | | (508) 840-6589 IBM Tech FIDO | | (508) 433-6491 The User Friendly BBS | | (704) 323-8223 KHIRON Software-Mail Only | 3:640/378 | 61-7-878-1194 Beyound Frontiers BBS | 2:230/101 | (+45)8694-1609 Collision Theory | | (703) 503-9441 Merlin's Mailbox | 2:245/39 | Ed-Net 9600 | 1:153/734 | (604) 732-8877 EILC BBS | 1:3610/60 | (407) 676-2998 Polysyncronism BBS | | (708) 358-5104 (Name Unknown) | | (315) 592-7300 - 28 -