Category Archives: A library re-written.
Performing Arithmetic on Bitsets in C++
The bitset class template comes with basic operations for manipulating sets of bits but doesn’t provide any arithmetic or comparison operations. This is because the library can’t safely assume what kind of numerical type a programmer might expect an arbitrary set of bits to represent.The functions below treat a bitset as a representation of an unsigned integer type, and provide you with functions for adding, subtracting, multiplying, dividing, and comparing them. These functions can provide a basis for writing custom-sized integer types. I did not use the most efficient algorithms I could for below function. Instead I chose the simplest possible algorithms because they are more easily understood. A much more efficient implementation would use similar algorithms, but would operate on words rather than single bits.
The functions below provide functions that allow arithmetic and comparison of bitset class template from the header as if it represents an unsigned integer.
#include <stdexcept>
#include <bitset>
bool fullAdder(bool b1, bool b2, bool& carry)
{
bool sum = (b1 ^ b2) ^ carry;
carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
return sum;
}
bool fullSubtractor(bool b1, bool b2, bool& borrow)
{
bool diff;
if (borrow)
{
diff = !(b1 ^ b2);
borrow = !b1 || (b1 && b2);
}
else
{
diff = b1 ^ b2;
borrow = !b1 && b2;
}
return diff;
}
template<unsigned int N>
bool bitsetLtEq(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--)
{
if (x[i] && !y[i]) return false;
if (!x[i] && y[i]) return true;
}
return true;
}
template<unsigned int N>
bool bitsetLt(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--) {
if (x[i] && !y[i]) return false;
if (!x[i] && y[i]) return true;
}
return false;
}
template<unsigned int N>
bool bitsetGtEq(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--) {
if (x[i] && !y[i]) return true;
if (!x[i] && y[i]) return false;
}
return true;
}
template<unsigned int N>
bool bitsetGt(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--)
{
if (x[i] && !y[i]) return true;
if (!x[i] && y[i]) return false;
}
return false;
}
template<unsigned int N>
void bitsetAdd(std::bitset& x, const std::bitset& y)
{
bool carry = false;
for (int i = 0; i < N; i++)
{
x[i] = fullAdder(x[i], y[i], carry);
}
}
template<unsigned int N>
void bitsetSubtract(std::bitset& x, const std::bitset& y)
{
bool borrow = false;
for (int i = 0; i < N; i++)
{
if (borrow)
{
if (x[i])
{
x[i] = y[i];
borrow = y[i];
}
else
{
x[i] = !y[i];
borrow = true;
}
}
else
{
if (x[i])
{
x[i] = !y[i];
borrow = false;
}
else
{
x[i] = y[i];
borrow = y[i];
}
}
}
}
template<unsigned int N>
void bitsetMultiply(std::bitset& x, const std::bitset& y)
{
std::bitset tmp = x;
x.reset( );
// we want to minimize the number of times we shift and add
if (tmp.count( ) < y.count( ))
{
for (int i=0; i < N; i++)
if (tmp[i]) bitsetAdd(x, y << i);
}
else
{
for (int i=0; i < N; i++)
if (y[i]) bitsetAdd(x, tmp << i);
}
}
template<unsigned int N>
void bitsetDivide(std::bitset x, std::bitset y,
std::bitset<N>& q, std::bitset<N>& r)
{
if (y.none( ))
{
throw std::domain_error("division by zero undefined");
}
q.reset( );
r.reset( );
if (x.none( ))
{
return;
}
if (x == y)
{
q[0] = 1;
return;
}
r = x;
if (bitsetLt(x, y))
{
return;
}
// count significant digits in divisor and dividend
unsigned int sig_x;
for (int i=N-1; i>=0; i--)
{
sig_x = i;
if (x[i]) break;
}
unsigned int sig_y;
for (int i=N-1; i>=0; i--)
{
sig_y = i;
if (y[i]) break;
}
// align the divisor with the dividend
unsigned int n = (sig_x - sig_y);
y <<= n;
// make sure the loop executes the right number of times
n += 1;
// long division algorithm, shift, and subtract
while (n--)
{
// shift the quotient to the left
if (bitsetLtEq(y, r))
{
// add a new digit to quotient
q[n] = true;
bitsetSubtract(r, y);
}
// shift the divisor to the right
y >>= 1;
}
}
Using the bitset_arithmetic.hpp functions:
#include "bitset_arithmetic.hpp"
#include <bitset>
#include <iostream>
#include <string>
using namespace std;
int main( )
{
bitset<10> bits1(string("100010001"));
bitset<10> bits2(string("000000011"));
bitsetAdd(bits1, bits2);
cout << bits1.to_string<char, char_traits<char="">, allocator >( ) << endl;
}
The program produces the following output:
0100010100
Related articles
- Binary Search Tree template Class (BST) (alikhuram.wordpress.com)
- More algorithms (aandrew99.wordpress.com)
- How I can improve my algorithmic coding skills? (thejatinbatra.wordpress.com)
Binary Search Tree
The mathematical definition of a binary tree is
“A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub-trees”. Each element of a binary tree is called a node of the tree.
A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. (Photo credit: Wikipedia)
There are nine nodes in the above figure of the binary tree. The node A is at the top of the tree. There are two lines from the node A to left and right sides towards node B and C respectively.
The definition of tree is of recursive nature. This is due to the fact that We have seen that which definition has been applied to the tree having node A as root, is applied to its subtrees one level downward. Similarly as long as we go downward in the tree the same definition is used at each level of the tree. And we see three parts i.e. root, left subtree and right subtree at each level.
Now if we carry out the same process on the right subtree of root node A, the node C will become the root of this right subtree of A. The left subtree of this root node C is empty. The right subtree of C is made up of three nodes F, H and I.
I have discussed that the node on the top is said root of the tree. If we consider the relationship of these nodes, A is the parent node with B and C as the left and right descendants respectively. C is the right descendant of A. Afterwards, We look at the node B where the node D is its left descendant and E is its right descendant. I can use the words descendant and child interchangeably. Now look at the nodes D, G, H and I. These nodes are said leaf nodes as there is no descendant of these nodes. I am just introducing the terminology here. In the algorithms, I can use the words root or parent, child or descendant. So the names never matter.
Strictly Binary Tree
There is a version of the binary tree, called strictly binary tree. A binary tree is said to be a strictly binary tree if every non-leaf node in a binary tree has non-empty left and right subtrees.
20+ 21+ 22 + ……… + 2d = 6d j=0 2j = 2d+1 – 1
Thus according to this summation, the total number of nodes in a complete binary tree of depth d will be 2d+1 – 1. Thus if there is a complete binary tree of depth 4, the total number of nodes in it will be calculated by putting the value of d equal to 4. It will be calculated as under.
24+1 – 1 = 25 – 1 = 32 – 1 = 31
Thus the total number of nodes in the complete binary tree of depth 4 is 31.
We know that the total number of nodes (leaf and non-leaf) of a complete binary tree of depth d is equal to 2d+1 – 1. In a complete binary tree, all the leaf nodes are at the depth level d. So the number of nodes at level d will be 2d . These are the leaf nodes. Thus the difference of total number of nodes and number of leaf nodes will give us the number of non-leaf (inner) nodes. It will be (2d+1 – 1) – 2d i.e. 2d – 1. Thus we conclude that in a complete binary tree, there are 2d leaf nodes and 2d – 1 non-leaf (inner) nodes.
Level of a Complete Binary Tree
We can conclude some more results from the above mathematical expression. We can find the depth of a complete binary tree if we know the total number of nodes. If we have a complete binary tree with n total nodes, then by the equation of the total number of nodes I can write
Total number of nodes = 2d+1 – 1 = n
To find the value of d, I solve the above equation as under
2d+1 – 1 = n
2d+1 = n + 1
d + 1 = log2 (n + 1)
d = log2 (n + 1) – 1
After having n total nodes, we can find the depth d of the tree by the above equation. Suppose we have 1000,000 nodes. It means that the value of n is 1000,000, reflecting a depth i.e. d of the tree will be log2 (1000000 + 1) – 1, which evaluates to 20. So the depth of the tree will be 20. In other words, the tree will be 20 levels deep.
Cost of Search
In the discussion on binary tree, I talked about the level and number of nodes of a binary tree. It was witnessed that if we have a complete binary tree with n numbers of nodes, the depth d of the tree can be found by the following equation:
d = log2 (n + 1) – 1
Suppose I have a complete binary tree in which there are 1000,000 nodes, then its depth d will be calculated in the following fashion.
d = log2 (1000000 + 1) – 1 = log2 (1000001) – 1= 20
The statement shows that if there are 1000,000 unique numbers (nodes) stored in a complete binary tree, the tree will have 20 levels. Now if I want to find a number x in this tree (in other words, the number is not in the tree), I have to make maximum 20 comparisons i.e. one comparison at each level. Now I can understand the benefit of tree as compared to the linked list. If I have a linked list of 1000,000 numbers, then there may be 1000,000 comparisons (supposing the number is not there) to find a number x in the list.
Thus in a tree, the search is very fast as compared to the linked list. If the tree is complete binary or near-to-complete, searching through 1000,000 numbers will require a maximum of 20 comparisons or in general, approximately log2(n). Whereas in a linked list, the comparisons required could be a maximum of n.
Tree with the linked structure, is not a difficult data structure. I have used it to allocate memory, link and set pointers to it. It is not much difficult process. In a tree, I link the nodes in such a way that it does not remain a linear structure. If instead of 1000,000, I have 1 million or 10 million or say, 1 billion numbers and want to build a complete binary tree of these numbers, the depth (number of levels) of the tree will be log2 of these numbers.The log2 of these numbers will be a small number, suppose 25, 30 or 40.
Thus I see that the number of level does not increase in such a ratio as the number of nodes increase. So I can search a number x in a complete binary tree of 1 billion nodes only in 30-40 comparisons. As the linked list of such a large number grows large, the search of a number in such a case will also get time consuming process. The usage of memory space does not cause any effect in the linked list and tree data structures. I use the memory dynamically in both structures.
However, time is a major factor. Suppose one comparison takes one micro second, then one billion seconds are required to find a number from a linked list (I are supposing the worst case of search where traversing of the whole list may be needed). This time will be in hours. On the other hand, in case of building a complete binary tree of these one billion numbers, I have to make 30-40 comparisons (as the levels of the tree will be 30-40), taking only 30-40 microseconds. I can clearly see the difference between hours and microseconds. Thus it is better to prefer the process of building a tree of the data to storing it in a linked list to make the search process faster.
Binary Search Tree
While discussing the search procedure, the tree for search was built in a specific order. The order was such that on the addition of a number in the tree, we compare it with a node. If it is less than this, it can be added to the left sub-tree of the node. Otherwise, it will be added on the right sub-tree.
This way, the tree built by us has numbers less than the root in the left sub-tree and the numbers greater than the root in the right sub-tree. A binary tree with such a property that items in the left sub-tree are smaller than the root and items in the right sub-tree are larger than the root is called a binary search tree (BST).
The searching and sorting operations are very common in computer science. In most of the cases, I sort the data before a search operation. The building process of a binary search tree is actually a process of storing the data in a sorted form. The BST has many variations, which will be discussed later. The BST and its variations play an important role in searching algorithms. As data in a BST is in an order, it may also be termed as ordered tree.
Traversing a Binary Tree
Now let’s discuss the ways to print the numbers present in a BST. In a linked list, the printing of stored values is easy. It is due to the fact that I know where from, a programmer needs to start and where the next element is. Equally is true about printing of the elements in an array. I execute a for loop starting from the first element (i.e. index 0) to the last element of the array. Now let’s see how we can traverse a tree to print (display) the numbers (or any data items) of the tree.
Here we see that the root node has the number 14. The left sub-tree has only one node i.e. number 4. Similarly the right sub-tree consists of a single node with the number 15. If we apply the permutations combinations on these three nodes to print them, there may be the following six possibilities.
1: (4, 14, 15)
2: (14, 4, 15)
3: (15, 4, 14)
4: (4, 15, 14)
5: (14, 15, 4)
6: (15, 14, 4)
Look at these six combinations of printing the nodes of the tree. In the first combination, the order of printing the nodes is 4-14-15. It means that left subtree- root-right subtree. In the second combination the order is root-left subtree-right subtree. In the third combination, the order of printing the nodes is right subtree-root- left subtree. The fourth combination has left subtree-right subtree-root. The fifth combination has the order root-rigth subtree- left subtree.
Finally the sixth combination has the order of printing the nodes right subtree-root-left subtree. These six possibilities are for the three nodes only. If we have a tree having a large number of nodes, then there may increase number of permutations for printing the nodes.
Let’s see the general procedure of traversing a binary tree. We know by definition that a binary tree consists of three sets i.e. root, left subtree and right subtree.
1: (L, N, R)
2: (N, L, R)
3: (R, L, N)
4: (L, R, N)
5: (N, R, L)
6: (R, N, L)
In these permutations, the left and right subtree are not single nodes. These may consist of several nodes. Thus where I see L in the permutations, it means traversing the left subtree. Similarly R means traversing the right subtree. In the previous tree of three nodes, these left and right subtrees are of single nodes. However, they can consist of any number of nodes. We select the following three permutations from the above six. The first of these three is (N, L, R), also called as preorder traversal. The second permutation is (L, N, R) which I called inorder traversal. Finally the third permutation, also termed as postorder traversal is (L, R, N).
Please follow below link to see complete code of a binary search tree template class.
Related articles
- Binary Search Tree template Class (BST) (alikhuram.wordpress.com)
Binary Search Tree template Class (BST)
Let’s see the code of the binary search tree (BST). This is a continuation of another article where I have explained the BST in detail. Please review that article as well. (link is below) We put the interface in the .h file. We also have the state variable in addition to the public and private methods of the class in it. In the public methods, the user of the class calls with their objects.
Here is the code of the program. BinarySearchTree.h file.
/* This file contains the declaration of binary node and the binary search tree */
#ifndef BINARY_SEARCH_TREE_H_
#define BINARY_SEARCH_TREE_H_
#include <iostream.h> // For NULL
// Binary node and forward declaration
template <class EType> class BinarySearchTree;
template <class EType> class BinaryNode
{
EType element; BinaryNode *left; BinaryNode *right;
BinaryNode( const EType & theElement, BinaryNode *lt, BinaryNode *rt ) : element( theElement ), left( lt ), right( rt ) { }
friend class BinarySearchTree<EType>;
};
// BinarySearchTree class
CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// EType find( x ) --> Return item that matches x
// EType findMin( ) --> Return smallest item
// EType findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
template <class EType> class BinarySearchTree
{
public:
BinarySearchTree( const EType & notFound ); BinarySearchTree( const BinarySearchTree & rhs );
~BinarySearchTree( );
const EType & findMin( ) const;
const EType & findMax( ) const;
const EType & find( const EType & x ) const;
bool isEmpty( ) const;
void printTree( ) const;
void makeEmpty( );
void insert( const EType & x );
void remove( const EType & x );
const BinarySearchTree & operator=( const BinarySearchTree & rhs );
private:
BinaryNode<EType> *root;
const EType ITEM_NOT_FOUND;
const EType & elementAt( BinaryNode<EType> *t ) const;
void insert( const EType & x, BinaryNode<EType> * & t ) const;
void remove( const EType & x, BinaryNode<EType> * & t ) const;
BinaryNode<EType> * findMin( BinaryNode<EType> *t ) const;
BinaryNode<EType> * findMax( BinaryNode<EType> *t ) const;
BinaryNode<EType> * find( const EType & x, BinaryNode<EType> *t ) const;
void makeEmpty( BinaryNode<EType> * & t ) const;
void printTree( BinaryNode<EType> *t ) const; BinaryNode<EType> * clone( BinaryNode<EType> *t ) const;
};
#include "BinarySearchTree.cpp"
#endif
/*BinarySearchTree.cpp file.*/
/* This file contains the implementation of the binary search tree */
#include <iostream.h>
#include "BinarySearchTree.h"
/**
* Construct the tree.
*/
template <class EType> BinarySearchTree<EType>::BinarySearchTree(const EType & notFound) : ITEM_NOT_FOUND( notFound), root( NULL )
{
}
/**
* Copy constructor.
*/
template<classEType>BinarySearchTree<EType>::BinarySearchTree(const BinarySearchTree<EType> & rhs )
:root( NULL ), ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND)
{
*this = rhs;
}
/**
* Destructor for the tree.
*/
template<classEType>BinarySearchTree<EType>::~BinarySearchTree ()
{
makeEmpty( );
}
/**
* Insert x into the tree; duplicates are ignored.
*/
template <class EType> void BinarySearchTree<EType>::insert( const EType & x )
{
insert( x, root );
}
/**
* Remove x from the tree. Nothing is done if x is not found.
*/
template <class EType> void BinarySearchTree<EType>::remove( const EType & x )
{
remove( x, root );
}
/**
* Find the smallest item in the tree.
* Return smallest item or ITEM_NOT_FOUND if empty.
*/
template <class EType> const EType & BinarySearchTree<EType>::findMin() const
{
return elementAt( findMin( root ) );
}
/**
* Find the largest item in the tree.
* Return the largest item of ITEM_NOT_FOUND if empty.
*/
template <class EType> const EType & BinarySearchTree<EType>::findMax() const
{
return elementAt( findMax( root ) );
}
/**
* Find item x in the tree.
* Return the matching item or ITEM_NOT_FOUND if not found.
*/
template <class EType>const EType & BinarySearchTree<EType>::find( const EType & x ) const
{
return elementAt( find( x, root ) );
}
/**
* Make the tree logically empty.
*/
template <class EType> void BinarySearchTree<EType>::makeEmpty()
{
makeEmpty( root );
}
/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
template <class EType> bool BinarySearchTree<EType>::isEmpty( ) const
{
return root == NULL;
}
/**
* Print the tree contents in sorted order.
*/
template <class EType> void BinarySearchTree<EType>::printTree() const
{
if( isEmpty( ) )
cout << "Empty tree" << endl;
else
printTree( root );
}
/**
* Deep copy.
*/
template <class EType> const BinarySearchTree<EType> & BinarySearchTree<EType>::operator=( const BinarySearchTree<EType> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}
/**
* Internal method to get element field in node t.
* Return the element field or ITEM_NOT_FOUND if t is NULL.
*/
template <class EType> const EType & BinarySearchTree<EType>::elementAt(BinaryNode<EType>*t) const
{
if( t == NULL )
return ITEM_NOT_FOUND;
else
return t->element;
}
/**
* Internal method to insert into a subtree.
* x is the item to insert.
* t is the node that roots the tree.
* Set the new root.
*/
template <class EType> void BinarySearchTree<EType>::insert( const EType & x, BinaryNode<EType> * & t ) const
{
if( t == NULL )
t = new BinaryNode<EType>( x, NULL, NULL );
else if( x < t->element )
insert( x, t->left ); else if( t->element < x ) insert( x, t->right );
else
; // Duplicate; do nothing
}
/**
* Internal method to remove from a subtree.
* x is the item to remove.
* t is the node that roots the tree.
* Set the new root.
*/
template <class EType> void BinarySearchTree<EType>::remove(const EType & x, BinaryNode<EType>
* & t ) const
{
if( t == NULL )
return; // Item not found; do nothing
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) // Two children
{
t->element = findMin( t->right )->element;
remove( t->element, t->right );
}
else
{
BinaryNode<EType> *nodeToDelete = t;
t = ( t->left!= NULL ) ? t->left : t->right;
delete nodeToDelete;
}
}
/**
* Internal method to find the smallest item in a subtree t.
* Return node containing the smallest item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::findMin( BinaryNode<EType>*t) const
{
if( t == NULL )
return NULL;
if( t->left == NULL )
return t;
return findMin( t->left );
}
/**
* Internal method to find the largest item in a subtree t.
* Return node containing the largest item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::findMax( BinaryNode<EType> *t ) const
{
if( t != NULL )
while( t->right != NULL )
{
t = t->right;
}
return t;
}
/**
* Internal method to find an item in a subtree.
* x is item to search for.
* t is the node that roots the tree.
* Return node containing the matched item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::
find( const EType & x, BinaryNode<EType> *t ) const
{
if( t == NULL )
return NULL;
else if( x < t->element )
return find( x, t->left );
else if( t->element < x )
return find( x, t->right );
else
return t; // Match
}
/****** NONRECURSIVE VERSION*************************
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::find( const EType & x, BinaryNode<EType> *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return t; // Match
return NULL; // No match
}
*****************************************************/
/**
* Internal method to make subtree empty.
*/
template <class EType> void BinarySearchTree<EType>::makeEmpty( BinaryNode<EType> * & t ) const
{
if( t != NULL )
{
makeEmpty( t->left ); makeEmpty( t->right ); delete t;
}
t = NULL;
}
/**
* Internal method to print a subtree rooted at t in sorted order.
*/
template <class EType> void BinarySearchTree<EType>::printTree( BinaryNode<EType> *t ) const
{
if( t != NULL )
{
printTree( t->left );
cout << t->element << endl;
printTree( t->right );
}
}
/**
* Internal method to clone subtree.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::clone( BinaryNode<EType> * t ) const
{
if( t == NULL )
return NULL;
else
return new BinaryNode<EType>( t->element, clone( t->left ), clone( t->right ) );
}
Smart Array (Linked List template implementation using C++)
As we have discussed about the Smart Array (Linked List) in our previous post and showed the Node class as well as the header file for the linked list. Below is the actual implementation of Linked List template in C++.
Any questions welcomed!
#include “list.h”
template <class T>
// in constructor we add a head node in the class as well as the cursor which we called current node.
// head node and current node set to null as there are no other nodes to point to.
List<T>::List()
{
headNode = new Node<T>();
headNode->setNext(NULL);
headNode->setLast(NULL);
currentNode = NULL;
size = 0;
}
//in destructor we do memory management as we did made nodes dynamically.
template <class T>
List<T>::~List ()
{
while (size != 0)
{
remove_node();
}
delete currentNode;
delete headNode;
}
// this function simply call remove_node function until all nodes are deleted.
template <class T>
bool List<T>::clear_list ()
{
while (size != 0)
{
remove_node ();
}
delete currentNode;
}
// this is the main addition of a node function.
template <class T>
void List<T>::add (T addObject)
{
Node<T> *newNode = new Node<T>();
newNode->set(addObject);
size ++;
if(currentNode != NULL) // in case we already have other nodes in the list
{
lastNode = currentNode;
newNode->setNext(currentNode->getNext()); // pointer will be adjusted for the new node.
if (newNode->getNext()!= NULL) // if the node is not at the end of the list.
{
currentNode = currentNode->getNext();
currentNode->setLast(newNode);
}
newNode->setLast(lastNode);
currentNode = newNode;
lastNode->setNext(newNode);
newNode->setIndex(size);
}
else // if this the very first node to be added in the list. this else part will be executed once in the life span of list.
{
newNode->setNext(NULL);
headNode->setNext(newNode);
newNode->setLast(headNode);
currentNode = newNode;
newNode->setIndex(size);
}
}
// this function return the current node value.
template <class T>
T List<T>::get()
{
if (currentNode != NULL)
{
return currentNode->get();
}if (currentNode == headNode) // if cursor is pointing towards head node. we cannot return anything as head node doesn’t
// have any value.
{
return false;
}
}
// move the cursor to next node only if the cursor is not reached on the last node.
template <class T>
bool List<T>::move_next()
{
if (currentNode->getNext() == NULL) return false ;
currentNode = currentNode->getNext();
}
//move the cursor to backwards only if the cursor is not reached till head node.
template <class T>
bool List<T>::move_back ()
{
if (currentNode->getLast() == headNode) return false;
currentNode = currentNode->getLast();
}
//move the cursor to very first node after head node, if there are any nodes in the list.
template <class T>
bool List<T>::move_first()
{
if (headNode->getNext()!=NULL)
currentNode = headNode->getNext();
}
//move the cursor to last node.
template <class T>
bool List<T>::move_last()
{
while (currentNode->getNext() != NULL)
{
currentNode= currentNode->getNext();
}
return currentNode;
}
//delete current node where cursor pointing to.
template <class T>
bool List<T>::remove_node()
{
Node<T> *temp = currentNode;
if (currentNode != NULL) // if cursor is actually pointing to a valid node
{
if (currentNode->getLast() == headNode) // if cursor is on the very first node after head node.
{
currentNode = headNode;
currentNode->setNext(NULL);
currentNode->setLast(NULL);
delete temp;
size–;
return true;
}else if (currentNode->getNext() == NULL) //if cursor is pointing to the very last node of the list.
{
move_back();
currentNode->setNext(NULL);
delete temp;
size–;
return true;
}else // if the cursor is not at the start or end of the list but somewhere in the middle.
{
move_back();
currentNode->setNext(temp->getNext());
move_next();
currentNode->setLast(temp->getLast());
delete temp;
size–;
return true;
}
}
}
//move the cursor to next node.
template <class T>
Node<T> List<T>::operator++()
{
move_next();
return *currentNode;
}
//move theh cursor to last node.
template <class T>
Node<T> List<T>::operator–()
{
move_back();
return *currentNode;
}
// add one node and assign rvalue to it. the name of list instance is used as lvalue.
template <class T>
Node<T> List<T>::operator=(T i)
{
add(i);
}
//cout object can be used to display list values.
template <class T>
std::ostream& operator << (std::ostream& leftOpr, List<T>& rhs)
{
leftOpr << rhs.get();
return leftOpr;
}
//cin can be used to add one node and assign it a value directing getting input from user.
template <class T>
std::istream& operator >> (std::istream& leftOpr, List<T>& rhs)
{
int i = 0;
leftOpr >> i;
rhs.add(i);
return leftOpr;
}
//return size of the list. number of nodes in the list.
template <class T>
int List<T>::get_size()
{
return size;
}
//return node value by index.
template <class T>
Node<T> List<T>::return_node(int i)
{
move_first();
while (currentNode->getNext() != NULL)
{
if (currentNode->getIndex() == i)
return *currentNode;
else
move_next();
}
}
//brackets can be used to access list elements by giving index as used in simple array.
template <class T>
Node<T> List<T>::operator[](int i)
{
return_node(i);
}
Related articles
- Data Structures implemantation in C++ (alikhuram.wordpress.com)
- Intersecting Linked Lists Faster (twistedoakstudios.com)
- doublelinkedBag (daniweb.com)
Data Structures implemantation in C++
I have implemented data structures in C++ with some tweaks. These are custom made for some specific needs which I have. These might be interesting for anyone who is interested in data structures and learn how to implement them. There can be many methods which I can think of and can provide with these data structures but as I have said earlier, I wrote these for some specific needs. However, if someone is interested to know or want some added functionality, I can help!
Any questions are welcomed!
/* The Node class
A node is basic building block of many user define data structures.
Below node class is used to implement double linked list, stack and Queue data structures.
As this node class will become a part of a larger data structures, it doesn’t contain utility functions and operators.
this is a smart node, which also keeps track index of itself. as well as the address of last node
and the next node.
the class is implemented as template so can be instantiated with any data type.
Author: Khuram Ali
*/
template <class T>
class Node
{
public:
Node<T> (){object;} //a node constructor can be called with a value which needs to be stored.
T get() { return object; }; //getter function for out putting value stored in a node.
void set(T object) { this->object = object; }; //setting value of a node.
Node<T> *getNext() { return nextNode; }; // return a pointer to next node.
Node<T> *getLast(){return lastNode;}; // return a pointer to last node.
void setNext(Node<T> *nextNode) { this->nextNode = nextNode; }; // set a pointer to next node.
void setLast (Node<T> *lastNode) {this->lastNode = lastNode;};//set a pointer to last node.
void setIndex (int num) {this->index = num;}; // set index of node.
int getIndex () {return index;}; // return the index of node.
private:
T object;
int index = 0;
Node<T> *nextNode;
Node<T> *lastNode;
};
ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
/* Smart Array header file:
this is a linked list implementation and I called it a smart array as you can do all, what you used to do with arrays,
with the flexibility of linked list. it is a double linked list so you can move forward and back easily. you can use
arithmetic operators as well as [] to access any node by its index. you can use iostream objects to print the elements on
the screen as you can do with normal array. though you can access any index of the list but if the list is big enough there is
a give n take on efficiency with ease of use. accessing a list element through index in a very large array is less efficient, if
the speed is what you want.
it is a template class so you can create a list of any data type.
Author Khuram Ali
*/
#include <iostream>
#include “node.cpp”
template <class T>
class List
{
public:
List();
~List();
void add (T); // function used to add an element (node) in the list.
T get(); //return current node value.
int get_size(); // return size of the list (number of nodes in a list)
bool move_next(); // move to next node and can go forward.
bool move_back (); // move to last node and can go backward.
bool move_first (); // move the cursor to first node.
bool move_last (); // move the cursor to last node.
bool remove_node (); // delete current node.
bool clear_list (); // delete all nodes in the list.
Node<T> return_node (int); // return node value by index.
Node<T> operator ++(); // move the cursor to next node.
Node<T> operator –(); // move the cursor to last node.
Node operator = (T); // add a new node and assign the rvalue to it.
Node<T> operator [] (int); // return node value by index.
template <class W>
friend std::ostream& operator << (std::ostream&, List<W>&); // printing node value on screen using cout.
template <class S>
friend std::istream& operator >> (std::istream&, List<S>&); // getting value from user from cin and add a new node
// with that value.
private:
int size;
Node<T> *headNode;
Node<T> *currentNode;
Node<T> *lastNode;
};
#endif // LIST_H_INCLUDED
/** implementation of List data structure will be added shortly.
Related articles
- Top 15 Data Structures and Algorithm Interview Questions for Java programmer – Answers (javarevisited.blogspot.com)
- Data Warehouse Dilemma | Solving Real Problems | Domo | Blog (domo.com)
- basic applications of data structure (stackoverflow.com)
- Help with implementing a linked list as an array in JAVA (daniweb.com)
- Why do we need pointers/references? (mortoray.com)
The Date Class
I am using a low level of complexity to show the working of general C++ classes, operator overloading and data hiding/encapsulation concepts. Below is the header file of Date Class. complete implementation will follow. However, Complete code of Date class can be used freely.
Questions/comments welcomed..!
Header File: date.h
#ifndef DATE_H
#define DATE_H
#include <iostream>
class Date
{
private:
short day;
short month;
short year;
short daysOfMonth(Date d); /**returns the no of days in a month*/
static const short daysInMonth[]; /** array containing the 12 month’s days*/
bool leapYear (short); /** tells the year is leap year or not*/
public:
/**constructor with default arguments*/
Date(short d=1, short m = 1, short y = 1900);
void display (); /** Display the date on the screen*/
void setDate (short, short, short); /** set the date with given arguments*/
Date operator ++(); /**pre increment operator used as ++date1*/
Date operator +(short); /**plus operator used as date1 + 5 */
Date operator –(); /**pre decrement operator used as –date1 */
Date operator -(short); /**decrement operator used as date1 – 5 */
short operator – (Date); /** return number of days between two dates */
Date operator +=(short); /** add short in left hand operand and return the same. */
Date operator -=(short); /** decrement short in left hand operand and return the same. */
short operator -=(Date); /** decrement Date object in left hand operand and return the same. */
friend Date operator – (short, Date); /**decrement operator used as 5 – date1 */
/**logical comarison operators*/
bool operator < (Date);
bool operator > (Date);
bool operator <=(Date);
bool operator >= (Date);
bool operator == (Date);
bool operator != (Date);
/** Stream insertion operators to get input and output with simple, cin and cout. */
friend std::ostream& operator << (std::ostream&, Date&);
friend std::istream& operator >> (std::istream&, Date&);
};
#endif // DATE_H
Khuram Ali 