Adventures of a Software Engineer

Month: July 2009

  • HashTable implemented using quadratic probing for collision resolution

    Using quadratic probing for collision resolution

    #define ERROR_TABLE_FULL       -1
#define ERROR_RECORD_NOT_FOUND -1
#define ERROR_DUPLICATE_RECORD -1

class HashTable{
public:
	HashTable(int table_size);
	int insert(const string &record);
	int retrieve(const string &record);
private:
	int hash(const string &record);
	int hash_size;
	int record_count;
	string* table;
};

/**
 * Constructor accepting table_size
 */
HashTable::HashTable(int table_size){
	hash_size = table_size;
	table = new string[hash_size];
	record_count = 0;
}
/**
 * Hash function calculated using
 * product p of all the characters of the key
 * and then returns the index where index=s%hash_size
 */
int HashTable::hash(const string &key) {
	int value = 1;
	for (int position = 0; position < max_key_length; position++){
		if(key[position] == 0){
			break;
		}
		value *= key[position];
	}
	value %= hash_size;
	if (value < 0){
		value += hash_size;
	}
	return value;
}
/**
 * Insert new record
 * Collision function uses h+i^2
 *
 */
int HashTable::insert(const string &record){
	if(record_count == hash_size){
		return ERROR_TABLE_FULL;
	}

	int hash_key = hash(record);
	int increment = 1;

	int probe_counter=0;
	int hash_mid=(hash_size+1)/2;

	while(1){
		//Check for overflow
		if(probe_counter > hash_mid){
			return ERROR_RECORD_NOT_FOUND;
		}
		string tmp = table[hash_key];
		//Empty slot
		if(tmp.empty()){
			break;
		}//Position already taken, duplicate keys are not allowed
		else if(tmp.compare(record) == 0) {
			return ERROR_DUPLICATE_RECORD;
		}
		else{
			//Handles collision using h+i^2
			hash_key = (hash_key+increment) % hash_size;
			increment+=2;
			probe_counter++;
		}
	}
	table[hash_key] = record;
	record_count++;
	return hash_key;

}
/**
 * Retrieve record index
 */
int HashTable::retrieve(const string &record){
	int hash_key = hash(record);
	int increment = 1;

	int probe_counter=0;
	int hash_mid=(hash_size+1)/2;

	while(1){
		//Overflow encountered if the probe is bigger than hash_size/2
		if(probe_counter > hash_mid){
			return ERROR_RECORD_NOT_FOUND;
		}
		string tmp = table[hash_key];
		//Record empty for the key
		if(tmp.empty()) {
			break;
		}
		else if(tmp.compare(record) == 0){
			return hash_key;
		}
		else{
			hash_key = (hash_key+increment) % hash_size;
			increment+=2;
			probe_counter++;
		}
	}
	return ERROR_RECORD_NOT_FOUND;
}

  • HashTable implemented using linear probing for collision resolution

    Using linear probing for collision resolution in hashtable

    
#define ERROR_TABLE_FULL       -1
#define ERROR_RECORD_NOT_FOUND -1
#define ERROR_DUPLICATE_RECORD -1

class HashTable{
public:
	HashTable(int table_size);
	int insert(const string &record);
	int retrieve(const string &record);

private:
	int hash(const string &record);
	int hash_size;
	int record_count;
	string* table;
};

/**
 * Constructor accepting table_size
 */
HashTable::HashTable(int table_size){
	hash_size = table_size;
	table = new string[hash_size];
	record_count = 0;
}

/**
 * Hash function calculated using
 * product p of all the characters of the key
 * and then returns the index where index=s%hash_size
 */
int HashTable::hash(const string &record) {
	int value = 1;
	for (int position = 0; position < max_key_length; position++){
		if(record[position] == 0){
			break;
		}
		value *= record[position];
	}
	value %= hash_size;
	if (value < 0){
		value += hash_size;
	}
	return value;
}

/**
 * Insert new record into out table, making sure that the table is not full
 */
