Linked Lists and Patterns

I had trouble with this assignment. I was unsure of what classes we were supposed to be working with: there is List, ListI, ListC, EmptyList, Node, CollectionI. ListC does all the work for you, am I supposed to be using this class then? Well, I hope so, because that’s what I did. Anyways, I decided to implement the Observer, Visitor, and State patterns to work with the ListC and Node classes.

In order to fill my lists with Items, I needed to create an Item to store. I chose to create the Integer class, which implements Item, and is just a class that represents an integer. Therefore, I have lists of Integers, which for all purposes are just integers.

The Observer Pattern. I created a ListObserver that watches a ListC and announces when any Item is being removed from the ListC. Although the idea of having an Observer to be notified when a link is changed or broken is interesting, I had trouble deciding what data the Observer should care about. If a Node is added in the list, all the changed Nodes (the previous Node, the new Node, and the next Node) cannot be given to the Observer; that seems like it would require a big mess of conditionals and spaghetti code for the Observer to handle. The Observer would have to know which Node is now previous to the new Node and announce that. The Observer would have to know which Node is the new Node and announce that. The Observer would have to know which Node is now the next Node and announce that.

That seems too messy for a situation like this, so I just decided that the Observer would receive the Node that is being removed so it could announce “X Node/Item is being removed.” At first, the Observer called the toString() method on the received Node, but that would spit out some memory address or useless identifier. This information could be useful, but for our purposes I just decided to have the Observer spit out the toString() of the received Node’s Item, which in my project is an Integer. The toString() method of an Integer just returns an int.

So, when a Node is removed from a ListC, an Observer receives this Node and announces that Node.getItem().toString() is being removed.

The Visitor Pattern. I chose to create a ReplaceVisitor that is instantiated with 2 integers. The ReplaceV would then traverse through a given ListC and replace all instances of one integer with the other. This is where I was held up from my confusion on what classes we’re supposed to work with for this assignment. Since I was using the ListC class, when the get() method is called, it returns a List, but really that is just a Node. Anyways, the ReplaceV doesn’t mess with the actual Nodes that store the integer to replace, instead it just changes the value of the Item (Integer) that stores the integer that the ReplaceV is to replace. This works, but I would have liked for the ReplaceV to actually remove the entire Node and create a new Node with the different information, then stitch the new Node into the list. If this were the functionality, then the ReplaceV would cause the Observer to be notified.

The State Pattern. Once again, due to my confusion, I decided to implement this pattern into the Node class rather than the ListC class. To exemplify this pattern, I just create some new Nodes and manually stitched them together (rather than using the ListC class). The Node has 2 states: emptyState and fullState. The only method that is contained in these states is getItem(). When a Node has an Item in it, then it is in the fullState. When the Node does not have an Item, it is in the emptyState. When getItem() is invoked on a Node that is in the emptyState, a null is returned and a message is announced that the Node is empty and a null value was returned. When this method is invoked on a Node that is in the fullState, the Item is simply returned.

If the next of a node is set to some node that comes before it, that would form a cycle. How could that be detected? (note to say that node A is “before” B means there is a chain of one or more next pointers stepping from A to B).

Perhaps a DetectCycleVisitor could be used.  The DetectCycleVisitor would start at the beginning of the list and traverse the entire list.  In doing so, it could store every Node that it has been to and verify that its current Node is not one that it has been to already.  If this is true, then the DetectCycleVisitor could break from the recursion loop (which obviously is very important: if there is a cycle in the list, then recursion will continue infinitely) and return the Node that is referenced twice (its current Node).  I don’t have this coded up, but I imagine this could be doable, although storing every Node that the visitor has been to could be a costly process if the list is large enough, as well as having to iterate over all of them from start to finish every time it needs to check that it hasn’t already been to this Node.

This certainly would be a useful visitor though.  This could even work well with the Observer Pattern.  Every time a list changes, it notifies its Observers.  The DetectCycleVisitor could be an Observer, and when notified will tell the list to acceptVisitor(this).  Then, the visitor would traverse the list and look for any cycles that might have been created.  If this is true, the visitor will then announce this, or throw an exception, or somehow remove the cycle.  This is important because if there was a cycle and you did not send in a DetectCycleVisitor, then the next time you try and iterate over the list, an infinite loop will be created and the program will crash.

