/* title 
  二元搜尋樹
*/

/* comment *****************************************************************

   樣板二元搜尋樹 ( binary search tree )

****************************************************************************/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <string>
#include <sstream>
#include <vector>

using namespace std ;

template <typename T>
struct Node {
    T data ;
    Node<T> *left , *right ;

    Node( const T& d ) : data(d) , left(NULL) , right(NULL) {}

    bool  is_leaf_node() const {
        return  ( left == NULL && right == NULL ) ? true : false ;
    }
    
} ;

template <typename T>
ostream& operator<<( ostream& out , const Node<T>& foo ) {
    return out << foo.data ;
}


template <typename T>
class BST {
  private :

    Node<T> *root ;


    // 列印 ptr 指向的 subtree
    void  print_subtree( ostream& out , const Node<T>* ptr , int depth = 1 ) const ;

    // 找出最靠近 ptr 指向的 subtree 的節點位置
    Node<T>*  max_subtree( const Node<T>* ptr ) const ;

    // 找出 ptr 指向的 subtree 的深度
    int  subtree_depth( const Node<T>* ptr ) const ;

    // 清除 ptr 指向的 subtreem, 同時 ptr 設為 NULL
    void  erase_subtree(  Node<T>* &ptr ) const ;

    // 複製 q 指向的 subtree 到 ptr
    void  copy_subtree( Node<T>* &ptr , const Node<T> *q ) const ;
    
    // 由小到大列印 ptr 指向的 subtree 的所有元素
    void  list_tree_nodes( const Node<T> *ptr , ostringstream& ostr ) const ;

    // 將 ptr 指向的 subtree 由小到大存入 foo 
    void  get_tree_nodes( const Node<T> *ptr , vector<T>& foo ) const ;
    
    // 去除根節點
    void  delete_root() ;

    // 去除非根節點 : p 指向所要去除的節點, q 為 p 的父節點
    void  delete_non_root_node ( Node<T>* p , Node<T> *q ) ;

    // 去除一筆資料 d
    bool  erase_element( const T& d ) ;

  public :

    BST() : root(NULL) {}

    // 複製建構函式
    BST( const BST<T>& foo ) ;

    // 指定運算子
    BST<T>&  operator= ( const BST<T>& foo ) ;

    // 解構函式
    ~BST () {  erase_subtree(root) ;  }

    // 清除 tree
    void  erase_tree() { erase_subtree(root) ; }
    
    // 插入資料 d :  若 d 較節點資料值大, 則存入右邊, 否則存入左邊
    void  insert ( const T& d ) ;

    // 由小到大輸出所有元素成字串
    string  tree_nodes() const ;

    // 計算樹的深度
    int  depth() const { return subtree_depth(root) ; }

    // 找尋資料 d, 回傳找到的位置
    const Node<T>*  find( const T& d ) const ;

    // 去除所有資料 d, 回傳刪除的個數
    int  erase( const T& d ) ;

    // 插入一個元素
    BST<T>&  operator+= ( const T& d ) ;

    // 兩樹合成
    BST<T>&  operator+= ( const BST<T>& foo ) ;
    
    // 去除所有資料 d
    BST<T>&  operator-=( const T& d ) ;

    // 兩樹合成
    template <typename S>
    friend  BST<S> operator+ ( const BST<S>& a , const BST<S>& b ) ;
    
    // 列印
    template <typename S>
    friend  ostream& operator<<( ostream& out , const BST<S>& foo ) ;

};



