|
|
|||||||||
Recursion with Patterns: State, Visitor, FactoryWe will be using the State, Visitor and Factory design patterns to implement a program to generate fractal Koch curves and snowflakes. The Koch curve is a self-similar pattern, meaning that a Koch curve consists of a particular pattern made of Koch curves. This is clearly a recursive relationship. In the finite world of computers, we cannot continue this recursive relationship indefinitely and thus there exists a base case where the Koch curve is simply a single straight line segment with well defined endpoints. A Koch curve can thus be modeled as a two state entity: a straight line or a collection of Koch curves. To generate the Koch curve, we will start with the straight line state. When commanded to "grow", that state will change to the multi-curve state. The collection of Koch curves consist of base case Koch curves in a pattern connectig the original endpoints. The pattern is determined from a supplied prototype mapped onto the original endpoints via an affine transformation. We will use our LRStructure package to represent the collection of Koch curves as a linear linked list. We will use LRStruct's visitor pattern algorithm extensions to write the algorithms to paint and grow the Koch curve. The "growing" of a Koch curve depends simply on the existence of a prototype and not on the specific pattern it implements. In such, rather than hard code the pattern, we will use the Factory design pattern to generate the list of Koch curves. This will decouple the growing of the Koch curve from the pattern with which it is growing. Since growing a Koch is a recursive process, the factory is used to generate the base case as well. A Koch snowflake is simply a Koch curve that starts in the peculiar situation of a set of base case curves in a pattern different than the growing pattern. The base case of a snowflake is generated by a factory just like a normal Koch curve. It uses another factory to generate its set of base case Koch curves. This Composite pattern thus allows dynamic compositional capabilities and arbitrarily complex snowflakes can thus be generated. Of course, the original code to grow the curve will still operate unmodified. This activity is adapted from a laboratory used by introductory students in the Oberlin College's CS150 "Principles of Computer Science I" course. It is the sixth in a series of weekly labs. This lab is preceded by two labs that develop the notions of circular linked lists, immutable linear linked lists and recursive algorithms. |