Codes for Exam 2 from Hash Maps and BST Jokes Labs

void hashMap::addKeyandValue(string k, string v)

int index = getIndex(k);
if (map[index] == NULL) {
    insertNewKeyandValue(k,v,index);
} else if (map[index]->key == k) {
    map[index]->addValue(v);
} else {
    int newIndex = dealWithCollisions(k,index);
    if (newIndex == -1) {
       cout << "Unable to fix collision for key: " << k << endl;
       return;
    }
    if (map[newIndex] == NULL) {
       insertNewKeyandValue(k, v, newIndex);
    }else{
       map[newIndex]->addValue(v);
    }
}

int hashMap::getIndex(string k)

if (whichHashFn == 1) {
    return hashFn1(k);
} else if (whichHashFn == 2) {
    return hashFn2(k);
} else {
    return hashFn3(k);
}

int hashMap::dealWithCollisions(string k, int i)

if (whichCollisionFn == 1) {
    return collFn1(k,i);
} else if (whichCollisionFn == 2) {
    return collFn2(k,i);
} else {
    return collFn3(k,i);
}

findKeyIndex(string k)

int index = getIndex(k);
	int startIndex = index;
	int attempts = 0;
	while (attempts < mapSize) {
		if (map[index] != NULL && map[index]->key == k) {
			return index;
		}
		index = dealWithCollisions(k,index);
		if (index == -1 || index == startIndex) {
			break;
		}
		attempts++;
	}
	return -1;

int hashMap::collFn1(string k, int i) 

int ct = 0;
while (ct < mapSize) {
    i = (i + 1)%mapSize;
    if (map[i] == NULL || map[i]->key == k) {
       collisionsCt += ct;
       return i;
    }
    ct ++;
}
if (ct == mapSize) {cout <<"ERROR" << endl; return -1;}
return i;

int hashMap::collFn2(string k,  int i)

int ct = 1;
while (ct < mapSize) {
    int newIndex = (i+ct*ct)%mapSize;
    if (map[newIndex]==NULL || map[newIndex]->key == k) {
       collisionsCt += ct;
       return newIndex;
    }
    ct ++;
}
return -1;

int hashMap::collFn3(string k, int i)

int step = 3 - (hashFn1(k) % 3);
int ct = 0;
while (ct < mapSize) {
    int newIndex = (i + ct * step) % mapSize;
    if (map[newIndex] == NULL || map[newIndex]->key == k) {
       collisionsCt += ct;
       return newIndex;
    }
    ct++;
}
return -1;

void hashMap::insertNewKeyandValue(string k, string v, int ind)

map[ind] = new hNode(k,v);
keysCt ++;
ckIfNeedToRehash();

int hashMap::hashFn1(string k)

int h_index = 0;
int len = k.length();
for (int i = 0; i < len; i++) {
    h_index = h_index + (int)k[i];
}
//cout << "hash index " << (h_index%mapSize) << endl;
return h_index%mapSize;

int hashMap::hashFn2(string k)

int hash = 0;
for (int i =0; i< k.length(); i+=2) {
    int part = 0;
    part += (int)k[i];
    if (i+1 < k.length()) {
       part = part * 256 + (int)k[i+1];
    }
    hash += part;
}
return hash%mapSize;

int hashMap::hashFn3(string k)

int hash = 0;
int base = 256;
for (int i = 0; i < k.length(); i++) {
    int power = 1;
    for (int j = 0; j< i; j++) {
       power = (power * base) % mapSize;
    }
    hash = (hash + (int)k[i]*power) % mapSize;
}
return hash;

void hashMap::ckIfNeedToRehash()

float check = (float)keysCt / (float)mapSize;
if (check >= 0.7f) {
    reHash();
}

int hashMap::getClosestPrime()

