12.8: From the Java Library- javax.swing.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 selection or choose a selection from a list that appears when the user requests 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 position within the menu ( getSelectedIndex()). There are also methods 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 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 interface 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:

private String items[] = 
    {"Sierpinski Gasket","Nested Boxes"};
private JComboBox patterns = new JComboBox(items);
private JComboBox levels = new JComboBox();

Note that in this case we pass the constructor for the menu an entire array of items. If we hadn’t done it this way, we would add individual items to the combo box in the JFrame’s constructor RecursivePatterns(). In fact, that’s how we’ll initialize the levels menu:

for (int k=0; k < 10; k++)   // Add 10 levels
    levels.addItem(k + "" );
levels.setSelectedItem("4"); // Select default level

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:

controls.add(levels);    // Control panel for menus
controls.add(patterns);
                                // Add the controls
getContentPane().add(controls, "North"); 
                           // And the drawing panel
getContentPane().add(canvas, "Center");  
              // Register the menus with a listener
levels.addItemListener(this);  
patterns.addItemListener(this);

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:

public void itemStateChanged(ItemEvent e) {
    canvas.setPattern(patterns.getSelectedIndex(), 
                         levels.getSelectedIndex());
    repaint();
}

The itemStateChanged() method has the same general form as the actionPerformed() method, except that its parameter is an . For this example, the program uses the getSelectedIndex() 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 [fig-seqdiag] 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 [fig-recursivepatterns].

-3pc

import java.awt.*;
import javax.swing.*;
import java.awt.event.*;

public class RecursivePatterns extends JFrame implements ItemListener  {
  private String choices[] = {"Sierpinski Gasket", "Nested Boxes"};
  private JComboBox patterns = new JComboBox(choices); // Pattern choices
  private JComboBox levels = new JComboBox();          // Level choices
  private Canvas canvas = new Canvas();                // Drawing panel
  private JPanel controls = new JPanel();

  public RecursivePatterns() {
    for (int k=0; k < 10; k++)            // Add 10 levels
      levels.addItem(k + "" );
    patterns.setSelectedItem(choices[0]); // Initialize menus
    levels.setSelectedItem("4");

    canvas.setBorder(BorderFactory.createTitledBorder("Drawing Canvas"));
    controls.add(levels);         // Control panel for menus
    controls.add(patterns);
    getContentPane().add(controls,"North"); // Add controls
    getContentPane().add(canvas,"Center");  // Add drawing panel
    levels.addItemListener(this);   // Register menus with listener
    patterns.addItemListener(this);
    setSize(canvas.WIDTH,canvas.HEIGHT+controls.getSize().width);
  } // init()

  public void itemStateChanged(ItemEvent e) {
    canvas.setPattern(patterns.getSelectedIndex(), 
                                     levels.getSelectedIndex());
    repaint();                             // Repaint the JFrame
  } // itemStateChanged()

   public static void main(String args[]) 
   {  
      JFrame f = new RecursivePatterns();
      f.setVisible(true);
   }
} // RecursivePatterns

The actual drawing of the fractal patterns is handled by the canvas JPanel component, whose design is shown in Figure [fig-canvas] and whose implementation is given in Figure [fig-canvaspanel]. All of the drawing is done in the paintComponent() method. Because the canvas is contained within the JFrame, the paintComponent() method is called automatically whenever the JFrame repaints itself. Notice how the switch statement uses the pattern that the user chose to call the corresponding drawing method. You can see from this switch statement that a JComboBox’s items are zero indexed.

-7pc

import javax.swing.*;
import java.awt.*;

public class Canvas extends JPanel {
  private static final int GASKET = 0, BOXES = 1;
  public static final int WIDTH=400, HEIGHT=400;
  private final int HBOX=10, VBOX=50, BOXSIDE=200, BOXDELTA=10;
  private final int gP1X = 10;  private final int gP1Y = 280; // Initial
  private final int gP2X = 290; private final int gP2Y = 280; // gasket
  private final int gP3X = 150; private final int gP3Y = 110; // points
  private int pattern = 0 ;                      // Current pattern
  private int level = 4;                         // Current level

  public Canvas() {
    setSize(WIDTH, HEIGHT);
  }

