Third Deliverable for project 2:

Due Thursday 13 April 2006 by 11:59pm

Phase1 description Phase2 description

NOTE:: if you make a new Bnode from inside your Node::split() function you must have node.cpp include Bnode.h

Bug fixes/Addendum

Have no fear. Get the latests tests.

There seems to be some confusion as to what belongs in which class so I have added the Broot and Bnode classes below.

Formulas for Calculating the two medians for Node::split()

You may need to include <math.h> 


    median1_index = (int)floor((double)(2.0 * m_order -2.0) / 3.0);
    median2_index = 2 * median1_index + 1;
    
  

  

  

    We only have two weeks between now and the due date.

    So what I have decided to do is make insert due by April 13 8:00am.

    This gives you more time to do insert but less time to complete delete.
  

  

    Once again you will find a script, named run_part3_tests.pl, to run your program against all the test I expect you to pass.

    Those tests will be all the previous tests up to the 30's.
  

  

    To finish this next phase of the assignment you will need something similar to the following in your node class:


class Node
{ 
  // member variables common two both types of nodes:
  int m_id;
  int m_count;
  int m_order;
  int m_max;
  int m_min;
  int* m_data;
  Node** m_branch;

  // helper functions
  void verbose_print();                                  // you know what this does
  bool has_room();                                       // returns true if m_count < m_max
  void wipe();                                           // empty out a node's data/pointers 

  // insertion functions:
  void push_in(int value, Node* pointer, int position);  // take this from kruse
  void push_in_lesser(int value, Node* pointer);         // when the pointer < value
  void push_in_greater(int value, Node* pointer);        // when the pointer > value

  // functions used to force an insert when a node is full
  void pop_out_smallest(int& value, Node*& pointer);     // notice that value and pointer are "output parameters"
  void pop_out_largest(int& value, Node*& pointer);      // so you pass in stuff and expect to get back smallest/largest

  // the motherload split, these must be performed by the parent of the node that is full
  // both regular nodes AND the parent node may perform this kind of split, DO NOT MAKE IT VIRTUAL!!!!
  void split(--arguments will vary depending on how you want to handle regular node splits--, must have at least: int position);

  // virtual destructor to satisfy the compiler warnings
  virtual ~Node() {};
};


  
 
  

    Take the time to understand why there are 5 functions for inserting nodes.
  

  

    Your B*tree is to "delay" splits by {passing,pushing,rotating,etc...all mean the same thing} values/pointers to adjacent siblings if it can.
  

  

    You Must have all the functions listed above before you can begin writing the pushdown() function that drives the insert algorithm.
  

  

    You cannot use kruse's push_down().  You must have the parent handle splits and delays.  Do model your push_down() after kruse's.  Make it part of the Btree class.  
  

  

    This function must NOT handle root_split().  Do rootsplits ONLY when push_down fails to insert a value that is not a duplicate.
  


  

    Your Broot and Bnode class will have to look something like this:


class Broot : public Node
{
    public:

      // constructor, needs order and id
      B_root(int order, int id);

      // needs the value and pointer that aren't in any node yet
      void root_split(int value, Node* pointer);

      // destructor, probably never gets called
      ~B_root();
};

class Bnode : public Node
{
    public:

      // constructor, needs the same stuff as a Broot
      B_node(int order, int id);

      // destructor, must use delete[] on m_data and m_branch, AFTER calling wipe()
      ~B_node();
};


  
    





///////////////////////////////////////////////////////////////////////////////////////////////////
// you need this to signal previous callers of pushdown() what happened during the recursive call
// Be carefull of naming these status or result because those are already
// defined by the standard namespace and you will get a strange compile error
///////////////////////////////////////////////////////////////////////////////////////////////////
enum BTREE_RESULT
{
  BTREE_DUPLICATE,   
  BTREE_OVERFLOW,    
  BTREE_SPLIT,
  BTREE_SUCCESS,
  BTREE_NOT_PRESENT
};

class Btree
{

    public:
        // these functions are your public interface to main.cpp
        /* A */     bool insert(int value);
        /* D */     bool delete(int value);
        /* S */     bool search(int value);
        /* P */     bool print();
        /* V */     bool verbose();


        // constructor
        B_tree(int order);                  // only should need order;


    // the non-public functions do all the heavy lifting
    private:

        // member variables, not many
        Node* m_root;
        int m_order;


        // recursive search function
        void search(int value, Node* node, bool& success);     // look familiar?

        // recursive print functions
        void print(Node* node);
        void verbose(Node* node);


        // this is a very important utility function!
        // returns true on duplicate value, else position is set to the pointer in m_branch[] to follow next
        bool search_node(Node* node, int value, int& position);


        // finally the one you've all been waiting for:
        // returns a message to the caller, insert_value and insert_branch are the value that MIGHT come 
        //   from lower in the tree due to splits OR when you bottom out.
        // Notice the use of "output" parameters again.
        BTREE_RESULT push_down(Node* node, int new_value, new_pointer; int& insert_value, Node*& insert_branch);
};


  

  

    Don't be overwhelmed.  If you can do the root split from last week then you can do the five insert functions and the split().
  

  

    Make sure to attend lecture this week.  We will have to meet outside of class to go over push_down in detail.