B-Tree in C++ HELP!!!

I have been given a project on implementing a B-tree in C++ in which a huge array of strings of length 50 is used to simulate a Hard drive sector.  The const string length=1000.

The project I have to do is pretty much insert, delete, search, print (preorder and postorder traversal), and do what my manager calls a "garbage collector", where it is a linked list of free items.

I have done a previous assignment from my old college day but it does not seem to be working.  I don't want to post my code on here since people will start taking it for their class homeworks and whatnot so I am ready to e-mail this code out to anyone who want to takle this thing with me. PLEASE SOMEONE HELP ME!!!!!!!!!!!
djchienaAsked:
Who is Participating?
 
sunnycoderConnect With a Mentor Commented:
>Just let me know what parts you think do not work and see if you can code it if you can.
I would never go through so much of C++ code.... I can write C code for the same in shorter duration ;o)
here are links to (hopefully) working implementations of B tree ... see if they serve your purpose

http://www.manlug.mcc.ac.uk/MailArchives/Man-LUG/2002/msg00023.html

this has source for C++ implementation
http://www.programmersheaven.com/zone3/cat451/index.htm
0
 
sunnycoderCommented:
I can help you a bit conceptually but not much with the code ...
you should be posting code here as it increases the value of the PAQ database...

>but it does not seem to be working
you can post the relevant section of code which is not working ... run your program through a debugger to locate the problem
0
 
djchienaAuthor Commented:
Well here's my code for it...It is giving me 5 errors when I compile it where my functions declared in the Class Btree where "void test();" "void test1();", "void printall()", and "void main();" are giving me this error:

"local function definitions are illegal"

Also, my printall doesn't print it in preorder and postorder traversal and I do not have that "garbage collector funtion". Someone help get this thing figured out!!!

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

struct pointerpack;

int L, M;  //global variables, L is max # of items in leaf, M is max # of branches for node

struct internalnode{
      internalnode();
      vector<int> key;
      pointerpack *child;
      int count();
};




internalnode::internalnode(){
      child=0;
}

struct leafnode{
      leafnode();
      vector<int> list;
      void printList();
      void inserttoleaf(int a);
      bool deletefromleaf(int a);
      int count();

};

leafnode::leafnode(){
      
}


int leafnode::count(){
      int i=0;
      while(list[i]!=list.back()){
            i++;
      }
      i++;
      return i;
}


bool leafnode::deletefromleaf(int a){
      if(!list.empty()){
            if(a==list.back()){
                  list.pop_back();
                  return true;
            }
            else{
                  int i=0;
                  
                  while(list[i]!=list.back()){
                        if(list[i]==a)
                              break;
                        else
                              i++;
                  }//

                  if(list[i]==list.back())
                        return false;

                  else{
                        while(list[i]!=list.back()){
                              list[i]=list[i+1];
                              i++;
                        }
                        list.pop_back();
                        return true;
                  }//else
            }//else
      }//if

      else
            return false;

      

}//delete
      

                        




void leafnode::inserttoleaf(int a){
  if(list.empty())
            list.push_back(a);
  else      
      if(a>list.back())
            list.push_back(a);
      else{
            int i=0;
            int stop;
            while(list[i]<a){
                  i++;
            }
            
            stop=i;
            
            list.push_back(0);
            while(list.back()!=list[i]){
                  i++;
            }

            while(i!=stop){
                  list[i]=list[i-1];
                  i--;
            }

            list[i]=a;
      }
}


void leafnode::printList(){
      int i=0;
      while((list[i]!=list.back())){
            cout << list[i] << endl;
            i++;
      }
      cout << list[i] << endl;
}//printList


struct returnleafs{
      leafnode *temp1;
      leafnode *temp2;
};


struct returnints{
      internalnode *temp3;
      internalnode *temp4;
};







struct pointerpack{
      pointerpack();
      internalnode *ptr;
      leafnode *pointer;
      pointerpack *next;
};

pointerpack::pointerpack(){
      ptr=0;
      pointer=0;
      next=0;
}


int internalnode::count(){
      pointerpack *counter=child;
      int i=1;
      while(counter->next!=0){
            counter=counter->next;
            i++;
      }
      return i;
}


