Java, Java, Java: From the Java Library: javax.swing.JComboBox

15. Recursive Problem Solving

15.9. From the Java Library: javax.swing.JComboBox

A JComboBox is a Swing component that combines a text field and a drop-down list (Fig. 12.28). It lets the user either type in a selec- tion or choose a selection from a list that appears when the user re- quests it—a JComboBox’s drop-down behavior is somewhat similar to a java.awt.Choice box.

A JComboBox can be used to represent a drop-down menu. When the user clicks on a JComboBox, a list of options drops down, and the user can select a particular option that is stored in the box’s internal state (Fig. 12.29). The list of options associated with a JComboBox can be built beforehand and inserted into the component in a constructor, or items can be inserted one at a time by repeatedly using its addItem() method.

As Figure 12.28 shows, either an array or a vector of items can be passed to a constructor method to initialize the box’s menu. The items stored in a JComboBox box are references to Objects, most commonly Strings that represent the name of the menu item. They are stored in the (zero indexed) order in which they are added. The addItem() method is used to add an individual Object to a JComboBox. By default, the first item added to a JComboBox will be the selected item until the user selects another item.

When the user makes a selection in a JComboBox, the item selected can be gotten either by its reference (getSelectedItem()) or by its po- sition within the menu (getSelectedIndex()). There are also meth- ods to setSelectedItem() and setSelectedIndex() that let you

select an individual item either by its reference or its position.The

addItemListener() method is used to designate some object as the listener for the ItemEvents that are generated whenever the user selects

a menu option. Alternatively, the addActionListener() method lets

you handle action events, such as when the user types a value into the box.

A JComboBox Example

As a simple example, let’s design an graphical interface that can be used to display the fractal patterns we developed earlier. We want an inter- face that lets the user select from among the available patterns—we’ll use the Sierpinski gasket and nested boxes for starters. In addition, the user should also be able to select different levels for the drawings, from 0 to 9. We want to present these options in two menus, with one JComboBox for each menu.

The first step is to declare and instantiate the JComboBoxes as instance variables:

Figure 12.28: A JComboBox re-

sponds to action events and item events.

Note that in this case we pass the constructor for the patterns menu

an entire array of items.If we hadn’t done it this way, we would

Figure 12.29: Using a JComboBox

box.

add individual items to the combo box in the JFrame’s constructor RecursivePatterns(). In fact, that’s how we’ll initialize the levels menu:

This loop would be placed in the JFrame’s constructor, RecursivePatterns().

It adds strings representing levels 0 to 9 to the menu and initializes the box so that level four is showing as the default option.

Our next step is to designate the JFrame as the ItemListener for both menus—that is, the JFrame is named as the object that will handle the events that occur in the JComboBoxes. Then we add the JComboBox component to the JFrame:

Note that we use a separate controls panel (a JPanel) for the two menus and a canvas panel (another JPanel) for the drawings.

The next step is to implement the itemStateChanged() method to handle the user’s selections. Whenever the user selects an item from a JComboBox menu, an ItemEvent is generated. In order to handle these events, the program must implement the ItemListener interface, which consists of the single method itemStateChanged(). This method is invoked automatically whenever the user selects an item from one of the JComboBoxes:

The itemStateChanged() method has the same general form as the actionPerformed() method, except that its parameter is an ItemEvent. For this example, the program uses the getSelected- Index() method to get the selected pattern and the selected level by their respective item numbers within the menus. It then passes these values along to the canvas object, which takes care of the drawing. Finally, the method invokes the repaint() method. Because the JFrame is a container, this will cause all of its components to be repainted as well.

Figure 12.30: This UML sequence diagram shows the interaction between the various objects in- cluded in the action of selecting an item from a JComboBox.

Figure 12.30 illustrates the sequence of events that occurs when an item is selected from a JComboBox. The complete implementation for the program is given in Figure 12.31.

The actual drawing of the fractal patterns is handled by the canvas JPanel component, whose design is shown in Figure 12.32 and whose implementation is given in Figure 12.33. All of the drawing is done in the paintComponent() method. Because the canvas is contained within the JFrame, the paintComponent() method is called automati- cally whenever the JFrame repaints itself. Notice how the switch state-

ment uses the pattern that the user chose to call the corresponding draw-Zero indexing

ing method. You can see from this switch statement that a JComboBox’s items are zero indexed.

580CHAPTER 12 • Recursive Problem Solving

import j ava . awt . ∗ ;

import j avax . swing . ∗ ;

import j ava . awt . event . ∗ ;

public c l a s s Recursive Patterns extends JFrame implements I tem Listener

