Objects First

Class Design - Dictionary Example

  1. The Users' Specification (or Requirements)

    Any programming problem will start with the users' requirements. Here is a typical one (one of the recent practical test questions). This is in English and has all the problems of a natural language:

    Once we've cleared up the ambiguities, we start designing the software.

    Following the step-by-step approach:

  2. Name the class

    The name must be sufficiently specific that a reader can infer from the name what to expect. Overly long names are cumbersome to read and severely abbreviated ones are difficult to interpret.
    Somewhere in between, there will be a set of 'reasonable' names. In this case, the obvious one is

    Dictionary

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

    		Other possibilities are:
    Dict Possibly a little too short
    Dictnry A common abbreviation strategy -
    leave out all the vowels.
    But the first one was left in!
    Fails a consistency test?
    TranslationDictionary Possibly a little too long!
    Dct Almost certainly too short

  3. Specification First!

    Start creating the file Dictionary.h which contains the formal software specification.

    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). Specifications which are not needed by this class are not imported at all!

    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. In this case, the constructor has a single argument - the maximum number of words needed in the table.

        We derived this constructor by observing that the requirements state:

        Dictionaries have a fixed maximum size - specified when they're built.
        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
          • ConsDictionary
          • DeleteDictionary
        2. Projectors
          • WordCount
          • FindForeign
          • FindEnglish
          These all project one of its attributes out of an object.
        3. Update methods
          • AddTranslation
          • ReplaceTranslation
          These all update at least one of the attributes of an object.

    5. 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 ..

    6. Implementation Last!

      Click here to load the implementation.

      1. Import
        • library classes, such as stdlib, stdio, assert.h, then
        • classes of your own on which this class depends.
      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.

        Note that in this case, the checking of a word passed as a parameter to a method involves

        • checking that the word isn't a NULL pointer and
        • checking that the word actually has some characters in it!
        so that we decided to make a macro VALID_WORD(w) which invokes both assert's in a single entry. This is done purely for convenience. However note that, if, at some later stage, we decided that it's necessary to check that a word also begins with a lower case alphabetic character (as we possibly should have done now anyway!), then we can simply extend this macro and all functions will automatically acquire the added checks. 
        #define VALID_WORD(w)   assert(w!=NULL);assert(strlen(w)>0); \
                 assert( (*w>='a') && (*w<='z') );
        Notes:
        1. The '\' extends the macro over two lines.
        2. I can access the first character of a string either by de-referencing the pointer (which points to the first character) or by using the array notation: w[0]. Both are equivalent and interchangeable.

        We could also add a reasonableness check which verified that words were not longer than some reasonable maximum. The longest word in English is generally reckoned to have 28 letters, so that adding: 

        #define MAX_WORD_CHARS	28
#define VALID_WORD(w)   assert(w!=NULL);assert(strlen(w)>0); \
                 assert(strlen(w)<=MAX_WORD_CHARS); \
                 assert( (*w>='a') && (*w<='z') );
        would make our code even more robust.

      5. Code the methods
        1. Pre-conditions first:
          Each pre-condition becomes as assert function.
        2. Then the code of the method.

      6. Some C notes

        1. The struct

          In this exercise, we want to construct arrays of characters strings - one array, English, with English words and the other, Foreign, containing the foreign words. Whenever we want to dynamically allocate space for an array by using malloc or calloc, we declare a pointer to the type of elements of the array. Here, the elements of the array are strings, and strings are represented by character pointers or char *. Therefore both English and Foreign are declared as char ** or pointers to character pointers. Think of English as an array (one of the *'s) of strings (the other *).

        2. ConsDictionary

          There are 3 malloc calls -

          • the first allocates space for the dictionary structure:
          • the other two allocate sufficient space for max_words string pointers.

        3. DeleteDictionary

          Not unsurprisingly, DeleteDictionary has 3 free calls - one to free each block of space malloc'd in the constructor.

        4. AddTranslation

          Observe that we have used strdup to make a copy of the word we're storing in the dictionary. This is to ensure that we've "captured" the appropriate word for storage in the dictionary. This allows the user to re-use the buffer in which the new words were placed. Look in the testing program and see how we simply set pointers to the word starting positions in the read buffer used by fgets. The buffer was used again for the next word read from the file.

    7. Verify the class

      Now we need to construct at least one program to verify that the class is correct: verify the Dictionary class.

    Continue on to Verifying the Class
    Back to the Table of Contents
    © John Morris, 1998