The Tutorial site

Quick Select

2011-06-22T11:44:00.000+05:30

What is Quick Select Algorithm? How to implement in C++?

The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements.
It is an $O (n)$ , worst-case linear time, selection algorithm. A typical selection by sorting method would need atleast O(n log n) time.
This algorithm is identical to quick sort but it does only a partial sort, since we already know which partition our desired element lies as the pivot is in final sorted position.

EXAMPLE:- Quick select implementation in C++

#include <iostream>
using namespace std;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < 5; i++ )
        cout << input[i] << " ";
    cout << endl;
}

int partition(int* input, int p, int r)
{
    int pivot = input[r];
    
    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;
        
        while ( input[r] > pivot )
            r--;
        
        if ( input[p] == input[r] )
            p++;
        else if ( p < r ) {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }
    
    return r;
}

int quick_select(int* input, int p, int r, int k)
{
    if ( p == r ) return input[p];
    int j = partition(input, p, r);
    int length = j - p + 1;
    if ( length == k ) return input[j];
    else if ( k < length ) return quick_select(input, p, j - 1, k);
    else  return quick_select(input, j + 1, r, k - length);
}

int main()
{
    int A1[] = { 100, 400, 300, 500, 200 };
    cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl;
    int A2[] = { 100, 400, 300, 500, 200 };
    cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl;
    int A3[] = { 100, 400, 300, 500, 200 };
    cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl;
    int A4[] = { 100, 400, 300, 500, 200 };
    cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl;
    int A5[] = { 100, 400, 300, 500, 200 };
    cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl;
}

OUTPUT:-
1st order element 100
2nd order element 200
3rd order element 300
4th order element 400
5th order element 500

C++ Tries

2011-06-17T11:16:00.000+05:30

What is a Trie? How to implement Tries in C++?

Tries are used to index and search strings in a text.
Some examples of tries usage include, finding the longest prefix match in a routing table, auto complete of web addresses in browser etc.
Trie is a tree where each vertex represents a word or prefix.
The root represents an empty string.
Markers are used to indicate end of words.
A typical node in a trie includes the content (a char), marker for end of word and a collection of children.
An example of trie. (Using words Hello, Balloon, Ball)

EXAMPLE:- Demonstrate a simple implementation of search in a Trie

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
    Node() { mContent = ' '; mMarker = false; }
    ~Node() {}
    char content() { return mContent; }
    void setContent(char c) { mContent = c; }
    bool wordMarker() { return mMarker; }
    void setWordMarker() { mMarker = true; }
    Node* findChild(char c);
    void appendChild(Node* child) { mChildren.push_back(child); }
    vector<Node*> children() { return mChildren; }

private:
    char mContent;
    bool mMarker;
    vector<Node*> mChildren;
};

class Trie {
public:
    Trie();
    ~Trie();
    void addWord(string s);
    bool searchWord(string s);
    void deleteWord(string s);
private:
    Node* root;
};

Node* Node::findChild(char c)
{
    for ( int i = 0; i < mChildren.size(); i++ )
    {
        Node* tmp = mChildren.at(i);
        if ( tmp->content() == c )
        {
            return tmp;
        }
    }

    return NULL;
}

Trie::Trie()
{
    root = new Node();
}

Trie::~Trie()
{
    // Free memory
}

void Trie::addWord(string s)
{
    Node* current = root;

    if ( s.length() == 0 )
    {
        current->setWordMarker(); // an empty word
        return;
    }

    for ( int i = 0; i < s.length(); i++ )
    {        
        Node* child = current->findChild(s[i]);
        if ( child != NULL )
        {
            current = child;
        }
        else
        {
            Node* tmp = new Node();
            tmp->setContent(s[i]);
            current->appendChild(tmp);
            current = tmp;
        }
        if ( i == s.length() - 1 )
            current->setWordMarker();
    }
}


bool Trie::searchWord(string s)
{
    Node* current = root;

    while ( current != NULL )
    {
        for ( int i = 0; i < s.length(); i++ )
        {
            Node* tmp = current->findChild(s[i]);
            if ( tmp == NULL )
                return false;
            current = tmp;
        }

        if ( current->wordMarker() )
            return true;
        else
            return false;
    }

    return false;
}


// Test program
int main()
{
    Trie* trie = new Trie();
    trie->addWord("Hello");
    trie->addWord("Balloon");
    trie->addWord("Ball");

    if ( trie->searchWord("Hell") )
        cout << "Found Hell" << endl;

    if ( trie->searchWord("Hello") )
        cout << "Found Hello" << endl;

    if ( trie->searchWord("Helloo") )
        cout << "Found Helloo" << endl;

    if ( trie->searchWord("Ball") )
        cout << "Found Ball" << endl;

    if ( trie->searchWord("Balloon") )
        cout << "Found Balloon" << endl;

    delete trie;
}

OUTPUT:-
Found Hello
Found Ball
Found Balloon

Merge Sort

2011-06-17T09:58:00.000+05:30

What is Merge Sort algorithm? How to implement Merge Sort in C++?

Merge Sort is a divide and conquer algorithm.
In the best/ average/ worst case it gives a time complexity of O(n log n).

Conceptually, a merge sort works as follows:

If the list is of length 0 or 1, then it is already sorted. Otherwise:
Divide the unsorted list into two sublists of about half the size.
Sort each sublist recursively by re-applying the merge sort.
Merge the two sublists back into one sorted list.