  public void setPattern(int pat, int lev) {
    pattern = pat;
    level = lev;
  }

    public void paintComponent(Graphics g) {
        g.setColor(getBackground());   // Redraw the panel's background
        g.drawRect(0, 0, WIDTH, HEIGHT);
        g.setColor(getForeground());
        switch (pattern) {
        case GASKET:
            drawGasket(g, level, gP1X, gP1Y, gP2X, gP2Y, gP3X, gP3Y);
            break;
        case BOXES:
            drawBoxes(g, level, HBOX, VBOX, BOXSIDE, BOXDELTA );
            break;
        } // switch
    } // paintComponent()

   /** drawGasket()---recursively draws the Sierpinski 
    *  gasket pattern, with points (p1X, p1Y), (p2X, p2Y), (p3X, p3Y) 
    *  representing the vertices of its enclosing triangle.
    * level (>= 0) is the recursion parameter (base case: level  0)
    */
    private void drawGasket(Graphics g, int lev, int p1X, int p1Y,
                   int p2X, int p2Y, int p3X, int p3Y) {
        g.drawLine(p1X, p1Y, p2X, p2Y);  // Draw a triangle
        g.drawLine(p2X, p2Y, p3X, p3Y);
        g.drawLine(p3X, p3Y, p1X, p1Y);
        if (lev > 0) { // If more levels, draw 3 smaller gaskets
            int q1X = (p1X + p2X) / 2;    int q1Y = (p1Y + p2Y) / 2;
            int q2X = (p1X + p3X) / 2;    int q2Y = (p1Y + p3Y) / 2;
            int q3X = (p2X + p3X) / 2;    int 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);
        }
    } // drawGasket()
   /** drawBoxes()---recursively draws pattern of nested squares 
    *  with (locX, locY) the top left corner of outer the square and
    *  side being the length square's side.
    * level (>= 0) is the recursion parameter (base case: level  0)
    * delta is used to adjust the length of the side.
    */
    private void drawBoxes(Graphics g, int level,
           int locX, int locY, int side, int delta) {
        g.drawRect(locX, locY, side, side );
        if (level > 0) {
            int newLocX = locX + delta; int newLocY = locY + delta;
            drawBoxes(g, level - 1, newLocX, newLocY,
                                          side - 2 * delta, delta);
        }
    } // drawBoxes()
} // Canvas

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

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 recursive 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.

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 algorithm 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.

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

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

Definition: twoToN(N), N >= 0
  1, if N == 0                   // Base case
  2 * twoToN(N - 1),  N > 0      // Recursive case

The function \(x^n\) is known as the power function:

Definition: power(X,N), N >= 0
  1, if N == 0                    // Base case
  X * power(X, N - 1),  N > 0     // Recursive case

Yes, the two definitions for nested boxes are equivalent. Suppose 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.

A recursive definition for the pattern in Figure 12.4:

Draw a square with side, s.
Inscribe a circle with diameter, s.
If s > 5,
  Draw a smaller version of same pattern. // Recursive case

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

A definition for countDown():

 /** countDown(N) recursively prints a countdown 
  *  beginning at N and ending at 1
  * @param N >= 1
  * Base case: N == 0
  */
void countDown(int N) {
    if (N == 0)                     // Base case
        System.out.println("blastoff");
    else {
        System.out.print(N + ", "); // Recursive case
        countDown(N - 1);
    }
} // countDown()

A revised definition for countDown():

 /** countDown(N) recursively prints a countdown  
  *  beginning at N, counting every other number, 10 8 6 ...  
  *  and ending at "blastoff"
  * @param N >= 1
  * Base case: N <= 0
  */
void countDown(int N) {
    if (N <= 0)                     // Base case
        System.out.println("blastoff");
    else {
        System.out.print(N + ", "); // Recursive case
        countDown(N - 2 );
    }
} // countDown()

A method to sum the numbers from 1 to N.

int sum(int N) {
    if (N == 0)
        return 0;
    else
        return N + sum(N-1);
}

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

