Objects First

Class Design - Histogram Example

The Users' Specification (or Requirements)
As before, we start with the requirements.
Following the step-by-step approach:

Name the class

In this case, the obvious one is

Histogram

It's not too long and is the same term used in the specification.

Other possibilities are:

`Hist`	Even though this is short, it's reasonable in this case - because not many words start with Hist which are likely to cause confusion here.
`Hstgrm`	The "leave out all the vowels" version - hardly worth saving three characters!
`FrequencyHistogram`	Possibly a little too long!
`FreqHistogram`	More explicit than just Histogram, reasonable length - a good choice
`Hst`	Almost certainly too short

Specification First!
Start creating the formal software specification in the file Histogram.h.
Click here to load the software specification.
I suggest that you re-size the windows to make two long ones side-by-side so that you can scroll through the code in one and these notes in the other.
1. Prologue
  After the prologue identifying the module, describing its function, listing the authors, modification dates, etc, we have:
2. Import of specifications on which this specification depends
  Only import specifications that are needed here in this class' specification. Specifications which are only needed in the implementation are imported there (in the .c file). In this case, the specification depends only on some C inbuilt classes, int, double, so we don't need to import anything here.
3. Name
  Name the class: use C's typdef to name a new C type. The name of the type should be the same as the class.
4. Methods
  1. Start with the constructor. Looking at the user requirements, we see that the user wants to specify the number of 'bins' for classifying data and the factor which converts an individual datum to a bin index. These are attributes of each individual histogram and can be stored with the histogram itself, so make them arguments to the constructor.
    Add a destructor which frees the memory allocated by a constructor.
  2. Other methods: Note that for each method, we have:
    1. Formal C specification of a function:
      - Return type
      - Name
      - Parameter list: each parameter has a
        
        type and
        name
        Note that the name is optional in ANSI C. However, it would generally be good practise to include one as it helps to describe the parameter.
    2. Description (in English) of the method
    3. Pre-conditions
    4. Post-conditions
  3. Method groups
    Note that we can group the methods:
    1. Constructors/Destructors
      - ConsHistogram
      - DeleteHistogram
    2. Projectors
      - TotalPoints
      - BinCount
      - SampleMean
      These all project one of its attributes out of an object. I include SampleMean here because, although it does a calculation, it doesn't update the object in any way: it just returns one of its properties.
    3. Update methods
      - AddDatum
      - ClearHistogram
      These update at least one of the attributes of an object.
Brick Wall
Don't forget the big brick wall here!

Check the specification
Now that you've written the specification, you should go back and check that it matches the users' requirements.

If it matches precisely ..
Implementation Last!
Click here to load the implementation.
1. Import
  - library classes, such as stdlib, stdio, assert.h. Note that math.h is imported here to obtain the specification for the function floor.
  - classes of your own on which this class depends. None for this simple class.
2. List the attributes of the class: put them in a C struct.
3. Import the specification of this class: make the compiler tell you when there is some inconsistency!
4. Constants and macros.
5. Code the methods
  1. Pre-conditions first:
    Each pre-condition becomes an assert function.
  2. Then the code of the method.
6. Some C notes
  The struct
  In order to make the class as flexible as possible, we've allowed the user to specify the number of bins at construction time. So, rather than have a fixed array for the bins, eg
```
struct histogram {
  ...
  int bins[MAX_BINS];
  }
```
  we just have a pointer to a block of memory which we're going to allocate when we find out how many bins this particular object needs.
  ConsHistogram
  
  There are 2 malloc calls:
  * the first allocates space for the dictionary structure,
  * the other allocate sufficient space for bin_count integers.
  
  Observe that once space has been allocated for the data structures and the two 'fixed' attributes, bin_count and factor, have been set, ClearHistogram is called to 'reset' all the remaining attributes of the object.
  DeleteHistogram
  Not unsurprisingly, DeleteHistogram has 2 free calls - one to free each block of space malloc'd in the constructor.
  ClearHistogram
  The pre-condition for this method (and all subsequent ones), states that h must be a valid histogram. The test, h != NULL, is a necessary condition, but certainly not a sufficient one. Here, we have attempted to "tighten up" the test a little bit more by checking that both h and h->bins are not NULL.
  In the loop which resets all the bin counts to zero, we've used the array index form for addressing the elements of the bins array. We could equally well have written:
```
int *ip;
...
ip = h->bins;
for(i=0;i<h->bin_count;i++) *ip++ = 0;
```
  Since this style of array addressing is commonly used by C programmers, you must be able to recognise it - even if you never use it yourself!
  Aside: There is an ANSI library function:
```
#include <string.h>

void *memset( void *s, int c, size_t n );
```
  which sets the n bytes of memory from address, s, to the value in c, which can also be used efficiently here. In this case, we would write:
```
memset( h->bins, 0, h->bin_count*sizeof(int) );
```
  Calling memset would generally be the most efficient way to clear memory: it can make use of any special instructions which the target machine may have and, being part of the ANSI standard library, should have an efficient implementation on every machine.
  AddDatum
  We have used the floor function (found in <math.h>) to truncate the result of multiplying x by the reduction factor which converts x to a bin index.
  Note the position of the assert after the calculation of the bin index. assert's - just like any function call - can go anywhere in the body of a C function. This one is actually checking the pre-condition that x must be in range - it turns out to be more convenient here to simply check the bin index after it's been calculated than, for example, to calculate the limits of the range of x and check against them.
  SampleMedian, SampleMean and MaxFrequency
  For SampleMedian, we have chosen to calculate the median from the data gathered already, whereas for SampleMean and MaxFrequency we have updated some variables stored in the object every time AddDatum was called.
  This illustrates a number of points in our OO design strategy:
  - The user specifies the result expected - the implementor is free to generate this result any way he or she pleases,
  - Should experience show that the implementor has made a bad choice of implementation strategy, because, perhaps, insufficient data was given about usage patterns to enable the optimum choice to be made, then the implementation can be changed without affecting any of the code using the class.
  - Since the class is an independent piece of code, if it is changed, it can be verified again by itself - and presumably using the same set of test programs that were used for the initial implementation.
  Thus, had the initial, somewhat arbitrary, choice for implementation strategy later proved less than optimally efficient, we could simply change the offending methods to use the alternative strategy and very little else is affected!
Verify the class
Now we need to construct at least one program to verify that the class is correct: verify the Histogram class.

Objects First

Class Design - Histogram Example

The Users' Specification (or Requirements)

Name the class

Specification First!

Prologue

Import of specifications on which this specification depends

Name

Methods

Method groups

Brick Wall

Check the specification

Implementation Last!

Some C notes

Verify the class