(Reference: http://en.wikipedia.org/wiki/Merge_sort)

EXAMPLE: Demonstrate a simple merge sort implementation

#include <iostream>
#include <cmath>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

void merge(int* input, int p, int r)
{
    int mid = floor((p + r) / 2);
    int i1 = 0;
    int i2 = p;
    int i3 = mid + 1;

    // Temp array
    int temp[r-p+1];

    // Merge in sorted form the 2 arrays
    while ( i2 <= mid && i3 <= r )
        if ( input[i2] < input[i3] )
            temp[i1++] = input[i2++];
        else
            temp[i1++] = input[i3++];

    // Merge the remaining elements in left array
    while ( i2 <= mid )
        temp[i1++] = input[i2++];

    // Merge the remaining elements in right array
    while ( i3 <= r )
        temp[i1++] = input[i3++];

    // Move from temp array to master array
    for ( int i = p; i <= r; i++ )
        input[i] = temp[i-p];
}

void merge_sort(int* input, int p, int r)
{
    if ( p < r )
    {
        int mid = floor((p + r) / 2);
        merge_sort(input, p, mid);
        merge_sort(input, mid + 1, r);
        merge(input, p, r);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    merge_sort(input, 0, 9);
    cout << "Output: ";
    print(input);
    return 0;
}
OUTPUT:-
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000

Facade Pattern

2011-06-14T15:41:00.000+05:30

What is Facade Pattern?

It is a structural design pattern.
Makes an existing complex software library easier to use by providing a simpler interface for common tasks.
Allows the applications/ clients using the library de-coupled from inner workings of a complex library.

EXAMPLE:- Demonstrate a simple Facade Pattern in C++

#include <iostream>
using namespace std;

// Transfer library
class Usb {
public:
    bool isAvailable()
    {
        return false;
    }

    void connect()
    {
        cout << "Connecting via USB" << endl;
    }

    void send(string file)
    {
        cout << file << " sent." << endl;
    }
};

class Bluetooth {
public:
    bool isAvailable()
    {
        return true;
    }

    void connect()
    {
        cout << "Connecting via BT" << endl;
    }

    void authenticate()
    {
        cout << "Authenticating BT" << endl;
    }

    void send(string file)
    {
        cout << file << " sent." << endl;
    }
};

// The Facade
class FileTransfer {
public:
    void sendFile(string fileName)
    {
        Usb* u = new Usb();
        Bluetooth* b = new Bluetooth();
        if ( u->isAvailable() )
        {
            u->connect();
            u->send(fileName);
        }
        else if ( b->isAvailable() )
        {
            b->connect();
            b->authenticate();
            b->send(fileName);
        }
        else
        {
            cout << "Not sent" << endl;
        }
        delete b;
        delete u;
    }
};

// Test Program
int main()
{
    FileTransfer* ft = new FileTransfer();
    ft->sendFile("mypicture");
    delete ft;
}

OUTPUT:-
Connecting via BT
Authenticating BT
mypicture sent.

Visitor Pattern

2011-06-14T09:42:00.000+05:30

What is a visitor pattern?

The visitor pattern is a behavioral design pattern.
This pattern allows to seperate the data structures and the algorithms to be applied on the data.
Both data structure objects and algorithm objects can evolve seperately. Makes development and changes easier.
Data structure (element) objects have an "accept" method which take in a visitor (algorithmic) object.
Algorithmic objects have a "visit" method which take in a data structure object.

EXAMPLE:- Demonstrate a simple visitor pattern using C++

#include <iostream>
#include <list>
using namespace std;

// Forwards
class VisitorIntf;

// Abstract interface for Element objects
class ElementIntf
{
public:
    virtual string name() = 0;
    virtual void accept(VisitorIntf* object) = 0;
};

// Abstract interface for Visitor objects
class VisitorIntf
{
public:
    virtual void visit(ElementIntf* object) = 0;
};

// Concrete element object
class ConcreteElement1 : public ElementIntf
{
public:
    string name()
    {
        return "ConcreteElement1";
    }

    void accept(VisitorIntf *object)
    {
        object->visit(this);
    }
};


// Concrete element object
class ConcreteElement2 : public ElementIntf
{
public:
    string name()
    {
        return "ConcreteElement2";
    }

    void accept(VisitorIntf *object)
    {
        object->visit(this);
    }
};

// Visitor logic 1
class ConcreteVisitor1 : public VisitorIntf
{
public:
    void visit(ElementIntf *object)
    {
        cout << "Visited " << object->name() <<
                " using ConcreteVisitor1." << endl;
    }
};

// Visitor logic 2
class ConcreteVisitor2 : public VisitorIntf
{
public:
    void visit(ElementIntf *object)
    {
        cout << "Visited " << object->name() <<
             " using ConcreteVisitor2." << endl;
    }
};

//  Test main program
int main()
{
    list<ElementIntf*> elementList1;
    elementList1.push_back(new ConcreteElement1());
    elementList1.push_back(new ConcreteElement2());

    VisitorIntf* visitor1 = new ConcreteVisitor1();
    while ( ! elementList1.empty() )
    {
        ElementIntf* element = elementList1.front();
        element->accept(visitor1);
        elementList1.pop_front();
    }

    list<ElementIntf*> elementList2;
    elementList2.push_back(new ConcreteElement1());
    elementList2.push_back(new ConcreteElement2());
    VisitorIntf* visitor2 = new ConcreteVisitor2();
    while ( ! elementList2.empty() )
    {
        ElementIntf* element = elementList2.front();
        element->accept(visitor2);
        elementList2.pop_front();
    }

    delete visitor1;
    delete visitor2;
}

OUTPUT:-
Visited ConcreteElement1 using ConcreteVisitor1.
Visited ConcreteElement2 using ConcreteVisitor1.
Visited ConcreteElement1 using ConcreteVisitor2.
Visited ConcreteElement2 using ConcreteVisitor2.

Adapter Pattern

2011-06-13T15:39:00.000+05:30

What is Adapter pattern ?

Adapter pattern is a structural design pattern.
Also referred as wrapper pattern.
An adapter allows classes to work together that normally could not because of incompatible interfaces, by providing its interface to clients while using the original interface.
The adapter translates calls to its interface into calls to the original interface.
The adapter is also responsible for transforming data into appropriate forms.
The adapter is created by implementing or inheriting both the interface that is expected and the interface that is pre-existing.
It is typical for the expected interface to be created as a abstract class.

EXAMPLE:- Demonstrate a simple adapter pattern using C++

#include <iostream>
#include <list>
#include <cstdlib>
using namespace std;

// Legacy account
class LegacyAccount
{
    int no;

public:
    LegacyAccount(int no)
    {
        this->no = no;
    }

    void legacyAccountPrint()
    {
        cout << "Display legacy account details " << no << endl;
    }
};

// Renewed interface
class RenewedAccountIntf
{
public:
    virtual void display() = 0;
};

// Renewed account object
class Account : public RenewedAccountIntf
{
    string no;

public:
    Account(string no) {
        this->no = no;
    }

    void display()
    {
        cout << "Display renewed account details " << no << endl;
    }
};

// Legacy account adapter to renewed interface
class LegacyAccountAdapter : public LegacyAccount,
        public RenewedAccountIntf
{
public:
    LegacyAccountAdapter(string no) :
        LegacyAccount(atoi(no.c_str()))
    {
    }

    void display()
    {
        this->legacyAccountPrint();
    }
};


// Test program
int main()
{
    list<RenewedAccountIntf*> accountList;
    accountList.push_back(new Account("accountholder 1"));
    accountList.push_back(new Account("accountholder 2"));
    accountList.push_back(new LegacyAccountAdapter("12345"));

    while ( ! accountList.empty() )
    {
        RenewedAccountIntf* obj = accountList.front();
        obj->display();
        accountList.pop_front();
    }
}

OUTPUT:-Display renewed account details accountholder 1
Display renewed account details accountholder 2
Display legacy account details 12345

Command Pattern

2011-06-13T11:58:00.000+05:30

What is Command Pattern?

Command pattern is a behavioral design pattern.
Encapsulates a command/ request. The command itself is treated as an object.
Classes participating in a command pattern include:-

Command:- An abstract interface defining the execute method.
Concrete Commands:- Extend the Command interface and implements the execute method. Invokes the command on the receiver object.
Receiver:- Knows how to perform the command action.
Invoker:- Asks the command object to carry out the request.
Client:- Creates the commands and associates with the receiver.

Some examples:-

Used when history of requests is needed. (Stock orders executed for today)
Asynchronous processing. Commands need to be executed at variant times.
Installation wizards.

EXAMPLE:- Demonstrates a simple implementation of command pattern in C++

#include <iostream>
#include <vector>
using namespace std;

// Command interface
class Command
{
public:
    virtual void execute() = 0;
};

// Receiver
class StockTrade
{
public:
    StockTrade() {}
    void buy() { cout << "Buy stock" << endl; }
    void sell() { cout << "Sell stock" << endl; }
};

// Concrete command 1
class BuyOrder : public Command
{
    StockTrade* stock;
public:
    BuyOrder(StockTrade* stock)
    {
        this->stock = stock;
    }

    void execute()
    {
        stock->buy();
    }
};

// Concrete command 2
class SellOrder : public Command
{
    StockTrade* stock;
public:
    SellOrder(StockTrade* stock)
    {
        this->stock = stock;
    }

    void execute()
    {
        stock->sell();
    }
};

// Invoker
class StockAgent
{
public:
    StockAgent() {}
    void order( Command* command )
    {
        commandList.push_back(command);
        command->execute();
    }
private:
    // Looking at this command list gives
    // this order history
    vector<Command*> commandList;
};

// Test program
int main()
{
    StockTrade* stock = new StockTrade();
    BuyOrder* buy1 = new BuyOrder(stock);
    BuyOrder* buy2 = new BuyOrder(stock);
    SellOrder* sell1 = new SellOrder(stock);

    StockAgent* agent = new StockAgent();
    agent->order(buy1);
    agent->order(buy2);
    agent->order(sell1);

    delete agent;
    delete sell1;
    delete buy2;
    delete buy1;
    delete stock;
}

OUTPUT:-
Buy stock
Buy stock
Sell stock

C++ Heaps

2011-06-10T14:15:00.000+05:30

What is a heap data structure? How to implement in C++?

Heap is a binary tree that stores priorities (or priority-element pairs) at the nodes.
It has the following properties:

All levels except last level are full. Last level is left filled.
Priority of a node is atleast as large as that of its parent (min-heap) (or) vice-versa (max-heap).
If the smallest element is in the root node, it results in a min-heap.
If the largest element is in the root node, it results in a max-heap.
A heap can be thought of as a priority queue. The most important node will always be at the root of the tree.
Heaps can also be used to sort data, heap sort.
The two most interesting operations in a heap is heapifyup and heapifydown.

Heapifyup (assumption min-heap)

Used to add a node to the heap. To add a node, it is inserted at the last empty space and heapifyup process is done.

When a node is added, its key is compared to its parent. If parent key is smaller than the current node it is swapped. The process is repeated till the heap propery is met.

Heapifydown

Used during removal of a node. When a node is removed which is always the root (lowest in priority) the last available node in heap is replaced as the root and heapifydown process is done.
The key of parent node is compared with the children. If any of the children have lower priority it is swapped with the parent. The process is repeated for the newly swapped node till the heap property is met.

Good references.

http://www.cprogramming.com/tutorial/computersciencetheory/heap.html

EXAMPLE:- Implement a heap in C++. Demonstrates min-heap using arrays.

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

class Heap {
public:
    Heap();
    ~Heap();
    void insert(int element);
    int deletemin();
    void print();
    int size() { return heap.size(); }
private:
    int left(int parent);
    int right(int parent);
    int parent(int child);
    void heapifyup(int index);
    void heapifydown(int index);
private:
    vector<int> heap;
};

Heap::Heap()
{
}

Heap::~Heap()
{
}

void Heap::insert(int element)
{
    heap.push_back(element);
    heapifyup(heap.size() - 1);
}

int Heap::deletemin()
{
    int min = heap.front();
    heap[0] = heap.at(heap.size() - 1);
    heap.pop_back();
    heapifydown(0);
    return min;
}

void Heap::print()
{
    vector<int>::iterator pos = heap.begin();
    cout << "Heap = ";
    while ( pos != heap.end() ) {
        cout << *pos << " ";
        ++pos;
    }
    cout << endl;
}

void Heap::heapifyup(int index)
{    
    //cout << "index=" << index << endl;
    //cout << "parent(index)=" << parent(index) << endl;
    //cout << "heap[parent(index)]=" << heap[parent(index)] << endl;
    //cout << "heap[index]=" << heap[index] << endl;
    while ( ( index > 0 ) && ( parent(index) >= 0 ) &&
            ( heap[parent(index)] > heap[index] ) )
    {
        int tmp = heap[parent(index)];
        heap[parent(index)] = heap[index];
        heap[index] = tmp;
        index = parent(index);
    }
}

void Heap::heapifydown(int index)
{     
    //cout << "index=" << index << endl;
    //cout << "left(index)=" << left(index) << endl;
    //cout << "right(index)=" << right(index) << endl;
    int child = left(index);
    if ( ( child > 0 ) && ( right(index) > 0 ) &&
         ( heap[child] > heap[right(index)] ) )
    {
        child = right(index);
    }
    if ( child > 0 )
    {
        int tmp = heap[index];
        heap[index] = heap[child];
        heap[child] = tmp;
        heapifydown(child);
    }
}

int Heap::left(int parent)
{
    int i = ( parent << 1 ) + 1; // 2 * parent + 1
    return ( i < heap.size() ) ? i : -1;
}

int Heap::right(int parent)
{
    int i = ( parent << 1 ) + 2; // 2 * parent + 2
    return ( i < heap.size() ) ? i : -1;
}

int Heap::parent(int child)
{
    if (child != 0)
    {
        int i = (child - 1) >> 1;
        return i;
    }
    return -1;
}

int main()
{
    // Create the heap
    Heap* myheap = new Heap();
    myheap->insert(700);
    myheap->print();
    myheap->insert(500);
    myheap->print();
    myheap->insert(100);
    myheap->print();
    myheap->insert(800);
    myheap->print();
    myheap->insert(200);
    myheap->print();
    myheap->insert(400);
    myheap->print();
    myheap->insert(900);
    myheap->print();
    myheap->insert(1000);
    myheap->print();
    myheap->insert(300);
    myheap->print();
    myheap->insert(600);
    myheap->print();

    // Get priority element from the heap
    int heapSize = myheap->size();
    for ( int i = 0; i < heapSize; i++ )
        cout << "Get min element = " << myheap->deletemin() << endl;

    // Cleanup
    delete myheap;
}

OUTPUT:-
Heap = 700
Heap = 500 700
Heap = 100 700 500
Heap = 100 700 500 800
Heap = 100 200 500 800 700
Heap = 100 200 400 800 700 500
Heap = 100 200 400 800 700 500 900
Heap = 100 200 400 800 700 500 900 1000
Heap = 100 200 400 300 700 500 900 1000 800
Heap = 100 200 400 300 600 500 900 1000 800 700
Get min element = 100
Get min element = 200
Get min element = 300
Get min element = 400
Get min element = 500
Get min element = 600
Get min element = 700
Get min element = 800
Get min element = 900
Get min element = 1000

Binary Search Trees in C++

2011-06-08T16:41:00.000+05:30

What is binary search trees? How to implemement in C++?

Binary Search Tree (BST) is a binary tree (has atmost 2 children).
It is also referred as sorted/ ordered binary tree.
BST has the following properties. (notes from wikipedia)

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

BST Operations:-

Searching in a BST

Examine the root node. If tree is NULL value doesn't exist.
If value equals the key in root search is successful and return.
If value is less than root, search the left sub-tree.
If value is greater than root, search the right sub-tree.
Continue until the value is found or the sub tree is NULL.
Time complexity. Average: O(log n), Worst: O(n) if the BST is unbalanced and resembles a linked list.

Insertion in BST

Insertion begin as a search.
Compare the key with root. If not equal search the left or right sub tre
When a leaf node is reached add the new node to left or right based on the value.
Time complexity. Average: O(log n), Worst O(n)

Deletion in BST

There are three possible cases to consider:

Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
Deleting a node with one child: Remove the node and replace it with its child.
Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

EXAMPLE:- A sample demonstration of BST using C++

#include <iostream>
using namespace std;

// A generic tree node class
class Node {
    int key;
    Node* left;
    Node* right;
    Node* parent;
public:
    Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    void setParent(Node* aParent) { parent = aParent; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
    Node* Parent() { return parent; };
};

// Binary Search Tree class
class Tree {
    Node* root;
public:
    Tree();
    ~Tree();
    Node* Root() { return root; };
    void addNode(int key);
    Node* findNode(int key, Node* parent);
    void walk(Node* node);
    void deleteNode(int key);
    Node* min(Node* node);
    Node* max(Node* node);
    Node* successor(int key, Node* parent);
    Node* predecessor(int key, Node* parent);
private:
    void addNode(int key, Node* leaf);
    void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
    root = NULL;
}

// Destructor
Tree::~Tree() {
    freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL ) 
    {
        freeNode(leaf->Left());
        freeNode(leaf->Right());
        delete leaf;
    }
}

// Add a node [O(height of tree) on average]
void Tree::addNode(int key)
{
    // No elements. Add the root
    if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
    root = n;
    }
    else {
    cout << "add other node ... " << key << endl;
    addNode(key, root);
    }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() )
    {
        if ( leaf->Left() != NULL )
            addNode(key, leaf->Left());
        else {
            Node* n = new Node();
            n->setKey(key);
            n->setParent(leaf);
            leaf->setLeft(n);
        }
    }
    else
    {
        if ( leaf->Right() != NULL )
            addNode(key, leaf->Right());
        else {
            Node* n = new Node();
            n->setKey(key);
            n->setParent(leaf);
            leaf->setRight(n);
        }
    }
}