I think this sounds very cool actually, to use the Observer Pattern and Visitor Pattern together to thwart the possibility of containing cycles in a linked list.  Too bad I didn’t think of this before I did the assignment, I would have implemented this.

The Lone Visitor

The Visitor Pattern has some serious power. It’s just begging to be tossed into a data structure. Unfortunately, I don’t have much of any data structures going on other than some ArrayLists. But, powerful none the less.

I decided to use the Visitor Pattern for drawing my game entities to the screen. So, I created a Visitor interface declaring some visit() methods for all the entities in my game (Ship and Projectile). Then, I made a concrete class called Draw2DVisitor, which, as you may guess, draws things in 2D.

Prior to implementing this Visitor, the Ships and Projectiles had the capability to draw themselves. Although this works and is a common method, you’re stuck with graphics. What if for debugging purposes you wanted to skip graphics and instead print to the screen all the information about where your entities are located? Well if you provided an interface for all kinds of Visitors to use, you could simply create a PrintStringVisitor that printed this information to the screen. Amazing.

So after removing the draw capabilities from all entities and creating the Draw2DVisitor class, I implemented the Visitor into the game. Unfortunately, I quickly ran into a minor but annoying problem. Due to the design of my game loop, the graphics for the window are instantiated every iteration of the game loop, which means I have to provide this new graphics setting to the Draw2DVisitor so it knew where to draw the entities. Well, the only way the Visitor gets this information is through its constructor, which meant I had to declare a variable for the Visitor outside of the game loop, and instantiate a new Draw2DVisitor every iteration of the game loop, providing it the newly created graphics setting. This bothered me. I don’t need to be creating a new Visitor every iteration of the game loop, that’s a lot of unnecessary object creation! But I couldn’t see any way around it due to the already implemented graphics.

Singleton saves the day! Wait a minute. I don’t need any more than one Draw2DVisitor anyways since the single instance is passed around to every entity, why not make it a Singleton and restrict instantiation? Well, it turned out to fit nicely. I changed the Draw2DVisitor class to a Singleton, and provided a static method to retrieve the single instance of the Draw2DVisitor. Since the Draw2DVisitor needs a Graphics2D setting to draw to, I simply added this as a parameter into the static retrieve method. Now when the retrieve method is called, it sets its internal Graphics2D variable to the given parameter, and returns the single instance of the Draw2DVisitor.

Now, each iteration through the game loop, rather than instantiating a new Draw2DVisitor, a simple method is called to retrieve the single Draw2DVisitor and set the appropriate Graphics2D. Job well done Singleton.

Four Patterns Demonstration

I ended up writing so much in the accompanying email of the project file, I thought I’d put that here to describe the design.

The program simulates a teacher at school. A Teacher is created, and then Students are created and given a random favorite design pattern. The Students are then divided into classrooms, and the Teacher goes to each classroom and attempts to drill the design principle of the day into their minds. He then quizzes the Students afterwards on what and how he just taught them the design principle. The Students will not only remember what principle he taught them, but also his tone of voice as well as any manners that the he had.

Two things are randomized that alter the outcome of the program:

– Each Student’s single favorite pattern is chosen at random. This determines whether they will change State when the Teacher announces the pattern of the day.

– Each classroom is assigned random Students. Depending on the number of Students in the classroom whose favorite pattern matches the pattern the Teacher will be teaching (i.e. the number of Students who are paying attention), the State of the Teacher will change.

Let me explain where the 4 patterns are applied:

The Strategy Pattern – A Teacher has a SpeakBehavior (a certain tone) and this SpeakBehavior is determined by the State of the Teacher.

The Observer Pattern – When a Teacher enters a classroom, all the Students observe the Teacher. Then the Teacher announces the pattern of the day, and the Students remove themselves as an Observer from the Teacher if the announced pattern is not their favorite.

The Decorator Pattern – The SpeakBehavior classes may be randomly wrapped by a FunnyManner or WeirdManner.

The State Pattern – The State of the Teacher is determined by how many Students are observing it (paying attention). If the Teacher has already taught 2 classrooms today, and if the Teacher is not in a bad mood (bad state), then the Teacher will be in a Tired state. The State of the Teacher changes the SpeakBehavior of the Teacher, and may even decide (at random) to decorate the SpeakBehavior with a FunnyManner or WeirdManner.

