The Data Structures Library in Java

JDSL Tutorial

Previous Lesson
Table of Contents
Next Lesson


Lesson 3: Auction

In the previous lessons, we learned about JDSL Sequences.  In this lesson, we will learn how to work with JDSL Positions, as we study this demo application which simulates an on-line auction.

New concepts covered:


There are eight source files involved in this application.  The first files describe the entity classes:

These files describe the user interface and the control classes:

This is a Java application.  The main method is in the AuctionSimulator class.  This method opens up a frame that simulates a running auction.  The auction begins when you either enter a bid, or click the start button.  As the auction progresses, bids from others are simulated.  You can top an existing bid, or withdraw from the auction.  When the auction ends, the winner is announced.


The only class we will examine in the tutorial is Auction.  The other classes -- not relevant to our lesson -- make use of only standard java, and the GUI code was produced using Visual Cafe, from Symantec.

The Auction class takes advantage of Positions to maintain a Sequence of Bid objects. Positions are a type of Accessor, an object that accesses the interior of a Container without violating encapsulation.  Accessors give you a quick way to find an element, without scanning through the entire Container, which can greatly improve the performance of your application.  The JDSL has two Accessor types: Positions and Locators (Locators  are covered in Lesson 4).

Let's look at the important parts of the Auction class:

  private Sequence bids = new NodeSequence();
  private double highBid;
We maintain the following three invariants in the bids NodeSequence: The highBid variable is a derived value that stores the high bid of the auction. The return type of this method is  Position. A Position is a place inside a Container that holds an element and usually is connected to other Positions in the Container. This means with its Position, you can find an element in constant time even if the Positions are restructured inside the Container.  In a Sequence, the Positions are connected linearly, such that each Position is associated with a rank (the first has rank 0, etc.). Not every Container has Positions. There is a sub-interface of Container that support Positions, called PositionalContainer.

A PositionalContainer builds and returns a Position when an element is inserted. Actually, Position is an interface. It is up to the designer of the class implementing PositionalContainer to determine how its Position will be implemented. From our perspective, we only need to know that we have a Position, and its element is the object we inserted. Here, the Position represents the place in the NodeSequence holding the Bid.

Notice that this method can throw an InvalidBidException.  This method is thrown by the checkBid(.) method:
 

  private void checkBid(double amount) throws InvalidBidException {
    if(closed)
      throw new InvalidBidException("Bids have closed.");
    if(amount<=0)
      throw new InvalidBidException("Bid must be positive.");
    else if(amount <= highBid)
      throw new InvalidBidException("Bid must top current high bid.");
  }
Bids are invalid if the auction has already closed, if the amount is negative, or if the amount doesn't top the existing high bid.
  public Position top(Position p, double amount)
      throws InvalidBidException {
    checkBid(amount);
    Bid b =(Bid)p.element();
    b.setAmount(amount);
    try {
      bids.remove(p);
    } catch(InvalidAccessorException e) {
      throw new InvalidBidException("Bidder not in Auction.");
    }
    highBid=amount;
    return bids.insertLast(b);
  }
Here is where we see the advantage of Positions. We have a new bid from someone who has already bid before. We have the rule that any bid must top the existing high bid, and the high bid is the last bid in the sequence. To maintain the invariants, when an individual tops an existing bid, we remove the Position, increase the bid amount, and re-insert the element at the end, returning a new Position.

Finding the bid for a person is very efficient (constant time) with a Position. However, this would be much less efficient using an array or a java.util.List, since these only allow access by rank (or index). When we want to find the bid, we would have to search through the array (or List) rather than have direct access. The gives us a direct reference to where the element is in the Container, no matter how the Container is restructured.
 

  public void quit(Position p) {
    bids.remove(p);
    if(bids.size()==0)
      highBid=0;
    else
      highBid=((Bid)bids.last().element()).amount();
  }
The quit(.) method represents an individual leaving the auction, so all we do is remove the associated Position.  If the person who quit the auction was the high bidder, then we need to adjust the highBid variable.

In the next lesson, we look at KeyBasedContainers, the other major JDSL Container type, and Locators, their Accessors.


Previous Lesson
Table of Contents
Next Lesson
Problems, comments?

Last modified: Sat Apr 19 16:53:54 CEST 2003