// Find a node [O(height of tree) on average]
Node* Tree::findNode(int key, Node* node)
{
    if ( node == NULL )
        return NULL;
    else if ( node->Key() == key )
        return node;
    else if ( key <= node->Key() )
        findNode(key, node->Left());
    else if ( key > node->Key() )
        findNode(key, node->Right());
    else
        return NULL;
}

// Print the tree
void Tree::walk(Node* node)
{
    if ( node )
    {
        cout << node->Key() << " ";
        walk(node->Left());
        walk(node->Right());
    }
}

// Find the node with min key
// Traverse the left sub-tree recursively
// till left sub-tree is empty to get min
Node* Tree::min(Node* node)
{
    if ( node == NULL )
        return NULL;

    if ( node->Left() )
        min(node->Left());
    else
        return node;
}

// Find the node with max key
// Traverse the right sub-tree recursively
// till right sub-tree is empty to get max
Node* Tree::max(Node* node)
{
    if ( node == NULL )
        return NULL;

    if ( node->Right() )
        max(node->Right());
    else
        return node;
}

// Find successor to a node
// Find the node, get the node with max value
// for the right sub-tree to get the successor
Node* Tree::successor(int key, Node *node)
{
    Node* thisKey = findNode(key, node);
    if ( thisKey )
        return max(thisKey->Right());
}