private S t r i n g choices [ ] =” S i e r p i n s k i Gasket ” , ” Nested Boxes” ;

private JComboBox pa t t e r n s = new JComboBox ( choices ) ; // P a t t e r n c h o i c e s

private JComboBox l e v e l s = new JComboBox ( ) ;// L e v e l c h o i c e s private Canvas canvas = new Canvas ( ) ;// D r a w i n g p a n e l private JPanel c o n t r o l s = new JPanel ( ) ;

public Recursive Patterns ( )

for ( in t k = 0 ; k < 1 0 ; k++)// Add 1 0 l e v e l s

l e v e l s . addItem ( k + ”” ) ;

pa t t e r n s . s e t S e l e c t e d I t e m ( choices [ 0 ] ) ; // I n i t i a l i z e m e n u s

l e v e l s . s e t S e l e c t e d I t e m ( ”4 ” ) ;

canvas . set Border ( Border Factory . c r e a t e T i t l e d B o r de r ( ”Drawing Canvas” ) ) ; c o n t r o l s . add ( l e v e l s ) ;// C o n t r o l p a n e l f o r m e n u s

c o n t r o l s . add ( pa t t e r n s ) ;

get Content Pane ( ) . add ( cont r ols , ” North” ) ; // Add c o n t r o l s

get Content Pane ( ) . add ( canvas , ” Center ” ) ;// Add d r a w i n g p a n e l

l e v e l s . add Item Listener ( t h i s ) ;// R e g i s t e r m e n u s w i t h l i s t e n e r

pa t t e r n s . add Item Listener ( t h i s ) ;

s e t S i z e ( canvas .WIDTH, canvas . HEIGHT+c o n t r o l s . ge t Size ( ) . width ) ;

} // i n i t ( )

public void itemStateChanged ( ItemEvent e )

canvas . s e t P a t t e r n ( pa t t e r n s . get Selected Index ( ) ,

l e v e l s . get Selected Index ( ) ) ;

r e pa int ( ) ;// R e p a i n t t h e J F r a m e

} // i t e m S t a t e C h a n g e d ( )

public s t a t i c void main ( S t r i n g args [ ] )

{JFrame f = new Recursive Patterns ( ) ; f . s e t V i s i b l e ( t rue ) ;

}

// R e c u r s i v e P a t t e r n s

Figure 12.31: The RecursivePatterns program.

CHAPTER SUMMARYTechnical Terms

base case computational

overhead head-and-tail

algorithm

iterative method last-in-first-out

(LIFO)

method call stack recursion parameter

recursive case recursive definition recursive method self-similarity

tail recursive

sign of a drawing

CHAPTER 12 • Chapter Summary581

Figure 12.33: The Canvas class is a drawing panel, Part I.

Summary of Important Points

A recursive definition is one that defines the nth case of a concept in terms of the (n 1)st case plus a limiting condition. It is based on the idea of breaking a problem up into smaller, self-similar problems.

A recursive method is one that calls itself. It is usually defined in terms of a base case or limiting case, which stops the recursive process, and a re- cursive case, which breaks the method into a smaller, self-similar copy of itself. A recursion parameter is generally used to control the recursion. An iterative algorithm is one that uses some kind of loop as its control structure. Any algorithm that can be done iteratively can also be done recursively, and vice versa.

public void paintComponent ( Graphics g )

g . set Color ( getBackground ( ) ) ;// R e d r a w t h e p a n e l ’ s b a c k g r o u n

g . drawRect ( 0 , 0 , WIDTH, HEIGHT ) ;

g . set Color ( getForeground ( ) ) ;

switch ( pattern )

case GASKET:

drawGasket ( g , l e ve l , gP1X , gP1Y , gP2X , gP2Y , gP3X , gP3Y ) ;

break ;

case BOXES :

drawBoxes ( g , le ve l , HBOX, VBOX, BOXSIDE , BOXDELTA ) ;

break ;

} // s w i t c h

} // p a i n t C o m p o n e n t ( )

/ ∗ ∗ d r a w G a s k e t () − − − r e c u r s i v e l y d r a w s t h e S i e r p i n s k i

∗g a s k e t p a t t e r n , w i t h p o i n t s ( p 1 X , p 1 Y ) , ( p 2 X , p 2 Y ) , ( p 3 X , p 3 Y )

∗r e p r e s e n t i n g t h e v e r t i c e s o f i t s e n c l o s i n g t r i a n g l e .

∗ l e v e l ( > = 0 ) i s t h e r e c u r s i o n p a r a m e t e r ( b a s e c a s e : l e v e l0 )

∗/