Recipe for Success: Implementing the State Pattern

The State Pattern – Allow an object to alter its behavior when its internal state changes. The object will appear to change its class.

Implementing the State Pattern:

1. Fortunately, the State Pattern is a simple concept, and it’s uses are obvious. To implement the pattern in your project, you must first find something that may have various states. This is no complex task; a state is something as simple as Hungry, Tired, Angry, Alive, Dead, Sleeping, Attacking, Defending, Running, Walking, Stationary (Immobile), Waiting, etc. You want to make sure that whatever you choose has more than one state; if it only has one state, then it’s not really a state to begin with, but it’s rather the definition of what that object is.
2. Now that you’ve found a Finite State Machine (something with multiple states), you need to decide explicitly what those various states will be. For example, you’ve decided a dog will be your FSM (Finite State Machine), then perhaps the states of the dog could be Hungry, Tired, Sleeping (quite a lazy dog).
3. Now decide what within your FSM (our dog) changes depending on the state that it’s in. For example, if our Dog was in a Hungry state, it might look for food, but if it’s in a Tired state, it might look for a place to sleep. Usually you will be choosing methods that vary depending on the state. In this case, say there was only one method that varied depending on the state of the dog; what the dog’s looking for. The method signature might be: public void lookForSomething();. Now take this method signature and copy it (don’t erase it from the dog class).
4. Now create a new hierarchy, either with an abstract base class or an interface, that declares (not defines) these methods — lookForSomething() — that you chose in step 3. This hierarchy will now be explicitly for use within your Dogs. If you have other animals that these states may apply to, you could use this hierarchy for them as well, but usually you will have a new hierarchy of states for each FSM that you have.
5. Now, create subclasses within your State hierarchy that define each of the various states that your FSM will be using. In our example, you would create HungryState, TiredState, and SleepingState subclasses. Now each of these classes must define the abstract methods that were declared in the base class. You would write a definition in each subclass for the lookForSomething() method. In the HungryState, the method might tell the Dog to look for something to eat. In the TiredState, the method might tell the Dog to look for a place to sleep. In the SleepingState, the method might not do anything; you could just leave it blank. This is a viable option because as you know, if you’re sleeping you’re not going to look for something. Therefore, it is okay to leave the method definition blank in the SleepingState, or you might want to send output notifying the caller that the Dog is sleeping.
6. You need to have an instance variable somewhere of the type of FSM that your states will be applied to. In our example, our abstract base class DogState would have a variable of type Dog. This is necessary for the various states so they have a Dog to change, otherwise they would just be definitions of methods that do something on their own, not change the way something acts. So, if you created your State hierarchy with an interface, you would have to add a variable of type Dog in each of the subclasses, but if you use an abstract class you could put that variable in the base class for every subclass to inherit.
7. Now, within your FSM, you need to add some new member variables, one (or many) for each of the possible states, plus one for the current state. So in our Dog class, we would add four new variables of type State, and it would look something like this:
   • class Dog {
   • State hungryState;
   • State tiredState;
   • State sleepingState;
   • State currentState;
   • … }
8. Now in the constructor of the Dog, you would create a new object of the various state subclasses, and assign those to the appropriate variables.
9. Now, go back to your methods in the Dog class, in our case just the lookForSomething() method. Within this method, you just delegate the task of lookForSomething() to the currentState. The definition of the lookForSomething() in the Dog would look like: currentState.lookForSomething();. This will invoke the correct method definition depending on what state the Dog is in.
10. When you make your checks on the Dogs hunger level and tired level, you would add an assignment to set the Dogs currentState = hungryState if its hunger level was low enough, or currentState = tiredState if it was tired enough.
11. Now when lookForSomething() is called on the Dog, the task will be delegated to the currentState of the dog, and an appropriate execution of the method will occur. If currentState = tiredState, when lookForSomething() is called, the definition provided in the TiredState class will be executed.

The Current State of Things

The State Pattern is used far and wide throughout games. Two common uses for it apply to:

1. The state of the game

– Opening/Introduction
– Main Menu
– Loading
– Running
– Paused
– Closing/Exiting

2. The state of the units/characters

– Damaged
– Full
– Upgraded

