Any ideas on how would I be able to traverse this BTree in asceding order? right now I am sorting the data and giving it to my retreival() function to look for the keys. But naturally it visits and prints the data in ascending order because I give it sorted data in the first place. But i dont think thats correct. I sort of need ideas of how to do inorder traversal on this one. As always, any suggestions would be quite appreciated :)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
#include <string>
using namespace std;
const int KeyFieldMax = 20;
const int KeyFieldMaxplus = KeyFieldMax+1;
const int DataFieldMax = 25;
const int DataFieldMaxplus = DataFieldMax+1;
typedef char KeyFieldType[KeyFieldMaxplus];
typedef char DataFieldType[DataFieldMaxplus];
typedef struct
{
KeyFieldType KeyField;
DataFieldType DataField;
}ItemType;
class TableBaseClass
{
public:
virtual bool Empty(void) = 0;
virtual bool Retrieve(KeyFieldType SearchKey, ItemType & Item) = 0;
public:
fstream DataFile;
long NumItems;
char OpenMode;
};
const int MaxKeys = 4;
const int MaxKeysPlusOne = MaxKeys + 1;
const int MinKeys = 2;
const long NilPtr = -1L;
typedef struct
{
int Count;
ItemType Key[MaxKeys];
long Branch[MaxKeysPlusOne];
} NodeType;
class BTTableClass: public TableBaseClass
{
public:
BTTableClass(char Mode, char * FileName);
bool Empty(void);
bool Insert(const ItemType & Item);
bool Retrieve(KeyFieldType SearchKey, ItemType & Item);
private:
bool SearchNode(const KeyFieldType Target, int & location) const;
void AddItem(const ItemType & NewItem, long NewRight,NodeType & Node, int Location);
void Split(const ItemType & CurrentItem, long CurrentRight,long CurrentRoot, int Location, ItemType & NewItem,long & NewRight);
void PushDown(const ItemType & CurrentItem, long CurrentRoot,bool & MoveUp, ItemType & NewItem, long & NewRight);
long Root;
long NumNodes;
int NodeSize;
NodeType CurrentNode;
};
BTTableClass::BTTableClass(char Mode, char * FileName)
{
OpenMode = Mode;
NodeSize = sizeof(NodeType);
if (Mode == 'r')
{
DataFile.open(FileName, ios::in | ios::binary);
if (DataFile.fail())
cout<<"cannot open"<<endl;
DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
if (DataFile.fail())
{
NumItems = 0;
NumNodes = 0;
Root = NilPtr;
}
else
{
NumItems = CurrentNode.Branch[0];
NumNodes = CurrentNode.Branch[1];
Root = CurrentNode.Branch[2];
}
}
else if (Mode == 'w')
{
DataFile.open(FileName, ios::in | ios::out | ios:: trunc | ios::binary);
if (DataFile.fail())
cout<<"cannot open"<<endl;
Root = NilPtr;
NumItems = 0;
NumNodes = 0;
CurrentNode.Branch[0] = NumItems;
CurrentNode.Branch[1] = NumNodes;
CurrentNode.Branch[2] = Root;
DataFile.seekp(0, ios::beg);
DataFile.write(reinterpret_cast <char *> (&CurrentNode), NodeSize);
}
else
cout<<"improper mode"<<endl;
}
bool BTTableClass::Empty(void)
{
return (Root == NilPtr);
}
bool BTTableClass::SearchNode(const KeyFieldType Target,int & Location) const
{
bool Found;
Found = false;
if (strcmp(Target, CurrentNode.Key[0].KeyField) < 0)
Location = -1;
else
{
Location = CurrentNode.Count - 1;
while ((strcmp(Target, CurrentNode.Key[Location].KeyField) < 0)&& (Location > 0))
Location--;
if (strcmp(Target, CurrentNode.Key[Location].KeyField) == 0)
Found = true;
}
return Found;
}
void BTTableClass::AddItem(const ItemType & NewItem, long NewRight,NodeType & Node, int Location)
{
int j;
for (j = Node.Count; j > Location; j--)
{
Node.Key[j] = Node.Key[j - 1];
Node.Branch[j + 1] = Node.Branch[j];
}
Node.Key[Location] = NewItem;
Node.Branch[Location + 1] = NewRight;
Node.Count++;
}
void BTTableClass::Split(const ItemType & CurrentItem, long CurrentRight,long CurrentRoot, int Location, ItemType & NewItem, long & NewRight)
{
int j, Median;
NodeType RightNode;
cout << "<--- Splitting Node at this point"<<endl;
if (Location < MinKeys)
Median = MinKeys;
else
Median = MinKeys + 1;
DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
for (j = Median; j < MaxKeys; j++)
{
RightNode.Key[j - Median] = CurrentNode.Key[j];
RightNode.Branch[j - Median + 1] = CurrentNode.Branch[j + 1];
}
RightNode.Count = MaxKeys - Median;
CurrentNode.Count = Median;
if (Location < MinKeys)
AddItem(CurrentItem, CurrentRight, CurrentNode, Location + 1);
else
AddItem(CurrentItem, CurrentRight, RightNode,Location - Median + 1);
NewItem = CurrentNode.Key[CurrentNode.Count - 1];
RightNode.Branch[0] = CurrentNode.Branch[CurrentNode.Count];
CurrentNode.Count--;
DataFile.seekp(CurrentRoot * NodeSize, ios::beg);
DataFile.write(reinterpret_cast <char *> (&CurrentNode), NodeSize);
NumNodes++;
NewRight = NumNodes;
DataFile.seekp(NewRight * NodeSize, ios::beg);
DataFile.write(reinterpret_cast <char *> (&RightNode), NodeSize);
}
void BTTableClass::PushDown(const ItemType & CurrentItem, long CurrentRoot,bool & MoveUp, ItemType & NewItem, long & NewRight)
{
int Location;
if (CurrentRoot == NilPtr)
{
MoveUp = true;
NewItem = CurrentItem;
NewRight = NilPtr;
}
else
{
DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
if (SearchNode(CurrentItem.KeyField, Location))
cout<<"Duplicates not allowed..will not insert: "<<CurrentItem.KeyField<<endl;
PushDown(CurrentItem, CurrentNode.Branch[Location + 1], MoveUp,NewItem, NewRight);
if (MoveUp)
{
DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
if (CurrentNode.Count < MaxKeys)
{
MoveUp = false;
AddItem(NewItem, NewRight, CurrentNode, Location + 1);
DataFile.seekp(CurrentRoot * NodeSize, ios::beg);
DataFile.write(reinterpret_cast <char *> (&CurrentNode),NodeSize);
}
else
{
MoveUp = true;
Split(NewItem, NewRight, CurrentRoot, Location,
NewItem, NewRight);
}
}
}
}
bool BTTableClass::Insert(const ItemType & Item)
{
bool MoveUp;
long NewRight;
ItemType NewItem;
PushDown(Item, Root, MoveUp, NewItem, NewRight);
if (MoveUp)
{
CurrentNode.Count = 1;
CurrentNode.Key[0] = NewItem;
CurrentNode.Branch[0] = Root;
CurrentNode.Branch[1] = NewRight;
NumNodes++;
Root = NumNodes;
DataFile.seekp(NumNodes * NodeSize, ios::beg);
DataFile.write(reinterpret_cast <char *> (&CurrentNode), NodeSize);
}
NumItems++;
return true;
}
bool BTTableClass::Retrieve(KeyFieldType SearchKey, ItemType & Item)
{
long CurrentRoot;
int Location;
bool Found;
Found = false;
CurrentRoot = Root;
while ((CurrentRoot != NilPtr) && (! Found))
{
DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
if (SearchNode(SearchKey, Location))
{
Found = true;
Item = CurrentNode.Key[Location];
}
else
CurrentRoot = CurrentNode.Branch[Location + 1];
}
return Found;
}
const int LineMax = KeyFieldMax + DataFieldMaxplus;
typedef char StringType[LineMax];
int MyGetLine(istream & InStream, char * String, int StringMax)
{
char Ch;
int Count, Last;
Count = 0;
Last = StringMax - 1;
Ch = InStream.get();
while ((Ch != '\n') && (! InStream.fail()))
{
if (Count < Last)
String[Count++] = Ch;
Ch = InStream.get();
}
String[Count] = NULL;
return Count;
}
void ReadLine(fstream & InputFile, KeyFieldType Word,DataFieldType Definition)
{
char Line[LineMax];
int k, ch;
MyGetLine(InputFile, Line, LineMax);
for (k = 0; k < KeyFieldMax; k++)
Word[k] = Line[k];
Word[KeyFieldMax] = NULL;
for (k = 0; k < DataFieldMax; k++)
{
ch = Line[KeyFieldMax + k];
if (ch == '\n')
break;
Definition[k] = ch;
}
Definition[k] = NULL;
}
void Load(fstream & InputFile, BTTableClass & Table)
{
ItemType Item;
int Count;
Count = 0;
ReadLine(InputFile, Item.KeyField, Item.DataField);
while (! InputFile.fail())
{
Count++;
cout << endl << "inserting: " << Item.KeyField << " ";
Table.Insert(Item);
ReadLine(InputFile, Item.KeyField, Item.DataField);
}
}
int main()
{
fstream Source;
ifstream DataFile("btree.txt");
char data;
int counter = 0;
char array[100];
while(DataFile >> data)
{
array[counter] = data;
counter++;
}
array[counter];
BTTableClass BTTable('w', "btree.dat");
Source.open("btree.txt", ios::in);
if (Source.fail())
{
exit(1);
}
Load(Source, BTTable);
Source.close();
ItemType Item;
KeyFieldType SearchKey;
KeyFieldType dat;
sort(array,array+counter);
int i=0;
memset(SearchKey,0,4);
cout<<"Traversing Ascending Order"<<endl;
while(i<counter)
{
memcpy(SearchKey,&array[i],1);
if (BTTable.Retrieve(SearchKey, Item))
cout << " Item "<<SearchKey<<" Found " << endl;
else
cout << " Item "<<SearchKey<<" Not Found " << endl;
i++;
}
return 0;
}