REALbasic University Resources: RBU: Glossary Defines common REALbasic programming terms   Archives Previously published columns Translations: Dutch Courtesy of Floris van Sandwijk   Japanese Courtesy of Kazuo Ishizuka   Chinese Courtesy of Dong Li   RBU Translation Guide Information on Translating RBU into other languages Books: Matt's Book (2nd Edition!) Ideal for experienced programmers   Erick's Book Best for beginning programmers Websites: Mother Ship The publisher of REALbasic   RB Webring Links to hundreds of REALbasic websites   RESExcellence Another REALbasic programming column   REALbasic Developer Magazine The premiere source for REALbasic instruction. REALbasic University is Sponsored by Make your Mac do what YOU want it to. Create games, utilities, cool Mac OS X tricks. Download REALbasic now and create your own software.

REALbasic University: Column 042

RBU Pyramid XV: Undo Part 1

Admittedly, last week's lesson wasn't too challenging. But this week we've got a mountain to climb. We're going to add an undo system to RBU Pyramid.

To be honest, we're going about this the wrong way. An undo system is so fundamental to the operation of a program that it should be one of the first things you design. When you're planning your program, especially the data structure, think about how you'll implement undo. This is even more critical when you want to support multiple undos, undos of various kinds of actions, and have a redo system as well.

It's certainly not impossible to add an undo system after the fact, but it's not easy. You'll find tracking down bugs to be a horrible pain. In fact, I've known there are bugs in RBU Pyramid's undo system for months -- and I've been putting off fixing them!

But for our lesson today we're going to be creating the buggy version -- extra points to whomever catches the bugs. We'll fix the problems in a future column, but meanwhile you'll get chance to see how difficult this is to add after the fact, as well as how complicated it is to debug.

Undo Basics

As always, we start by planning what our undo system is going to do. Is it going to be a single undo/redo or multiple undo/redo?

The nature of the Pyramid card game is such that a player follows various paths by making irreversible choices: Do you match the 8 and 5 in the pyramid or the 8 in the pyramid and the 5 on the permanent discard pile? Because of those multiple paths, it can sometimes be valuable to back up several moves and try a different trail.

Also, since I was writing RBU Pyramid specifically with the idea of using it in a tutorial, I felt a more complex, full featured undo system would be most valuable for RBU readers. Thus I made the decision that I wanted to support multiple undos. In fact, unlimited undos. The player should be able to undo all the way back to the beginning of the game!

However, since a pyramid can be cleared (won) and redealt as many times as the player keeps winning, I also decided that the undo system would be reset with each card shuffle. There's no point in a player going back to a game they won. That does make our job a little easier, but it's still going to be rough.

Let's look at what happens in a typical Pyramid card game.

The user clicks on two visible, uncovered cards, attempting to find a match. If the values of the cards add up to 13, the cards are removed. Kings are removed with a single click. There are two discard piles: a temporary and a permanent. When the user clicks on the Deck, a fresh card is placed on the temp discard. If there's already a card there, it is moved to the permanent discard. Cards already in place on the permanent discard pile just stack up on top of each other (face up). Worst of all, when the Deck runs out of cards the first time, the permanent discard cards are flipped over and become the new Deck!

So already we can see several challenges. To support undo, we must be able to keep track of what the user has done. If a pair of cards have been removed, they must be put back. We must also watch what happens with the Deck and two discard piles, reversing any changes therein. And -- and this is the killer one -- we must be able to put the Deck back even after the user redistributed the permanent discard pile!

In principle, an undo system is simple: we just keep track of what the user has done, step by step, and reverse it step by step, if the user requests it. Simple, right?

In practice, however, it can be much tricker. For example, let's say the user deletes something. If your program actually deletes the data, it's gone. There is no undo. You can't regenerate that data from nothing. So the only way undo works is because the program doesn't actually delete it: it just pretends to do so while keeping a backup copy around in case the user changes their mind.