// Find predecessor to a node
// Find the node, get the node with max value
// for the left sub-tree to get the predecessor
Node* Tree::predecessor(int key, Node *node)
{
    Node* thisKey = findNode(key, node);
    if ( thisKey )
        return max(thisKey->Left());
}

// Delete a node
// (1) If leaf just delete
// (2) If only one child delete this node and replace
// with the child
// (3) If 2 children. Find the predecessor (or successor).
// Delete the predecessor (or successor). Replace the
// node to be deleted with the predecessor (or successor).
void Tree::deleteNode(int key)
{
    // Find the node.
    Node* thisKey = findNode(key, root);

    // (1)
    if ( thisKey->Left() == NULL && thisKey->Right() == NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(NULL);
        else
            thisKey->Parent()->setLeft(NULL);

        delete thisKey;
    }

    // (2)
    if ( thisKey->Left() == NULL && thisKey->Right() != NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(thisKey->Right());
        else
            thisKey->Parent()->setLeft(thisKey->Right());

        delete thisKey;
    }
    if ( thisKey->Left() != NULL && thisKey->Right() == NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(thisKey->Left());
        else
            thisKey->Parent()->setLeft(thisKey->Left());

        delete thisKey;
    }

    // (3)
    if ( thisKey->Left() != NULL && thisKey->Right() != NULL )
    {
        Node* sub = predecessor(thisKey->Key(), thisKey);
        if ( sub == NULL )
            sub = successor(thisKey->Key(), thisKey);        

        if ( sub->Parent()->Key() <= sub->Key() )
            sub->Parent()->setRight(sub->Right());
        else
            sub->Parent()->setLeft(sub->Left());

        thisKey->setKey(sub->Key());
        delete sub;
    }
}

// Test main program
int main() {
    Tree* tree = new Tree();

    // Add nodes
    tree->addNode(300);
    tree->addNode(100);
    tree->addNode(200);
    tree->addNode(400);
    tree->addNode(500);

    // Traverse the tree
    tree->walk(tree->Root());
    cout << endl;

    // Find nodes
    if ( tree->findNode(500, tree->Root()) )
        cout << "Node 500 found" << endl;
    else
        cout << "Node 500 not found" << endl;

    if ( tree->findNode(600, tree->Root()) )
        cout << "Node 600 found" << endl;
    else
        cout << "Node 600 not found" << endl;

    // Min & Max
    cout << "Min=" << tree->min(tree->Root())->Key() << endl;
    cout << "Max=" << tree->max(tree->Root())->Key() << endl;

    // Successor and Predecessor
    cout << "Successor to 300=" <<
            tree->successor(300, tree->Root())->Key() << endl;
    cout << "Predecessor to 300=" <<
            tree->predecessor(300, tree->Root())->Key() << endl;

    // Delete a node
    tree->deleteNode(300);

    // Traverse the tree
    tree->walk(tree->Root());
    cout << endl;

    delete tree;
    return 0;
}

OUTPUT:-
add root node ... 300
add other node ... 100
add other node ... 200
add other node ... 400
add other node ... 500
300 100 200 400 500
Node 500 found
Node 600 not found
Min=100
Max=500
Successor to 300=500
Predecessor to 300=200
200 100 400

Bubble Sort in C++

2011-06-08T15:51:00.000+05:30

What is bubble sort algorithm? How to implement in C++?

Bubble sort is a simple sorting algorithm.
Best case time complexity is O(n) when the list is already sorted.
Average and Worst case complexity is O(n*n). So it is not recommended for large input sets.
Bubble sort involves these simple steps.

Compare adjacent items and swap them if they are not in the correct order.
Perform the above step until no exchanges are required,

EXAMPLE:- A sample implementation of bubble sort using C++

#include <iostream>
using namespace std;

static int count = 0;
const int INPUT_SIZE = 10;

void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

void bubblesort(int* input)
{
    count++;
    int exchanges = 0;
    for ( int i = 0; i < INPUT_SIZE; i++ )
    {
        if ( input[i] > input[i+1] )
        {
            int tmp = input[i];
            input[i] = input[i+1];
            input[i+1] = tmp;
            exchanges++;
        }
    }
    
    if ( exchanges == 0 ) return;
    cout << "Parse " << count << ":";
    print(input);
    bubblesort(input);
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    bubblesort(input);
    cout << "Output: ";
    print(input);
    return 0;
}

OUTPUT:-
Input: 500 700 800 100 300 200 900 400 1000 600
Parse 1:500 700 100 300 200 800 400 900 600 1000
Parse 2:500 100 300 200 700 400 800 600 900 1000
Parse 3:100 300 200 500 400 700 600 800 900 1000
Parse 4:100 200 300 400 500 600 700 800 900 1000
Output: 100 200 300 400 500 600 700 800 900 1000

2011-06-08T15:36:00.001+05:30

What is Quick Sort algorithm? How to implement Quick Sort in C++?

Quick Sort is a sorting algorithm. It is also referred as partition exchange sort.
In the best/ average case it gives a time complexity of O(nlogn) and worst case time complexity of O(n*n).
Can be implemented as in-place sorting without need for additional space.
Quick Sorting involves these steps:

Pick a pivot element from the input list.
Perform an input partition operation based on the pivot. Move all elements less than pivot before the pivot element in the list. Move all elements greater than the pivot after the pivot element in the list.
Recursively sort the left and right sub-lists of the pivot.

EXAMPLE:- A simple demonstration of quick sort

#include <iostream>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

// The partition function
int partition(int* input, int p, int r)
{
    int pivot = input[r];

    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;

        while ( input[r] > pivot )
            r--;

        if ( input[p] == input[r] )
            p++;
        else if ( p < r )
        {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }

    return r;
}

