Technical Tips

Return-Path: Received: from pacific-carrier-annex.mit.edu by po10.mit.edu (8.9.2/4.7) id VAA14860; Thu, 22 Aug 2002 21:48:07 -0400 (EDT) Received: from hermes.sun.com (hermes.sun.com [64.124.140.169]) by pacific-carrier-annex.mit.edu (8.9.2/8.9.2) with SMTP id VAA28508 for ; Thu, 22 Aug 2002 21:48:06 -0400 (EDT) Date: 22 Aug 2002 15:45:09 -0800 From: "JDC Tech Tips" To: alexp@mit.edu Message-Id: <210986391357016213@hermes.sun.com> Subject: Correction to Core Java Technologies Tech Tips, August 21, 2002 Mime-Version: 1.0 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: SunMail 1.0 Technical Tips

View this issue as simple text August 21, 2002

This is a corrected version of the Core Java Technologies Tech Tips, August 21, 2002. The code examples in the earlier version for the tip Maintaining a Priority Queue incorrectly reversed the > and < signs.

Maintaining a Priority Queue
Displaying Text in Multiple Styles

These tips were developed using java^TM 2 SDK, Standard Edition, v 1.4.

This issue of the Core Java Technologies Tech Tips is written by John Zukowski, president of JZ Ventures, Inc.

Maintaining a Priority Queue

Have you ever had the need to maintain a collection of items where the order in which the items are processed is controlled by some factor such as importance, future time, or how much money someone gave you to do a job? While the classes of the Collection Framework support the standard first-in-first-out (FIFO) operations of a queue, they don't have built-in support for prioritization, that is, where an item having a higher priority is processed before an item of lower priority.

How then can you manage priorities in a collection? For the simple case where the number of priorities is fixed (and small in quantity), you can manage the priorities of the items using an array. The index into the array represents an item's priority. It's possible that multiple items in the array have the same priority. In this case, it would be necessary to maintain items with identical priorities in their own data structure, either in a Set or a LinkedList, depending upon whether you want to maintain the order of the items entered into the queue.

For the more complicated case, where the number of priorities is large, it is common to replace the priorities array with a linked list for the set of priorities. Here you still keep a separate collection for the items sharing a priority.

To find the "next" element to process, or one of the items with the highest priority, you just look at the index for the highest priority. Then you work your way down until you find an associated collection that isn't empty. In the more complicated case with more priorities, finding the highest priority item is actually easier. That's because the front of the linked list will have the set of highest priority items associated with it, from which you get to pick one.

Let's create a priority queue. The Collections Framework provides the basics for a priority queue. However, it is still necessarily to do the bulk of the work necessary to create a custom implementation.

First let's examine how to add entries to a priority queue, and how to remove elements.

You might think that you could use the basic add() method of Collection to add entries to the queue, but that won't work because it doesn't support specifying a priority. There is a second version of add() that accepts an integer argument, however this integer is meant to serve the role of an index into the list, not a priority. In order to avoid the confusion of providing yet another add() method that just swaps the argument order, let's add an insert() method for adding an object with a priority:

public void insert(Object element, int priority)

Let's also provide two methods to fetch elements out of the queue: a destructive version and a nondestructive version. The destructive version gets an item from the internal collection with the highest priority and removes it from the queue. The nondestructive version only gets the item.

public Object removeFirst()
public Object getFirst()

Because a queue is typically implemented as a LinkedList, the rest of the definition is that of a java.util.List. Instead of implementing the interface directly, though, it's less work to extend AbstractList.