This is what I plan to implement into my game as well. I currently have a Game class, so I will add in a few States, particularly an OpeningState, a RunningState, and a ClosingState. As for my Ships, I will have the EnemyShips contain a DamagedState and a FullState, while the PlayerShip will contain a DamagedState, FullState, and UpgradedState.

So far I’ve not run into any problems. I’ve implemented the Ship states already and they’re working properly, but I haven’t started on the Game states. Although I’ve got the Ship states added, I don’t have any of the AI created in these states yet.

As for graphics, I’ve got them up and running, but I currently don’t have all the animations (frames) that I want implemented yet, and I haven’t found the BlasterBeam and Torpedo images that I want to use yet, so I have some images just for building purposes. I’ve got the PlayerShip movement and primary weapon fire methods added. They can be seen here:

Notice the jet on the Ship blasts out the back when it accelerates forward/up the screen, and goes away when not accelerating forward/up. I plan to add this same type of animation for the PlayerShip; when it flies to the left the ship leans left, and when it flies to the right the ship leans right.

Recipe for Success: Implementing the Decorator Pattern

Decorator Pattern – Attach additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality.

How to implement the Decorator Pattern:

1. Take into consideration a class hierarchy, preferably one with many subclasses. The pattern applies very well when you have several features that a class of yours is comprised of. Rather than creating a subclass for every possible combination of these features, you want to create a Decorator for each individual feature. The Decorator must extend the class that it is going to be decorating, since a Decorator wraps itself around an object that it is decorating, and then stands in place of the decorated object. Therefore, the object and decorator must be of the same type. You can achieve this either through extending a class or implementing an interface.
2. Now that you have a particular hierarchy that you want to change, you need to separate (but keep within the same hierarchy) your concrete classes from your decorator classes. For example, when you order a House Coffee with A Shot of Espresso and Whip Cream, your concrete class would be the House Coffee, and the Decorators would be A Shot of Espresso and Whip Cream. Remember, your Decorators must extend the same base class as your concrete classes.
3. Within your new hierarchy, you should have a base class (Beverage), then a few concrete subclasses (HouseCoffee, DecafCoffee, etc…), and another abstract subclass as your decorator (BeverageDecorator). Within your abstract Decorator class, you need to include a member variable of type Beverage (whatever your base class is; whatever you want to decorate). When you decorate an object, that object is stored in this member variable. In the constructor for a Decorator, add a Beverage parameter, because when you construct a Decorator you must give it a Beverage to Decorate. Then, you should have all of your various features extending the Decorator class (BeverageDecorator). The features would be something like EspressoShot, WhipCream, etc.
4. The idea of the Decorators is that they can modify the behaviors of the object they decorate. Using our example, each Decorator would add a cost to the total amount. After you’ve decorated your HouseCoffee with EspressoShot and WhipCream, when you call the cost() method of the Beverage, the call will pass through each decorator, where that decorator will add its own cost to the returning amount. Therefore, your Decorators must have a common functionality with your concrete classes (this should be implied since they all extend the same base class). If your Decorators do not, they probably shouldn’t be decorating the object.
5. Now, to use the Decorators, it is simple. Here is an example:

Beverage beverage = new HouseCoffee();

beverage = new EspressoShot(beverage);

beverage = new WhipCream(beverage);

beverage.getCost();

problem = new DecoratorProblem (problem);

The Decorator Pattern is fun. In my game, I’ve decided that every Ship will have a Weapon and a Shield. My “decorators” are the specific types (sub-classes) of Weapons and Shields, namely RailCannon and TorpedoCannon, and HeatShield and BlastShield, respectively. The idea is that I instantiate a Ship with the default Weapon and Shield, then decorate the Weapon and Shield with the decorators to give the Ship some kick. This allows for multiple decorators to stack onto the default weapon and shields, so if I wanted to upgrade the RailCannon, I could just decorate the weapon with another RailCannon. This just stacks a new RailCannon onto the weapon, so it doesn’t really upgrade the RailCannon, it just doubles the effects of the RailCannon.

