A design characteristic of Parham is efficiency. In this example it is shown that Parham composition model is very efficient.

Combining Queue and Tree components

Assume that we need a queue with an extra feature: we need to be able to remove an element from the queue by providing its key.

It means that we need the following operations.

  • enqueue. It adds an elements to the tail of the queue.
  • dequeue. It removes an element from the head of the queue.
  • remove. It removes an arbitrary element from the queue (the element is provided as argument).
  • removeByKey. It removes an element by specifying its key.

All of the above methods except removedBykey are already provided by the Queue component.

To provide removeByKey a simple solution is to iterate over the elements of the queue and remove the element that matches the key. The cost of this approach is O(n) which is not acceptable.

A better solution is to augment Queue by a binary tree (the Tree component) so that an element that matches a key can be found in O(log n).

The combination of them forms a new component named QT. The cost of operations is QT are as follows.

  • enqueue. O(log n)
  • deque. O(log n)
  • remove. O(log n)
  • removeByKey. O(log n)

The interesting point is that doing the same thing in Java is not possible.

In other words, augmenting a queue (LinkedList class of Java) with a binary tree does not yield any improvement.

Files

The example is implemented in four files.

  • QT
  • Queue
  • Tree
  • App
  • I/O functions (in C)

The implementation of QT component is provided in the front panel.

After the declaration of QT, there are two instances declarations: Queue and Tree.

After them, the implementation of operations are provided. They are straightforward.

The complete code of the sample can be downloaded from the link provided at the beginning of the discussion.

QT[Root, Node]


Queue[Root queue, Node];

Tree[Root tree, Node];


public void Root.enqueue (Node n)

{

    queue.enqueue (n);

    tree.insert (n);

}

public Node Root.deque ()

{

    Node ret;

    ret = queue.deque ();

    if (!ret)

        return null;

    tree.remove (ret);

    return ret;

}

public void Root.remove (Node n)

{

    queue.remove (n);

    tree.remove (n);

}

public Node Root.removeByKey (Node n)

{

    Node ret;

    ret = tree.removeByKey (n);

    if (!ret)

        return null;

    queue.remove (ret);

    return ret;

}

QT component