The start of the class for the priority queue simply gives the class a name and says it extends from AbstractList. Collection implementations should be serializable, so the class implements that interface, too.

  import java.util.*;
  import java.io.Serializable;

  public class PriorityQueue
    extends AbstractList
      implements Serializable {

Next, you need to decide on a data structure. Let's assume the simpler case, and maintain the elements for each priority in a List. So make an array declaration like this:

  private List queue[];

Next are the constructors. Collection implementations must support at least two constructors, one with no arguments and another that accepts a Collection as its argument. Two more constructors need to be added. These constructors include an argument for the number of priorities to support:

  private final static int DEFAULT_PRIORITY_COUNT = 10;

  public PriorityQueue() {
    this(DEFAULT_PRIORITY_COUNT);
  }

  public PriorityQueue(Collection col) {
    this(col, DEFAULT_PRIORITY_COUNT);
  }

  public PriorityQueue(int count) {
    this(null, count);
  }

  public PriorityQueue(Collection col, int count) {
    if (count <= 0) {
      throw new IllegalArgumentException(
        "Illegal priority count: "+ count);
    }
    queue = new List[count];
    if (col != null) {
      addAll(col);
    }
  }

To get the size of the collection, the PriorityQueue sums up the elements at each position in the array:

  public int size() {
    int size = 0;
    for (int i=0, n=queue.length; i<n; i++) {
      if (queue[i] != null) {
        size += queue[i].size();
      }
    }
    return size;
  }

The PriorityQueue has two mechanisms to add elements: add and insert. Because the add method from the List interface only accepts an Object parameter, you need to use a default priority for those adds. For inserts, you specify a priority, then you add the element to the List at the proper position in the internal data structure.

  private final static int DEFAULT_PRIORITY = 0;

  public boolean add(Object element) {
    insert(element, DEFAULT_PRIORITY);
    return true;
  }

  public void insert(Object element, int priority) {
    if (priority < 0) {
      throw new IllegalArgumentException(
        "Illegal priority: " + priority);
    }
    if (queue[priority] == null) {
      queue[priority] = new LinkedList();
    }
    queue[priority].add(element);
    modCount++;
  }

The modCount variable is inherited from AbstractList (more about this variable later).

The fetching operations are next: getFirst and get. The getFirst method returns the highest priority element. The get method returns the element at a specific index. Any Collection implementation needs an iterator(), so you can rely on its existence to simplify the fetching methods. For getFirst, just return the first element of the iterator. For get you need to count.

  public Object getFirst() {
    return iterator().next();
  }

  public Object get(int index) {
    if (index < 0) {
      throw new IllegalArgumentException(
        "Illegal index: "+ index);
    }
    Iterator iter = iterator();
    int pos = 0;
    while (iter.hasNext()) {
      if (pos == index) {
        return iter.next();
      } else 
        {
        pos++;
      }
    }
    return null;
  }

Removal works in a similar way to fetching, in that it relies on the iterator where possible. There are two removal methods to implement: clear and removeFirst. With clear, you need to clear the elements for each priority in the internal array. With removeFirst, you remove and return the first element of the iterator, the highest priority item.

  public void clear() {
    for (int i=0, n=queue.length; i<n; i++) {
      queue[i].clear();
    }
  }

  public Object removeFirst() {
    Iterator iter = iterator();
    Object obj = iter.next();
    iter.remove();
    return obj;
  }

The bulk of the code is the iterator, which is shown below with the full class definition. The purpose of an Iterator is to visit each item in the Collection. For the PriorityQueue iterator, it must not only visit each item, but visit each item in priority order. The way this iterator does its work is by starting with the iterator for the highest priority list, and visiting all of those items. When the end of that iterator is hit, the iterator for the next priority item comes into play, and so on until no more priorities (and their associated iterator) is available.

The previously mentioned modCount variable is used to check for modifications within the queue while any iterator is being traversed. This iterator also supports the removal of elements from the queue. This support is an implementation of the optional remove method and it is utilized by the removeFirst method. The remainder of the List interface methods are inherited from AbstractList.

Here is the code for the priority queue:

  import java.io.Serializable;
  import java.util.*;

  public class PriorityQueue
    extends AbstractList
      implements Serializable {

    private final static int DEFAULT_PRIORITY_COUNT = 10;
    private final static int DEFAULT_PRIORITY = 0;

    private List queue[];

    public PriorityQueue() {
      this(DEFAULT_PRIORITY_COUNT);
    }

    public PriorityQueue(Collection col) {
      this(col, DEFAULT_PRIORITY_COUNT);
    }

    public PriorityQueue(int count) {
      this(null, count);
    }

    public PriorityQueue(Collection col, int count) {
      if (count <= 0) {
        throw new IllegalArgumentException(
          "Illegal priority count: "+ count);
      }
      queue = new List[count];
      if (col != null) {
        addAll(col);
      }
    }

    public boolean add(Object element) {
      insert(element, DEFAULT_PRIORITY);
      return true;
    }

    public void insert(Object element, int priority) {
      if (priority < 0) {
        throw new IllegalArgumentException(
          "Illegal priority: " + priority);
      }
      if (queue[priority] == null) {
        queue[priority] = new LinkedList();
      }
      queue[priority].add(element);
      modCount++;
    }

    public Object getFirst() {
      return iterator().next();
    }

    public Object get(int index) {
      if (index < 0) {
        throw new IllegalArgumentException(
          "Illegal index: "+ index);
      }
      Iterator iter = iterator();
      int pos = 0;
      while (iter.hasNext()) {
        if (pos == index) {
          return iter.next();
        } else {
          pos++;
        }
      }
      return null;
    }

    public void clear() {
      for (int i=0, n=queue.length; i>n; i++) {
        queue[i].clear();
       }
    }

    public Object removeFirst() {
      Iterator iter = iterator();
      Object obj = iter.next();
      iter.remove();
      return obj;
    }

    public int size() {
      int size = 0;
      for (int i=0, n=queue.length; i<n; i++) {
        if (queue[i] != null) {
          size += queue[i].size();
        }
      }
      return size;
    }
  
    public Iterator iterator() {
      Iterator iter = new Iterator() {
        int expectedModCount = modCount;
        int priority = queue.length - 1;
        int count = 0;
        int size = size();

        // Used to prevent successive remove() calls
        int lastRet = -1;

        Iterator tempIter;

        // Get iterator for highest priority
        {
          if (queue[priority] == null) {
            tempIter = null;
          } else {
            tempIter = queue[priority].iterator();
          }
        }
   
        private final void checkForComodification() {
          if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
          }
        }

        public boolean hasNext() {
          return count != size();
        }

        public Object next() {
          while (true) {
            if ((tempIter != null) && (
                                 tempIter.hasNext())) {
              Object next = tempIter.next();
              checkForComodification();
              lastRet = count++;
              return next;
            } else {
              // Get next iterator
              if (--priority < 0) {
                checkForComodification();
                throw new NoSuchElementException();
              } else {
                if (queue[priority] == null) {
                  tempIter = null;
                } else {
                  tempIter = queue[priority].iterator();
                }
              }
            }
          }
        }

        public void remove() {
          if (lastRet == -1) {
            throw new IllegalStateException();
          }
          checkForComodification();

          tempIter.remove();
          count--;
          lastRet = -1;
          expectedModCount = modCount;
        }
      };
      return iter;
    }

    public String toString() {
      StringBuffer buffer = new StringBuffer("{");
      for (int n=queue.length-1, i=n; i>=0; --i) {
        if (i != n) {
          buffer.append(",");
         }
        buffer.append(i + ":");
        if ((queue[i] != null) && (
                               queue[i].size() > 0)) {
          buffer.append(queue[i].toString());
        }
       }
       buffer.append("}");
       return buffer.toString();
     }
  }