Unfortunately with the Decorator Pattern, an object does not know what objects are decorating it, and there is no way to remove a decorator. I noticed this problem when considering the ammunition for my Weapons. Currently, each Weapon has an ammunition, and every time fire() method is called, an ammunition check is made. If the check passes (ammo > 0), then the Weapon fires and decrements its ammunition. The problem is that when the ammunition runs out (ammo == 0), there is no way to refill the ammo because I cannot target the specific decorator. This wouldn’t be much of a problem if I could just remove the empty weapon, and replace it with a new weapon with more ammunition (to simulate a reload), but there’s no way to remove a decorator.

The good news is that I smell another design pattern within this mess of Weapons, RailCannons, and Projectiles. I could very well see decoupling pattern fitting perfectly between these classes, but that is something that I would realize and implement later. Unfortunately, I demand a solution to the problem now. The current options seem to be removing specific weapon ammunitions, and just have a single ammunition count that each weapon decorator can add to. Although this would be easily implemented, it’s not really an ammunition count; it’s a ‘how-many-times-you-can-fire’ count. An example of the problem can be seen here:

1. A Ship has 3 weapons and an “ammunition” count. Weapon a adds 60 to the ammunition, weapon b adds 30 to the ammunition, and weapon c adds 10 to the ammunition.
2. This makes the ammunition count equal to 60+30+10 = 100.
3. Every time the Ship fires, it reduces the ammunition count by the number of decorators, 100 – 3 = 97, since each weapon fired once.
4. Do this many more times, say 12 more fire()’s. Here the problem occurs. The Ship has fired all its weapons 13 times, but the ammunition of weapon c was only 10, yet weapon c fired 13 times. Moreover, there is still 97 – (12 x 3) = 61 ammunitions left.

Obviously, this wouldn’t be a practical solution.

There also exists the easy-way-out solution of removing ammunition altogether and just allow Ships to fire() infinitely, or at least not be restricted by ammunition. If I chose this option, I would probably try and add a new restriction, like Temperature, that would limit how often a Weapon can be fired within a certain time.

Recipe for Success: Implementing the Observer Pattern

Probably the most difficult thing when implementing the Observer Pattern is realizing where you actually need to use it. In some cases it may be very obvious, but in other cases you might have a minor, unnoticed relationship that would greatly benefit from the Observer Pattern. I imagine that sometimes it might be easier to realize the necessity for the pattern when you’re actually doing the nitty-gritty coding.

Here are the steps:

1. Realize what relationships within your program would benefit from the Observer Pattern. These relationship may be one-to-one or one-to-many.
2. Figure out which objects within your relationship will be the Observers and which will be the Subject (Observable). This step actually proves to be quite troublesome as you might feel that the Observer Pattern is backwards when you begin to implement the code. The solution to this problem is to take a step back and look at all your objects within your relationship. Now, realize which objects change. The objects that change will be the Subject (Observable). The goal is that when your Subject changes, all the Observers will get new information.
3. Now that you’ve figured which objects will be the Subject (Observable) and which will be the Observers, you need to extend and implement the Observable class and the Observer interface. Here lies one of the patterns major downfalls: you must extend. Since Java does not allow multiple inheritance, if you’ve already created a class hierarchy and you’re attempting to implement the pattern, you can’t. You simply cannot. You must redefine your hierarchy, or move the extension to the super class. If you’re using the prebuilt Java Observable class and Observer interface, you don’t have to do much. All you need to do is define the update() method within your Observer class, and define when your Subject (Observable) will call notifyObservers().
4. Your Observers will receive an Object that is the Subject through the update() method. You must then decide what your Observers want to do with the Subject they’re observing. You can either have the Observers pull the information they want from their Subject, or you may have the Subject send out all its information that changes to all its Observers.

Problems implementing the Observer Pattern

At first it was unclear as to where I should apply the Observer Pattern, but after deciding on how I was going to implement the various objects in my game it became more clear. I first created a class hierarchy for my spaceships, then I decided that I wanted my ships to be able to observe other ships, but when I began to implement the Observer Pattern I ran into the single largest pitfall of the Observer Pattern: your class must extend Observable. This was a problem as my ships were already extending classes. So I decided I needed to redefine how I implemented my spaceships in the game anyways, and went ahead and removed the Observer Pattern as well as redesign my ship hierarchy. Now, I have a base class Ship that extends Observable and implements Observer. Problem fixed. The relation between the Ships utilizes the Observer Pattern by allowing the Ships to communicate between each other their specific location. When you two Ships are about to engage in combat, they observe one another, and as the combat goes on the Ships drift around in space, so their locations change, and if the opposing Ship is locked on (observing), then they receive an update of that Ships location. Ships may choose to attempt an escape, where they disengage from combat and fly away. The opposing Ship may choose to follow them. Once again, the locations of the ships change and the observing Ships get updated on this change.

