5 objects, and a maximum of 5 child nodes...we insert 6 sucesfully and
"explode" to create 3 child nodes, but when it gets to 7 our temp node
has null pointers???
DRIVER PROGRAM::
#include <iostream>
#include "MLH.h"
using std::cout;
using std::endl;
int main()
{
MLH< int tree;
for(int i = 1; i<=300; i++)
{
tree.MLH_insert(i, i );
}
tree.print();
}
MLH.H (data structure)::
#include <iostream>
using std::cout;
using std::endl;
#define Max_levels 8
#include "node.h"
#include "ML_hash.h"
template< typename T >
class MLH
{
friend class Node< T >;
public:
MLH();
int MLH_insert(int, const T &data);
int MLH_delete(int);
int MLH_get(int);
int explode(Node< T *current, Object< T *newObj);
int collapse(Node< T *curr, int);
void print_rec(Node< T *temporary);
void print();
private:
Node< T Sentinel;
Node< T *temp;
int Dlevel;
Node< T nodecount[Max_levels];
int counter;
};
template< typename T >
MLH< T >::MLH()
{
// for (int i = 0; i < Max_levels; i++)
// nodecount[i] = 0;
counter = 0;
Dlevel = 0;
}
template< typename T >
int MLH< T >::MLH_insert(int id, const T &data)
{
temp = &Sentinel;
Node< T *countpath;
int nextnode;
while(1)
{
if (temp->count num_ob) //checks if the node is a stem node
{
nextnode = ML_hash(temp->level + 1, id);
if (temp->nArray[nextnode]==NULL)
{
Node< T *newNode = new Node< T >();
Object< T *newObj = new Object< T >(id, data);
temp->nArray[nextnode] = newNode;
newNode->up = temp;
newNode->level= temp->level +1;
counter++;
if (newNode->level Dlevel)
Dlevel = newNode->level;
temp = newNode;
int r = 0;
while (temp->objectarray[r] != NULL && r<5)
{
r++;
}
temp->objectarray[r] = newObj;
cout<< "You have successfully inserted the
object! Noobsicle!" << endl;
counter++;
countpath = temp;
while (countpath->up != NULL)
{
countpath->count++;
counter++;
countpath = countpath->up;
}
Sentinel.count++;
return 1;
}
else{
temp= temp->nArray[nextnode];
counter++;
// continue;
}
}
if (temp->count < num_ob) /*checks if node has enough space in it*/
{
for(int i = 0; i < num_ob; i++)
{
if (temp->objectarray[i] != NULL)
{
if (temp->objectarray[i]->key == id)
{
cout << "Object is already in list! Noobsicle!" << endl;
counter++;
return 0;
}
}
}
for(int h = 0; h < num_ob; h++)
{
if(temp->objectarray[h] == NULL)
{
Object< T *newObj = new Object< T >(id, data);
temp->objectarray[h] = newObj;
cout<< "You have successfully inserted the object! Noobsicle!" <<
endl;
counter++;
countpath = temp;
while (countpath->up != NULL)
{
countpath->count++;
counter++;
countpath = countpath->up;
}
Sentinel.count++;
return 1;
}
}
break;
}
if (temp->count == num_ob)
{
//first need to check to see if the element is already there
for(int j = 0; j < num_ob; j++)
{
if (temp->objectarray[j]->key == id)
{
cout << "Object is already in list! Noobsicle!"
<< endl;
counter++;
return 0;
}
}
Object< T *newObj = new Object< T >(id, data);
explode(temp, newObj);//moves the current objects in that node into
another node below it
//then it inserts the object we wish to insert
return 1;
}
}
}
template< typename T >
int MLH< T >::MLH_delete(int id)
{
temp = &Sentinel;
int nextnode;
Node< T *countpath;
int noob;
while(1)
{
if (temp->count num_ob)
{
nextnode = ML_hash(temp->level + 1, id);
temp = temp->nArray[nextnode];
counter++;
continue;
}
if (temp->count < num_ob)
{
for(int i = 0; i < num_ob; i++)
{
if (temp->objectarray[i] != NULL)
{
if (temp->objectarray[i]->key == id)
{
// temp->count--;
countpath = temp;
// noob = i;
while (countpath->up != NULL)
{
countpath->count--;
countpath = countpath->up;
counter++;
}
Sentinel.count--;
delete temp->objectarray[i];
while(temp->objectarray[i+1] != NULL && (i+1) < num_ob ){
temp->objectarray[i] = temp->objectarray[i+1];
i++;
}
temp->objectarray[i] = NULL;
cout << "Object was Deleted! Noobsicle!" << endl;
collapse(temp, nextnode);
counter++;
return 1;
}
}
}
for(int h = 0; h < num_ob; h++)
{
if(temp->objectarray[h] == NULL)
{
counter++;
cout<< "The object you are looking for was not found! Noobsicle!"
<< endl;
return 0;
}
}
break;
}
if (temp->count == num_ob)
{
for(int j = 0; j < num_ob; j++)
{
if (temp->objectarray[j]->key == id)
{
// temp->count--;
countpath = temp;
// noob = j;
while (countpath->up != NULL)
{
countpath->count--;
counter++;
countpath = countpath->up;
}
Sentinel.count--;
delete temp->objectarray[j];
while(temp->objectarray[j+1] != NULL && (j+1) < num_ob){
temp->objectarray[j] = temp-
>objectarray[j+1];j++;
}
temp->objectarray[j] = NULL;
counter++;
cout << "Object was Deleted! Noobsicle!" <<
endl;
collapse(temp, nextnode);
//run collapse() or should i make check in here?
return 1;
}
}
}
}
}
template< typename T >
int MLH< T >::MLH_get(int id)
{
temp = &Sentinel;
int nextnode;
while(1)
{
if (temp->count num_ob)
{
nextnode = ML_hash(temp->level + 1, id);
counter++;
temp = temp->nArray[nextnode];
continue;
}
if (temp->count < num_ob)
{
for(int i = 0; i < num_ob; i++)
{
if (temp->objectarray[i] != NULL)
{
if (temp->objectarray[i]->key == id)
{
counter++;
cout << "Object was found! Noobsicle!" << endl;
return 1;
}
}
}
for(int h = 0; h < num_ob; h++)
{
if(temp->objectarray[h] == NULL)
{
counter++;
cout<< "The object you are looking for is was not found!
Noobsicle!" << endl;
return 0;
}
}
break;
}
if (temp->count == num_ob)
{
for(int j = 0; j < num_ob; j++)
{
if (temp->objectarray[j]->key == id)
{
cout << "Object was found Noobsicle!" <<
endl;
counter++;
return 1;
}
}
}
}
}
template< typename T >
int MLH< T >::explode(Node< T *current, Object< T *newObj)
{
int hashpath;
int ki;
int x=0;
Node< T *countpath;
while(x != 1){
for (int k = 0; k < num_ob; k++)
{
ki = current->objectarray[k]->key;
hashpath = ML_hash(current->level+1 , ki);
if (current->nArray[hashpath]==NULL){
Node< T *newNode = new Node< T >();
current->nArray[hashpath] = newNode;
newNode->up = current;
newNode->level= current->level +1;
counter++;
if (newNode->level Dlevel)
Dlevel = newNode->level;
}
int r=0;
while (current->nArray[hashpath]->objectarray[r] != NULL && ( r <
num_ob) ){
r++;
}
current->nArray[hashpath]->objectarray[r] = current->objectarray[k];
current->nArray[hashpath]->count++;
/* ignore
countpath = current->nArray[hashpath];
while (countpath->up != NULL)
{
countpath->count++;
countpath = countpath->up; //doesnt add to Sentinel's count
}
Sentinel.count++;
*/
}
hashpath = ML_hash(current->level+1, newObj->key); //hashpath of the
element that i want to insert
if (current->nArray[hashpath]==NULL){
Node< T *newNode = new Node< T >();
current->nArray[hashpath] = newNode;
newNode->up = current;
newNode->level= current->level + 1;
counter++;
if (newNode->level Dlevel)
Dlevel = newNode->level;
}
for(int b=0; b<num_ob; b++)
{
if (current->nArray[hashpath]->objectarray[b] == NULL)
x=1;
//there is space in the node
}
if (x!=1){
current = current->nArray[hashpath];
continue;
}
int r=0;
while (current->nArray[hashpath]->objectarray[r] != NULL && r
< num_ob ){
r++;
}
current->nArray[hashpath]->objectarray[r] = newObj;
countpath = current->nArray[hashpath];
while (countpath->up != NULL)
{
countpath->count++;
countpath = countpath->up;
counter++;
}
Sentinel.count++;
return 1;
}
}
template< typename T >
int MLH< T >::collapse(Node< T *curr, int nn) /*return 0 if no need
to collapse*/
{
for (int f=0; f<num_ob; f++)
{
if (curr->objectarray[f] != NULL) //there is an object in the node
{
return 0;
}
}
if (curr == Sentinel)
return 0;
if (curr->level == Dlevel)
Dlevel--;
delete curr->up->nArray[nn];
curr->up->nArray[nn] = NULL;
curr = curr->up;
int i= 0;
while (curr->up->nArray[i] != curr) //not sure if this works???
{
i++; //location of curr in the nArray of the node above it
}
/*
for(int i = 0; i<num_ob; i++)
{
if (curr->up->nArray[i] == curr) //not sure if this works
break;
}
*/
collapse(curr, i);
}
template< typename T >
void MLH< T >::print()
{
Node< T *tem = &Sentinel;
if (tem->count <= num_ob)
{
for (int i = 0; i < num_ob; i++)
{
if (tem->objectarray[i] != NULL)
{
cout << "Object: " << tem->objectarray[i]->data << " Level: " <<
tem->level << endl;
}
}
}
else{
for (int i = 0; i < num_ob; i++)
{
if(tem->nArray[i] != NULL)
{
print_rec(tem->nArray[i]);
}
}
}
cout << "Number of Objects in list: " << Sentinel.count << endl;
cout << "Deepest node level in repository: "<< Dlevel <<endl;
}
template< typename T >
void MLH< T >::print_rec(Node< T *tem)
{
if (tem->count <= num_ob)
{
for (int i = 0; i < num_ob; i++)
{
if (tem->objectarray[i] != NULL)
{
cout << "Object: " << tem-
>objectarray[i]->data << " Level: " << tem->level << endl;}
}
}
else{
for (int i = 0; i < num_ob; i++)
{
if(tem->nArray[i] != NULL)
{
print_rec(tem->nArray[i]);
}
}
}
cout << "Number of Objects in list: " << Sentinel.count <<
endl;
cout << "Deepest node level in repository: "<< Dlevel <<endl;
}
