Week 5: More on Structs, Linked Lists, Const-correctness

C++ Milestones
- Other Important g++ Compiler Flag
  - -Wall flag
Assignment of Week 4
LL-Based Queues
Regular Functions and Methods
Preprocessing
Const Correctness
Advanced: Intro to Build Systems
- Installation

C++ Milestones

Compiling C++ of 2003

g++ -std=c++03 source_code.cpp -o output_name

Compiling C++ of 2011

g++ -std=c++11 source_code.cpp -o output_name

Other Important g++ Compiler Flag

`-Wall` flag

Let your compiler not just reports you errors.
Let him report you all the warnings.
Fixing warning avoids many run-time issues.

Compiling C++ of 2003

g++ -Wall -std=c++03 source_code.cpp -o output_name

Compiling C++ of 2011

g++ -Wall -std=c++11 source_code.cpp -o output_name

Assignment of Week 4

General LL: 11 operations

operations:

insertion at front.
insertion at back.
remove front.
remove back.
return front.
return back.
return node at arbitrary index.
remove the kth-node.
remove nodes with given data, i.e filtaration.
is empty?
printAll.
delete the whole list from the heap.

A: LL of Integers

struct IntegerNode
{
    int data;
    IntegerNode *next = nullptr;
};

struct IntegerLL
{
    IntegerNode *front;
};

void insertBack( IntegerLL &list , int data )
{
    // Logic
}

void insertFront( IntegerLL &list, int data  )
{
    // Logic
}

int front( IntegerLL &list )
{
    // Logic
}

int back( IntegerLL &list )
{
    // Logic
}

int getNth( IntegerLL &list , int n )
{
    // Logic
}

void removeBack( IntegerLL &list )
{
    // Logic
}

void removeFront( IntegerLL &list )
{
    // Logic
}

void removeNth( IntegerLL &list , int n )
{
    // Logic
}

void removeNext( IntegerLL &list, IntegerNode *node )
{
    // Logic
}

void filter( IntegerLL &list , int data )
{
    // Logic
}

bool isEmpty( IntegerLL &list )
{
    // Logic
}

void printAll( IntegerLL &list )
{
    // Logic
}

void clear( IntegerLL &list )
{
    // Logic
}

B: LL of Characters

struct CharNode
{
    char data;
    CharNode *next = nullptr;
};

struct CharLL
{
    CharNode *front = nullptr;
};

Stacks using LL

Node type

struct CharNode
{
    char data;
    CharNode* next = nullptr;
};

Stack-LL

In case of LL-based stack, we can represent a stack using only a single pointer, i.e the front of the stack.

struct CharStackLL
{
    CharNode *front = nullptr;
};

Initially, when stack is empty, the front pointer points to nothing, i.e nullptr.

Push operation

When we push a new element, we add that element to the front. We make sure that we link the new node correctly.

void push( CharStackLL &stack , char data )
{
    CharNode *newNode = new CharNode;

    newNode->data = data;
    newNode->next = stack.front;

    stack.front = newNode;
}

or, equivalently

void push( CharStackLL &stack , char data )
{
    CharNode *newNode = new CharNode{ data , stack.front };
    stack.front = newNode;
}

or, a DRY solution (optional):

void push( CharStackLL &stack , char data )
{
    // 1. Make list interface
    CharLL list{ stack.front };

    // 2. DRY
    lists::insertFront( list , data );

    // 3. Update Stack front
    stack.front = list.front; // update the front of the stack
}

Front access

As simple as:

char front( CharStackLL &stack  )
{
    return stack.front->data;
}

Pop operation

When popping (deleting) an element from the front,

void pop( CharStackLL &stack )
{
    if( stack.front )
    {
        // Save the pointer of the front, so we delete it later
        CharNode *oldFront = stack.front;

        // Update the front of the stack
        stack.front = stack.front->next;

        // Now delete the old pointer
        delete oldFront;
    }
    else
    {
        // If the stack is empty, make the program to terminate (crash)!
        // The user of this function should have checked if the stack is not empty.
        exit( 1 );
    }
}

or DRY solution,

void pop( CharStack &stack )
{
    // 1. Make list interface
    CharLL list{ stack.front };

    // 2. DRY
    lists::removeFront( list );
    
    // 3. Update Stack front
    stack.front = list.front;
}