My second implementation was between the class Radar and the class Asteroid. Every Ship in the game will have a Radar, which will performScan() and pickup any nearby Asteroids. The movement of the Asteroids varies; some are stationary while others float through space. As a Ship locks on to an Asteroid, it may shoot at it to destroy it, or try to avoid it. Since the location of the Asteroids may change, the Ship will be updated on this change. This seems to provide a nifty life-like feature: your Ship detects an Asteroid field ahead moving your direction; do you try and blast your way through, or attempt to outmaneuver them?

Unfortunately, the code that I turn in does not do very much. Yes, it exemplifies the Observer Pattern but it is not practical code. I have to correctly design my Ship hierarchies and implement them before I can properly use the Radar/Asteroid relationship, as well as the Ship/Ship relationship.

Recipe for Success: Implementing the Strategy Pattern

There are a few Design Principles surrounding the Strategy Pattern:

1. Identify the aspects of your application that vary and separate them from what stays the same, i.e. take the parts that vary and encapsulate them, so that later you can alter or extend the parts that vary without affecting those that don’t.
2. Favor composition over inheritance.
3. Program to an interface, not an implementation.

You should keep these in mind when implementing the Strategy Pattern in your software.

Here are the basic steps for implementing the Strategy Pattern:

1. Within your class hierarchy, decide which methods vary depending on the subclass. There will probably be more than one method, so select all of them and remove them from that class (should be removing them from the base/super class). All that should be left within your base/super class should be constants, or methods that do not vary depending on the subclass. This is the idea of encapsulation, you’re taking what changes and separating it from what is constant.
2. Now, for each of your methods that you removed create a new hierarchy, either with an abstract class or interface (preferably interface). Your new hierarchies should contain only one or two methods within the base class or interface.
3. Now that you have several new hierarchies, you need to create subclasses for all of them. These subclasses should implement the interface (or extend the base class), and will be concrete classes (i.e. you will instantiate them). Each subclass varies by its own definition of its inherited method. Once you are finished, you should have a few new hierarchies with several subclasses each.
4. With your new hierarchies complete, it’s time to return to your original class hierarchy (where you removed the methods). Within the base/super class of this hierarchy, you need to add several new member variables. These member variables should be types corresponding to your new hierarchies. You will need to declare a level of protection (private, protected, public) for these member variables. If you choose to make them private, you will need to add new methods to your base/super class to set them, or you could make them protected and allow your subclasses to directly modify them. Either way works fine for our purposes.
5. Now you need to edit the constructor code for all of your subclasses. Within each constructor, set the appropriate member variables to the correct subclasses from each of your new hierarchies. You will need to instantiate new objects of the correct subclass (from your new hierarchies). By correct I don’t mean there’s a right or wrong way of doing this, I mean that if you have, for example, an object of type Bully, you would set his member variable of type Attitude to “Mean,” (correct) you wouldn’t set it to “Happy” (incorrect), unless for some reason you wanted a Bully to have a Happy attitude (but that is beside the point). You have several member variables that need to be set accordingly for each of your subclasses (of your original class hierarchy), so you will pick and choose 1 subclass from your new hierarchies to set to each of the member variables.
6. If you haven’t already, it might be nice to add set methods to the base class of your original hierarchy so you can change at runtime the member variables for each of your subclasses. Since the member variables of your subclasses are actually objects, it’s very simple to change them at runtime; all it takes is a simple “bully.setBehavior(new Happy());” line of code.

This pattern is very nice as it exemplifies encapsulation very well as well as code reuse and delegation. The encapsulation is obvious, and your new hierarchies may now be used for anything that is given an appropriate member variable. As for delegation, because you separated what changes from what stays constant, you can give your removed methods to other programmers to design the hierarchies for, and all they need to give you is the interface or abstract class that they used for the hierarchy so you can add them as member variables to your original hierarchy.