Constructive and destructive abstract data types: Sets using Arrays, part 3

A constructive set implementation

In the previous set of notes, we considered an implementation of sets of integers using arrays of integers where when an add or delete operation was performed on a set, a new array was constructed representing the way the changed set is stored in the computer. This new array replaced the array within the object. But it remained the same object, since any variable referring to that object would refer to the same place in the computer though with its internal (invisible outside the set class) array changed.

An alternative way of dealing with this would be for the add and delete operations to create entirely new objects representing the change to the set. In this case, the object representing the old set would remain in place unchanged. In Java terms, the operations are represented by methods add() and delete() which return sets. Previously these methods had return type void so they were called as statements on their own, with their effect being to change the object the call was attached to. Here is an implementation with the methods returning new set objects:

class IntSet7
{
// Constructive Set class

 private int[] array;

 public IntSet7()
 {
  array = new int[0];
 }

 private IntSet7(int[] a)
 {
  array = a;
 }

 public IntSet7 delete(int n)
 {
  int i;
  for(i=0; i<array.length&&array[i]<n; i++) {}
  if(i<array.length&&array[i]==n)
     {
      int[] array1 = new int[array.length-1];
      for(int j=0; j<i; j++)
         array1[j]=array[j];
      for(i++;i<array.length; i++)
         array1[i-1]=array[i];
      return new IntSet7(array1);
     }
  return this;
 }

 public IntSet7 add(int n)
 {
  int i;
  for(i=0; i<array.length&&array[i]<n; i++) {}
  if(i==array.length||array[i]>n)
     {
      int[] array1 = new int[array.length+1];
      for(int j=0; j<i; j++)
         array1[j]=array[j];
      array1[i]=n;
      for(int j=array.length; j>i; j--)
         array1[j]=array[j-1];
      return new IntSet7(array1);
     }
  return this;
 }

 public boolean member(int n)
 {
  int from=0, to=array.length;
  int mid=(from+to)/2;
  while(from!=to&&array[mid]!=n)
     {
      if(array[mid]>n)
         to=mid;
      else
         from=mid+1;
      mid=(from+to)/2;
     }
  return from!=to;
 }

 public String toString()
 {
  int i;
  String str="{";
  if(array.length>0)
     {
      str+=array[0];
      for(i=1;i<array.length;i++)
         str+=","+array[i];
     }
  return str+"}";
 }
}

The code here is similar to the previous code, but rather than replacing the array in the object in the methods add and delete a new object is created and returned. Because the new object needs to be created with the new array inside it, a private constructor is necessary which returns a set object with the array object given as its argument inside. Since this constructor is declared as private it can only be used inside the class IntSet7, where it is used in just the two places, in method delete and in method add. It would not be appropriate to make this constructor public since it might then be called with its argument an array that is not in ascending numerical order, which would result in the creation of a set object with its internal data not in the correct format which is relied on by the other methods.

Note that if a call is made to delete a number not in the set, or to add a number which is already in the set, the method returns this. The keyword this in a method means "the object to which this method is attached" (so this can't be used in static methods since when they are called they are not attached to objects).

Mutable and immutable objects

In the code in the previous set of notes and the previous one to that, the statement

s.add(3);

on its own (where s is a variable of type IntSet5 or one of the other set types) would have changed the set represented by the variable s to make it become one which includes the number 3. In this new code,

s.add(3);

on its own, where s is a variable of type IntSet7 is meaningless (although permitted as legal Java). The reason for this is that it doesn't change s but returns a new set object, but nothing is done with that set object. The call s.add(3) only makes sense when used as part of another statement, either assigned to a variable or as an argument to another method call (or it could be used to represent an object on which another method call is made).

If we have variables s1 and s2 of type IntSet6, suppose s1 represents the set {1,2,5,8}. Then the call

s2=s1.add(3);

will cause s2 to represent the set {1,2,3,5,8} while s1 still represents the set {1,2,5,8}. The situation following this statement is:

The add method is referred to as a constructive method because it constructs a new object with a new data structure. In contrast, the method add in the previous examples can be referred to as destructive, since it has its effect by changing the data structure of the object it is attached to, and hence destroying the old value.

If a class has no destructive methods, objects of that class are referred to as immutable. This means that once an object of that type is created, its internal structure can never be changed. If the internal structure of an object can be changed by the call of some method (or if it has fields declared as public but not final so they can be assigned new values directly), the object is referred to as being mutable.

Note that since the add and delete methods can return this, a call to them can result in an object being aliased. For example, if s1 represents the set {1,2,5,8} and we call

s2=s1.add(5);

since 5 is already in the set represented by s1 the method returns this i.e. a reference to s1 so the situation following the call is:

However, aliasing will only ever have an effect if there are destructive methods that can be called on the aliased object. If not, there is no way in which a change on the object referred to by one alias can effect the (same) object referred to by the other alias, because there is no way it can be changed at all.

Axioms

If we have an abstract data type, we need to ensure the code that implements it not only gives methods with the correct signatures but also that those methods behave correctly. So far we have simply assumed an understanding of what sets mean, but if we wish to be more rigorous we can specify the behaviour of an abstract data type using mathematical rules called axioms.

The axioms that define the correct behaviour of any type that implements the concept of a set are quite simple. Firstly, for any i, i is not a member of a newly created set. Secondly, for any i and set s, i is a member of the set created by calling add(i) on s. Thirdly, for any i and set s, i is a not a member of the set created by calling delete(i) on s. Fourthly, for any i and j and set s, j is a member of the set obtained by adding i to s if and only if j is a member of s providing i is not equal to j. Fifthly, for any i and j and set s, j is a member of the set obtained by deleting i from s if and only if j is a member of s providing i is not equal to j.

Or formally:

1. (new set()).member(i) == false
2. s.add(i).member(i) == true
3. s.delete(i).member(i) == false
4. s.add(i).member(j) == s.member(j) if i!=j
5. s.delete(i).member(j) == s.member(j) if i!=j

Note that these axioms assume the methods are constructive.

So long as a class provides the methods member, add and delete and they behave such that the above rules are always obeyed, the class is a correct implementation of the concept of a set. Using these axioms, providing we follow the chain of method calls used to create a set, we can always prove whether a particular number is a member of that set or not.

Matthew Huntbach

Last modified: 9 February 2003