class Btree{
public:
      internalnode *root;

      

      
      Btree();
      leafnode mergeleaf(leafnode A, leafnode B);
      returnleafs splitleaf(leafnode A);
      internalnode mergeint(internalnode A, internalnode B);
      returnints splitint(internalnode A);
      
      
      void insert(int a);
      void del(int a);
      int search(int a);
      void printall();

      void Test();
      void Test1();
};

Btree::Btree(){
root=0;
}



leafnode Btree::mergeleaf(leafnode A, leafnode B){
      
      int i=0;
      
      while((B.list[i]!=B.list.back())){
          A.list.push_back(B.list[i]);
            i++;
      }
      A.list.push_back(B.list[i]);
      return A;
}//merge

returnleafs Btree::splitleaf(leafnode A){
      returnleafs returning;
      int count=0;
      while((A.list[count]!=A.list.back())){
            count++;
      }
      count++;
      int b=ceil(count/2);
      int i=0;
      returning.temp1=new leafnode;
      returning.temp2=new leafnode;
      while(i<=b-1){
            returning.temp1->list.push_back(A.list[i]);
            i++;
      }
      
      while(i<=count-1){
            returning.temp2->list.push_back(A.list[i]);
            i++;
      }

      return returning;
}//split


internalnode Btree::mergeint(internalnode A, internalnode B){
      pointerpack *current;
      current=A.child;
      while(current->next!=0){
            current=current->next;
      }
      current->next=B.child;
      int i=0;
      while(B.key[i]!=B.key.back()){
      A.key.push_back(B.key[i]);
      i++;
      }
      A.key.push_back(B.key[i]);
      return A;
}

returnints Btree::splitint(internalnode A){
      returnints returning;
      returning.temp3=new internalnode;
      returning.temp4=new internalnode;
      pointerpack *currently;
      currently=A.child;
      int i=1;
      while(currently->next!=0){
            currently=currently->next;
            i++;
      }
      int count=ceil(i/2);
      pointerpack *head;
      
      pointerpack *current=0;
      pointerpack *current1=0;
      head=A.child;
      current=returning.temp3->child=head;
      
      int set=1;
      while(set<=count){
            current=current->next;
            set++;
      }

      current1=current->next;
      
      returning.temp4->child=current1;
      current->next=0;
      
      set=0;
      int count1=0;
      while(A.key[count1]!=A.key.back()){
            count1++;
      }
      count1++;
      int number=ceil(count1/2);
      
      while(set<=number-1){
      returning.temp3->key.push_back(A.key[set]);      
      set++;
      }
      set++;
      
      while(set<=count1-1){
            returning.temp4->key.push_back(A.key[set]);
            set++;
      }
      return returning;
      
}