// The quicksort recursive function
void quicksort(int* input, int p, int r)
{
    if ( p < r )
    {
        int j = partition(input, p, r);        
        quicksort(input, p, j-1);
        quicksort(input, j+1, r);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    quicksort(input, 0, 9);
    cout << "Output: ";
    print(input);
    return 0;
}

OUTPUT:-
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000

C++ Deque

2011-06-02T09:09:00.004+05:30

What is a deque? How to implement deques using C++?

Deque is an abbreviation for double-ended queue.

It is a data structure in which the elements can only be added or removed from front and back of the queue.

A typical deque implementation support the following operations. Insert at front an element, insert at back an element, remove from back an element, remove from front an element, list the front element and list the back element.

Simple method of implementing a deque is using a doubly linked list.

The time complexity of all the deque operations using a doubly linked list can be achieced O(1).

A general purpose deque implementation can be used to mimic specialized behaviors like stacks and queues.

For example to use deque as a stack. Insert at back an element (Push) and Remove at back an element (Pop) can behave as a stack.

For example to use deque as a queue. Insert at back an element (Enqueue) and Remove at front an element (Dequeue) can behave as a queue.

Deque is also supported in C++ Standard Template Library.

EXAMPLE:- Implement a deque using doubly linked lists.

#include <iostream>
using namespace std;

class DequeEmptyException
{
public:
    DequeEmptyException()
    {
        cout << "Deque empty" << endl;
    }
};

// Each node in a doubly linked list
class Node
{
public:
    int data;
    Node* next;
    Node* prev;
};

class Deque
{  
private:
    Node* front;
    Node* rear;
    int count;

public:
    Deque()
    {
        front = NULL;
        rear = NULL;
        count = 0;
    }      
  
    void InsertFront(int element)
    {
        // Create a new node
        Node* tmp = new Node();
        tmp->data = element;
        tmp->next = NULL;
        tmp->prev = NULL;

        if ( isEmpty() ) {
            // Add the first element
            front = rear = tmp;
        }
        else {
            // Prepend to the list and fix links
            tmp->next = front;
            front->prev = tmp;
            front = tmp;
        }

        count++;
    }

    int RemoveFront()
    {
        if ( isEmpty() ) {
            throw new DequeEmptyException();
        }

        //  Data in the front node
        int ret = front->data;

        // Delete the front node and fix the links
        Node* tmp = front;
        if ( front->next != NULL )
        {
            front = front->next;
            front->prev = NULL;
        }
        else
        {
            front = NULL;
        }
        count--;
        delete tmp;

        return ret;
    }

    void InsertBack(int element)
    {          
        // Create a new node
        Node* tmp = new Node();
        tmp->data = element;
        tmp->next = NULL;
        tmp->prev = NULL;

        if ( isEmpty() ) {
            // Add the first element
            front = rear = tmp;
        }
        else {
            // Append to the list and fix links
            rear->next = tmp;
            tmp->prev = rear;
            rear = tmp;
        }

        count++;
    }

    int RemoveBack()
    {
        if ( isEmpty() ) {
            throw new DequeEmptyException();
        }

        //  Data in the rear node
        int ret = rear->data;

        // Delete the front node and fix the links
        Node* tmp = rear;
        if ( rear->prev != NULL )
        {
            rear = rear->prev;
            rear->next = NULL;
        }
        else
        {
            rear = NULL;
        }
        count--;
        delete tmp;

        return ret;
    }
  
    int Front()
    {          
        if ( isEmpty() )
            throw new DequeEmptyException();

        return front->data;
    }

    int Back()
    {
        if ( isEmpty() )
            throw new DequeEmptyException();

        return rear->data;
    }
  
    int Size()
    {
        return count;
    }

    bool isEmpty()
    {
        return count == 0 ? true : false;
    }
};

int main()
{      
    // Stack behavior using a general dequeue
    Deque q;
    try {
        if ( q.isEmpty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q.InsertBack(100);
        q.InsertBack(200);
        q.InsertBack(300);

        // Size of queue
        cout << "Size of dequeue = " << q.Size() << endl;

        // Pop elements
        cout << q.RemoveBack() << endl;
        cout << q.RemoveBack() << endl;
        cout << q.RemoveBack() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }

    // Queue behavior using a general dequeue
    Deque q1;
    try {
        if ( q1.isEmpty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q1.InsertBack(100);
        q1.InsertBack(200);
        q1.InsertBack(300);

        // Size of queue
        cout << "Size of dequeue = " << q1.Size() << endl;

        // Pop elements
        cout << q1.RemoveFront() << endl;
        cout << q1.RemoveFront() << endl;
        cout << q1.RemoveFront() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:
Deque is empty
Size of dequeue = 3
300
200
100
Deque is empty
Size of dequeue = 3
100
200
300

EXAMPLE:- Using the STL deque

#include <iostream>
#include <deque>
using namespace std;

int main()
{
    // Stack behavior using a STL deque
    deque<int> q;
    try {
        if ( q.empty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q.push_back(100);
        q.push_back(200);
        q.push_back(300);

        // Size of queue
        cout << "Size of deque = " << q.size() << endl;

        // Pop elements
        cout << q.back() << endl;
        q.pop_back();
        cout << q.back() << endl;
        q.pop_back();
        cout << q.back() << endl;
        q.pop_back();
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }

    // Queue behavior using a STL deque
    deque<int> q1;
    try {
        if ( q1.empty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q1.push_back(100);
        q1.push_back(200);
        q1.push_back(300);

        // Size of queue
        cout << "Size of deque = " << q1.size() << endl;

        // Pop elements
        cout << q1.front() << endl;
        q1.pop_front();
        cout << q1.front() << endl;
        q1.pop_front();
        cout << q1.front() << endl;
        q1.pop_front();
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

Deque is empty
Size of dequeue = 3
300
200
100
Deque is empty
Size of dequeue = 3
100
200
300

C++ Pre-Order, In-Order, Post-Order Traversal of Trees

2011-05-09T14:56:00.008+05:30

What is Pre-Order, In-Order, Post-Order traversal of B-Trees?

Pre-Order, In-Order and Post-Order are depth first search traversal methods.

Starting at the root of binary tree the order in which the nodes are visited define these traversal types.

Basically there are 3 main steps. (1) Visting the current node, (2) Traverse the left node and (3) Traverse the right nodes.
From Wikipedia,

To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:
1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

To traverse a non-empty binary tree in inorder (symmetric), perform the following operations recursively at each node:
1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

#include <iostream>
using namespace std;

// Node class
class Node {
    int key;
    Node* left;
    Node* right;
public:
    Node() { key=-1; left=NULL; right=NULL; };
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
};

// Tree class
class Tree {
     Node* root;
public:
     Tree();
     ~Tree();
     Node* Root() { return root; };
     void addNode(int key);
     void inOrder(Node* n);
     void preOrder(Node* n);
     void postOrder(Node* n);
private:
     void addNode(int key, Node* leaf);
     void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
     root = NULL;
}

// Destructor
Tree::~Tree() {
     freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
       freeNode(leaf->Left());
       freeNode(leaf->Right());
       delete leaf;
    }
}

// Add a node
void Tree::addNode(int key) {
     // No elements. Add the root
     if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
    root = n;
     }
     else {
    cout << "add other node ... " << key << endl;
    addNode(key, root);
     }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
      addNode(key, leaf->Left());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
      addNode(key, leaf->Right());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setRight(n);
       }
    }
}

// Print the tree in-order
// Traverse the left sub-tree, root, right sub-tree
void Tree::inOrder(Node* n) {
    if ( n ) {
       inOrder(n->Left());
       cout << n->Key() << " ";
       inOrder(n->Right());
    }
}

// Print the tree pre-order
// Traverse the root, left sub-tree, right sub-tree
void Tree::preOrder(Node* n) {
    if ( n ) {
       cout << n->Key() << " ";
       preOrder(n->Left());
       preOrder(n->Right());
    }
}

// Print the tree post-order
// Traverse left sub-tree, right sub-tree, root
void Tree::postOrder(Node* n) {
    if ( n ) {
       postOrder(n->Left());
       postOrder(n->Right());
       cout << n->Key() << " ";
    }
}


// Test main program
int main() {
   Tree* tree = new Tree();
   tree->addNode(30);
   tree->addNode(10);
   tree->addNode(20);
   tree->addNode(40);
   tree->addNode(50);

   cout << "In order traversal" << endl;
   tree->inOrder(tree->Root());
   cout << endl;

   cout << "Pre order traversal" << endl;
   tree->preOrder(tree->Root());
   cout << endl;

   cout << "Post order traversal" << endl;
   tree->postOrder(tree->Root());
   cout << endl;

   delete tree;
   return 0;
}
.

OUTPUT:-

add root node ... 30
add other node ... 10
add other node ... 20
add other node ... 40
add other node ... 50
In order traversal
10 20 30 40 50
Pre order traversal
30 10 20 40 50
Post order traversal
20 10 50 40 30

C++ Level Order Traversal of B-Tree

2011-05-09T12:26:00.013+05:30

What is level-order traversal of binary tree?

Level order traversal is also referred as Breadth First/ Width First tree traversals.

In simple terms every node of a level is visited before going to the lower level.

An example:

Traversal of the above binary tree in level order produces the following result.
30 10 40 20 50

Traversal in level order is usually done with assitance of queue with the following steps:-

Add the root node to the queue and then repeat the following if queue is not empty.

Dequeue a node from the front of queue and visit it.

Enqueue the node's children from left to right.

EXAMPLE: Demonstrate the level order traversal of binary tree

#include <iostream>
#include <queue>
using namespace std;

// Node class
class Node {
    int key;
    Node* left;
    Node* right;
public:
    Node() { key=-1; left=NULL; right=NULL; };
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
};

// Tree class
class Tree {
     Node* root;
public:
     Tree();
     ~Tree();
     Node* Root() { return root; };
     void addNode(int key);
     void levelOrder(Node* n);
private:
     void addNode(int key, Node* leaf);
     void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
     root = NULL;
}

// Destructor
Tree::~Tree() {
     freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
       freeNode(leaf->Left());
       freeNode(leaf->Right());
       delete leaf;
    }
}

// Add a node
void Tree::addNode(int key) {
     // No elements. Add the root
     if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
    root = n;
     }
     else {
    cout << "add other node ... " << key << endl;
    addNode(key, root);
     }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
      addNode(key, leaf->Left());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
      addNode(key, leaf->Right());
       else {
      Node* n = new Node();
      n->setKey(key);
      leaf->setRight(n);
       }
    }
}

// Print the tree level-order assisted by queue
void Tree::levelOrder(Node* n) {
   // Create a queue
   queue<Node*> q;

   // Push the root
   q.push(n);

   while ( ! q.empty() )
   {
       // Dequeue a node from front
       Node* v = q.front();
       cout << v->Key() << " ";

       // Enqueue the left children
       if ( v->Left() != NULL )
            q.push(v->Left());

       // Enqueue the right children
       if ( v->Right() != NULL )
            q.push(v->Right());

       // Pop the visited node
       q.pop();
   }
}

// Test main program
int main() {
   Tree* tree = new Tree();
   tree->addNode(30);
   tree->addNode(10);
   tree->addNode(20);
   tree->addNode(40);
   tree->addNode(50);

   cout << "Level order traversal" << endl;
   tree->levelOrder(tree->Root());
   cout << endl;

   delete tree;
   return 0;
}

OUTPUT:-

add root node ... 30
add other node ... 10
add other node ... 20
add other node ... 40
add other node ... 50
Level order traversal
30 10 40 20 50

HTML/ CSS Text and Image side by side

2010-07-27T09:30:00.004+05:30

This code snippet provides a CSS and HTML to place image and text side by side in a HTML page.

The CSS.

.mydiv {background: lightblue; width:250px; height: 250px;}

.myimage {float:left; width:100px; height:150px; margin:5px;}

The HTML.

<html>

    <head>

        <link rel='stylesheet' href="testme.css">

    </head>

    <body>

    <div class="mydiv">

        <img class="myimage" src="testme.jpg"/>

        Hi. Image with text on the same line.

        Hi. Image with text on the same line.

        Hi. Image with text on the same line.

        Hi. Image with text on the same line.

        Hi. Image with text on the same line.

        Hi. Image with text on the same line.

        Hi. Image with text on the same line.

        Hi. Image with text on the same line.

    </div>

    </body>

</html>.

The output.

Javascript scroll to bottom of page

2010-07-23T09:26:00.000+05:30

This code snippet provides a javascript function to scroll a HTML page
programatically to the bottom on page load. Make the browser height
smaller to observe the scrolling effect.

The javascript.


window.onload=toBottom;

function toBottom()
{
alert("Scrolling to bottom ...");
window.scrollTo(0, document.body.scrollHeight);
}

The test html code.

<html>
    <head>
        <script src="testme.js" language="javascript" type="text/javascript"></script>
    </head>
    <body>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>
        Some big text<br>        
  </body>
</html>

C++ Singly Linked Lists

2008-07-25T07:27:00.008+05:30

What is a singly linked list? How to implement singly linked lists in C++?

Linked lists are building blocks for many other data structures like stacks and queues.
Linked lists are a sequence of nodes containing data fields and pointers to the next node (or) next node and previous nodes based on its type.
Linked lists permit addition/ removal of node in constant time.
Unlike arrays the order of linked list elements need not be contiguous in memory.
Unlike arrays there is no upper limit on the amount of memory reserved.
A singly linked list is the simplest of linked lists.
Each node of a singly linked list has data elements and a single link (pointer) that points to the next node of the list (or) NULL if it is the last node of the list.
Addition/ Deletion of a node to the singly linked list involves the creation/ deletion of the node and adjusting the node pointers accordingly.
A singly linked list could be represented as below:-

EXAMPLE:- Demonstrate the implementation of a singly linked list

#include <iostream>
using namespace std;

// Node class
class Node {
    int data;
    Node* next;

  public:
    Node() {};
    void SetData(int aData) { data = aData; };
    void SetNext(Node* aNext) { next = aNext; };
    int Data() { return data; };
    Node* Next() { return next; };
};

// List class
class List {
    Node *head;
  public:
    List() { head = NULL; };
    void Print();
    void Append(int data);
    void Delete(int data);
};

/**
 * Print the contents of the list
 */
void List::Print() {

    // Temp pointer
    Node *tmp = head;

    // No nodes
    if ( tmp == NULL ) {
    cout << "EMPTY" << endl;
    return;
    }

    // One node in the list
    if ( tmp->Next() == NULL ) {
    cout << tmp->Data();
    cout << " --> ";
    cout << "NULL" << endl;
    }
    else {
    // Parse and print the list
    do {
        cout << tmp->Data();
        cout << " --> ";
        tmp = tmp->Next();
    }
    while ( tmp != NULL );

    cout << "NULL" << endl;
    }
}

/**
 * Append a node to the linked list
 */
void List::Append(int data) {

    // Create a new node
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->SetNext(NULL);

    // Create a temp pointer
    Node *tmp = head;

    if ( tmp != NULL ) {
    // Nodes already present in the list
    // Parse to end of list
    while ( tmp->Next() != NULL ) {
        tmp = tmp->Next();
    }

    // Point the last node to the new node
    tmp->SetNext(newNode);
    }
    else {
    // First node in the list
    head = newNode;
    }
}

/**
 * Delete a node from the list
 */
void List::Delete(int data) {

    // Create a temp pointer
    Node *tmp = head;

    // No nodes
    if ( tmp == NULL )
    return;

    // Last node of the list
    if ( tmp->Next() == NULL ) {
    delete tmp;
    head = NULL;
    }
    else {
    // Parse thru the nodes
    Node *prev;
    do {
        if ( tmp->Data() == data ) break;
        prev = tmp;
        tmp = tmp->Next();
    } while ( tmp != NULL );

    // Adjust the pointers
    prev->SetNext(tmp->Next());

    // Delete the current node
    delete tmp;
    }
}

int main()
{
    // New list
    List list;

    // Append nodes to the list
    list.Append(100);
    list.Print();
    list.Append(200);
    list.Print();
    list.Append(300);
    list.Print();
    list.Append(400);
    list.Print();
    list.Append(500);
    list.Print();

    // Delete nodes from the list
    list.Delete(400);
    list.Print();
    list.Delete(300);
    list.Print();
    list.Delete(200);
    list.Print();
    list.Delete(500);
    list.Print();
    list.Delete(100);
    list.Print();
}

OUTPUT:-
100 --> NULL
100 --> 200 --> NULL
100 --> 200 --> 300 --> NULL
100 --> 200 --> 300 --> 400 --> NULL
100 --> 200 --> 300 --> 400 --> 500 --> NULL
100 --> 200 --> 300 --> 500 --> NULL
100 --> 200 --> 500 --> NULL
100 --> 500 --> NULL
100 --> NULL
EMPTY

C++ Queues

2008-07-13T17:36:00.007+05:30

What is a queue? How to implement queues using C++?

Queue is a first-in, first-out (FIFO) data structure. i.e. the element added first to the queue will be the one to be removed first.

Elements are always added to the back of the queue and removed from the front of the queue.

Typical use cases of queues include:- (1) In Inter-Process Communication (IPC) message queues is a common mechanism for communication between processes.

Some of the common terminology associated with queues inlcude ADD/ PUSH and DELETE/ POP of elements to the queue.

ADD/ PUSH refers to adding an element to the queue.

DELETE/ POP refers to removing an element from the queue.

Diagram below explains the queue.

EXAMPLE: Demonstrate the implmentation of a simple queue using arrays

#include <iostream>
#include <cstdlib>
using namespace std;

const int MAX_SIZE = 100;

class QueueOverFlowException
{
public:
   QueueOverFlowException()
   {
       cout << "Queue overflow" << endl;
   }
};

class QueueEmptyException
{
public:
   QueueEmptyException()
   {
       cout << "Queue empty" << endl;
   }
};

class ArrayQueue
{  
private:
   int data[MAX_SIZE];
   int front;
   int rear;
public:
   ArrayQueue()
   {
       front = -1;
       rear = -1;
   }      
 
   void Enqueue(int element)
   {
       // Don't allow the queue to grow more
       // than MAX_SIZE - 1
       if ( Size() == MAX_SIZE - 1 )                 
           throw new QueueOverFlowException();

       data[rear] = element;

       // MOD is used so that rear indicator
       // can wrap around
       rear = ++rear % MAX_SIZE;
   }      

   int Dequeue()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       int ret = data[front];

       // MOD is used so that front indicator
       // can wrap around
       front = ++front % MAX_SIZE;

       return ret;   
   }      
 
   int Front()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       return data[front];
   }
 
   int Size()
   {
       return abs(rear - front);
   }
 
   bool isEmpty()
   {
       return ( front == rear ) ? true : false;
   }
};

