• ADT definition using C++ syntax

template <class T, int Max>

class set

{

set();

boolean is_empty();

boolean is_full();

void insert(T);

void erase(T);

boolean exists_in(T);

set<T,Max> operator+(set<T, Max>);

set<T,Max> operator*(set<T, Max>);

};

• We could have created a function called union
• z = x.union(y)
• if we replace union with "operator+"
• z = x.operator+(y)
• another way of writing the same thing
• z = x+y
• program is more readable.
• We are overloading the operator +.
• Similarly we have also overloaded the operator *.
• We will represent set as a string of bits
• all the operations are done using bitwise operations
• Very efficient: constant time.
• Assume universe is {a1,a2,a3,.....,a32}
• we are storing a1 in the first bit, a2 in the second bit,.....,a32 in the 32nd bit.
• if ith bit is on then ai exists in the set
• For now we will assume that our universe is not greater than 32 elements.
• We will store a set using a single long integer.
• union is bitwise or(|), intersection is bitwise and (&)
• exists_in(ai) will be same as returning a & (1 << (I-1));

• Probably is the only type that allows you to create your own constants
• Let us say wanted a type that takes the values sun..sat
• enum days {sun,mon,tue,wed,thu,fri,sat};
• any variable of the type days can take the value sun..sat
• days x;
• x = mon;
• There is an automatic mapping from int o any type created using enum
• sun=0,mon->1, tue->2,wed->3,....,sat->6
• int(thu) will give you 4
• days(5) will give us fri

• Using a data structure that is already created for us
• Assume that we have the data structure set
• Set is a template which needs a type and maximum size
• set<days,7> s;
• the new type was created by supplying days as the type and 7 as the maxsize to the template
• You cannot do this with any arbitrary type
• The type has to have
  • a reversible one-to-one and onto mapping from elements in the set to integers between 0..31
  • an output operator that will output the value of the type
  • look at testset.cpp
• we are using bit patterns to represent a set
• first bit (bit 0) is on then the first element exists in set. In our example, that will be Sunday
• & operator will correspond to intersection
• | operator corresponds to union
• ~ corresponds to the complement of the set
• Look at set.cpp for the implementation
• Obvious limitation is that we can only have sets with 32 elements maximum. This limitation can be taken care of by using an array of unsigned numbers. If we have 200 elements then the array will have Max/32 + 1
• Space wise we are using minimal storage. You cannot have less than one bit per element. We are wasting some bits because if the set is going to have maximum of 7 elements then we are wasting 25 bits. This wastage can be reduced by using an array of unsigned characters. We will not look at the details. This additional efficiency is going to be at the expense of unreadable code.
• Time requirements are minimal. Linear for output operator (can't do better than that). All other operations are constant time.