void Btree::insert(int a){
      returnints returner;
      returnleafs returning;
      if(root==0)
            root=new internalnode;
      internalnode *help=root;
      
      internalnode *hold=0;
      leafnode *keep=0;
      if(help->child==0){
            help->child=new pointerpack;
            keep=new leafnode;
            keep->inserttoleaf(a);
            help->child->pointer=keep;
            help->child->next=0;
      
      }

      else{
            if(help->child->ptr==0){            //one level
                  if(help->key.empty()){  //only one leafnode
                        help->child->pointer->inserttoleaf(a);
                        if(help->child->pointer->count()>L){
                              leafnode helper=*help->child->pointer;
                              returning=splitleaf(helper);
                              pointerpack *one1, *two2;
                              leafnode *one, *two;

                              one=returning.temp1;
                              two=returning.temp2;
                              
                              
                              
                              one1=new pointerpack;
                              two2=new pointerpack;
                              help->child=one1;
                              one1->pointer=one;
                              two2->pointer=two;
                              one1->next=two2;
                              two2->next=0;
                              
                              
                                                

                              
                              help->key.push_back(help->child->pointer->list.back());
                              
                              
                        }//if

                  }//if

                  else{
                        int k=0;
                        while((help->key[k]<a)&&(help->key[k]!=help->key.back())){
                              k++;
                        }
                        if((help->key[k]==help->key.back())&&(a>help->key[k]))
                              k++;
                        pointerpack *tempor=help->child;
                        int count=0;
                        while(count<k){
                              tempor=tempor->next;
                              count++;
                        }//while
                        tempor->pointer->inserttoleaf(a);
                        help->key[k]=tempor->pointer->list.back();
                        if(tempor->pointer->count()>L){
                              returnleafs junior;
                              pointerpack *holder=tempor->next;
                              pointerpack *insert=new pointerpack;
                              junior=splitleaf(*tempor->pointer);
                              tempor->pointer=junior.temp1;
                              insert->pointer=junior.temp2;
                              tempor->next=insert;
                              insert->next=holder;
                              help->key[k]=tempor->pointer->list.back();
                              
                                    
                              k++;
                              int hold=k;
                              help->key.push_back(0);
                              while(help->key.back()!=help->key[k]){
                                    k++;
                              }

                              while(k!=hold){
                                    help->key[k]=help->key[k-1];
                                    k--;
                              }

                              help->key[k]=insert->pointer->list.back();
                        }//if
                  
                  }//else
            }//if

}//insert



void Btree::Test(){
      returnints returning;
      returnleafs returning1;
      leafnode d,y,z;
      
      
      int k;
      cin >> k;
      while(k!=0){
            d.list.push_back(k);
            cin>>k;
      }
      cout <<endl;
      cin >> k;
      while(k!=0){
            y.list.push_back(k);
            cin>>k;
      }
      cout << endl;      
      cin >> k;
      while(k!=0){
            z.list.push_back(k);
            cin>>k;
      }
      returning1=splitleaf(z);
      z=mergeleaf(*returning1.temp1, *returning1.temp2);
      
      
      internalnode one, two, three;
      pointerpack *current, *anoth, anoth2;
      current=new pointerpack;
      anoth=new pointerpack;
      pointerpack *anoth1=new pointerpack;
      anoth->pointer=&y;
      anoth1->pointer=&z;
      one.child=current;
      one.child->pointer=&d;
      
      one.child->next=anoth;

      
      anoth->next=anoth1;
      
      anoth1->next=0;
      
      
      
      one.key.push_back(5);
      one.key.push_back(10);
            one.key.push_back(15);
      one.key.push_back(20);
      
      returning=splitint(one);
      pointerpack *help;
      
      help=returning.temp3->child;
      help->pointer->printList();
      help->next->pointer->printList();
      help=returning.temp4->child;
      help->pointer->printList();
      cout << returning.temp3->key[0];
      cout << returning.temp3->key[1];
cout << returning.temp4->key[0];

};


void Btree::Test1(){
      L=3;      
      int k;
      cin >> k;
      while(k!=0){
            
            
            insert(k);
            
            cin>>k;
      }
 
}

void Btree::printall(){
      pointerpack *what=root->child;
      while(what!=0){
            what->pointer->printList();
            what=what->next;
      }
}

void main(){
      Btree C;
      C.Test();
      C.printall();
}







      

0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
CallandorCommented:
Could it be that you haven't declared the functions in your .h file?  Fix that first, and you'll be able to single-step through your code to solve the other problems.
0
 
djchienaAuthor Commented:
I didn't make any .h files but i did include a .h in the #include headers and the errors didn't come up except one...the vector.h file does not exist.  I'm coding this through Visual C++. I think i may have lost my vector.h file but I don't remember making such a file 3 years ago.  When I take the .h off the #include <vector.h>, it gave me those errors I posted earlier but they disappear once I put the .h back on. Weird I must say. At least I am getting some kind of progress.
0
 
djchienaAuthor Commented:
Any other ideas guys...HELP ME!!! I need to get this thing finished by next week.
0
 
sunnycoderCommented:
I can help you write it in C... I am way out of touch for C++ (its been years since I used it in any form)
0
 
djchienaAuthor Commented:
C is fine with me...
0
 
sunnycoderCommented:
errr... you are not expecting me to write the whole code... are you ?
0
 
djchienaAuthor Commented:
I don't expect anyone to write the whole code out. Just let me know what parts you think do not work and see if you can code it if you can.
0
All Courses

From novice to tech pro — start learning today.