int HashTable::insert(const string &record){
	//Check if HashTable is full if it is then return overflow
	if(record_count == hash_size){
		return ERROR_TABLE_FULL;
	}
	int hash_key = hash(record);
	while(1){
		string tmp = table[hash_key];
		//Check if table bucket is empty
		if(tmp.empty()) {
			break;
		}//Position already taken, duplicate keys are not allowed 0 = equal
		else if(tmp.compare(record) == 0) {
			return ERROR_DUPLICATE_RECORD;
		}
		//Collision detected multiple records mapped to same location
		//Try next bucket
		else {
			hash_key = (hash_key+1) % hash_size;
		}
	}
	table[hash_key] = record;
	record_count++;

	return hash_key;
}

/**
 * Retrieve record index
 */
int HashTable::retrieve(const string &record){
	int hash_key = hash(record);
	while(1){
		string tmp = table[hash_key];
		//Record empty for the key
		if(tmp.empty()){
			break;
		}//if entry found return index
		else if(tmp.compare(record) == 0) {
			return hash_key;
		}
		else { //Resolving collision using linear probing
			hash_key = (hash_key+1) % hash_size;
		}
	}

	//No record Found
	return ERROR_RECORD_NOT_FOUND;
}

  • Quicksort implementation using Linked List

    About QuickSort

    Wikipedia QuickSort definition.

    General idea revolves around partitioning a list where values less than pivot go into left list while greater than go into right list.
    Pivot here is the first item of the passed in list. We apply this recursively to the sublists them merge left+pivot+right.

    CPP Code

    First of all not a cpp developer so if you can improve this them post a comment with suggestions.

    
template 
Node * List::quick_sort_recursive(Node* list)
{
	//Base case : list  is NULL
	if(list ==  NULL){
		return NULL;
	}

	//We choose first entry in the list as the pivot node
	Node * pivotNode = new Node();
	pivotNode->entry=list->entry;
	Record pivot = pivotNode->entry;

	Node *tmp=list->next;
	Node *leftHead=NULL;
	Node *rightHead=NULL;

	Node *leftTail=NULL;
	Node *rightTail=NULL;

	//Partition the list into left/right sublists
	while(tmp != NULL){
		Node *entryNode=new Node();
		entryNode->entry = tmp->entry;
		entryNode->next = NULL;
		if(tmp->entry < pivot){
			if(leftTail == NULL){
				leftTail = entryNode;
				leftHead=entryNode;
			}else{
				leftTail->next=entryNode;
				leftTail=leftTail->next;
			}
		}
		else{
			if(rightTail == NULL){
				rightTail = entryNode;
				rightHead=entryNode;
			}else{
				rightTail->next=entryNode;
				rightTail=rightTail->next;
			}
		}
		tmp = tmp->next;
	}

	//Recursively subdivide the left / right list
	leftHead  = quick_sort_recursive(leftHead);
	rightHead = quick_sort_recursive(rightHead);

	//Combine left+pivot+right
	Node * mergedHead=NULL;
	Node * mergedTail=NULL;

	Node *tmpNode=leftHead;
	while(tmpNode){
		Node *new_node=new Node();
		new_node->entry=tmpNode->entry;
		if(mergedTail == NULL){
			mergedTail = new_node;
			mergedHead= new_node;
		}else{
			mergedTail->next= new_node;
			mergedTail=mergedTail->next;
		}
		tmpNode=tmpNode->next;
	}
	//Pivot point
	if(mergedTail == NULL){
		mergedTail = pivotNode;
		mergedHead = pivotNode;
	}else{
		mergedTail->next=pivotNode;
		mergedTail=mergedTail->next;
	}
	//Right sublist
	tmpNode=rightHead;
	while(tmpNode){
		Node *new_node=new Node();
		new_node->entry=tmpNode->entry;
		mergedTail->next=new_node;
		mergedTail=mergedTail->next;
		tmpNode=tmpNode->next;
	}

	return mergedHead;
}



template 
struct Node {
//  data members
   Node_entry entry;
   Node *next;
//  constructors
   Node();
   Node(Node_entry, Node *link = NULL);
};

  • Android Daily Deals Agent – ImpulseShopper

    Update : Beta released

    First beta have been unlished on the Android Marketplace. So far so good, some one reported that the program crashes(unknown cause)

    Overview

    This is idea for my Daily deals agent that will monitor certain sites for daily deals.

    Current sites to consider

    • Woot.com – woot | shirt | wine | sellout
    • 1saleaday.com – wireless, watches

    Simple yet powerful enough to help me keep tabs on sweet deals.

    Screenshots

    [nggallery id=7]