String addBlanks(String s) {
  if (s.length() == 0)
     return "";
  else if (s.charAt(0) == ' ')
     return ' ' + s.charAt(0) + addBlanks(s.substring(1));
  else
     return s.charAt(0) + addBlanks(s.substring(1));
}

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.

 public static void printOutcomes(String str, int N){
     if (N = 1){ // Base case: win, lose, or draw one game
         System.out.println(str + "W");
         System.out.println(str + "L");
         System.out.println(str + "D");
     } else {  // Recursive case
         printOutcomes(str + "W", N - 1);
         printOutcomes(str + "L", N - 1);
         printOutcomes(str + "D", N - 1);
     } //else
 }// printOutcomes()

public static void main(String args[]) {
  int numbers[] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18};
  Searcher searcher = new Searcher();
  for (int k = 0; k <= 20; k++) {
    int result = searcher.search(numbers, k);
    if (result != -1)
      System.out.println(k + " found at " + result);
    else
      System.out.println(k + " is not in the array ");
  } // for
} // main()

The sort() method is used as a public interface to the recursive selectionSort() method:

/** sort(arr) sorts the int array, arr
 *  Pre: arr is not null
 *  Post: arr will be arranged so that arr[j] <= arr[k] 
 *     for any j < k
 */
public void sort(int arr[]) {
    selectionSort(arr, arr.length - 1);  
             // Just call the recursive method
}

An iterative version of findMax():

 /** findMax (arr,N) returns the index of the largest
  *  value between arr[0] and arr[N], N >= 0.
  *  Pre: 0 <= N <= arr.length -1
  *  Post: arr[findMax()]>=arr[k] for k between 0 and N.
  */
private int findMax(int arr[], int N) {
    int maxSoFar = 0;
    for (int k = 0; k <= N; k++)
        if (arr[k] > arr[maxSoFar])
            maxSoFar = k;
    return maxSoFar;
} // findMax()

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

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.

private void  drawBoxes(Graphics g, int level, int locX, 
                   int locY, int side, int delta) {
    g.drawRect(locX, locY, side, side );
    if (level > 0) {
      int dside = side * delta / 100; // Percent delta
      int newLocX = locX + dside;
      int newLocY = locY + dside;
      drawBoxes(g, level - 1, newLocX, newLocY, 
                         side - 2 * dside, delta);
    }
} // drawBoxes()

private void drawBoxesIterative(Graphics g, int level,  
            int locX, int locY, int side, int delta) {
 for (int k = level; k >= 0; k--) {
  g.drawRect(locX, locY, side, side );  // Draw a square
  locX += delta;             // Calculate new location
  locY += delta;
  side -= 2 * delta;         // Calculate new side length
 }
} // drawBoxes()

The level two and three gaskets are shown in Figure [fig-sierpinski23].

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

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.

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.

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

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

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

Write a recursive method to print each element of an array of double.

Write a recursive method to print each element of an array of double from the last to the first element.

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

Write a recursive method that is passed a single int parameter, \(N \geq 0\), and prints all the odd numbers between 1 and N.

Write a recursive method that takes a single int parameter and prints the sequence of even numbers between N down to 0.

Write a recursive method that takes a single int parameter \(N \geq 0\) and prints the multiples of 10 between 0 and N.

Write a recursive method to print the following geometric

#
# #
# # #
# # # #
# # # # #

Write recursive methods to print each of the following

# # # # # # # #     # # # # # # # #
  # # # # # # #     # # # # # # #
    # # # # # #     # # # # # #
      # # # # #     # # # # #
        # # # #     # # # #
          # # #     # # #
            # #     # #
              #     #

Write a recursive method to print all multiples of M up to * N.

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

Write a recursive method to count the occurrences of a substring within a string.

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

Implement a recursive version of the Caesar.decode() method from Chapter 8.

The Fibonacci sequence (named after the Italian mathematician 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 preceding numbers. Write a recursive method fibonacci(N) that prints the first N Fibonacci numbers.

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

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

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.

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.

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.

Challenge: Towers of Hanoi. According to legend, some Buddhist 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"):

Move 1 disk from A to B.
Move 1 disk from A to C.
Move 1 disk from B to C.
Move 1 disk from A to B.
Move 1 disk from C to A.
Move 1 disk from C to B.
Move 1 disk from A to B.