int newSize = mapSize*2;
while (true) {
    bool isPrime = true;
    if (newSize <= 2) {
       isPrime = newSize == 2;
    } else if (newSize % 2 == 0) {
       isPrime = false;
    } else {
       for (int i = 3; i*i <= newSize; i += 2) {
          if (newSize % i == 0) {
             isPrime = false;
             break;
          }
       }
    }
    if (isPrime) {
       return newSize;
    }
    newSize++;
}

void hashMap::reHash()

hNode ** oldMap = map;
int oldMapSize = mapSize;
this->printMap();
mapSize = getClosestPrime();
map = new hNode*[mapSize];
for (int i = 0; i < mapSize; i++) {
    map[i] = NULL;
}
keysCt = 0;
for (int i = 0; i < oldMapSize; i++) {
    if (oldMap[i] != NULL) {
       string k = oldMap[i]->key;
       for (int j = 0; j < oldMap[i]->valuesCt; j++) {
          string v = oldMap[i]->valueArr[j];
          addKeyandValue(k, v);
       }
       delete oldMap[i];
    }
}
delete[] oldMap;

hashMap::~hashMap()

for (int i = 0; i < mapSize; i++) {
    if (map[i] != NULL) {
       cout << "Deleting " << map[i]->key << endl;
       delete map[i];
    }
}
delete[] map;

void hashMap::printMap()

for (int i = 0; i < mapSize; i++) {
    //cout << "In loop" << endl;
    if (map[i] != NULL) {
       cout << map[i]->key << " ("<< i << "): ";
       for (int j = 0; j < map[i]->valuesCt;j++) {
          cout << map[i]->valueArr[j] << ", ";
       }
       cout << endl;
    }
}

void hNode::addValue(string v)

valueArr[valuesCt] = v;
valuesCt++;

hNode::~hNode()

delete[] valueArr;

void BSTJokes::clearTree(TNode *tmp)

if (root != NULL) {
    return;
}
clearTree(tmp->left);
clearTree(tmp->right);
remove(tmp->person->first, tmp->person->last, tmp->person->mi);

BSTJokes::~BSTJokes()

if (root != NULL) {
    clearTree(root);
}

void BSTJokes::remove(string l, string f, string m)

TNode*node = find(l, f, m);

if (node == NULL) {
    return;
}
if (node->left == NULL && node->right == NULL) {
    removeNoKids(node);
} else if (node->left == NULL || node->right == NULL) {
    removeOneKid(node);
} else {
    removeTwoKids(node);
}

void BSTJokes::removeTwoKids(TNode *tr)

if (tr == NULL) {
    return;
}
TNode* replacement = findReplacement(tr);
TNode *replacedNode = find(tr->person->last, tr->person->first, tr->person->mi);
Person*newPerson = new Person(replacement->person->last, replacement->person->first,replacement->person->mi, replacement->person->joke);
if (replacement->right != NULL) {
    removeOneKid(replacement);
} else {
    removeNoKids(replacement);
}
replacedNode->person = newPerson;

TNode *BSTJokes::findReplacement

if (tr == NULL || tr->right == NULL) {
    return NULL;
}
TNode *currNode = tr->right;
while (currNode->left != NULL) {
    currNode = currNode->left;
}
return currNode;

void BSTJokes::removeOneKid(TNode *tr)

TNode *removed = find(tr->person->last, tr->person->first, tr->person->mi);
TNode *parent = removed->parent;
TNode *child =  removed->left;
if (removed->left == NULL) {
    child = removed->right;
}
if (parent->left == removed) {
    parent->left = child;
    child->parent = parent;
}
else {
    parent->right = child;
    child->parent = parent;
}
delete removed;
setHeight(child);

void BSTJokes::removeNoKids(TNode *tr)

if (tr == NULL) {
    return;
}
TNode *parent = tr->parent;
if (parent == NULL) {
    root = NULL;
} else {
    if (parent->left == tr) {
        parent->left = NULL;
    } else if (parent->right = tr){
        parent->right = NULL;
    }
    setHeight(parent);
}
delete tr;

void BSTJokes::setHeight(TNode *n)