int main() {

    BST<int> foo , bar ;

    srand( static_cast<unsigned>(time(NULL)) ) ;
    
    int  random ;
    for ( int i = 0 ; i < 10 ; ++i ) {
        random = rand() % 10 ;
        foo += random ;
        bar += random+rand()%5 ;
    }

    cout << "> foo : \n" 
         << foo << endl << endl ;

    cout << "> bar : \n" 
         << bar << endl << endl ;

    
    BST<int>  c = foo + bar ;
    cout << "> c (foo+bar) : \n" 
         << c << "\n\n\n" ;
    

    bar = c ;
    cout << "> bar :\n" 
         << bar << endl << endl ;
    cout << "> elements : " << bar.tree_nodes() << endl ;


    int d ;
    while ( 1 ) {
        cout << "> element to be deleted  : " ;
        cin >> d ;
        cout << "> Nodes of being deleted : " << bar.erase(d) << endl ;
        cout << bar << endl ;
        cout << "> elements : " << bar.tree_nodes() << endl ;
    }

    return 0 ;
}




// 列印 ptr 指向的 subtree
template <typename T>
void  BST<T>::print_subtree( ostream& out , const Node<T>* ptr , int depth ) const {
    if ( ptr == NULL ) {
        out << setw((depth-1)*5) << "|--> " 
            << setw(5) << left << "." << right << "\n" ;
    } else {
        if ( depth > 1 ) out << setw((depth-1)*5) << "|--> " ;
        out << setw(5) << left << ptr->data << right << endl ;
        if ( ! ptr->is_leaf_node() ) {
            print_subtree( out , ptr->right , depth+1 ) ;
            print_subtree( out , ptr->left , depth+1 ) ;
            if ( ptr->left == NULL || ( ptr->left != NULL && ptr->left->is_leaf_node() ) ) out << endl ;
        }
    }
}


// 找出最靠近 ptr 指向的 subtree 的節點位置
template <typename T>
Node<T>*  BST<T>::max_subtree( const Node<T>* ptr ) const {
        
    if ( ptr == NULL || ptr->left == NULL ) 
        return NULL ;
    else {
        Node<T> *p = ptr->left ;
        while ( p->right != NULL ) p = p->right ;
        return  p ;
    }

}
    

// 找出 ptr 指向的 subtree 的深度
template <typename T>
int  BST<T>::subtree_depth( const Node<T>* ptr ) const {
    if ( ptr == NULL ) 
        return 0 ;
    else 
        return 1 + max( subtree_depth(ptr->left) , subtree_depth(ptr->right) ) ;
}

    
// 清除 ptr 指向的 subtreem, 同時 ptr 設為 NULL
template <typename T>
void  BST<T>::erase_subtree(  Node<T>* &ptr ) const {
    if ( ptr == NULL ) 
        return ;
    else {
        erase_subtree( ptr->left ) ;
        erase_subtree( ptr->right ) ;
        delete ptr ;
        ptr = NULL ;
    }
}


// 複製 q 指向的 subtree 到 ptr
template <typename T>
void  BST<T>::copy_subtree( Node<T>* &ptr , const Node<T> *q ) const {
    if ( q == NULL ) {
        ptr = NULL ;
    } else {
        ptr = new Node<T>(q->data) ;
        copy_subtree( ptr->left  , q->left ) ;
        copy_subtree( ptr->right , q->right ) ;
    }
}

    
// 由小到大列印 ptr 指向的 subtree 的所有元素
template <typename T>
void  BST<T>::list_tree_nodes( const Node<T> *ptr , ostringstream& ostr ) const {
        
    if ( ptr != NULL ) {
        list_tree_nodes(ptr->left,ostr) ;
        ostr << ptr->data << " " ;
        list_tree_nodes(ptr->right,ostr) ;
    } 

}


// 將 ptr 指向的 subtree 由小到大存入 foo 
template <typename T>
void  BST<T>::get_tree_nodes( const Node<T> *ptr , vector<T>& foo ) const {
        
    if ( ptr != NULL ) {
        get_tree_nodes(ptr->left,foo) ;
        foo.push_back(ptr->data) ;
        get_tree_nodes(ptr->right,foo) ;
    } 

}


// 去除根節點
template <typename T>
void  BST<T>::delete_root() {
        
    if ( root == NULL ) {
        return  ;
    } else if ( root->is_leaf_node() ) {
        delete root ;
        root = NULL ;
    } else if ( root->left == NULL ) {
        Node<T> *p = root ;
        root = root->right ;
        delete p ;
    } else if ( root->right == NULL ) {
        Node<T> *p = root ;
        root = root->left ;
        delete p ;
    } else {

        Node<T> *q = root ;
        Node<T> *p = root->left ;

        if ( p->right == NULL ) {
            p->right = root->right ;
            root = p ;
            delete q ;
        } else {
                
            q = p ;
            p = p->right ;

            while ( p->right != NULL ) {
                q = p ;
                p = p->right ;
            }
            root->data = p->data ;
            delete_non_root_node( p , q ) ;

        }
            
    }

}


// 去除非根節點 : p 指向所要去除的節點, q 為 p 的父節點
template <typename T>
void  BST<T>::delete_non_root_node ( Node<T>* p , Node<T> *q ) {

    if ( p->is_leaf_node() || p->left == NULL ) {

        // p is a leaf node or its left pointer is null
        if ( q->left == p ) 
            q->left = p->right ;
        else 
            q->right = p->right ;
         
        delete p ;

    } else if ( p->left->right == NULL ) {

        // p left right pointer is null
        if ( q->left == p ) {
            q->left = p->left ;
            q->left->right = p->right ;
        } else {
            q->right = p->left ;
            q->right->right = p->right ;
        }
            
        delete p ;
            
    } else {
        
        Node<T> *r = p ;
            
        q = r->left ;
        r = r->left->right ;
            
        while ( r->right != NULL ) {
            q = r ;
            r = r->right ;
        }
        
        p->data = r->data ;
            
        delete_non_root_node( r , q ) ;

    }

}
    


// 去除一筆資料 d
template <typename T>
bool  BST<T>::erase_element( const T& d ) {

    if ( root == NULL ) {

        return false ;

    } else if ( root->data == d ) {

        delete_root() ;
        return  true ;

    } else {

        Node<T>  *p = root ;
        Node<T>  *q ;
            
        while ( p != NULL ) {
            if ( p->data == d ) {
                delete_non_root_node(p,q) ;
                return true ;
            }  else {
                q = p ;
                p = ( p->data < d ? p->right : p->left ) ;
            }
                
        }

        return false ;
            
    }
    
}

        
// 複製建構函式
template <typename T>
BST<T>::BST( const BST<T>& foo ) {

    if ( foo.root == NULL ) 
        root = NULL ;
    else {
        root = new Node<T>(foo.root->data) ;
        copy_subtree( root , foo.root ) ;
    }
        
}


// 指定運算子
template <typename T>
BST<T>&  BST<T>::operator= ( const BST<T>& foo ) {

    if ( root == foo.root ) {
        return *this ;
    } else {
        erase_subtree( root ) ;
        copy_subtree( root , foo.root ) ;
    }

}


// 插入資料 d, 
// 若 d 較節點資料值大, 則存入右邊, 否則存入左邊
//
template <typename T>
void  BST<T>::insert ( const T& d ) {

    Node<T> *tmp = new Node<T>(d) ;
    Node<T> *p = root , *q ;

    if ( root == NULL )
        root = tmp ;
    else {
        while( p != NULL ) {
            q = p ;
            p =  ( p->data < tmp->data ? p->right : p->left ) ;
        }
        if ( q->data < tmp->data )
            q->right = tmp ;
        else
            q->left = tmp ;
    }

}


// 插入一個元素
template <typename T>
BST<T>&  BST<T>::operator+= ( const T& d ) {
    insert(d) ;
    return  *this ;
}
    

// 由小到大輸出所有元素
template <typename T>
string  BST<T>::tree_nodes() const {
    ostringstream  ostr ;
    list_tree_nodes( root , ostr ) ;
    return  ostr.str() ;
}        


