Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Principles of Object-Oriented Programming » Ordering Object and Priority Queue

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • OrangeGrove display tagshide tags

    This collection is included inLens: Florida Orange Grove Textbooks
    By: Florida Orange Grove

    Click the "OrangeGrove" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

Also in these lenses

  • Busbee's Compter Science display tagshide tags

    This collection is included inLens: Busbee's Computer Science Lens
    By: Kenneth Leroy Busbee

    Comments:

    "Texas Common Course Numbering: COSC1337 or COSC1437"

    Click the "Busbee's Compter Science" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • eScience, eResearch and Computational Problem Solving

    This collection is included inLens: eScience, eResearch and Computational Problem Solving
    By: Jan E. Odegard

    Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Ordering Object and Priority Queue

Module by: Stephen Wong, Dung Nguyen. E-mail the authors

Summary: The module describes comparator objects for determining a binary order and builds a generalized priority queue with it.

Order Relation

When comparing two objects, there are two ways to look at the comparison behavior, which creates a notion of ordering between the two objects:

  1. Each object knows how to compare itself -- Comparison is considered intrinsic to the object and is part of its behavior.
  2. Comparison is done by an external object -- A third object is introduced that contains the ability to compare two objects.

These two different outlooks on binary object ordering will be explored below in terms of the two Java interfaces that are used to model them.

java.lang.Comparable

There are many computing tasks that require performing some sort of comparison between data objects. A few data types are endowed with a "natural" ordering of their values. The integers have a natural ordering "less or equal to", labeled "<=", defined as follows.

n <= m iff m = n + k, for some non-negative integer k
(Note: a rigorous mathematical definition of the set of non-negative integers is beyond the scope of this lecture).

The above natural order of the integers is a concrete instance of an abstract concept called an order relation. An order relation on a set S is a boolean function R on S x S that is

  • reflexive: R(x, x) is true for all x in S,
  • anti-symmetric: R(x,y) and R(y,x) implies x = y, for all x, y in S, and
  • transitive: R(x, y) and R(y, z) implies R(x, z), for all x, y, z in S.

To model order relations that are naturally endowed in certain types of data objects, Java provides an interface called Comparable, which has exactly one method called

int compareTo(Object rhs), defined abstractly as

  • x.compareTo(y) < 0 means x is "less than" y,
  • x.compareTo(y) == 0 means x is "equal to" y, and
  • x.compareTo(y) > 0 means y is "less than" x.

For example, the Integer class implements the Comparable interface as follows. If x and y are Integer objects then,

  • x.compareTo(y) < 0 means x < y,
  • x.compareTo(y) == 0 means x == y, and
  • x.compareTo(y) > 0 means y < x.

Common data types that have a natural ordering among their values, such as Double, String, Character, all implement Comparable.

Advantages and disadvantages

  • Advantages
    • Objects carry their ability to be compared with them and thus can be involved in comparison operations anywhere.
    • The comparison operation is invariant and thus consistent in all situations.
  • Disadvantages
    • Comparison operation cannot be changed to match different situations.

java.util.Comparator

Most of the time, the ordering among the data objects is an extrinsic operation imposed on the object by the user of the objects. For example, the Pizza objects in homework 2 have no concepts of comparing among themselves, however, the user can impose an ordering on them by comparing their price/area ratios or their profits. To model extrinsic ordering relation, Java provides an interface in the java.util package called Comparator, which has exactly two methods:

  • int compare(Object x, Object y), to model the ordering
    • compare(x, y) < 0 means x is "less than" y,
    • compare(x, y) == 0 means x is "equal to" y, and
    • compare(x, y) > 0 means yis "less than" x, and
  • boolean equals(Object x), to model equality of Comparators. Unlike the equals method of most objects, equality of Comparators also requires that their comparison behavior be identical.

In most applications, when we implement a Comparator interface, we only need to override the compare(...) method and simply inherit the equals(...) method from Object.

Advantages and disadvantages

  • Advantages
    • Object ordering can be considered variant and be redefined for different situations.
    • Creating composite comparison behavior can be easily acheived by decorating or other composite techniques.
  • Disadvantages
    • Objects are not intrinsically comparable, requiring the inclusion of an otherwise disconnected entity in the system.

Exercise 1

Implement a Comparator class that will compare Integer objects.

In-Order Insertion Example