while (n != NULL) {
    int leftHeight, rightHeight;
    if (n->left == NULL) {
        leftHeight = 0;
    } else {
        leftHeight = n->left->height;
    }
    if (n->right == NULL) {
        rightHeight = 0;
    } else {
        rightHeight = n->right->height;
    }
    int maxHeight = leftHeight;
    if (rightHeight > maxHeight) {
        maxHeight = rightHeight;
    }
    n->height = maxHeight + 1;
    n = n->parent;
}

void BSTJokes::printTreePost(TNode *n)

if (n == NULL) {
    return;
}
else {
    printTreePost(n->left);
    printTreePost(n->right);
    n->printNode();
}

void BSTJokes::printTreePre(TNode *n)

if (n == NULL) {
    return;
}
else {
    n->printNode();
    printTreePre(n->left);
    printTreePre(n->right);
}

void BSTJokes::printTreeIO(TNode *n)

if (n == NULL) {
  return;
}
else {
     printTreeIO(n->left);
     n->printNode();
     printTreeIO(n->right);
}

TNode *BSTJokes::find(string l, string f, string m)

TNode* currNode = root;
while (currNode != NULL) {
    if (l == currNode->person->last) {
        if (f == currNode->person->first) {
            if (m == currNode->person->mi) {
                return currNode;
            }else if (m < currNode->person->mi) {
                currNode = currNode->left;
            } else {
                currNode = currNode->right;
            }
        } else if (f < currNode->person->first) {
            currNode = currNode->left;
        } else {
            currNode = currNode->right;
        }
    } else if (l < currNode->person->last) {
        currNode = currNode->left;
    } else {
        currNode = currNode->right;
    }
}
return NULL;

bool BSTJokes::add(string l, string f, string m, string j)

TNode* newNode = new TNode(l,f,m,j);
if (root == NULL) {
    root = newNode;
    root->left = NULL;
    root->right = NULL;
    root->parent = NULL;
    return true;
}
TNode*currNode = root;
int count = 0;
int check = 0;
while (check != 1) {
    count++;
    if (l > currNode->person->last) {
        if (currNode->right != NULL) {
            currNode = currNode->right;;
        } else {
            currNode->right = newNode;
            newNode->parent = currNode;
            newNode->right = NULL;
            newNode->left = NULL;
            check = 1;
            setHeight(newNode);
            return true;
        }
    } else if (l < currNode->person->last) {
        if (currNode->left !=NULL) {
            currNode = currNode->left;
        } else {
            currNode->left = newNode;
            newNode->parent = currNode;
            newNode->right = NULL;
            newNode->left = NULL;
            check = 1;
            setHeight(newNode);
            return true;
        }
    } else if (f > currNode->person->first) {
        if (currNode->right != NULL) {
            currNode = currNode->right;
        } else {
            currNode->right = newNode;
            newNode->parent = currNode;
            newNode->left = NULL;
            newNode->right = NULL;
            check = 1;
            setHeight(newNode);
            return true;
        }
    } else if (f < currNode->person->first) {
        if (currNode->left != NULL) {
            currNode = currNode->left;
        }
        else {
            currNode->left = newNode;
            newNode->parent = currNode;
            newNode->right = NULL;
            newNode->left = NULL;
            check = 1;
            setHeight(newNode);
            return true;
        }
    } else if (m > currNode->person->mi) {
        if (currNode->right != NULL) {
            currNode = currNode->right;
        }
        else {
            currNode->right = newNode;
            newNode->parent = currNode;
            newNode->left = NULL;
            newNode->right = NULL;
            check = 1;
            setHeight(newNode);
            return true;
        }
    }
    else if (m < currNode->person->mi) {
        if (currNode->left != NULL) {
            currNode = currNode->left;
        }
        else {
            currNode->left = newNode;
            newNode->parent = currNode;
            newNode->right = NULL;
            newNode->left = NULL;
            check = 1;
            setHeight(newNode);
            return true;
        }
    }
    else {
        return false;
    }
}