You can probably see how unlimited undo eats up memory. Just a few years ago, this meant that few programs offered more than one undo or maybe a handful, such as 10. Today, most computers have hundreds of megabytes of RAM and huge hard drives, so with simpler programs, multiple undos are feasible (though still complicated). Even Adobe Photoshop supports multiple undos via its History palette (though telling Photoshop to remember more than a few undos can dramatically slow down the program, especially if you're editing 100 megabyte photos).

In the case of RBU Pyramid, program resources are not a significant problem: with a meg of memory we could probably remember thousands of user actions. But it's something to remember if your program creates a lot of data.

Creating an Undo Data Structure

The first thing we start with when designing our undo system, of course, is with a data structure. We've got to have some way to remember everything the user does. In our case, any action by the user could result in multiple things happening: the Deck could advance or reset, there could be movement between the two discards, and cards could be removed. That's a lot of action to remember!

So the first thing I did was to create a custom undo class, containing properties telling me the state of things when the user does something. Within your project, create a new class (File menu, "New Class"). Name it undoClass and add the following properties to it (Edit menu, "New Property"):

As you can see, we've got a number of flags (flags are usually booleans that you use to tell you if a state exists or a condition has changed) and several properties which will tell you which cards were on the discard piles or selected by the user.

That gives us a structure for our undo data, but we still have no place to put it. Let's create a global array for the undo data. Open globalsModule and add this property: gUndoList(0) as undoClass.

Now since we want the undo data to be erased whenever a new shuffle of cards is dealt, let's make sure it gets deleted whenever there's a new shuffle. Go to the freshDeck method (within globalsModule) and scroll to the bottom. Somewhere after the // Erase the discard line, put in this:

  
 
   // Erase undos 
 
   redim gUndoList(0) 
 
  

That should finish our work with globalsModule for now. Close it and let's get into gameWindow's code editor (Option-tab while the item is selected).

Adding Undo Routines

The first thing we'll do is add a few methods (Edit menu, "New Method"). Name the first one doUndo, the second eraseUndo, and the third saveUndo. For all of them, leave the "parameters" line blank.

Now let's add property to gameWindow. Go to the Edit menu, choose "New Property" and type in theUndo as undoClass and click okay.

Now let's write the saveUndo method. This is what you'll call whenever you want the current state of the program saved (i.e. right after the user has done something undoable).

Here's the code for saveUndo:

  
 
   dim n as integer 
 
    
 
   // This routine saves the last action into the undo array 
 
    
 
   // Expand the undo array by one 
 
   n = uBound(gUndoList) + 1 
 
   redim gUndoList(n) 
 
   gUndoList(n) = new undoClass 
 
    
 
   // Copy the passed value to the array element 
 
   gUndoList(n).deckReset = theUndo.deckReset 
 
   gUndoList(n).deckAdvance = theUndo.deckAdvance 
 
   gUndoList(n).mainDiscard = theUndo.mainDiscard 
 
   gUndoList(n).pyramidCard1 = theUndo.pyramidCard1 
 
   gUndoList(n).pyramidCard2 = theUndo.pyramidCard2 
 
   gUndoList(n).tempDiscard = theUndo.tempDiscard 
 
    
 
   enableMenuItems // make sure edit menu is active 
 
  

The first thing we do is enlarge our global undo array by one element: we need to make room for the new data. We do this by finding the current size of the array with the uBound function, add one that value, and redim the array with the new size.

Next, we initialize that new array element with a new instance of the undoClass object. (Remember, classes are objects, and thus must be instantiated before they can be used.)

Once we've done that, the rest of the code is simple: we just assign the values in theUndo to the matching values in the array element.

In Detail

Note that we cannot just simply put gUndoList(n) = theUndo. While RB won't complain about that code, it doesn't actually transfer the values of the individual fields. Don't ask me why -- it sort of makes an alias of theUndo in gUndoList(n) and changes to either affect both. It creates a very messy situation with unpredictable results. Trust me -- it's not something you want to debug!

The eraseUndo method is very simple: it just resets everything in the undo object to their default values. We need that, because as you'll see, most routines that call saveUndo only modify the field or fields of theUndo that need to be changed. If we didn't erase theUndo first, those fields would contain old, incorrect data that would be saved in the undo array.

Here's eraseUndo:

  
 
   theUndo.deckReset = false 
 
   theUndo.deckAdvance = false 
 
   theUndo.mainDiscard = 0 
 
   theUndo.pyramidCard1 = 0 
 
   theUndo.pyramidCard2 = 0 
 
   theUndo.tempDiscard = 0 
 
  

As I said, very simple. However, doUndo is not:

  
 
   dim i, n as integer 
 
    
 
   // This routine undoes the last action saved in the undo array 
 
   // First, we try to figure out what kind of undo situation we have. 
 
   // There are multiple possibilities: 
 
   //   - A match was made and cards removed 
 
   //   - The deck was advanced 
 
   //   - The deck was reset 
 
    
 
   n = uBound(gUndoList) 
 
    
 
   // Is it a deck reset? 
 
   if gUndoList(n).deckReset or gUndoList(n).deckAdvance then 
 
      
 
     if gUndoList(n).deckReset then 
 
       // Flip deck back over 
 
       redim gTheDiscard(0) 
 
       for i = 1 to uBound(gTheDeck) 
 
         gTheDiscard.append gTheDeck(i) 
 
       next 
 
        
 
       // Erase the deck 
 
       redim gTheDeck(0) 
 
        
 
       // Was there a temp discard card? 
 
       if gUndoList(n).tempDiscard > 0 then 
 
         // There was, so put it back 
 
         gTempDiscard.card = gUndoList(n).tempDiscard 
 
         gTempDiscard.selected = false 
 
         gTempDiscard.clickable = true 
 
         gTempDiscard.refresh 
 
       end if // gUndoList(n).tempDiscard > 0 
 
        
 
       // Was there a main discard card? 
 
       if gUndoList(n).mainDiscard > 0 then 
 
         gDiscard.card = gUndoList(n).mainDiscard 
 
         gDiscard.clickable = true 
 
       else 
 
         gDiscard.card = 0 
 
         gDiscard.clickable = false 
 
       end if // gUndoList(n).mainDiscard > 0 
 
       gDiscard.selected = false 
 
       gDiscard.refresh 
 
        
 
       // Reset deck counter 
 
       if not gFirstTimeThrough then 
 
         gFirstTimeThrough = true 
 
       end if 
 
        
 
     else 
 
       // Undo advancing the deck 
 
        
 
       // Move temp discard back to deck 
 
       gTheDeck.append gTempDiscard.card 
 
        
 
       // Was there a card on the temp deck before? 
 
       // if so, move it 
 
       if gUndoList(n).tempDiscard > 0 then 
 
         gTempDiscard.card = gUndoList(n).tempDiscard 
 
         gTempDiscard.selected = false 
 
         gTempDiscard.clickable = true 
 
         gTempDiscard.refresh 
 
       else 
 
         gTempDiscard.card = 0 
 
         gTempDiscard.selected = false 
 
         gTempDiscard.clickable = false 
 
         gTempDiscard.refresh 
 
       end if // gUndoList(n).tempDiscard > 0 
 
        
 
       if uBound(gTheDiscard) > 0 then 
 
         // No card on temp discard, so move card on main discard to temp discard 
 
         gTempDiscard.card = gTheDiscard(uBound(gTheDiscard)) 
 
          
 
         // Remove it from the main discard pile 
 
         gTheDiscard.remove uBound(gTheDiscard) 
 
          
 
         // Set the top card to last item of gTheDiscard 
 
         if uBound(gTheDiscard) > 0 then 
 
           gDiscard.card = gTheDiscard(uBound(gTheDiscard)) 
 
           gDiscard.clickable = true 
 
         else 
 
           gDiscard.card = 0 
 
           gDiscard.clickable = false 
 
         end if 
 
         gDiscard.selected = false 
 
         gDiscard.refresh 
 
       end if // uBound(gTheDiscard) > 0 
 
        
 
     end if // gUndoList(n).deckReset 
 
      
 
     // Undoing deck action, so refresh the deck 
 
     gDeck.refresh 
 
      
 
   else 
 
     // not a deck action, therefore must be a match of some kind. 
 
     // Figure out which cards and undo them. 
 
      
 
     if gUndoList(n).pyramidCard1 > 0 then 
 
       // Reset the card 
 
       cardCanvas(gUndoList(n).pyramidCard1).visible = true 
 
       cardCanvas(gUndoList(n).pyramidCard1).selected = false 
 
       cardCanvas(gUndoList(n).pyramidCard1).refresh 
 
       gScore = gScore - 1 
 
     end if // gUndoList(n).pyramidCard1 > 0 
 
      
 
     if gUndoList(n).pyramidCard2 > 0 then 
 
       // Reset the card 
 
       cardCanvas(gUndoList(n).pyramidCard2).visible = true 
 
       cardCanvas(gUndoList(n).pyramidCard2).selected = false 
 
       cardCanvas(gUndoList(n).pyramidCard2).refresh 
 
       gScore = gScore - 1 
 
     end if // gUndoList(n).pyramidCard2 > 0 
 
      
 
     if gUndoList(n).tempDiscard > 0 then 
 
       gTempDiscard.card = gUndoList(n).tempDiscard 
 
       gTempDiscard.selected = false 
 
       gTempDiscard.clickable = true 
 
       gTempDiscard.refresh 
 
       gScore = gScore - 1 
 
     end if // gUndoList(n).tempDiscard > 0 
 
      
 
     if gUndoList(n).mainDiscard > 0 then 
 
       // Add undone card back to discard pile 
 
       gTheDiscard.append gUndoList(n).mainDiscard 
 
       gDiscard.card = gTheDiscard(uBound(gTheDiscard)) 
 
       gDiscard.selected = false 
 
       gDiscard.clickable = true 
 
       gDiscard.refresh 
 
       gScore = gScore - 1 
 
     end if // gUndoList(n).mainDiscard > 0 
 
   end if // gUndoList(n).deckReset or gUndoList(n).deckAdvance 
 
    
 
   // Remove this undo (it's been used) 
 
   gUndoList.remove n 
 
    
 
   enableMenuItems 
 
   updateCards 
 
  

Woah, what the heck does all that do? Well, I'm not going to tell. I'll just let you figure it out for yourself.

Just kidding! I wouldn't be that cruel. Figuring out someone else's code is bad enough, and wading through undo code is the worst. The first thing to do is to take this gently, step by step. Then it's not so overwhelming.

Note that the code is heavily commented: I didn't do that so much for the tutorial as I did for my own sanity while writing this. Trust me: when you get into hairy stuff like this, it's best to go slow and comment like mad!

Remember the purpose of this routine: this method is called when the user chooses the undo command from the Edit menu. So our code here must figure out exactly what actions we need to undo and do that.

The first thing we do is figure out the size of the undo array. That's because the last element is the one containing the undo info we need. So, using that array element, we look to see if there was a Deck advance or Deck reset.

The Deck reset is the most complicated. If that's the state, we have to do a bunch of stuff:

• We erase the permanent discard pile and refill it with the cards in the Deck.
• Then we erase the Deck.
• We check to see if there was a temp discard card: if there was, we put it back.
• We check to see if there was a main discard card (logically there should be, but we check anyway) and if there was, make sure it's clickable.
• Finally, we reset the Deck counter (that's the flag that tells us if the user has reset the Deck yet: since the user just did that, but is undoing it, we must reset it back to show that the user has not reset the Deck).

If it's not a Deck reset, then it's a Deck advance (the user drew a card from the Deck). This is simpler, but still involved:

• First, we move the card that's currently on the temp discard pile back into the Deck.
• Then we check to see if there used to be a card on the temp discard before the Deck advance: if so, we put it back from the main discard.
• Then we make sure if there's a card on the main discard, that it's clickable.

After either of these actions, we must refresh the Deck (gDeck) so it is redrawn with the appropriate appearance.

Finally, if neither of the above conditions were true (Deck reset or Deck advance), the user must have made a match. The only thing tricky about this is figuring out what kind of a match: two pyramid cards, two discard cards, or a combination of pyramid and one of the discard piles?

That sounds intimidating, but it's not that bad. If there's a value greater than zero within gUndoList(n).pyramidCard1 or gUndoList(n).pyramidCard2, we know those are pyramid cards. All we do is restore those cards to their visible, clickable state. (Remember, cards involved in matches in the pyramid are never actually deleted, just hidden!)

If there's a value within either of the discards, it's slightly more complicated as we have to restore the original value and put a card back onto the stack of the main discard pile (from a programming perspective, we add a card element to the gTheDiscard array).

Note that for any of these occurrences -- a card match -- we decrement the player's score. We wouldn't want them racking up a super high score by cheating!

Finally, after all this stuff has been done, we remove the current undo object from the undo array: it's been used so we don't need it any more. Then we call enableMenuItems to make sure our menus are up-to-date and updateCards to make sure all the cards are in the correct state (selectable, etc.).

That's it! We're done!

Just kidding, unfortunately. We've only scratched the surface. All we've done is write the code to support the undo data structure -- we have never actually called any of these routines anywhere in our program yet, so running RBU Pyramid right now would do nothing differently.

However, this is all we've got time for this week, so we'll finish the rest of the undo system next week.

Meanwhile, if you would like the complete REALbasic project file for this week's tutorial (including resources), you may download it here.

Next Week

In Undo Part 2, we'll have less theory and get that darn undo system working!

REALbasic University Quick Tip

It's easy to forget that the REALbasic IDE supports contextual menus: control-clicking within the Code Editor will bring up a quick list of areas of your program that have code, such as events, methods, and properties. Selecting one of these will jump you to that element.

Letters

This week a couple readers respond with suggestions for last week's letter regarding large numbers in REALbasic.

George Bate writes:

Dear Marc

Remek can easily calculate 1000! by using the wonderful free MPCalc plugin written by Bob Delaney. It emulates an HP RPN Calculator and can be downloaded from:

http://homepage.mac.com/delaneyrm/MPCalcPlugin.html

The answer to 16 decimal digits (ie approx.) is:

0.4023872600770938 x 10 to the power 2568

You can, if you wish and have the time, perform the calculation to a precision of up to 30,000 decimal digits (really). The range of numbers that can be handled is

10 to the power -167100000 to 10 to the power +167100000

10,000,000! is 0.1202423400515903 x 10 to the power 65657060 (check if you don't believe it)

Sadly, 100,000,000! is too large to calculate by this method.

As a matter of interest I have used this plugin to implement the original HP Calculator in REALbasic.

That's great, George! Thanks for the link... though RPN (Reverse Polish Notation for those of us without math degrees) is something I've never mastered. I'm glad Bob includes a tutorial.

Next, John Johnson (you can tell his parents had a sense of humor ;-) chips in with:

I just recently read your response on large numbers in REALBasic. If your reader is a C whiz, he might try grabbing a copy of Numerical Recipes in C and simply translating over to REALBasic. A copy online can be found at http://www.nr.com/nronline_switcher.html. They have a section that deals with arbitrary precision arithmetic, including (if I remember correctly) arbitrary-size integer arithmetic.

Actually, the translation shouldn't be too hard. The only thing: finding the product of every number from 1 to 1000 is a huge problem, and it will take an extraordinary amount of memory to even hold the behemoth of a number, not to mention the large amount of time required to perform the simple multiplications.

My advice: find a better problem to use the computing resources.

Incidentally, finding the number of digits of the product from 1 to 1000 is easy using logarithms. Throw this code into the open event of a 3-column listbox:

  
 
   dim i as integer 
 
   for i = 1 to 1000 
 
     me.addrow Cstr(i) 
 
     me.cell(me.LastIndex,1) = CStr(log(i)/log(10)) 
 
     if i=1 then 
 
       me.cell(me.LastIndex,2) = "0" 
 
     else 
 
       me.cell(me.LastIndex,2) = CStr(CDbl(me.cell(me.LastIndex-1,2)) + log(i)/log(10)) 
 
     end if 
 
   next 
 
  

Now, round up the number in the last column. That is the number of digits in the product of all numbers from 1 to the number in the first column. At 1000, you get 2568 digits!

Hope this helps. Cheers!

Groan. I knew I shouldn't have opened to door to a math question! I failed algebra twice. (Okay, technically I got a D the first time and dropped the class halfway through the retake, but it's pretty much the same thing. Math and Marc just don't mix well.)

I guess if I knew what a logarithm was I'd be impressed, but I do note that your 2568 digits just happens to match the power amount George used in his letter... I guess that's not a coincidence, but I'm too math ignorant to understand the significance. Oh well. I'm sure this info will be helpful for someone out there.

Each week we answer select reader questions, and we're always open to ideas for future columns. Send your questions to . (Keep your questions simple and specific. General queries like "How do I write my own web browser?" will be neglected.) Your question won't be answered immediately, but will be answered in a future column. (If you don't want your correspondence published, just be sure to indicate that when you write. Otherwise it's fair game.)

About the Author
is an author, philosopher, graphic designer, photographer, film director, soccer fanatic, and programmer (among other things). He writes for MacOpinion, runs his own software company, Stone Table Software, which sells the revolutionary Z-Write word processor, and is Publisher and Editor of REALbasic Developer. He lives in Northern California with his cats, Mischief and Mayhem, and is rapidly running out of free time.

See the REALbasic University Archives

.