Recall the problem of inserting an Integer object in order into a sorted list of Integers. Instead of writing an algorithm that only works for Integer, we can write an algorithm that will work for any Object that can be compared by some Comparator. The table below contrasts the insert in order algorithm for Integer and the insert in order algorithm that uses a Comparator as a strategy (as in strategy pattern) for comparison. Both are algorithms for LRStruct, the mutable list.

First, let's look at a regular in-order insertion algorithm that works only on Integer objects because the comparison technique is hard-coded in:

InsertInOrderLRS Visitor class


import lrs.*;

public class InsertInOrderLRS implements IAlgo {

  public static final InsertInOrderLRS Singleton = new InsertInOrderLRS();

  private InsertInOrderLRS() {
  }

  /**
  * Simply inserts the given parameter n at the front.
  * @param host an empty LRStruct.
  * @param n an Integer to be inserted in order into host.
  * @return LRStruct
  */
  public Object emptyCase(LRStruct host, Object... n) {
    return host.insertFront(n[0]);
  }

  /**
  * Based on the comparison between first and n,
  * inserts at the front or recurs!
  * @param host a non-empty LRStruct.
  * @param n an Integer to be inserted in order into host.
  * @return LRStruct
  */
  public Object nonEmptyCase(LRStruct host, Object... n) {

    if (n[0] < (Integer)host.getFirst();) {  // could use Integer.compareTo() 
      return host.insertFront(n[0]);
    }
    else {
      return host.getRest().execute(this, n[0]);
    }
  }
}

A visitor to an LRStruct that performs an in-order insertion, but only for Integer objects.

Now let's look at how the simple substitution of a Comparator for the hard-coded comparison allows the otherwise identical code to be used for any objects. All one has to do is to supply the desired Comparator instance that matches the type of objects stored in the LRStruct. Here is the implementation of a visitor to an LRStruct that performs an in-order insertion, for any objects that are comparable with the given Comparator:

InsertInOrder Visitor class


import lrs.*;
import java.util.*;

public class InsertInOrder implements IAlgo {

  private Comparator _order;

  public InsertInOrder(Comparator ord) {
      _order = ord;
  }

  /**
  * Simply inserts the given parameter n at the front.
  * @param host an empty LRStruct.
  * @param n an Object to be inserted in order into host,
  *   based on the given Comparator.
  * @return LRStruct
  */
  public Object emptyCase(LRStruct host, Object... n) {
    return host.insertFront(n[0]);
  }

  /**
  * Based on the comparison between first and n,
  * inserts at the front or recurs!
  * @param host a non-empty LRStruct.
  * @param n an Object to be inserted in order into host,
  *   based on the given Comparator.
  * @return LRStruct
  */
  public Object nonEmptyCase(LRStruct host, Object... n) {
    if (_order.compare(n[0], host.getFirst()) < 0) {
      return host.insertFront(n[0]);
    }
    else {
      return host.getRest().execute(this, n[0]);
    }
  }
}

3. Priority Queue

The InsertInOrder algorithm given in the above can be used as part of a strategy for a Restricted Access Container ("RAC") called priority queue. In the code below, it is assumed that "smaller" objects have higher priority, i.e. will be retrieved from the RAC before "larger" objects. The code also shows how, if the RAC elements are Comparable objects, that a Comparator could be used to provide their ordering in the RAC, even to the point of reversing their order if desired.

PQComparatorRACFactory priority queue implementation

package rac;

import lrs.*;
import lrs.visitor.*;
import java.util.*;

/*
 * Implements a factory for restricted access containers that
 * return the ``highest priority'' item.
 */
public class PQComparatorRACFactory extends ALRSRACFactory {

    private Comparator _comp;

    /**
     * Used when the items in the container are Comparable objects.
     */
    public PQComparatorRACFactory() {
        _comp = new Comparator() {
            public int compare(Object x, Object y) {
                /*
                 * Intentionally reverse the ordering so that the
                 * largest item will be first, just to show that it can be done.
                 */
                return ((Comparable)y).compareTo(x);
            }
        };
    }

    /**
     * Used when we want to prioritize the items according to a given Comparator.
     * @param comp the item that is smallest according to comp has the highest
     * priority.
     */
    public PQComparatorRACFactory(Comparator comp) {
        _comp = comp;
    }

    /**
     * Create a container that returns the item with the highest priority
     * according to a given Comparator.
     */
    public IRAContainer makeRAC() {
        return new LRSRAContainer(new InsertInOrder(_comp));
    }
}

A priority queue can easily be implemented from a RAC by using a Comparator.

Collection Navigation

Content actions

Download:

Collection as:

PDF | More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks