// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Header File Name: mnode.h 
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer   
// File Creation Date: 02/12/1997 
// Date Last Modified: 03/15/1999
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- // 
// ---------- Include File Description and Details  ---------- // 
// ----------------------------------------------------------- // 
/*
The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
All those who put this code or its derivatives in a commercial
product MUST mention this copyright in their documentation for
users of the products in which this code or its derivative
classes are used. Otherwise, you have the freedom to redistribute
verbatim copies of this source code, adapt it to your specific
needs, or improve the code and release your improvements to the
public provided that the modified files carry prominent notices
stating that you changed the files and the date of any change.

THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

The Multi-way node (E)ntryKey class and (M)ulti-way (n)ode
classes are used to make up (B)alanced multi-way (T)rees.
Each node in the tree will have a left branch that leads to
all nodes with keys smaller than the smallest key. The right
branches will be paried with a key, each branch leading to all
nodes with keys greater than the given key, but less than the
key to the right. 
*/
// ----------------------------------------------------------- //   
#ifndef __MNODE_HPP
#define __MNODE_HPP

#include "entrykey.h"
#include "int32.h"

// Order of the tree and maximum number of branches for the node.
// A MAXKEYSIZE of 64 each will generate Mnodes 464 bytes in
// length: the count field, plus the left child pointer, plus six
// entry keys. A 464 byte Mnode plus a 16 byte block header,
// plus a 4 byte checksum makes a total of 484 bytes between
// each Mnode in the B-tree index file.
// NOTE: If the NBR constant (B-tree order) is changed, all the
// VBD index files will have to rebuilt if they used a different
// NBR value when they were created. 
const int NBR = 7; // This will allow 4 nodes per branch

// (M)ulti-way (n)ode class 
class Mnode
{
public:
  Mnode() { cnt = 0; left = 0; }

public:
  int Search(const EntryKey &e, int &posn);
  int FullSearch(const EntryKey &e, int &posn);
  void Split(Mnode &b, int split_posn);
  void InsEntryKey(EntryKey &e, int posn);
  void Cat(EntryKey &e) { InsEntryKey(e, cnt); }
  void Cat(Mnode &n);
  void DelEntryKey(int posn);
  INT32 &Branch(int posn);
  INT32 &GetBranchs(int posn);
  INT32 LastPosn() { return cnt-1; }

  // Returns true if node is empty
  int IsEmpty() { return cnt == 0; }

  // Returns true if node if full
  int IsFull() { return cnt == NBR-1; }

  // Returns true if node hase fewer than the minimum number of entries
  int IsPoor() { return cnt < (NBR-1)/2; }

  // Returns true if node has more than the minimum number of entries
  int IsPlentiful() { return cnt > (NBR-1)/2; }

public:
  // The cnt field indicates how many entries are actually in use.
  INT32 cnt;  // Must come before left

  // Branches are indexed from -1 to NBR-2. The -1th branch
  // represents  the left branch and the 0th branch is the
  // right branch of the of the first entry.

  // NOTE: In order for the Branch() function to work with this
  // indexing scheme there cannot be any gaps between the left
  // and entry fields.
  
  INT32 left; // Points to leftmost child. Must come before entry[].
  EntryKey entry[NBR-1];
};

#endif // __MNODE_HPP
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
