// File:     cs2multiset.h

#ifndef cs2multiset_h_
#define cs2multiset_h_

#include <iostream>
#include <vector>


//  Auxiliary class for nodes in the tree.  A parent ptr has been
//  added to the class.  For the root node, this ptr should be null.
//  For all other nodes, this ptr should point the node immediately
//  above in the tree.

template <class T>
class TreeNode {
public:
  TreeNode() : left(0), right(0), parent(0) {}
  TreeNode(const T& init) : value(init), left(0), right(0), parent(0) {}
  T value;
  TreeNode* parent;
  TreeNode* left;
  TreeNode* right;
};


//  Forward declaration of the templated cs2set class so that the
//  iterator class allows it to be named as a friend.

template <class T> class cs2multiset;


///////////////////////////////////////////////////////////////////
///////////////         Iterator definitions          /////////////
///////////////////////////////////////////////////////////////////

//  These are incomplete because the iterator increment and
//  decrement operators are a bit beyond the scope of this course.

template <class T>
class tree_iterator {
private:
  TreeNode<T>* ptr_;
public:
  tree_iterator() : ptr_(0) {}
  tree_iterator( TreeNode<T>* p ) : ptr_(p) {}
  tree_iterator( const tree_iterator& old ) : ptr_(old.ptr_) {}
  ~tree_iterator() {}
  
  tree_iterator& operator=( const tree_iterator& old )
  { ptr_ = old.ptr_;  return *this; }
  
  //  operator* gives constant access to the value at the pointer
  const T& operator*() const
  {
    return ptr_->value;
  }

  //  Comparions operators are straightforward
  friend bool operator== ( const tree_iterator& lft, const tree_iterator& rgt )
  { return lft.ptr_ == rgt.ptr_; }
  
  friend bool operator!= ( const tree_iterator& lft, const tree_iterator& rgt )
  { return lft.ptr_ != rgt.ptr_; }

  //  pre-increment
  tree_iterator<T> & operator++( ) 
  { 
    ptr_ = next_inorder( ptr_ );
    return *this;
  }

  //  post-increment is indicated by the dummy int argument
  tree_iterator<T> operator++( int ) 
  {
    tree_iterator<T> temp( *this );
    ptr_ = next_inorder( ptr_ );
    return temp;
  }

  //  pre-decrement
  tree_iterator<T> & operator--( ) 
  { 
    ptr_ = prev_inorder( ptr_ );
    return *this;
  }

  //  post-decrement is indicated by the dummy int argument
  tree_iterator<T> operator--( int ) 
  {
    tree_iterator<T> temp( *this );
    ptr_ = prev_inorder( ptr_ );
    return temp;
  }

private:
  // ****
  // Find the next node in the tree in an inorder traversal.  This
  // must be completed to get the two versions of operator++ to work. 
  TreeNode<T>* next_inorder( TreeNode<T>* p )
  {
  }

  // ****
  // Find the previous node in the tree in an inorder traversal.  This
  // must be completed to get the two versions of operator-- to work. 
  TreeNode<T>* prev_inorder( TreeNode<T>* p )
  {
  }
  
};



///////////////////////////////////////////////////////////////////
/////////////////       Main cs2multiset class          ////////////////
///////////////////////////////////////////////////////////////////


template <class T>
class cs2multiset {
public:
  typedef tree_iterator<T> iterator;

private:
  TreeNode<T>* root_;
  int size_;

public:
  //  Constructor with no arguments
  cs2multiset() : root_(0), size_(0) 
  {}

  //  Copy constructor
  cs2multiset( const cs2multiset<T>& old ) : size_(old.size_)
  {
    root_ = this -> copy_tree( old.root_ );
  }

  // ****
  // Construct a multiset from a vector that is assumed to be in
  // non-decreasing order.  This function should be efficient (can't
  // just call insert N times), and should create a tree where at each
  // node the number of values in the left and right subtrees differ
  // by at most 1.
  cs2multiset( const vector<T> & values )
  {
  }

  //  Destructor
  ~cs2multiset()
  {
    this -> destroy_tree( root_ );
    root_ = 0;
  }

  //  Assignment operator.
  cs2multiset& operator=( const cs2multiset<T>& old )
  {
    if ( old != *this ) {
      this -> destroy_tree( root_ );
      root_ = this ->  copy_tree( (TreeNode<T>*) 0, old.root_ );
      size_ = old.size_;
    }
    return *this;
  }

  int size() const { return size_; }
  
  // ****
  // Insert a value, returning the iterator referencing the location
  // in the multiset
  iterator insert( T const& key_value )
  {
  }

  // ****
  // Find the key_value in the multiset, returning an iterator that
  // references the value.  If the key_value is in the multiset more
  // than once, any one of these can be chosen here.
  iterator find( const T& key_value ) const
  {
  }

  // ****
  // Erase ALL INSTANCES of the key_value in the multiset, returning
  // the total number of instances erased.  Try to make this function
  // as efficient as possible.
  int erase( T const& key_value )
  {
  }

  // ****
  // Erase the entry in the multiset references by the current
  // iterator. 
  void erase( iterator p )
  {
  }

  // ****
  // Return the number of instances of the given key_value in the multiset.
  int count( T const& key_value ) const
  {
  }

  // ****
  // Return an iterator referring to the smallest value in the
  // multiset that is greater than or equal to the key_value.  If the
  // key_value is in the multiset, this will be the first occurrence
  // of the key_value in an in-order traversal.  If the key_value is
  // larger than any value in the set, this will be the end iterator.
  iterator lower_bound( T const& key_value) const
  {
  }

  // ****
  // Return an iterator referring to the smallest value in the
  // multiset that is greater than the key_value.  If the key_value is
  // greater than or equal to any value is the multiset, this will be
  // the end iterator
  iterator upper_bound( T const& key_value) const
  {
  }


  friend std::ostream& operator<< ( std::ostream& ostr, const cs2multiset<T>& s )
  {
    s.print_in_order( ostr, s.root_ );
    return ostr;
  }

  void print_as_sideways_tree( std::ostream& ostr ) const
  {
    print_as_sideways_tree( ostr, root_, 0 );
  }

  iterator begin() const
  { 
    if ( ! root_ )
      return iterator(0);
    else
      {
        TreeNode<T>* p = root_;
        while ( p->left ) p = p->left;
        return iterator(p);
      }
  }

  iterator end() const { return iterator( 0 ); }


private:

  // ****
  TreeNode<T>*  copy_tree( TreeNode<T>* old_root )
  {
  }

  // ****
  void destroy_tree( TreeNode<T>* p )
  {
  }

  void print_in_order( std::ostream& ostr, const TreeNode<T>* p ) const
  {
    if ( p )
      {
        print_in_order( ostr, p->left );
        ostr << p->value << "\n";
        print_in_order( ostr, p->right );
      }
  }

  void print_as_sideways_tree( std::ostream& ostr, const TreeNode<T>* p,
                               int depth  ) const
  {
    if ( p ) 
      {
        print_as_sideways_tree( ostr, p->right, depth+1 );
        for ( int i=0; i<depth; ++i ) ostr << "    ";
        ostr << p->value << "\n";
        print_as_sideways_tree( ostr, p->left, depth+1 );
      }
  }

};



#endif