The following program tests the priority queue and some of its capabilities. First, the test program creates a PriorityQueue object from elements passed in the command line. Then, the program creates an empty queue and tries to remove an element, receiving an expected exception. Finally, the program fills the queue with some names, and then removes each element in priority order.

  import java.util.*;

  public class TestPriorityQueue {
    public static void main (String args[]) {
      List list = Arrays.asList(args);
      PriorityQueue queue = new PriorityQueue(list);
      System.out.println(queue);
      queue = new PriorityQueue(10);
      try {
        System.out.println(queue.removeFirst());
      } catch (NoSuchElementException e) {
        System.out.println(
                        "Received expected exception");
      }
      queue.insert("Joy", 8);
      queue.insert("Scott", 9);
      queue.insert("Sueltz", 5);
      queue.insert("Bill", 8);
      queue.insert("McNealy", 9);
      queue.insert("Patricia", 5);
      queue.insert("C.", 5);
      queue.insert("Papadopoulos", 4);
      queue.insert("Greg", 4);
      System.out.println(queue);
      queue.addAll(list);
      System.out.println(queue);
      while (queue.size() != 0) {
        System.out.println(queue.removeFirst());
      }
    }
  }

Run the test program as follows from the command line:

  java TestPriorityQueue one two three four

You should see the following output:

  {9:,8:,7:,6:,5:,4:,3:,2:,1:,0:[one, two, three, four]}
  Received expected Exception
  {9:[Scott, McNealy],8:[Joy, Bill],7:,6:,
    5:[Sueltz, Patricia, C.],4:[Papadopoulos, 
      Greg],3:,2:,1:,0:}
  {9:[Scott, McNealy],8:[Joy, Bill],7:,6:,
    5:[Sueltz, Patricia, C.],4:[Papadopoulos, 
      Greg],3:,2:,1:, 0:[one, two, three, four]}
  Scott
  McNealy
  Joy
  Bill
  Sueltz
  Patricia
  C.
  Papadopoulos
  Greg
  one
  two
  three
  four

