slanted W3C logo

Day 24 — Collections II

Today we look at chained traversal of a collection, searching a collection for a particular element, and computational complexity.

Review: Indexed Traversal

The Portfolio class supports indexed access of the elements it holds:

      // Portfolio with capacity 3
      Portfolio pf = new Portfolio("My Portfolio", 3);
      
      Investment inv0 = new Investment( new Stock("HR.A"), 1, 1.00 );
      Investment inv1 = new Investment( new Stock("HR.B"), 1, 2.00 );
      Investment inv2 = new Investment( new Stock("HR.C"), 1, 3.00 );
      pf.add(inv0);
      pf.add(inv1);
      pf.add(inv2);
      
      Investment inv = pf.get(1);
      output.println(inv);

To iterate over the investments, the client writes a loop that counts from 0 to the size - 1:

      for (int i = 0; i < pf.size(); i++)
      {
         Investment inv = pf.get(i);
         // do something with the investment here ...
      }
import java.io.PrintStream;
import type.lib.Investment;
import type.lib.Stock;
import type.lib.Portfolio;

public class Collections5
{
   public static void main(String[] args)
   {
      PrintStream output = System.out;
      
      Portfolio pf = new Portfolio("My Portfolio", 3);
      
      Investment inv0 = new Investment( new Stock("HR.A"), 1, 1.00 );
      Investment inv1 = new Investment( new Stock("HR.B"), 1, 2.00 );
      Investment inv2 = new Investment( new Stock("HR.C"), 1, 3.00 );
      pf.add(inv0);
      pf.add(inv1);
      pf.add(inv2);

      for (int i = 0; i < pf.size(); i++)
      {
         Investment inv = pf.get(i);
         output.println(inv);
      }
   }
}

Chained Traversals

Some collections provide chained traversal instead of indexed traversal. In chained traversal, the client gets the first element in the collection, and then the next, and then the next, and so on until there are no more elements.

The traversal order depends on the implementation details of the collection. Some collections will traverse the elements in a "natural" (sorted) order, whereas other collections will traverse the elements in some order not meaningful to the client. All that is guaranteed is that the traversal visits every element, and each element is visitied only once.

Chained Traversal

Both Portfolio and GlobalCredit support chained traversal. To perform a chained traversal, the client writes a loop:

      // make a portfolio filled with random investments 
      Portfolio pf = Portfolio.getRandom();
      
      final int PERCENT = 100;
      for (Investment i = pf.getFirst();
           i != null;
           i = pf.getNext())
      {
         double bookValue = i.getQty() * i.getBookValue();
         Stock s = i.getStock();
         double currValue = i.getQty() * s.getPrice();
         double yield =
            (currValue - bookValue) / bookValue * PERCENT;
         output.printf("yield for %s is %.2f%%%n",
                       s.getName(), yield);
      }                       

If getFirst returns null, the collection is empty and the loop will be skipped. Otherwise, the loop visits one investment per iteration until getNext returns null.

import java.io.PrintStream;
import type.lib.Investment;
import type.lib.Stock;
import type.lib.Portfolio;

public class Collections6
{
   public static void main(String[] args)
   {
      PrintStream output = System.out;
      
      // make a portfolio filled with random investments 
      Portfolio pf = Portfolio.getRandom();
      
      final int PERCENT = 100;
      for (Investment i = pf.getFirst();
           i != null;
           i = pf.getNext())
      {
         double bookValue = i.getQty() * i.getBookValue();
         Stock s = i.getStock();
         double currValue = i.getQty() * s.getPrice();
         double yield =
            (currValue - bookValue) / bookValue * PERCENT;
         output.printf("yield for %s is %.2f%%%n",
                       s.getName(), yield);
      } 
   }
}

Searching by Traversal

Once you have a collection of things it becomes a very frequent occurrence that you want to find a particular element of the collection. For example, you might want to search for:

In one type of search, you are only interested whether or not the element is in the collection (you don't need a reference to the element). This type of search returns a boolean value (true if the element is in the collection, and false otherwise).

A second type of search, you want the reference to the searched for element. This type of search returns a reference to an object if the element is in the collection, and null otherwise.

Search by Traversal I

Both kinds of search can be solved using traversal. By visiting every element in the collection you can determine if a particular element is in the collection using equals and a boolean variable.

The following loop incorrectly searches for an investment of a particular stock in a portfolio:

      Portfolio pf = Porfolio.getRandom();

      // the stock to search for      
      Stock st = new Stock(".MP");
      
      boolean found = false;
      for (Investment i = pf.getFirst();
           i != null;
           i = pf.getNext())
      {
         found = i.getStock().equals(st);
      }

The above loop uses traversal to visit every investment in the portfolio. The problem with the loop is that the value of found is determined by the last investment visited in the traversal.

Search by Traversal I

To correct the loop, we need to stop the loop when found becomes true; that is, we want the loop to run whenever the investment is not null AND found is false:

      // the stock to search for      
      Stock st = new Stock(".MP");

      boolean found = false;
      for (Investment i = pf.getFirst();
           i != null && !found;
           i = pf.getNext())
      {
         found = i.getStock().equals(st);
      }

!found (NOT found) is equivalent to found == false.

Search by Traversal II

When a reference to the searched for object is needed, you use the exact same approach except you also need a reference variable to hold the reference to the searched for object:

      boolean found = false;
      Investment inv = null;
      for (Investment i = pf.getFirst();
           i != null && !found;
           i = pf.getNext())
      {
         found = i.getStock().equals(st);
         if (found)
         {
            inv = i;
         }
      }
      
      if (found)
      {
         output.printf("you have %d shares of %s%n",
                        inv.getQty(),
                        st.getName());
      }
      else
      {
         output.printf("you have no investments in %s%n",
                        st.getName());
      }
import java.io.PrintStream;
import type.lib.Investment;
import type.lib.Stock;
import type.lib.Portfolio;

/*
   WARNING: You might have to run this program many
   times before it generates a random portfolio with
   an .MP stock investment. 
*/

public class Collections7
{
   public static void main(String[] args)
   {
      PrintStream output = System.out;
      
      // make a portfolio filled with random investments 
      Portfolio pf = Portfolio.getRandom();
      
      // the stock to search for      
      Stock st = new Stock(".MP");

      boolean found = false;
      Investment inv = null;
      for (Investment i = pf.getFirst();
           i != null && !found;
           i = pf.getNext())
      {
         found = i.getStock().equals(st);
         if (found)
         {
            inv = i;
         }
      }
      
      if (found)
      {
         output.printf("you have %d shares of %s%n",
                        inv.getQty(),
                        st.getName());
      }
      else
      {
         output.printf("you have no investments in %s%n",
                        st.getName());
      }

   }
}

Search by Traversal III

The previous two types of search stopped after we found the first element that satisified the search criteria. Another kind of search looks for all of the elements that satisfy the search criteria. For example, we might want to count all investments in a portfolio where the stock name begins with a letter in the range [A-M]:

      final String SPLIT = "N";
      int num = 0;
      boolean found = false;
      for (Investment i = pf.getFirst();
           i != null;
           i = pf.getNext())
      {
         String namei = i.getStock().getName();
         if (SPLIT.compareToIgnoreCase(namei) > 0)
         {
            num++;
         }
      }
      output.println(num);

Computational Complexity

Computational complexity is a branch of theoretical computer science concerned with classifying computational problems based on their difficulty. One measure of difficulty is the worst-case complexity: how many basic operations are required to solve a problem of size N where N is a large number.

For search of a collection, N is the size of the collection. In the worst case, you have to visit all N elements in the collection. We say that the complexity of exhaustive search is O(N).

O(N) is pronounced "big-O of N" or "order of N".

Computational Complexity

Suppose you wanted to output the investments in a portfolio in order from the smallest total current value to the highest total current value. A simple algorithm that can perform this sorting is called selection sort.

1. find the investment with the smallest current value
      output it and remove it from the portfolio
2. repeat step 1
3. continue repeating step 1 until the portfolio is empty

What is the worst-case complexity of step 1? What is the worst-case complexity of the entire algorithm?

To Do For Next Lecture