Asking a Stack if it is Empty

bool isEmpty( CharacterStackLL &stack )
{
    if( stack.front == nullptr )
    {
        return true;
    }
    else
    {
        return false;
    }
}

Again, could be done that way:

bool isEmpty( CharacterStackLL &stack )
{
    return stack.front == nullptr;
}

Home Demo

Open StackLL and play with the stack to realize its behaviour. This demo shows a Stack implemented with linked list.

LL-Based Queues

The same node struct.

struct DoubleNode
{
    double data;
    DoubleNode *next;
};

And the whole Queue is represented by two elements: Front (or Head) and Back (or Rear). We can wrap these element in the following struct:

struct DoublesQueueLL
{
    DoubleNode *front = nullptr;
    DoubleNode *back = nullptr;
};

Asking if the LL is Empty

bool isEmpty( NumbersQueueLL queue )
{
    if( queue.back == nullptr )
    {
        return true;
    }
    else
    {
        return false;
    }
}

Or equivalently,

bool isEmpty( NumbersQueueLL queue )
{
    return queue.back == nullptr;
}

Enqueuing a New Element

The new elements will be directly added using back pointer.

void enqueue( NumbersQueueLL &queue , double newSample )
{
    if( isEmpty( queue ))
    {
        queue.back = new DoubleNode{ newSample , nullptr };
        queue.front = queue.back;
    }
    else
    {
        queue.back->next = new DoubleNode{ newSample , nullptr };
        queue.back = queue.back->next;
    }
}

The above snippet is updated at Thursday 22 March 2019.

Dequeueing an Element

Left for the assignment.

Bonus: Array-Based Queues

Trick: Circular Buffer.

Regular Functions and Methods

CharStackLL cstack;

Which is more elegant?

push( cstack , 'A' );

What if we can do

cstack.push('A');

First version => regular function.
Second version => method.

Procedural Paradigm

struct CharStackLL
{
    CharNode *front = nullptr;
};

void push( CharStackLL &stack , char data )
{
    CharNode *newNode = new CharNode{ data , stack.front };
    stack.front = newNode;
}

Object Oriented Paradigm (OOP)

struct CharStackLL
{
    CharNode *front = nullptr;
    
    void push( char newElement )
    {
        CharNode *newNode = new CharNode{ newElement , this->front };
        this->front = newNode;
    }
};

A method inside a struct has an access to a very special pointer called this.
this pointer gives a method access to all the struct members.

Preprocessing

Compilation

Preprocessor directives

Includes.
Include guards.
Macros.
Macro functions.

#ifndef MATHEMATICS_HPP
#define MATHEMATICS_HPP

// includes of external headers here

// Your functions here

#endif // MATHEMATICS_HPP

Include guards

Const Correctness

When passing a pointer or reference that should not be modified, It is very recommended to add const qualifier, so you guarantee the used function won’t modify its contents.

struct IntegerNode
{
    int data;
    IntegerNode *next = nullptr;
};

struct IntegerLL
{
    IntegerNode *front;
};

void insertBack( IntegerLL &list , int data)
{
    // Logic
}

void insertFront( IntegerLL &list, int data )
{
    // Logic
}

int front( const IntegerLL &list )
{
    // Logic
}

int back( const IntegerLL &list )
{
    // Logic
}

void removeBack( IntegerLL &list )
{
    // Logic
}

void removeFront( IntegerLL &list )
{
    // Logic
}

void removeNode( IntegerLL &list , IntegerNode *node )
{
    // Logic
}

void removeData( IntegerLL &list , int data )
{
    // Logic
}

bool isEmpty( const IntegerLL &list )
{
    // Logic
}

void printAll( const IntegerLL &list )
{
    // Logic
}

void clear( IntegerLL &list )
{
    // Logic
}

Advanced: Intro to Build Systems

An introduction to build systems by Marwan Abdellah, Ph.D, Blue Brain Project, EPFL

To access the workshop pages and materials: The Second Biomedical Engineering Workshop.

In depth:

Introduction to CMake from Kitware on Vimeo.

Installation

sudo apt-get install cmake