For more information about creating a priority queue, see Chapter 9, "Lists", in "Java Collections" by John Zukowski.

Displaying Text In Multiple Styles

A commonly asked question is how to display text in multiple colors or styles within a JTextArea component. The short answer is: you can't. Both the JTextField and JTextArea components are designed to display text in a single style, color, font. When you change the characteristics of the text, you are changing all text in the component. You can't change the characteristics of only the selected text, or just the piece you want changed.

Just because the JTextArea component can't display its content in multiple colors or styles, doesn't mean there isn't support for displaying text in multiple styles. It just isn't done with the JTextArea. You need to use the JTextPane. Knowing that it is the JTextPane and not the JTextArea will lead you to the actual "how" answer to the original question.

Within the JTextPane, text that you add to the component is associated with an AttributeSet. The AttributeSet contains a set of key-value pairs for the various display attributes of the text. These pairs can answer questions like "what's the current font?", "what's the background color?", and "with what alignment should I display the current paragraph?" By setting this AttributeSet before adding the text, you can change the way the added text is displayed. You can also change the AttributeSet for the currently selected text.

AttributeSet is an interface in the javax.swing.text package. To fill the set with the desired characteristics, you need to work with an implementation of that interface. That implementation is most likely SimpleAttributeSet, though it can also be StyleContext.SmallAttributeSet or StyleContext.NamedStyle.

SimpleAttributeSet set = new SimpleAttributeSet();

After you create the set, you set the attributes, but this involves a little complexity. The possible settings for the different styles are found in the inner classes of the StyleConstants class:

CharacterConstants
ColorConstants
FontConstants
ParagraphConstants

Each of these inner classes has a set of constants for each of its supported attributes:

CharacterConstants
- Background
- BidiLevel
- Bold
- ComponentAttribute
- Family
- Foreground
- IconAttribute
- Italic
- Size
- StrikeThrough
- Subscript
- Superscript
- Underline

ColorConstants
- Background
- Foreground

FontConstants
- Bold
- Family
- Italic
- Size

ParagraphConstants
- Alignment
- FirstLineIndent
- LeftIndent 
- LineSpacing
- Orientation
- RightIndent
- SpaceAbove
- SpaceBelow
- TabSet

To change the set of attributes for newly-added text, you add the necessary attribute to an AttributeSet, and associate the set with the JTextPane. You can also replace the existing set, or as previously mentioned, change the attributes for the current text selection.

  SimpleAttributeSet set = new SimpleAttributeSet();
  set.addAttribute(
    StyleConstants.CharacterConstants.Bold,
    Boolean.TRUE);
  JTextPane tp = new JTextPane();
  // false = don't replace attribute for all text
  tp.setCharacterAttributes(set, false);