int main()
{  
   ArrayQueue q;
   try {
       if ( q.isEmpty() )
       {
           cout << "Queue is empty" << endl;
       }

       // Enqueue elements
       q.Enqueue(100);
       q.Enqueue(200);
       q.Enqueue(300);

       // Size of queue
       cout << "Size of queue = " << q.Size() << endl;

       // Front element
       cout << q.Front() << endl;

       // Dequeue elements
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
   }
   catch (...) {
       cout << "Some exception occured" << endl;
   }
}

OUTPUT:-
Queue is empty
Size of queue = 3
100
100
200
300

EXAMPLE: Demonstrate the implementation of a simple queue using linked lists

#include <iostream>
using namespace std;

class QueueEmptyException
{
public:
   QueueEmptyException()
   {
       cout << "Queue empty" << endl;
   }
};

class Node
{
public:
   int data;
   Node* next;
};

class ListQueue
{  
private:
   Node* front;
   Node* rear;
   int count;

public:
   ListQueue()
   {
       front = NULL;
       rear = NULL;
       count = 0;
   }      
 
   void Enqueue(int element)
   {
       // Create a new node
       Node* tmp = new Node();
       tmp->data = element;
       tmp->next = NULL;

       if ( isEmpty() ) {
           // Add the first element
           front = rear = tmp;
       }
       else {
           // Append to the list
           rear->next = tmp;
           rear = tmp;
       }

       count++;
   }      

