Title: Sets a-la Pascal

Many programmers who have been satisfied with Pascal for years but for some reason want to switch to C++, will miss the Set facility from Pascal. For a Pascal programmer it may seem strange that the enum type exists, but not the Set.

Fortunately C++ is a language which permits easy construction of new types. The following is my own implementation as I prefer it. In Pascal there exist operations on sets, such as +, - and *. I've always found it confusing - I prefer something easier to remember.

A Set is a string of bits that may be set or removed according to some state of the program or its data. Sets in Pascal are of fixed size. In C++ the size may be determined at run-time.

In class Set the bits are stored in a whole number of bytes, each byte containing 8 bits. Bit manipulations are performed by the binary operators available in C++. Bits are numbered 76543210.

Bitwise operations

If for example bit 4 (00010000) has to be added to the byte b the following operation is performed: b = b | (1 << 4), or shorter:

b |= (1 << 4)

If the 4th bit is already set, the Set remains unchanged.

To remove a bit, the operation is a little more tricky. For example to remove bit 4 the following operation, we cannot just OR with a zero bit as this would remove other bits in the byte. We have to AND with 11101111 in order to remove bit 4 and preserve all other bits. The expression b &= ~(1 << 4) does it.

When a set contains more than a byte, we must find the byte number and, within the byte, the bitnumber in order to handle a single bit. To find the byte to operate on is easy. It is BitNum div 8. The bit is BitNum mod 8.

All in all, these operations are (surprisingly?) easily managed by the bitwise operators in C++.

Almost like Pascal

In class Set the operator << is for adding a bit and >> for removing a bit. This is convenient as I can write:

enum Color { Green, Blue, Yellow, Red } ;
Set Colors(10); // define a set with 10 bits
  s << Red << Green << Blue;
  if (Colors[Blue]) print("Blue was in the Set s");

It is not quite like Pascal, but the same functionality is there.

I've also made a function that adds one set to another set, eventually of different size. As far as I remember Pascal, my function works as in Pascal. As an example like the above may be found in most Pascal books, I've also found it natural to include an exercise for the reader. See the SET.CPP file included in this article. Don't worry - it is not too difficult.

// SET.H  -- Set operations a-la Pascal
typedef unsigned int Word;
typedef unsigned char Byte;
const Word ByteSize = 8;
class Set { // Set operations a-la Pascal
  Byte *BitStr;
  Word  BitStrSize;
  Word  BitsInUse;
public:
  Set(Word MaxBits);
  Set(const Set & TheSet);
  virtual ~Set();
  int SetSize(void);
  void ClearSet(void);
  int operator[](Word BitNum);          // test if a bit is present
  Set & operator =(const Set &TheSet);  // assignment of sets
  Set & operator <<(Word BitNum);       // add a bit
  Set & operator >>(Word BitNum);       // remove a bit
  int   operator ==(Set &TheSet);       // compare sets
  int   operator !=(Set &TheSet);       // compare sets
  void AddBitSet(Set &TheSet);
  void RemoveBitSet(Set &TheSet);
}; // class Set

In SET.CPP
//         SET.CPP  -- Set operations a-la Pascal
//        Written by:  John Plate <plate@infotek.dk>
// Date:        August 1995
// Compiler:    Borland Turbo C++
// Copyright:   The code is in the public domain
#include "set.h"
#include <values.h>
#include <mem.h>
Set::Set(Word MaxBits) { // MaxBits is number of bits in the Set
  BitsInUse = MaxBits;
  if (MaxBits > MAXINT || MaxBits == 0) { // i.e. impossible values  
    BitStr = 0;
    BitStrSize = 0;
  }
  else {
    BitStrSize = (BitsInUse - 1) / ByteSize + 1;
    BitStr = new Byte(BitStrSize);
    ClearSet();
  }
} // constructor
Set::Set(const Set & TheSet){ // Copy constructor
  BitStr = new Byte[BitStrSize = TheSet.BitStrSize];
  BitsInUse = TheSet.BitsInUse;
  if (BitStr) memcpy(BitStr, TheSet.BitStr, BitStrSize);
} // Copy constructor
Set::~Set(){ // De-allocate the BitStr array
  if (BitStr) delete BitStr;
} // destructor
void Set::ClearSet(void){ // Zero fill the whole Set one byte at a time
  for (int i = 0; i < BitStrSize; i++) BitStr[i] = 0;
} // ClearSet
int Set::SetSize(void){ // Return the bits used, i.e. the size of the Set
  return(BitsInUse);
} // SetSize
int Set::operator[](Word BitNum){ // Return the value of bit BitNum. 
                                  // Notice: Zero is returned if BitNum is not within the Set.
  if (BitNum <= BitsInUse) {
    return(BitStr[BitNum / ByteSize] & (1 << (BitNum % ByteSize)));
  }
  else return(0);
} // operator []
Set & Set::operator =(const Set & TheSet){ //copy assignment 
  if (this != &TheSet) {
    delete(BitStr);
    BitStr = new Byte[BitStrSize = TheSet.BitStrSize];
    BitsInUse = TheSet.BitsInUse;
    if (BitStr) memcpy(BitStr, TheSet.BitStr, BitStrSize);
  }
  return(*this);
} // operator =
int Set::operator ==(Set & TheSet){ // Compare two sets
  int Equal = BitStrSize == TheSet.BitStrSize &&
    BitsInUse == TheSet.BitsInUse &&
    memcmp(BitStr, TheSet.BitStr, BitStrSize) == 0;
  return(Equal);
} // operator ==
int Set::operator !=(Set & TheSet){ // Compare two sets
  return(! (*this == TheSet));
} // operator !=
Set & Set::operator <<(Word BitNum){ // Set the bit, return 'this Set'
  if (BitNum < BitsInUse) {
    BitStr[BitNum / ByteSize] |= (1 << (BitNum % ByteSize));
  }
  return(*this);
} // operator <<
Set & Set::operator >>(Word BitNum){ // Remove the bit, return 'this Set'
  if (BitNum < BitsInUse) {
    BitStr[BitNum / ByteSize] &= ~(1 << (BitNum % ByteSize));
  }
  return(*this);
} // operator >>
void Set::AddBitSet(Set &TheSet){ 
    // Add bits from TheSet, i.e. perform an OR operation on both sets.
    // Notice that the sets may be of different size.
  int BitsUsed = min(TheSet.BitsInUse, BitsInUse);
  int Bytes = BitsUsed / ByteSize;     // no of whole bytes
  for (int i = Bytes; i >= 0; i--) BitStr[i] |= TheSet.BitStr[i];
  int Bits = BitsInUse % ByteSize;     // the rest
  if (Bits > 0) { // mask out relevant bits before the OR operation
    BitStr[Bytes+1] |= (~0 << (ByteSize - Bits)) & TheSet.BitStr[Bytes+1];
  }
} // AddBitSet
void Set::RemoveBitSet(Set &TheSet){
  // This left as an excercise for the reader :-)
  // Hint: See the functions above.
} // RemoveBitSet

Finally, something to think about. What operators should be provided (if any) and how would they best be provided. Perhaps the design experts might like to critique the design. Any thoughts on the variety of ways that << and >> are used in the context of this design? Material such as this is presented to provoke your thoughts and develop ideas and understanding, not as recipes for definitive answers. Francis.