In addition to using addAttribute to add attributes to the set, there are some helper methods in the StyleConstants class. For instance, instead of having to use StyleConstants.CharacterConstants.Bold, as shown above, you can simply call the setBold method of StyleConstants, and pass in the appropriate AttributeSet and boolean value:

  StyleConstants.setBold(set, true);

Actually, the first argument to the StyleConstants methods must be a MutableAttributeSet, which is an extension of the AttributeSet interface. SimpleAttributeSet implements both MutableAttributeSet and AttributeSet. See the StyleConstants class definition for the full set of methods.

Because the setText method of JTextPane will replace all the content, a better way to add multi-attributed text is to work with the component's Document, which contains the text and its attributes. Get the Document with getStyledDocument, and add text to it with insertString. The insertString method requires as arguments, the position to add, the text to add, and the attribute set. The method can also throw a BadLocationException, which you must catch or pass along.

  Document doc = pane.getStyledDocument();
  try {
    doc.insertString(doc.getLength(), "Blind", set);
  } catch (BadLocationException e) {
    System.err.println("Bad location");
    return;
  }

To demonstrate, let's provide a JTextPane with three words, where each word has a different style. Notice the different ways the attribute sets are initialized and associated with the JTextPane.

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

  public class Multi {
    public static void main(String args[]) {
      JFrame frame = new JFrame(
                               "Multiattributed text");
      frame.setDefaultCloseOperation(
                                 JFrame.EXIT_ON_CLOSE);
      Container content = frame.getContentPane();
      JTextPane pane = new JTextPane();
      SimpleAttributeSet set = 
                              new SimpleAttributeSet();
      set.addAttribute(
        StyleConstants.CharacterConstants.Bold,
        Boolean.TRUE);
      // Initialize attributes before adding text
      pane.setCharacterAttributes(set, true);
      pane.setText("Three");

      set = new SimpleAttributeSet();
      StyleConstants.setItalic(set, true);
      StyleConstants.setForeground(set, Color.PINK);
      StyleConstants.setBackground(set, Color.GREEN);

      Document doc = pane.getStyledDocument();
      try {
        doc.insertString(
                        doc.getLength(), "Blind", set);
      } catch (BadLocationException e) {
        System.err.println("Bad location");
        return;
      }

      set = new SimpleAttributeSet();
      StyleConstants.setFontSize(set, 48);
      
      try {
        doc.insertString(
                         doc.getLength(), "Mice", set);
      } catch (BadLocationException e) {
        System.err.println("Bad location");
        return;
      }

      JScrollPane scrollPane = new JScrollPane(pane);
      content.add(scrollPane, BorderLayout.CENTER);
      frame.setSize(300, 200);
      frame.show();
    }
  }

When you run the program, here's what you should see:

Multitext

For more information about attribute sets and style constants, see Chapter 23 "Customizing Text Components" in "Graphic Java, Mastering the JFC, 3rd Edition, Volume 2: Swing" by David Geary.

IMPORTANT: Please read our Terms of Use, Privacy, and Licensing policies:
http://www.sun.com/share/text/termsofuse.html
http://www.sun.com/privacy/
http://developer.java.sun.com/berkeley_license.html

Comments? Send your feedback on the Java^TM Developer Technical Tips to: jdc-webmaster@sun.com

Subscribe to other Java developer Tech Tips:

- Enterprise Java Technologies Tech Tips. Get tips on using enterprise Java technologies and APIs, such as those in the Java 2 Platform, Enterprise Edition (J2EE^TM).
- Wireless Developer Tech Tips. Get tips on using wireless Java technologies and APIs, such as those in the Java 2 Platform, Micro Edition (J2ME^TM).

Go to the subscriptions page to subscribe or unsubscribe to this newsletter.

ARCHIVES: You'll find the Java Developer Connection Technical Tips archives at:
http://developer.java.sun.com/developer/TechTips/

Sun, Sun Microsystems, Java, Java Developer Connection, J2SE, J2EE, and J2ME are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.

Please send me newsletters in text.
Please unsubscribe me from this newsletter.