   int Dequeue()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       int ret = front->data;
       Node* tmp = front;

       // Move the front pointer to next node
       front = front->next;

       count--;
       delete tmp;
       return ret;   
   }      
 
   int Front()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       return front->data;
   }
 
   int Size()
   {
       return count;
   }

   bool isEmpty()
   {
       return count == 0 ? true : false;
   }
};

int main()
{  
   ListQueue q;
   try {
       if ( q.isEmpty() )
       {
           cout << "Queue is empty" << endl;
       }

       // Enqueue elements
       q.Enqueue(100);
       q.Enqueue(200);
       q.Enqueue(300);

       // Size of queue
       cout << "Size of queue = " << q.Size() << endl;

       // Front element
       cout << q.Front() << endl;

       // Dequeue elements
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
   }
   catch (...) {
       cout << "Some exception occured" << endl;
   }
}

OUTPUT:-
Queue is empty
Size of queue = 3
100
100
200
300

EXAMPLE: Demonstrate the queue library usage in standard template library (STL).

#include <iostream>
#include <queue>
using namespace std;

int main()
{
   queue<int> q;
   q.push(100);
   q.push(200);
   q.push(300);
   q.push(400);

   cout << "Size of the queue: " << q.size() << endl;

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   if ( q.empty() ) {
   cout << "Queue is empty" << endl;
   }
}

OUTPUT:-
Size of the queue: 4
100
200
300
400
Queue is empty

C++ Stacks

2008-07-11T18:42:00.009+05:30

What is a stack? How to implement stacks using C++?

Stack is a last-in, first-out (LIFO) data structure. i.e. the element added last to the stack will be the one to be removed first.
Typical use cases of stacks include:- (1) During debugging it is quite common to examine the function call stack during panics. (2) In RTOS like Symbian there are concepts like cleanup stack to avoid memory leaks.
Some of the common terminology associated with stacks inlcude PUSH, POP and TOP of the stack.
PUSH refers to adding an element to the stack.
POP refers to removing an element from the stack.
TOP refers to the first element that could be POPed (or) the last element PUSHed.
Diagram below explains the stack.

EXAMPLE: Demonstrate the implementation of a simple stack using arrays.

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

class StackOverFlowException 
{
    public:
        StackOverFlowException() 
        {
            cout << "Stack overflow" << endl;
        }
};

class StackUnderFlowException 
{
    public:
        StackUnderFlowException() 
        {
            cout << "Stack underflow" << endl;
        }
};

class ArrayStack 
{    
    private:        
        int data[MAX_SIZE];        
        int top;    
  public:        
      ArrayStack() 
      {            
          top = -1;        
    }        
    
    void Push(int element)
    {            
        if ( top >= MAX_SIZE ) 
            {            
                throw new StackOverFlowException();
            }                   
            data[++top] = element;        
    }        
            
    int Pop()
    {            
        if ( top == -1 ) 
            {            
                throw new StackUnderFlowException();            
            }            
            return data[top--];        
    }        
    
    int Top() 
    {            
        return data[top];        
    }
    
    int Size() 
    {
        return top + 1;
    }
    
    bool isEmpty() 
    {
        return ( top == -1 ) ? true : false;
    }
};

