Obfuscated Abstract Data Type

Computer Science Level 3

Abstract data type O over items of type int has the following interface (here written as Java code):

public class O {

/** Constructor: precondition true; postcondition Q() */
public O() { ... }

/** Query: precondition true */
public boolean Q() { ... }

/** Query: precondition ! Q() */
public int S() { ... }

/** Command: precondition true; postcondition ! Q() */
public P(int i) { ... }

/** Command: precondition ! Q() */
public R() { ... }

}

It satisfies the following four properties for every instance O o and item int i .

If o.Q() holds, then o.P(i) establishes o.S() == i .
If ! o.Q() holds, then o.P(i) preserves o.S() (that is, o.S() is invariant/unchanged).
If o.Q() holds, then o.P(i); o.R() preserves o.Q() .
If ! o.Q() holds, then o.P(i); o.R() and o.R(); o.P(i) are equivalent.

What abstract data type is O ?

Notes:

! means "not" (boolean negation)

Dictionary Stack Heap Queue Priority Queue

1 solution

Tom Verhoeff
Sep 5, 2016

Every valid sequence op O , P , R commands, starting with a constructor call O o = new O(); can be rewritten, according to the postulated properties (especially properties 3 and 4), into an equivalent sequence of the form

O o = new O(); o.P(i_1); o.P(i_2); ...; o.P(i_k);

for some k at least 0. That is, all R commands can be eliminated.

If k > 0 , then after that sequence the condition ! o.Q() holds, and furthermore o.S() will then return i_1 (see properties 1 and 2), and after the command o.R() the resulting state will be equivalent to

O o = new O(); o.P(i_2); ...; o.P(i_k);

That is, the command o.P(i_1); is "canceled".

Obviously, after the command o.P(i_x) , the resulting state will be equivalent to

O o = new O(); o.P(i_1); o.P(i_2); ...; o.P(i_k); o.P(i_x);

Thus, the state of O o is uniquely determined by a sequence of items [i_1, i_2, ..., i_k] .

This shows that O is a Queue , where

Q() queries for emptiness
S() serves (return) the item at the front (without removing it; this is a pure query)
P(i) puts item i at the end
R() removes the item at the front (without returning anything; this is a pure command)

Notes:

A Stack satisfies properties 1 and 3, but not 2 and 4.
A Priority Queue satisfies properties 1 and 3, but not 2 and 4 (items can "overtake" each other depending on their priority).
A Dictionary needs both a type for the key and for the value when putting an item.
A Heap is a possible data structure for an (efficient) implementation of a priority queue.

Obfuscated Abstract Data Type

1 solution

0 pending reports