Implementation of AbstractQueue as a (dynamically resized) circular buffer based on array. More...

Inheritance diagram for aud.Queue< T >:

Collaboration diagram for aud.Queue< T >:

Public Member Functions
	Queue ()
	create empty queue More...

	Queue (int capacity)
	create empty queue and reserve storage More...

boolean	is_empty ()
	Is queue empty? More...

T	front ()
	Get front element of queue. More...

T	dequeue ()
	Remove front element from queue. More...

void	enqueue (T x)
	Enqueue element at end of queue. More...

String	toString ()
	Get string representation. More...

abstract boolean	is_empty ()
	Is queue empty? More...

abstract T	front ()
	Get front element of queue. More...

abstract T	dequeue ()
	Remove front element from queue. More...

abstract void	enqueue (T x)
	Enqueue element at end of queue. More...

String	toString ()

Additional Inherited Members
Protected Member Functions inherited from aud.adt.AbstractQueue< T >
	AbstractQueue ()
	create empty queue More...

Detailed Description

Implementation of AbstractQueue as a (dynamically resized) circular buffer based on array.

Definition at line 11 of file Queue.java.

Constructor & Destructor Documentation

◆ Queue() [1/2]

aud.Queue< T >.Queue ( )

create empty queue

Definition at line 21 of file Queue.java.

                 {
    this(DEFAULT_SIZE);
  }

◆ Queue() [2/2]

aud.Queue< T >.Queue ( int capacity )

create empty queue and reserve storage

Definition at line 27 of file Queue.java.

                             {
    data_=(T[]) new Object[capacity];
    head_=tail_=0;
  }

Member Function Documentation

◆ dequeue()

T aud.Queue< T >.dequeue ( )

Remove front element from queue.

Requires !is_empty().

Exceptions

NoSuchElementException

Returns: removed element

Reimplemented from aud.adt.AbstractQueue< T >.

Reimplemented in aud.example.VerboseQueue< T >.

Definition at line 50 of file Queue.java.

                               {
    if (is_empty())
      throw new NoSuchElementException();
    T obj=data_[head_];
    data_[head_]=null; // "free" entry (for GC)
    head_=(head_+1)%data_.length;
    return obj;
  }

References aud.Queue< T >.is_empty().

Referenced by aud.example.expr.ExpressionTreeTraversal.levelorder(), aud.example.BinaryTreeTraversal.levelorder(), aud.example.expr.ExpressionParser2.product(), aud.example.graph.BreadthFirstSearch.start(), aud.example.expr.ExpressionParser2.sum(), and aud.test.QueueTest.testInvalid_dequeue().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ enqueue()

void aud.Queue< T >.enqueue ( T x )

Enqueue element at end of queue.

Parameters

x	new element

Reimplemented from aud.adt.AbstractQueue< T >.

Reimplemented in aud.example.VerboseQueue< T >.

Definition at line 62 of file Queue.java.

                           {
    int newtail=(tail_+1)%data_.length;
 
    if (newtail!=head_) {
      // no "overrun" we just advance an index.
      data_[tail_]=x;
      tail_=newtail;
    }
    else {
      //@>queue:enqueue1
      //System.err.println("enlarge buffer of size "+data_.length);
 
      // detected "overrun": the new head "hits" tail --
      // This means the alloacted buffer data is too small!
 
      // get larger buffer q
      Queue<T> q=new Queue<T>(data_.length*2);
 
      // copy data into q
      while (!is_empty())
        q.enqueue(dequeue());
      q.enqueue(x);
 
      // "steal" state of temporary object q
      data_=q.data_;
      head_=q.head_;
      tail_=q.tail_;
      assert(head_==0 && tail_<data_.length);
    }
  }

Referenced by aud.example.grid.Grid.bfs(), aud.example.expr.ExpressionTreeTraversal.levelorder(), aud.example.BinaryTreeTraversal.levelorder(), aud.example.expr.ExpressionParser2.product(), aud.example.graph.BreadthFirstSearch.start(), and aud.example.expr.ExpressionParser2.sum().

Here is the caller graph for this function:

◆ front()

T aud.Queue< T >.front ( )

Get front element of queue.

Requires !is_empty().

Exceptions

NoSuchElementException

Returns: front element

Reimplemented from aud.adt.AbstractQueue< T >.

Definition at line 42 of file Queue.java.

                   {
    if (is_empty())
      throw new NoSuchElementException();
    return data_[head_];
  }

References aud.Queue< T >.is_empty().

Referenced by aud.test.QueueTest.testInvalid_front().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_empty()

boolean aud.Queue< T >.is_empty ( )

Is queue empty?

Reimplemented from aud.adt.AbstractQueue< T >.

Definition at line 35 of file Queue.java.

                            {
    return head_==tail_;
  }

Referenced by aud.Queue< T >.dequeue(), aud.Queue< T >.front(), aud.example.IterativePreorderTraversal.level_order_traversal(), aud.example.expr.ExpressionTreeTraversal.levelorder(), aud.example.BinaryTreeTraversal.levelorder(), aud.example.expr.ExpressionParser2.product(), aud.example.graph.BreadthFirstSearch.start(), aud.example.expr.ExpressionParser2.sum(), and aud.Queue< T >.toString().

Here is the caller graph for this function:

◆ toString()

String aud.Queue< T >.toString ( )

Get string representation.

Impementation note:

This method reads out the queue in reverse order, i.e., we are "going backwards" and shift an index by -1 instead of +1 modulo array length.

The Java expression ab computes the remainder of an integer division and is differs from the mathematical definition of a mod b for negative operands!

The modulo operation is defined as

a mod b := b-floor(a/b)*b

where floor(x) rounds to the greatest integer that is less than or equal to x (i.e., "towards negative infinity").

This is what we want, because

a mod b = (a+k*b) mod b for any integer k (regardless of sign)

For example consider an array of size 3 then position -1 should refer to the last entry

-1 mod 3 = -1+3 mod 3 = 2 mod 3 = 2

Java (and similarly C/C++) defines the remainder operator differently such that the sign is treated "symmetrically" (not rounding towards negative infinity but towards 0):

a%b = (-a%b) for b>=0

For the example, we get

(-1)%3 = 1%3 = 1

which is not what we want as index into the buffer!

We avoid this issue by adding -1+data_.length instead of -1.

Summary:

Computing the remainder of an integer division (by an operator) is treated differently in different programming languages.
The same is true for the (rounding mode of the) integer division itself. The reason for the "non-mathematical" definition is probably the behavior of the machine instructions (like idiv< on Itel CPUs).
Differences show up for negative operands And they can lead to subtle bugs!
To be safe, make sure that operands are nonegative!

Reimplemented from aud.adt.AbstractQueue< T >.

Definition at line 152 of file Queue.java.

                           {
    if (is_empty())
      return "<";
 
    String s="";
 
    int t=(tail_+data_.length-1)%data_.length;
    for (;;) {
      s=data_[t]+"<"+s;
      if (t==head_)
        break;
      t=(t+data_.length-1)%data_.length;
    }
    return s;
  }