private void drawGasket ( Graphics g , in t lev , in t p1X , in t p1Y ,

in t p2X , in t p2Y , in t p3X , in t p3Y)

g . drawLine ( p1X , p1Y , p2X , p2Y ) ;// Draw a t r i a n g l e

g . drawLine ( p2X , p2Y , p3X , p3Y ) ; g . drawLine ( p3X , p3Y , p1X , p1Y ) ;

i f ( lev > 0 )// I f m o r e l e v e l s , d r a w 3 s m a l l e r g a s k e t s

in t q1X = ( p1X + p2X) / 2 ;in t q1Y = ( p1Y + p2Y) / 2 ; in t q2X = ( p1X + p3X) / 2 ;in t q2Y = ( p1Y + p3Y) / 2 ; in t q3X = ( p2X + p3X) / 2 ;in t q3Y = ( p2Y + p3Y) / 2 ;

drawGasket ( g , lev − 1 , p1X , p1Y , q1X , q1Y , q2X , q2Y ) ; drawGasket ( g , lev − 1 , p2X , p2Y , q1X , q1Y , q3X , q3Y ) ; drawGasket ( g , lev − 1 , p3X , p3Y , q2X , q2Y , q3X , q3Y ) ;

}

} // d r a w G a s k e t ( )

/ ∗ ∗ d r a w B o x e s () − − − r e c u r s i v e l y d r a w s p a t t e r n o f n e s t e d s q u a r e s

∗w i t h ( l o c X , l o c Y ) t h e t o p l e f t c o r n e r o f o u t e r t h e s q u a r e a n d

∗s i d e b e i n g t h e l e n g t h s q u a r e ’ s s i d e .

∗ l e v e l ( > = 0 ) i s t h e r e c u r s i o n p a r a m e t e r ( b a s e c a s e : l e v e l0 )

∗ d e l t a i s u s e d t o a d j u s t t h e l e n g t h o f t h e s i d e .

∗/

private void drawBoxes ( Graphics g , in t l e ve l ,

in t locX , in t locY , in t side , in t de l t a ) g . drawRect ( locX , locY , side , s ide ) ;

i f ( l e v e l > 0 )

in t newLocX = loc X + de l t a ; in t newLocY = loc Y + de l t a ; drawBoxes ( g , l e v e l − 1 , newLocX , newLocY ,

s ide − 2 ∗ delta , de l t a ) ;

}

} // d r a w B o x e s ( )

// C a n v a s

Figure 12.33: The Canvas class, Part II.

Because method calling is relatively costly both in terms of memory used and CPU time involved, a recursive algorithm is generally less efficient than an iterative one that does the same thing.

In designing recursive algorithms, the base case defines a limit. Each level of recursion should make progress toward the limit, and the algo- rithm should eventually reach the limit. The limit is usually expressed in terms of the recursion parameter.

A recursive method is tail recursive if and only if each of its recursive calls is the last action executed by the method.

A Swing JComboBox component is used to represent a GUI drop- down menu.

SOLUTION 12.1 The output produced by mystery(0) would be 0 1 2 3 4 5 6. The output produced by mystery(100) would be 100.

SOLUTION 12.2 The output produced by mystery(5) would be: 5 4 3, and so on. In other words, this is an infinite recursion.

SOLUTION 12.3

SOLUTIONS TO

SELF-STUDY EXERCISES

SOLUTION 12.4 The function xn is known as the power function:

SOLUTION 12.5 Yes, the two definitions for nested boxes are equivalent. Sup- pose the square starts out with a side of 20. The definition given in the exercise will also draw squares with sides of 20, 15, 10, 5.

SOLUTION 12.6 A recursive definition for the pattern in Figure 12.4:

SOLUTION 12.7 The printString2("hello") method will print: “olleh.”

SOLUTION 12.8 A definition for countDown():

SOLUTION 12.9 A revised definition for countDown():

SOLUTION 12.10 A method to sum the numbers from 1 to N.

SOLUTION 12.11 A method to change each blank within a string to two blanks.

SOLUTION 12.12 A method to print out all possible outcomes for a chess player playing N games. printOutcomes(str, N) will print all outcomes for the next N games given that results for previous games are stored in the string named str.

SOLUTION 12.13

SOLUTION 12.14 The sort() method is used as a public interface to the recur- sive selectionSort() method:

Level 4

SOLUTION 12.15 An iterative version of findMax():

Level 5

Figure 12.34: Levels four and five of the nested boxes pattern.

SOLUTION 12.16 Levels four and five of the nested boxes pattern are shown in Figure 12.34.

SOLUTION 12.17 The following method will reduce the length of the side by delta percent at each level of recursion. The spacing between the boxes will vary by a constantly decreasing amount.

