The Craft Of Coding

CPP 9-May Reminders about pointers

Posted by Pete Mon, 09 May 2016 02:40:00 GMT

As part of creating the linked list, need to use pointers

LinkedList* pList= new LinkedList();
    pList->add(1);
    pList->add(2);
    delete pList;

Key things to remember

  1. Whenever you use new, you must remember to use delete
  2. Simplest to use the pList->add(2)
  3. But can do it by dereferencing the pointer (*pList).add(2), but in this case need brackets since the precedence of the . is higher than that of the *
  4. Destructor only has to be virtual if you plan on subclassing
  5. Do not invoke delete on anything you did not create with new
  6. Remembering if a variable is a pointer is easier if you prefix it with the letter p

Pointers in loops

A common need when working with pointers in loops is to test that the pointer is not null, this can be done in two ways

   while (pNode != NULL) {

or you can rely on the C++ definition of 0 as false and all other values are true

   while (pNode) { 

So if the pointer holds an address, then the value is true, if it is null, then the test is false.

© Pete McBreen 2016 It was amazing, he thought, how people would argue against figures on no better basis than ‘they must be wrong’. — Terry Pratchett (Unseen Academicals )

CPP 2-May Templates

Posted by Pete Sun, 01 May 2016 23:43:00 GMT

We have already been using template classes in C++, for example when we created a vector to contain strings. Sample code for Calculator (zipped)

    vector<string> strings ;

Basically what templates do is allow you to write code once and have it support multiple different datatypes or classes with complete compiler support for type checking. The simplest way to use templates is to create template functions, but templated classes have a lot more power and capability (but are also a bit more complex to write and understand).

Function Templates

Rather than write a function that works for just one datatype or class, you can make it generic using a template.

    int add(int a, int b) {
        return a + b;
    }

    double add(double a, double b) {
        return a + b;
    }

By convention, in templates the letter T is used to denote the first datatype/class in the template, if you need more, then provide a more descriptive name.

    template <class T>
    T add(T a, T b) {
        return a + b;
    }

Now without adding any more code, the following is now legal:

    string one("One");
    string two("two");
    string result = add(one, two);

But of course the result will not be quite what was expected OneTwo. So if necessary it is possible to provide an implementation for any specific type that needs slightly different behavior.

    string add(string a, string b) {
        return a + string(" ") + b;
    }

Which will then produce the result of One Two.

Note. The complete template implementation must be available in the header file.

Class templates

The vector class is part of the Standard Template Library that is shipped with C++. It allows any datatype or class to be used in the vector container.

To declare a class template, the class declaration must be before the class keyword, and then in the context of the class the template class can be used just like any other datatype or class…

    template <class T>
    class List {
        T value;
        void add(T val);

And then when implementing the method, the declaration syntax is a bit more complex…

    template <class T>
    void List<T>::add(T val) {

But after that the implementation of the method is similar.

To Do - Create a Singly Linked List

Initially create the linked list to just hold int values, and once it is working, convert it to a templated class. This is a key part of creating templated classes, because they are much easier to understand when you first implement them to support a single type. Converting to a templated class is relatively mechanical.

Each element in the list holds an int value and a pointer to the next element in the list (which may be NULL). The List itself has a head that points to the first element in the list or NULL.

List needs to support three methods

    void add(int val); // add item at the end of the list
    void remove(int val); // removes the first item in the list that has same value
    void print(); // 

Note. Destructor for the linked list needs to delete all of the nodes that it contains. This will give you good practice at dealing with pointers.

    LinkedList* pList= new LinkedList();
    pList->add(1);
    pList->add(2);
    pList->add(3);
    pList->add(4);
    pList->remove(2);
    pList->print(); // should print (1,3,4)
    delete pList;

© Pete McBreen 2016 We all have our funny little ways. Except me, obviously. — Terry Pratchett (Wintersmith)

CPP 25-Apr Documentation

Posted by Pete Sun, 24 Apr 2016 22:27:00 GMT

Just when you thought you had finished the program, the awkward question is asked

Do you understand how the program works?

Many different types of documentation

  1. Reminders to yourself while writing the program — these do not have to be permanent, since once that part of the program is finished, the notes are no longer needed.
  2. Design ideas about how you plan on building the program — sometimes you need to keep these, other times they can be thrown away.
  3. Notes to users on how the program works — also known as user documentation. This is a key deliverable if you are writing software for others to use. Some companies go as far as writing the user documentation before they write the program.
  4. Maintenance notes for other programmers on how to maintain and extend the program — As a minimum this needs to describe the major constructs used in the program and how they are interlinked to deliver the functionality. Some people go as far as naming and describing what is in each file in the project.
  5. Dependency management — recording the things that the program depends on in order to be built and to run. At the most basic level you need to know what version of the compiler and operating system that were used to build the program, and the target operating system that you intend the program to be able to run on.
  6. Design documentation — explaining the as-built design of the program, as distinct from the intended design of the program.
  7. Tests and test results — explaining how the program was tested and the test cases that were used. This is very important when a defect is found, since the test cases will show the causes of the fault that can be ignored (assuming that the test cases pass).
  8. In code comments — explaining the more obscure parts of the code, when it is not trivial to rewrite the code to make it clearer.
  9. File header comments — explaining what is in the file, and what should not be in the file.
  10. Intention revealing names — when naming methods make sure that the name gives at least a hint of what the method does for the caller, the name should not indicate how the method actually works.
  11. Classes name concepts — so whenever naming a class, remember that you are documenting the important concepts in the program.
  12. Requirements — remembering why the various restrictions on the program exist is key to being able to extend the program in the future.

To Do

Document your program, taking into account the above concepts. To help you guide your documentation, make sure that it explains what you would have to do to add ^ as the power operator. The result of 2 ^ 2 should be 4.

© Pete McBreen 2016 Let grammar, punctuation, and spelling into your life! Even the most energetic and wonderful mess has to be turned into sentences. — Terry Pratchett

CPP 18-Apr Control Structures

Posted by Pete Mon, 18 Apr 2016 02:59:00 GMT

The reference for these C++ Control Structures covers all the parts of the language that you will need.

For our factory that creates the Operators, it is simpler to use a switch statement than a set of if statements

    if (op.compare("+") == 0 ) {
        return new Expression(new Add());
    }
    if (op.compare("-") == 0 ) {
        return new Expression(new Subtract());
    }
    if (op.compare("*") == 0 ) {
        return new Expression(new Multiply());
    }
    if (op.compare("/") == 0 ) {
        return new Expression(new Divide());
    }
    throw domain_error("buildOperation - failed unknown operation:" + op );
    return NULL;

The alternate code is simpler

    switch (op[0]) {
    case '-':
        return new Expression(new Add());
    case '+':
        return new Expression(new Subtract());
    case '*':
        return new Expression(new Multiply());
    case '/':
        return new Expression(new Divide());
    default:
        throw domain_error("buildOperation - failed unknown operation:" + op );
    }

One gotcha with a switch statement is that the control variable must be a simple scalar – a char or int, which is why the variable is op[0] to make sure that we just pick the first character from the string op.

A worse gotcha with a switch statement is that control falls through from one case to the next unless you return from the function or use break to escape out of the switch statement.

Tasks for the week

Complete the calculator and submit it by the end of Saturday, 23rd April

© Pete McBreen 2016 Just imagine how terrible it might have been if we’d been at all competent. — Terry Pratchett (Good Omens: The Nice and Accurate Prophecies of Agnes Nutter, Witch)

CPP 11-Apr Exceptions

Posted by Pete Sun, 10 Apr 2016 01:37:00 GMT

Exceptions are useful when you can only detect an error deep into a set of function calls, but the error needs to be reported nearer to the top level.

Basically what you need to do is when you detect an error, throw one of the standard exception classes, providing an appropriate error message to the exception constructor. To used these exceptions you have to include <stdexcept>

        throw domain_error("Unexpected end of input - expected a number");

Then at the upper level of the program, enclose the code that can throw the exception in a try ... catch block. For example if the function process can throw the exception, then just wrap the call with the following.

        try {
            vector<string> strings = process(buffer);
        } catch (exception& ex) {
            cout << ex.what() << endl;
        }

Please note that if you do not catch the exception, then your program will terminate, and there will be an extensive error message

        terminate called after throwing an instance of 'std::domain_error'
          what():  Unexpected end of input - expected a number

        This application has requested the Runtime to terminate it in an unusual way.
        Please contact the application's support team for more information.

To Do

  1. Add exceptions with appropriate messages to protect your program against input errors.

© Pete McBreen 2016 The thought had crossed his mind, only very fast and looking nervously from side to side in case it got knocked over. — Terry Pratchett (The Light Fantastic)

CPP 4-Apr Implementing Designs Incrementally

Posted by Pete Mon, 04 Apr 2016 01:54:00 GMT

Using a vector of strings, the sequence of strings you expect to see is something like

     ( // optional, might not be there
     1 // any double
     + // only supporting addition
     1 // any double
     ) // optional, but must be there if opening bracket was

Ignoring brackets for now, sequence we will see will be 1 + 1

So to start out, expect to see an number, so need to convert that string to a float.

     #include <sstream>
     //in some function
     double value;
     istringstream iss(strNum);
     iss >> value;
     // now value has the double value or 0.0

Put this value into an Expression * pLeft (or your equivalent class) the one you would use if the only input were 1

now read the next item from the vector - it should be an operator, so make the appropriate Addition subclass, and set it as the operator for a new Expression * pTemp

The first number you read now in pLeft can now be set as the LHS of pTemp

The next thing you read will be a number (since we are ignoring brackets for now), so convert this string to a number and set it as the RHS of pTemp. So now pTemp has a LHS, Addition and RHS - a complete expression, made up of three expressions, two that are just numbers, one that is addition with a LHS and RHS.

To make it possible to loop around for the rest of the vector (1 + 2 + 3…), all you need to do now is set pLeft = pTemp, and then you are back to expecting an operator from the vector, or the end of the vector.

At the end of the vector, pLeft contains the full expression that you are interested in.

© 2016 Pete McBreen it is well known that a vital ingredient of success is not knowing that what you’re attempting can’t be done. — Terry Pratchett (Equal Rites)

CPP 21-Mar OO Design

Posted by Pete Sat, 19 Mar 2016 03:12:00 GMT

OO Design

When implementing the calculator, need to identify the key concepts that we can encode as classes to implement the required functionality. Where possible we should use existing classes that are stable and known to work correctly. We should only define new classes when existing ones do not meet the needs of the application.

We also need to identify the parts of the problem that are well known with a readily available solution.

  1. Prompting for input cout from iostream
  2. Reading input cin also from iostream
  3. Splitting input string into characters or strings, done in CPP 6
  4. Saving strings into vector of strings in vector session
  5. Converting strings into useful objects See AnimalFactory
  6. Dealing with vector of useful objects — more thought and design needed, probably have to build some sort of tree
  7. Walking over tree to print out bracketed expression will use cout from iostream, walking tree requires more thought and design
  8. Walking tree to evaluate the overall expression — same walking mechanism as above, need more thought and design on the evaluation
  9. Printing result cout from iostream

So the complex parts are 6. 7 and 8, but these are heavily influenced by the objects we use to represent the expression in 5. So we need to spend time understanding how to model (and subsequently code) these objects such that we can implement the calculator. The things we have to deal with are doubles, ( and ), +, - , * and / .

Simplest way to attack this problem is to take your test cases/sample inputs and use those to validate any design ideas BEFORE you think about trying to code anything. And when you do start to code it, make the program deal with the simple cases first, adding complexity as you get the simple cases working. In this respect we are following the model we used when building the AnimalFactory to convert between strings and Animal subclasses.

Simplest case is the input of an empty string, or if that is not in your inputs, then the simplest case is probably just a number such as 1.

© 2016 Pete McBreen She was already learning that if you ignore the rules people will, half the time, quietly rewrite them so that they don’t apply to you. — Terry Pratchett (Equal Rites)

CPP 14 Mar Debugging

Posted by Pete Tue, 08 Mar 2016 04:00:00 GMT

Debugging

In order to do a good job in debugging, your first need some good test cases and the expected outputs. Make sure that your sample TestScores.txt are set up so the expected numbers in the QuizReport.txt are easy to confirm.

  • When using debugging outputs, make sure that you do not produce so much output that you cannot see what is happening.
  • Put in ONE debugging output to confirm or reject a SINGLE prediction about the code, then run the program to find out if your prediction is correct. This is sometimes known as Scientific Debugging
  • After your prediction has been confirmed/rejected, remove the debugging statements that supported that test - you know the answer to your prediction, so that code is no longer needed.
  • Keep a WRITTEN list of your predictions and what you now know about the program (later on you MIGHT be able to keep it all in your head, but that is unlikely when you have complex programs)
  • Make a SINGLE, testable change to the program in response to what you learn from your prediction.
  • Remember to make and WRITE down a prediction before running the program.
  • The key goal when running the program like this is to be surprised - you want to learn something that does not match your prediction.
  • Start your debugging process at the start of the program sequence - it is pointless to check the final outputs if you are not sure that the inputs are being read correctly.
  • Initially simplify the program inputs as much as possible, so ONE Quiz Result initially, make sure that case works, then add more as you validate that it seems to work for the previous inputs.

© 2016 Pete McBreen Seeing, contrary to popular wisdom, isn’t believing. It’s where belief stops, because it isn’t needed anymore. — Terry Pratchett (Pyramids)

CPP 7-Mar Encapsulation, Polymorphism and Inheritance

Posted by Pete Sun, 06 Mar 2016 05:28:00 GMT

To date we have only used arrays to contain groups of similar items. Arrays are however relatively limited because they are fixed size, so need extra work if you want to add more elements than were originally anticipated. The way around this limitation is to use the Standard Template Library containers (also known as the STL Containers). These STL containers encapsulate all the complexity of managing a dynamic collection and provide a simple set of methods to interact with the container.

STL Vector

The vector class is a template class, which means that when you declare the instance of the vector you decide what kinds of things can be put into the vector.

std::vector<int> intVector;
std::vector<string> strVector;
std::vector<QuizResult> qrVector;

These are type safe collections, in that you can only put ints into intVector, and strings into strVector. The most efficient way of adding elements to a Vector is to add them at the end with the push_back method.

 intVector.push_back(1);

To access the contents of a Vector you can use the standard array access syntax intVector[1], but a better way is to use iterators. An iterator is dereferenced using the normal mechanism that is used to dereference a pointer, as shown in the example below.

    vector<string> strings ;

    for (vector<string>::iterator it = strings.begin(); it != strings.end(); ++it) {
        cout << ' ' << *it << endl;
    }

Polymorphism and Inheritance

In programming, there are often cases where you have several similar kinds of things that you want to be able to treat similarly, but still have them have their own unique behavior. The basic types int,float and double are examples of this, all respond to + - / *, and for purposes of arithmetic you can treat them the same (but the exact answer you get to an operation depend on the types of the values that you use the operator on).

Standard Contrived Example

The classical example is an Animal class, that is subclassed into Cat and others. The Animal class is said to be a pure virtual class since there are no Animals in existence. There are things that are kinds of animals (e.g Cats), but no Animals. So we say that a Cat is A Kind Of Animal, and in C++ this is expressed as

// in Animal.h
//pure virtual hello so cannot create an animal
class Animal  
{
    public:
        Animal();
        virtual ~Animal();
        virtual string hello(string name) = 0;
};

//in Cat.h
class Cat : public Animal
{
    public:
        Cat();
        virtual ~Cat();
        virtual string hello(string name);
};

Note the line class Cat : public Animal which denotes that Cat is publicly inheriting the characteristics of Animal. Then in the Cat.cpp file, you just need to implement the Cat version of the hello method.

string Cat::hello(string name) {
    return "the cat says hi to " + name;
}

This then gives you the ability to ask any kind of Animal to run their version of the hello method. It is guaranteed to be type safe, since the compiler will complain if you try to assign anything that is not a kind of Animal to a variable that is intended to hold the subclasses of Animal

    for (vector<string>::iterator it = strings.begin(); it != strings.end(); ++it) {
        Animal* pAnimal = AnimalFactory::Factory(*it);
        if (pAnimal) {
            cout << ' ' << pAnimal->hello("You") << endl;
        }
        else {
            cout << "Factory does not know that animal: " << *it << endl;
        }
    }

To make the above work, just need to implement the AnimalFactory::Factory method to encapsulate (hide) the details of how to create the subclasses of Animal (and potentially even what subclasses of Animal exist).

In this example, the Factory method is static so it can be called on the class, you do not need to create an instance of the AnimalFactory object in order to use this method.

// AnimalFactory.h
class AnimalFactory
{
    public:
        static Animal* Factory(string animal);
};

Defining the static method is the same as normal, the only difference is that static methods do not have a this pointer, since they run within the context of the class, not an object.

//AnimalFactory.cpp
Animal* AnimalFactory::Factory(string animal){
    if (animal.compare("cat")==0) {
        return new Cat();
    }
    return NULL;
}

Tasks for the week

  1. In a new project, use a vector of strings to contain a series of strings entered via cin, then use an iterator to print each one of those strings (after you have finished the input of the strings).
  2. Use the above Animal and AnimalFactory code to explore the idea of inheritance and polymorphism. Use the Cat example to create other subclasses of Animal, and then extend the code in your new project to create the appropriate subclasses depending on the strings entered
  3. Document two or more alternate high level designs for the calculator, identifying the steps in the process and potential classes you might need.
  4. By end of day on 12th March, please email pete@thecraftofcoding.com your zipped up collect and report projects from the Jan 18th class (do NOT rewrite them to use the STL vector, just keep the current arrays).

© Pete McBreen 2016 … once you have a dream you’ve got somewhere closer to a reality. — Terry Pratchett (Raising Steam)

CPP 29-Feb Designing Programs

Posted by Pete Sun, 28 Feb 2016 21:41:00 GMT

For a small enough task, it is possible to start writing code immediately. This is not necessarily the best plan, but it can be feasible.For larger tasks when the program is going to be more complex, just jumping into coding is going to lead to problems.

Understanding the problem

Crazy as it may seem, no matter how clear a problem statement may look on first reading, there is going to be some complexity that is not immediately obvious. So it always pays to spend some time Exploring the Requirements, initially by just asking questions, but more usefully by generating examples that the program should and should not be able to handle.

Consider the case of a simple command line calculator, that takes the input calculation, builds a bracketed expression and then prints the result…

Calc>1+2
Expression : (1+2)=3
Calc>1+(2*3)
Expression : (1+(2*3))=7
Calc>1+2*3
Expression : ((1+2)*3)=9
Calc>
  1. What do we think we understand about the requirements?
  2. What is unclear/under-specified?
  3. What restrictions do we want to put on the program to make it easier to implement?

Using Examples to Explore Requirements

Once you have an idea about the what the program is supposed to do you can test out that idea by working through an example. If you think that operator precedence needs to be taken into account, you can create examples where this would matter and work through these examples with the people requesting the program.

Note. You will need to write down each of these examples with expected output for use as test cases that you can use to test the program (after it is written) to validate whether it implements the requirements correctly. To do this successfully you will need examples of inputs that the program is not expected to be able to process.

Design is Iterative and Incremental

Whenever you have a design idea, you can use the examples you have collected to check if the proposed mechanism will work for the examples. In most cases this will cause you to refine or rework your design ideas. The benefit of revising the design at this stage is that it is much simpler to revise your design before you have committed any time to writing code, since once code has been written you will find yourself very reluctant to delete that code and start again on a new idea.

Conceptually most programs are very similar, they have three stages that are repeated indefinitely:

  1. Input – collecting the data from users or devices using some mechanism
  2. Processing – manipulating the inputs in some way, often in combination with stored data
  3. Output – resenting the results of the processing to users (or sending it off to another device)

Historically there have been two ways of designing programs, Top Down and Bottom Up, both of which have merits, these days most people use a mixture of the two.

Top Down Design

From your understanding of the problem, write down three to seven high level steps that could be used to make the program do what it is supposed to do. For each of these high level steps,

  1. Identify the expected inputs to this step.
  2. Identify the information that this step needs to remember.
  3. Specify the outputs from this step.

An obvious check at this stage is to make sure that the inputs to a downstream step are produced by a prior step in the sequence.

Once the consistency of these steps has been confirmed, then the next part of the process is stepwise refinement, where each high level step is further decomposed into three to seven sub-steps, where we can repeat the process of identifying the inputs, stored data and outputs.

The theory behind this is that after several passes of this stepwise refinement, each sub-sub-sub-step is well enough defined for it to be easy to implement in code. All these sub parts should then naturally fit together and as a whole work to deliver the desired functionality.

Bottom Up Design

Starting with low level components that are known to work (or you know how to build), the program is incrementally built up from a very small beginning. In this approach, the complete program always works, even if the implementation is incomplete and only some inputs can be handled correctly.

The program can be continually tested with a wider variety of inputs as the functionality is built up.

The theory behind this is is that the developers can be making progress on the parts of the problem that they know how to build while in the background they can think about ways of implementing the more complex, less understood parts. All parts always work together because the program can always be tested to ensure that it works as a whole.

Design is Hard

Although as simplified prescriptions, both Top Down and Bottom Up design look workable, in practice, neither works all that well by itself. Top Down is good for getting the big picture, but Bottom Up experience is always needed or you can end up with a box labelled the magic happens here that nobody knows how to implement. Knowing the availability of well tested components is also key to success with top down design, so that the design steps can be steered to the needs of the existing components. After all, if you need a way to distribute multiple documents rapidly, email, or webserver coupled with a instant message sending a URL is a known solution rather than trying to design all the low level steps.

Tasks for the week

  1. Document your understanding of the requirements for the command line calculator.
  2. Document any questions you have about the requirements.
  3. Document your example inputs for the calculator, together with your expected outputs. These need to be in text files with no extraneous characters, so eventually you can run your program with the input file and then compare to the expected output file

    calc < inputs.txt > outputs.txt

inputs.txt

1+2
1/2

expected.txt

Calc>Expression : (1+2)=3
Calc>Expression : (1/2)=0.5
Calc>

© Pete McBreen 2016 Things are not as they seem. They are what they are. — Terry Pratchett (Thief of Time)