int main()
{    
    ArrayStack s; 
    try {
        if ( s.isEmpty() ) 
            {
            cout << "Stack is empty" << endl;    
            }
        // Push elements    
        s.Push(100);    
        s.Push(200);    
        // Size of stack
        cout << "Size of stack = " << s.Size() << endl;
        // Top element    
        cout << s.Top() << endl;    
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}
OUTPUT:-
Stack is empty
Size of stack = 2
200
200
100
Stack underflow
Some exception occured

EXAMPLE: Demonstrate the implementation of a simple stack using linked lists.

#include <iostream>
using namespace std;

class StackUnderFlowException 
{
    public:
        StackUnderFlowException() 
        {
            cout << "Stack underflow" << endl;
        }
};

struct Node 
{
    int data;
    Node* link;
};

class ListStack 
{
    private:                 
        Node* top;
        int count;
            
  public:        
      ListStack() 
      {            
          top = NULL;
          count = 0;        
    }        
    
    void Push(int element)
    { 
        Node* temp = new Node();
        temp->data = element;
        temp->link = top;
        top = temp;     
        count++;          
    }        
            
    int Pop()
    {            
        if ( top == NULL ) 
            {            
                throw new StackUnderFlowException();            
            }        
            int ret = top->data;    
            Node* temp = top->link;
            delete top;
            top = temp;
            count--;
            return ret;        
    }        
    
    int Top() 
    {            
        return top->data;        
    }
    
    int Size() 
    {
        return count;
    }
    
    bool isEmpty() 
    {
        return ( top == NULL ) ? true : false;
    }
};

int main()
{    
    ListStack s; 
    try {
        if ( s.isEmpty() ) 
            {
            cout << "Stack is empty" << endl;    
            }
        // Push elements    
        s.Push(100);    
        s.Push(200);    
        // Size of stack
        cout << "Size of stack = " << s.Size() << endl;
        // Top element    
        cout << s.Top() << endl;    
        // Pop element    
        cout << s.Pop() << endl;
      // Pop element    
        cout << s.Pop() << endl;
      // Pop element    
        cout << s.Pop() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:-
Stack is empty
Size of stack = 2
200
200
100
Stack underflow
Some exception occured

C++ Bit Fields

2008-06-27T09:44:00.003+05:30

What are bit-fields?

Bit fields provide a mechanism to optimize memory usage by allowing to specify the exact number of bits required to store data.
Quite useful in embedded programming like mobile phones where memory is limited.
The declaration of bit field members follow the syntax "variable name : number of bits".
Unnamed bit fields with width 0 are used for alignment of the next bit field to the field type boundary.

EXAMPLE: Demonstrate the usage of bit fields.

#include <iostream>
#include <assert>
using namespace std;

class MyTime {

 unsigned hour : 5;
 unsigned mins : 6;
 unsigned secs : 6;

public:

 void SetHour(int aHour) {
     assert ( aHour < 24 );
     hour = aHour;
 }

 void SetMins(int aMins) {
     assert ( aMins < 60 );
     mins = aMins;
 }

 void SetSecs(int aSecs) {
     assert ( aSecs < 60 );
     secs = aSecs;
 }

 void Print() {
     cout << hour << ":" << mins << ":" << secs << endl;
 }
};

int main()
{
 MyTime t;
 t.SetHour(12);
 t.SetMins(58);
 t.SetSecs(23);
 t.Print();

 cout << "Size of MyTime = " << sizeof(t) << endl;
}

OUTPUT:-
12:58:23
Size of MyTime = 4

C++ Overriding

2008-06-23T21:05:00.003+05:30

What is overriding in C++?

Redefining a base class function in the derived class to have our own implementation is referred as overriding.
Often confused with overloading which refers to using the same function name but with a different signature. However in overriding the function signature is the same.

EXAMPLE: Demonstrate the usage of overriding

#include <iostream>
using namespace std;

class Base {
    public:
        virtual void myfunc() {
            cout << "Base::myfunc .." << endl;
        }
};

class Derived : public Base {
    public:
        void myfunc() {
            cout << "Derived::myfunc .." << endl;
        }
};

void main()
{
    Derived d;
    d.myfunc();
}

OUTPUT:-
Derived::myfunc ..

C++ Template Pattern

2008-06-23T19:23:00.004+05:30

What is template design pattern?

Template pattern is a behavioral design pattern.
This has nothing to do with C++ templates as such.
Template patterns is a common form in object oriented programming. Having an abstract base class (one or more pure virtual functions) is a simple example of template design pattern.
In the template pattern, parts of program which are well defined like an algorithm are defined as a concrete method in the base class. The specifics of implementation are left to the derived classes by making these methods as abstract in the base class.
The method which implements the algorithm is also refered as template method and the class which implements this methods as the template class.

EXAMPLE: Demonstrate the usage of template design pattern

#include <iostream>
using namespace std;

// Base class
// Template class
class Account {
    public:
        // Abstract Methods
        virtual void Start() = 0;

        virtual void Allow() = 0;

        virtual void End() = 0;

        virtual int MaxLimit() = 0;

        // Template Method
        void Withdraw(int amount) {

            Start();

            int limit = MaxLimit();
            if ( amount < limit ) {
            Allow();
            }
            else {
            cout << "Not allowed" << endl;
            }

            End();
        }
};

// Derived class
class AccountNormal : public Account {
    public:
        void Start() {
            cout << "Start ..." << endl;
        }

        void Allow() {
            cout << "Allow ..." << endl;
        }

        void End() {
            cout << "End ..." << endl;
        }

        int MaxLimit() {
            return 1000;
        }
};

// Derived class
class AccountPower : public Account {
    public:
        void Start() {
            cout << "Start ..." << endl;
        }

        void Allow() {
            cout << "Allow ..." << endl;
        }

        void End() {
            cout << "End ..." << endl;
        }

        int MaxLimit() {
            return 5000;
        }
};

int main() {
    AccountPower power;
    power.Withdraw(1500);

    AccountNormal normal;
    normal.Withdraw(1500);
}

OUTPUT:-
Start ...
Allow ...
End ...

Start ...
Not allowed
End ...

C++ Copy Assignment Operator

2008-06-17T21:00:00.004+05:30

What is copy assignment operator in C++?

The copy assignment operator allows to assign objects of same class to each other by overloading '=' operator.
The compiler automatically generates this member function if is not defined explicitly.
The generated copy assignment funcion does a bit wise copy or in other words shallow copy.
If our class has dynamically allocated members then it becomes necessary to write our own implementation of copy assignment function to perform a deep copy.

EXAMPLE: Demonstrate the usage of copy assignment operator

#include <iostream>
using namespace std;

class MyClass {  
    private:      
        char* str;  
    public:      
        MyClass();
        MyClass(char* aStr);      
        MyClass& operator=(const MyClass& obj);      
        void Print();      
        ~MyClass();
};

MyClass::MyClass() {
}

MyClass::MyClass(char* aStr) {  
    cout << "In constructor ..." << endl;  
    str = strdup(aStr);
}

// Copy assignment
MyClass& MyClass::operator=(const MyClass& other) {
    cout << "In copy assignment ..." << endl;
    str = strdup(other.str);
    return *this;
}

void MyClass::Print() {  
    cout << str << endl;
}

MyClass::~MyClass() {  
    cout << "In destructor ..." << endl;  
    delete str;
}

void main()
{  
    // Create obj1
    MyClass* obj1 = new MyClass("Hello World");
    obj1->Print();

    // Assignment. obj1 to obj2
    MyClass obj2;
    obj2 = *obj1;

    // Cleanup obj1
    delete obj1;

    obj2.Print();
}

OUTPUT:-
In constructor ...
Hello World
In copy assignment ...
In destructor ...
Hello World
In destructor ...

C++ Default Arguments

2008-06-16T17:57:00.006+05:30

What are default arguments in C++?

Default argument is a value given in the function declaration. The compiler automatically inserts this if a value is not provided during the function call.
Default arguments are similar to function overloading in the sense that both features allow to use a single function name in different scenarios.
The guideline to follow default arguments vs function overloading. When the desired behavior is almost similar it is recommended to use default arguments and when the behavior is different function overloading.
Only trailing arguments can be defaulted. Once a particular arguments is made default all the following arguments should also be made default.
Default arguments are useful in cases where capability of an existing function is increased by adding a new argument. Existing function calls need not be changed for this.

EXAMPLE: Demonstrate the usage of default arguments

#include <iostream>

using namespace std;

// Function with default arguments

void myfunc(int a, bool flag = true) {

    if ( flag == true ) {

       // Do something
       cout << "Flag is true. a = " << a << endl;
    }
    else {

       // Do something
       cout << "Flag is false. a = " << a << endl;
    }
}


int main()
{
    myfunc(100);

    myfunc(200, false);

    return 0;
}


OUTPUT:-
Flag is true. a = 100
Flag is false. a = 200

C++ STL Reference

2008-06-13T07:23:00.002+05:30

Good reference to Standard Template Library:-