#include <stdlib.h>   // Provides size_t and NULL
#include "node1.h"    // Provides node class.

class bag
{
    public:
        // TYPEDEFS
        typedef size_t size_type;
        typedef node::value_type value_type;
        // CONSTRUCTORS and DESTRUCTOR
        bag( );
        bag(const bag& source);
	     ~bag( );
        // MODIFICATION MEMBER FUNCTIONS
        size_type erase(const value_type& target);
        bool erase_one(const value_type& target);
        void insert(const value_type& entry);
        void operator +=(const bag& addend);
        void operator =(const bag& source);
        // CONSTANT MEMBER FUNCTIONS
        size_type size( ) const { return many_nodes; }
        size_type count(const value_type& target) const;
        value_type grab( ) const;
        value_type max1() const;
        value_type max2() const;
        value_type max3() const;
        node* max4() const;
        friend void operator >> (istream& ins,  bag& b);
        friend void operator << (ostream& outs, bag& b);
    private:
        node *head_ptr;       // List head pointer
        size_type many_nodes; // Number of nodes on the list
};

bag::bag( )
{
	head_ptr = NULL;
	many_nodes = 0;
}

bag::bag(const bag& source)
{
   node *tail_ptr;  // Needed for argument of list_copy

   list_copy(source.head_ptr, head_ptr, tail_ptr);
   many_nodes = source.many_nodes;
}
    
bag::~bag( )
{
   list_clear(head_ptr);
   many_nodes = 0;
}

bag::size_type bag::count(const value_type& target) const
{
	size_type answer;
	const node *cursor; // Use const node* since we don't change the nodes.
	
	answer = 0;
	cursor = list_search(head_ptr, target);
	while (cursor != NULL)
	{
	    // Each time that cursor is not NULL, we have another occurrence of
	    // target, so we add one to answer, and move cursor to the next
	    // occurrence of the target.
	    ++answer;
	    cursor = cursor->link( );
	    cursor = list_search(cursor, target);
	}
	return answer;
}

bag::size_type bag::erase(const value_type& target)
{
   size_type answer = 0;
   node *target_ptr;

   target_ptr = list_search(head_ptr, target);
   while (target_ptr != NULL)
   {
       // Each time that target_ptr is not NULL, we have another occurrence
	    // of target. We remove this target using the same technique that
	    // was used in erase_one.
       target_ptr->set_data( head_ptr->data( ) );
       target_ptr = target_ptr->link( );
       target_ptr = list_search(target_ptr, target);
       list_head_remove(head_ptr);
	    --many_nodes;
       ++answer;
   }
   return answer;
}
    
bool bag::erase_one(const value_type& target)
{
	node *target_ptr;
	
	target_ptr = list_search(head_ptr, target);
	if (target_ptr == NULL)
	    return false; // target isn't in the bag, so no work to do
	target_ptr->set_data( head_ptr->data( ) );
	list_head_remove(head_ptr);
	--many_nodes;
	return true;
}

bag::value_type bag::grab( ) const
{
	size_type i;
	const node *cursor; // Use const node* since we don't change the nodes.

	assert(size( ) > 0);
	i = (rand( ) % size( )) + 1;
	cursor = list_locate(head_ptr, i);
	return cursor->data( );
}

void bag::insert(const value_type& entry)
{
	list_head_insert(head_ptr, entry);
	++many_nodes;
}

void bag::operator +=(const bag& addend)
{
	node *copy_head_ptr;
	node *copy_tail_ptr;
	
	if (addend.many_nodes > 0)
	{
	    list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
	    copy_tail_ptr->set_link( head_ptr ); 
	    head_ptr = copy_head_ptr;
	    many_nodes += addend.many_nodes;
	}
}

void bag::operator =(const bag& source)
{
	node *tail_ptr; // Needed for argument to list_copy

	if (this == &source) // why? in case of self-assignment like b1 = b1
           return;

	list_clear(head_ptr);
	many_nodes = 0;
	list_copy(source.head_ptr, head_ptr, tail_ptr);
	many_nodes = source.many_nodes;
}

// NONMEMBER FUNCTIONS for the bag class:
bag operator +(const bag& b1, const bag& b2)
{
	bag answer;

	answer += b1; 
	answer += b2;
	return answer;
}

void operator >> (istream& ins, bag& b)
{
   bag::value_type number;
   cout << "Enter numbers, -1 when done: ";
   ins >> number;
   while (number >= 0)
   {
      /*list_head_insert(b.head_ptr, number);
        b.many_nodes++;
      */
      b.insert(number);
      ins >> number;
   }
}

void operator << (ostream& outs, bag& b)
{
    list_display(outs, b.head_ptr);
}


////////////////////////////////////////////////////////////////////////////////

// to maintain a max variable found so far
bag::value_type bag::max1() const
{  assert(head_ptr != NULL);
   bag::value_type max = head_ptr->data(); // treat head as the max node
   node* cursor = head_ptr->link();



}

// to maintain a pointer (not a value) pointing the max node
bag::value_type bag::max2() const
{  assert(head_ptr != NULL);
   node* max_ptr = head_ptr; // treat head_ptr as the ptr poiting the max node





}


// to maintain a pointer (not a value) pointing the max node and return the
// pointer, not the max value!
node* bag::max3() const
{  assert(head_ptr != NULL);
   node* max_ptr = head_ptr; // treat head_ptr as the ptr poiting the max node
                             


}

////////////////////////////////////////////////////////////////////////////////

void main( )
{
    bag b1, b2, b3;

    cin >> b1;
    cout << b1;

    cin >> b2;
    cout << b2;

    b3 = b1 + b2;
    cout << "B1 + B2 = " << b3;

    cout << "Method 1: Max item in b3 = " << b3.max1() << endl;
    cout << "Method 2: Max item in b3 = " << b3.max2() << endl;
    cout << "Method 3: Max item in b3 = " << b3.max3()->data() << endl;
}