Figure 12.35: Levels two and three of the Sierpinski gasket.

SOLUTION 12.18

SOLUTION 12.19 The level two and three gaskets are shown in Figure 12.35.

SOLUTION 12.20 The printReverse() method is not tail recursive because in that method the recursive call is not the last statement executed.

SOLUTION 12.21 The countChar() method is tail recursive. The recursive calls are not the last statements in the method definition. However, each of the recursive calls would be the last statement executed by the method.

EXERCISE 12.1 Explain the difference between the following pairs of terms:

Iteration and recursion.

Recursive method and recursive definition.

Base case and recursive case.

Head and tail.

Tail and nontail recursive.

EXERCISE 12.2 Describe how the method call stack is used during a method call and return.

EXERCISE 12.3 Why is a recursive algorithm generally less efficient than an iterative algorithm?

EXERCISE 12.4 A tree, such as a maple tree or pine tree, has a recursive struc- ture. Describe how a tree’s structure displays self-similarity and divisibility.

EXERCISE 12.5 Write a recursive method to print each element of an array of

double.

EXERCISE 12.6 Write a recursive method to print each element of an array of

double from the last to the first element.

EXERCISE 12.7 Write a recursive method that will concatenate the elements of an array of String into a single String delimited by blanks.

EXERCISES

Note: For programming exercises, first draw a UML class diagram describing all classes and their inheritance relationships and/or associations.

EXERCISE 12.8 Write a recursive method that is passed a single int parameter,

N ≥ 0, and prints all the odd numbers between 1 and N.

EXERCISE 12.9 Write a recursive method that takes a single int parameter

N ≥ 0 and prints the sequence of even numbers between N down to 0.

EXERCISE 12.10 Write a recursive method that takes a single int parameter

N ≥ 0 and prints the multiples of 10 between 0 and N.

EXERCISE 12.11 Write a recursive method to print the following geometric pattern:

EXERCISE 12.12 Write recursive methods to print each of the following patterns.

EXERCISE 12.13 Write a recursive method to print all multiples of M up to

M * N.

EXERCISE 12.14 Write a recursive method to compute the sum of grades stored in an array.

EXERCISE 12.15 Write a recursive method to count the occurrences of a sub- string within a string.

EXERCISE 12.16 Write a recursive method to remove the HTML tags from a string.

EXERCISE 12.17 Implement a recursive version of the Caesar.decode()

method from Chapter 8.

EXERCISE 12.18 The Fibonacci sequence (named after the Italian mathemati- cian Leonardo of Pisa, ca. 1200) consists of the numbers 0,1,1,2,3,5,8,13,... in which each number (except for the first two) is the sum of the two preced- ing numbers. Write a recursive method fibonacci(N) that prints the first N Fibonacci numbers.

EXERCISE 12.19 Write a recursive method to rotate a String by N characters to the right. For example, rotateR("hello", 3) should return “llohe.”

EXERCISE 12.20 Write a recursive method to rotate a String by N characters to the left. For example, rotateL("hello", 3) should return “lohel.”

EXERCISE 12.21 Write a recursive method to convert a String representing a binary number to its decimal equivalent. For example, binTodecimal("101011") should return the int value 43.

EXERCISE 12.22 A palindrome is a string that is equal to its reverse—“mom,” “i,” “radar” and “able was i ere i saw elba.” Write a recursive boolean method that determines whether its String parameter is a palindrome.

EXERCISE 12.23 Challenge: Incorporate a drawBinaryTree() method into the RecursivePatterns program. A level-one binary tree has two branches. At each subsequent level, two smaller branches are grown from the endpoints of every existing branch. The geometry is easier if you use 45-degree angles for the branches. Figure 12.36 shows a level-four binary tree drawn upside down.

EXERCISE 12.24 Challenge: Towers of Hanoi. According to legend, some Bud- dhist monks were given the task of moving 64 golden disks from one diamond needle to another needle, using a third needle as a backup. To begin with, the disks were stacked one on top of the other from largest to smallest (Fig. 12.37). The rules were that only one disk can be moved at a time and that a larger disk can never go on top of a smaller one. The end of the world was supposed to occur when the monks finished the task!

Write a recursive method, move(int N, char A, char B, char C), that will print out directions the monks can use to solve the towers of Hanoi problem. For example, here’s what it should output for the three-disk case, move(3, "A", "B", "C"):

Figure 12.36: A level-four binary tree pattern.

ABC

Figure 12.37: The towers of Hanoi problem. Move all the disks from needle A to needle B. Only one disk can be moved at a time, and a larger disk can never go on top of a smaller one.

Chapter 13