// 找尋資料 d, 回傳找到的位置
template <typename T>
const Node<T>*  BST<T>::find( const T& d ) const {

    Node<T>  *p = root ;
    while ( p != NULL ) {
        if ( p->data == d ) 
            return p ;
        else 
            p = ( p->data < d ? p->right : p->left ) ;
    }
    return p ;

}

// 去除所有資料 d, 回傳刪除的個數
template <typename T>
int  BST<T>::erase( const T& d ) {
        
    int c = 0 ;
    while ( erase_element(d) ) ++c ;
    return c ;

}


// 去除所有資料 d
template <typename T>
BST<T>&  BST<T>::operator-=( const T& d ) {
    erase(d) ;
    return  *this ;
}


// 兩樹合成
template <typename T>
BST<T>&  BST<T>::operator+= ( const BST<T>& foo ) {
    return  *this = *this + foo ;
}

    
// 兩樹合成
template <typename T>
BST<T> operator+ ( const BST<T>& a , const BST<T>& b ) {
    vector<T>  nodes ;
    b.get_tree_nodes(b.root,nodes) ;
    BST<T>  sum = a ;
    for ( int i = 0 ; i < nodes.size() ; ++i ) sum.insert(nodes[i]) ;
    return  sum ;
}
    
    
// 列印
template <typename T>
ostream& operator<<( ostream& out , const BST<T>& foo ) {
    foo.print_subtree( out , foo.root ) ;
    return out ;
}

/***********************************************************************
  OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT
 ***********************************************************************

> foo :
7
|--> 9
     |--> .
     |--> 9
          |--> .
          |--> 8
               |--> .
               |--> 8

|--> 1
     |--> 2
          |--> 7
          |--> .

     |--> 0
          |--> .
          |--> 0



> bar :
8
|--> 10
     |--> 11
          |--> 12
          |--> .

     |--> 10

|--> 3
     |--> 8
          |--> .
          |--> 4

     |--> 1
          |--> 3
          |--> .



> c (foo+bar) :
7
|--> 9
     |--> 10
          |--> 11
               |--> 12
               |--> .

          |--> 10

     |--> 9
          |--> .
          |--> 8
               |--> .
               |--> 8
                    |--> .
                    |--> 8
                         |--> .
                         |--> 8

|--> 1
     |--> 2
          |--> 7
               |--> .
               |--> 3
                    |--> 4
                    |--> 3

          |--> .

     |--> 0
          |--> 1
          |--> 0




> bar :
7
|--> 9
     |--> 10
          |--> 11
               |--> 12
               |--> .

          |--> 10

     |--> 9
          |--> .
          |--> 8
               |--> .
               |--> 8
                    |--> .
                    |--> 8
                         |--> .
                         |--> 8

|--> 1
     |--> 2
          |--> 7
               |--> .
               |--> 3
                    |--> 4
                    |--> 3

          |--> .

     |--> 0
          |--> 1
          |--> 0



> elements : 0 0 1 1 2 3 3 4 7 7 8 8 8 8 9 9 10 10 11 12
> element to be deleted  : 7
> Nodes of being deleted : 2
4
|--> 9
     |--> 10
          |--> 11
               |--> 12
               |--> .

          |--> 10

     |--> 9
          |--> .
          |--> 8
               |--> .
               |--> 8
                    |--> .
                    |--> 8
                         |--> .
                         |--> 8

|--> 1
     |--> 2
          |--> 3
               |--> .
               |--> 3

          |--> .

     |--> 0
          |--> 1
          |--> 0


> elements : 0 0 1 1 2 3 3 4 8 8 8 8 9 9 10 10 11 12
> element to be deleted  : 8
> Nodes of being deleted : 4
4
|--> 9
     |--> 10
          |--> 11
               |--> 12
               |--> .

          |--> 10

     |--> 9

|--> 1
     |--> 2
          |--> 3
               |--> .
               |--> 3

          |--> .

     |--> 0
          |--> 1
          |--> 0


> elements : 0 0 1 1 2 3 3 4 9 9 10 10 11 12

....

***********************************************************************/