// the 3rd version of the bag using Linked List
// we no longer need to check whether the bag reaches its capacity.
#include "linklist.h"   // Provides everything about Linked list
#include <conio.h>
class Bag
{
    public:
        // TYPEDEF
        typedef Node::Item Item;
        // CONSTRUCTORS and DESTRUCTOR
        Bag( );
        Bag(const Bag& source);
        ~Bag( );
        // MODIFICATION functions
        void insert(const Item& entry);
        void remove(const Item& target);
        void operator +=(const Bag& addend);
        void operator -=(const Bag& subend);
        void operator =(const Bag& source);
        // CONSTANT functions
        size_t size( ) const { return many_nodes; }
        size_t occurrences(const Item& target) const;
        Item grab( ) const;
        friend void operator >> (istream& ins, Bag& b);
        friend void operator << (ostream& outs, Bag& b);
        friend Bag operator ^ (const Bag& b1, const Bag& b2);
    private:
        Node *head_ptr;    // Head pointer for the list of items
        size_t 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;
}

void Bag::remove(const Item& target)
{
    Node *target_ptr;

    target_ptr = list_search(head_ptr, target);
    if (target_ptr == NULL)
        return; // target isn't in the Bag, so no work to do
    target_ptr->data = head_ptr->data;  // see page 242
    list_head_remove(head_ptr);
    many_nodes--;
}

size_t Bag::occurrences(const Item& target) const
{
    size_t answer;
    Node *cursor;

    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;
}

void Bag::insert(const Item& 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->link = head_ptr;
        head_ptr = copy_head_ptr;
        many_nodes += addend.many_nodes;
    }
}

void Bag::operator -=(const Bag& subend)
{


}

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

    if (source.head_ptr == head_ptr)
        return;

    list_clear(head_ptr);
    many_nodes = 0;

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

Bag::Item Bag::grab( ) const
{
    size_t i;
    Node *cursor;

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

Bag operator -(const Bag& b1, const Bag& b2)
{
    Bag answer;

    answer = b1;
    answer -= b2;
    return answer;
}

Bag operator +(const Bag& b1, const Bag& b2)
{
    Bag answer;

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

Bag operator ^ (const Bag& b1, const Bag& b2)
{







}

void operator >> (istream& ins, Bag& b)
{
   Bag::Item 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(b.head_ptr);
}

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

    cin >> b1;
    cout << b1;

    cin >> b2;
    cout << b2;

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

    b3 = b1 ^ b2;
    cout << "B1 ^ B2 = " << b3;
    getch();
}