/*

 Date:    2014-04-29

 purpose: An implementation of MAP using binary search tree.

 */

 #ifndef CUSTOMIZED_MAP_H

 #define CUSTOMIZED_MAP_H

 #ifndef NULL

 #define NULL 0

 #endif

 class NODE{

 public:

     NODE(int _key, char * _data):key(_key),data(_data),left(NULL),right(NULL){}

 public:

     int key;

     char * data;

     NODE * left;

     NODE * right;

 };

 class CUST_MAP{

 public:

     CUST_MAP():root(NULL){}; // how about construction failed?

     ~CUST_MAP();

     void destructorImp(NODE * root);

     bool appendItem(int key, char * data);

     bool removeItem(int key);

     bool traverse();

     bool traverseImp(NODE * root);

 public:

     NODE * root;

 };

 #endif

 #include <iostream>

 #include <vector>

 #include "Customized_MAP.h"

 using std::cout;

 using std::endl;

 using std::string;

 bool CUST_MAP::appendItem(int key, char * data){

     enum Direction{LEFT, RIGHT}; //append which direction of the pended item

     Direction direction = LEFT; 

     //routine check.

     NODE * root = this->root;

     if (root == NULL){

         this->root = new NODE(key, data);

         if (this->root)

             return true;

         else return false;

     }

     NODE * image = root;//record the history of root

     // find inserting point

     while (root){

         image = root;

         if (root->key > key){

             root = root->left;

             direction = LEFT;

         }

         else if (root->key < key){

             root = root->right;

             direction = RIGHT;

         }

         else return false;  // duplicated key==> abort appending operation

     }

     // append the fresh node

     NODE * newNode = new NODE(key, data);

     if (direction == LEFT){

         image->left = newNode;

     }else if (direction == RIGHT){

         image->right = newNode;

     }

     return true;

 }

 bool CUST_MAP::removeItem(int key){

     enum Direction{LEFT, RIGHT}; //append which direction of the new item

     Direction direction = LEFT;

     NODE * root = this->root;

     if (root == NULL) // no node deleted. return false

         return false;

     NODE * parent = NULL;

     while(root){

         if (root->key > key){

             parent = root;

             root = root->left;

             direction = LEFT;

         }

         else if (root->key < key){

             parent = root;

             root = root->right;

             direction = RIGHT;

         }

         else if (root->key == key){

             if (root->left && root->right){//要删除的节点有两个孩子节点

                 if (root->right->left == NULL){

                     //要删除节点的右孩子结点没有左孩子节点

                     //1：copy data, root->right  ===>  root.

                     //2: record pointer

                     //3: delete root->right

                     //4: finish pointer association

                     //how to delete root->data;

                     root->data = root->right->data;

                     root->key = root->right->key;

                     NODE * right = root->right->right;

                     delete root->right;

                     root->right = right;

                 }else{

                     //要删除节点的右孩子结点有左孩子节点

                     //root: 要删除的节点

                     //找到root右孩子的 最左方没左孩子的节点： tParent

                     NODE * t = root->right;

                     NODE * tParent = NULL;

                     while (t->left){

                         tParent = t;

                         t = t->left;

                     }

                     root->key = t->key;

                     root->data = t->data;

                     NODE * right = t->right;

                     delete t;

                     t = NULL;

                     tParent->left = right;

                 }

             }else if (root->left){//要删除的节点只有左孩子节点

                 if (direction == LEFT)

                     parent->left = root->left;

                 else if(direction == RIGHT)

                     parent->right = root->left;

                 delete root;

                 root = NULL;

             }else if(root->right){//要删除的节点只有右孩子节点

                 if (direction == LEFT)

                     parent->left = root->right;

                 else if(direction == RIGHT)

                     parent->right = root->right;

                 delete root;

                 root = NULL;

             }else if (root->left==NULL && root->right==NULL){//要删除的节点没有孩子节点

                 if (direction == LEFT)

                     parent->left = NULL;

                 else if(direction == RIGHT)

                     parent->right = NULL;

                 delete root;

                 root = NULL;

             }

             return true;

         }

     }

     return false;

 }

 void CUST_MAP::destructorImp(NODE * root){

     if (root){

         destructorImp(root->left);

         destructorImp(root->right);

         delete root;

         root = NULL;

     }

 }

 CUST_MAP::~CUST_MAP(){

     destructorImp(root);

 }

 bool CUST_MAP::traverseImp(NODE * root){

     if (root){

         traverseImp(root->left);

         cout<<root->data<<endl;

         traverseImp(root->right);

     }

     return true;

 }

 bool CUST_MAP::traverse(){

     traverseImp(root);

     return true;

 }

 int main(){

     CUST_MAP mapTest;

     mapTest.appendItem(, "1 one");

     mapTest.appendItem(, "28 twenty-eight");

     mapTest.appendItem(, "16 sixteen");

     mapTest.appendItem(, "12 twelf");

     mapTest.appendItem(, "24 twety-four");

     mapTest.appendItem(, "56 fifty-six");

     mapTest.appendItem(, "36 thirty-six");

     mapTest.appendItem(, "66 sixty-six");

     mapTest.appendItem(, "46 fourty-six");

     cout<<"New:"<<endl;

     mapTest.traverse();

     cout<<endl<<endl;

     mapTest.removeItem();

     cout<<"New:"<<endl;

     mapTest.traverse();

     cout<<"over"<<endl;

     return ;

 }