/* Program extracts from Chapter 11 of   "Data Structures and Program Design in C++"   by Robert L. Kruse and Alexander J. Ryba   Copyright (C) 1999 by Prentice-Hall, Inc.  All rights reserved.   Extracts from this file may be used in the construction of other programs,   but this code will not compile or execute as given here. */// Section 11.2:class Trie {public:  //  Add method prototypes here.private:  //  data members   Trie_node *root;};const int num_chars = 28;struct Trie_node {//    data members   Record *data;   Trie_node *branch[num_chars];//    constructors   Trie_node();};Error_code Trie::trie_search(const Key &target, Record &x) const/*Post: If the search is successful, a code of success is      returned, and the output parameter x is set as a copy      of the Trie's record that holds target.      Otherwise, a code of not_present is returned.Uses: Methods of class Key.*/{   int position = 0;   char next_char;   Trie_node *location = root;   while (location != NULL && (next_char = target.key_letter(position)) != ' ') {         //  Terminate search for a NULL location or a blank in the target.      location = location->branch[alphabetic_order(next_char)];         //  Move down the appropriate branch of the trie.      position++;         //  Move to the next character of the target.   }   if (location != NULL && location->data != NULL) {      x = *(location->data);      return success;   }   else      return not_present;}Error_code Trie::insert(const Record &new_entry)/*Post: If the Key of new_entry is already in the Trie,      a code of duplicate_error is returned.      Otherwise, a code of success is returned and      the Record new_entry is inserted into the Trie.Uses: Methods of classes Record and Trie_node.*/{   Error_code result = success;   if (root == NULL) root = new Trie_node;  //  Create a new empty Trie.   int position = 0;                        //  indexes letters of new_entry   char next_char;   Trie_node *location = root;              //  moves through the Trie   while (location != NULL &&         (next_char = new_entry.key_letter(position)) != ' ') {      int next_position = alphabetic_order(next_char);      if (location->branch[next_position] == NULL)         location->branch[next_position] = new Trie_node;      location = location->branch[next_position];      position++;   }   //  At this point, we have tested for all nonblank characters of new_entry.   if (location->data != NULL) result = duplicate_error;   else location->data = new Record(new_entry);   return result;}// Section 11.3:template <class Record, int order>class B_tree {public:  //  Add public methods.private: //  data members   B_node<Record, order> *root;         //  Add private auxiliary functions here.};template <class Record, int order>struct B_node {//  data members:   int count;   Record data[order - 1];   B_node<Record, order> *branch[order];//  constructor:   B_node();};template <class Record, int order>Error_code B_tree<Record, order>::search_tree(Record &target)/*Post: If there is an entry in the B-tree whose key matches that in target,      the parameter target is replaced by the corresponding Record from      the B-tree and a code of success is returned.  Otherwise      a code of not_present is returned.Uses: recursive_search_tree*/{   return recursive_search_tree(root, target);}template <class Record, int order>Error_code B_tree<Record, order>::recursive_search_tree(           B_node<Record, order> *current, Record &target)/*Pre:  current is either NULL or points to a subtree of the B_tree.Post: If the Key of target is not in the subtree, a code of not_present      is returned. Otherwise, a code of success is returned and      target is set to the corresponding Record of the subtree.Uses: recursive_search_tree recursively and search_node*/{   Error_code result = not_present;   int position;   if (current != NULL) {      result = search_node(current, target, position);      if (result == not_present)         result = recursive_search_tree(current->branch[position], target);      else         target = current->data[position];   }   return result;}template <class Record, int order>Error_code B_tree<Record, order>::search_node(   B_node<Record, order> *current, const Record &target, int &position)/*Pre:  current points to a node of a B_tree.Post: If the Key of target is found in *current, then a code of      success is returned, the parameter position is set to the index      of target, and the corresponding Record is copied to      target.  Otherwise, a code of not_present is returned, and      position is set to the branch index on which to continue the search.Uses: Methods of class Record.*/{   position = 0;   while (position < current->count && target > current->data[position])      position++;         //  Perform a sequential search through the keys.   if (position < current->count && target == current->data[position])      return success;   else      return not_present;}template <class Record, int order>Error_code B_tree<Record, order>::insert(const Record &new_entry)/*Post: If the Key of new_entry is already in the B_tree,      a code of duplicate_error is returned.      Otherwise, a code of success is returned and the Record new_entry      is inserted into the B-tree in such a way that the properties of a B-tree      are preserved.Uses: Methods of struct B_node and the auxiliary function push_down.*/{   Record median;   B_node<Record, order> *right_branch, *new_root;   Error_code result = push_down(root, new_entry, median, right_branch);   if (result == overflow) {  //  The whole tree grows in height.                              //  Make a brand new root for the whole B-tree.      new_root = new B_node<Record, order>;      new_root->count = 1;      new_root->data[0] = median;      new_root->branch[0] = root;      new_root->branch[1] = right_branch;      root = new_root;      result = success;   }   return result;}template <class Record, int order>Error_code B_tree<Record, order>::push_down(                 B_node<Record, order> *current,                 const Record &new_entry,                 Record &median,                 B_node<Record, order> *&right_branch)/*Pre:  current is either NULL or points to a node of a B_tree.Post: If an entry with a Key matching that of new_entry is in the subtree      to which current points, a code of duplicate_error is returned.      Otherwise, new_entry is inserted into the subtree: If this causes the      height of the subtree to grow, a code of overflow is returned, and the      Record median is extracted to be reinserted higher in the B-tree,      together with the subtree right_branch on its right.      If the height does not grow, a code of success is returned.Uses: Functions push_down (called recursively), search_node,      split_node, and push_in.*/{   Error_code result;   int position;   if (current == NULL) { //  Since we cannot insert in an empty tree, the recursion terminates.      median = new_entry;      right_branch = NULL;      result = overflow;   }   else {   //   Search the current node.      if (search_node(current, new_entry, position) == success)         result = duplicate_error;      else {         Record extra_entry;         B_node<Record, order> *extra_branch;         result = push_down(current->branch[position], new_entry,                            extra_entry, extra_branch);         if (result == overflow) {  //  Record extra_entry now must be added to current            if (current->count < order - 1) {               result = success;               push_in(current, extra_entry, extra_branch, position);            }            else split_node(current, extra_entry, extra_branch, position,                            right_branch, median);            //  Record median and its right_branch will go up to a higher node.         }      }   }   return result;}template <class Record, int order>void B_tree<Record, order>::push_in(B_node<Record, order> *current,   const Record &entry, B_node<Record, order> *right_branch, int position)/*Pre:  current points to a node of a B_tree.  The node *current is not full      and entry belongs in *current at index position.Post: entry has been inserted along with its right-hand branch      right_branch into *current at index position.*/{   for (int i = current->count; i > position; i--) {  //  Shift all later data to the right.      current->data[i] = current->data[i - 1];      current->branch[i + 1] = current->branch[i];   }   current->data[position] = entry;   current->branch[position + 1] = right_branch;   current->count++;}template <class Record, int order>void B_tree<Record, order>::split_node(   B_node<Record, order> *current,    //  node to be split   const Record &extra_entry,          //  new entry to insert   B_node<Record, order> *extra_branch,//  subtree on right of extra_entry   int position,                  //  index in node where extra_entry goes   B_node<Record, order> *&right_half, //  new node for right half of entries   Record &median)                     //  median entry (in neither half)/*Pre:  current points to a node of a B_tree.      The node *current is full, but if there were room, the record      extra_entry with its right-hand pointer extra_branch would belong      in *current at position position, 0 <= position < order.Post: The node *current with extra_entry and pointer extra_branch at      position position are divided into nodes *current and *right_half      separated by a Record median.Uses: Methods of struct B_node, function push_in.*/{   right_half = new B_node<Record, order>;   int mid = order/2;  //  The entries from mid on will go to right_half.   if (position <= mid) {   //  First case:  extra_entry belongs in left half.      for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.         right_half->data[i - mid] = current->data[i];         right_half->branch[i + 1 - mid] = current->branch[i + 1];      }      current->count = mid;      right_half->count = order - 1 - mid;      push_in(current, extra_entry, extra_branch, position);   }   else {  //  Second case:  extra_entry belongs in right half.      mid++;      //  Temporarily leave the median in left half.      for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.         right_half->data[i - mid] = current->data[i];         right_half->branch[i + 1 - mid] = current->branch[i + 1];      }      current->count = mid;      right_half->count = order - 1 - mid;      push_in(right_half, extra_entry, extra_branch, position - mid);   }      median = current->data[current->count - 1]; //  Remove median from left half.      right_half->branch[0] = current->branch[current->count];      current->count--;}template <class Record, int order>Error_code B_tree<Record, order>::remove(const Record &target)/*Post: If a Record with Key matching that of target belongs to the      B_tree, a code of success is returned and the corresponding node      is removed from the B-tree.  Otherwise, a code of not_present      is returned.Uses: Function recursive_remove*/{   Error_code result;   result = recursive_remove(root, target);   if (root != NULL && root->count == 0) {  //  root is now empty.      B_node<Record, order> *old_root = root;      root = root->branch[0];      delete old_root;   }   return result;}template <class Record, int order>