///////////////////////////////////////////////////////////
// Softwarebauelemente II, C2.1
//
// A template for polymorphic set - designed in MFC-style
// The only parameter is the base class of all elements
// (at least CObject)
// All elements are copied by the interface methods 
// to avoid unexpected behaviour (e.g. external erase)
//
// author:			Stephan Brumme
// last changes:	August 3, 2001

#if !defined(AFX_POLYMORPHICSET_H__BA324DAE_872B_11D5_9BB8_AB7BB57BD00C__INCLUDED_)
#define AFX_POLYMORPHICSET_H__BA324DAE_872B_11D5_9BB8_AB7BB57BD00C__INCLUDED_


#include "stdafx.h"


#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000


template<class C> class CPolymorphicSet : public CObject  
{
public:
    // default constructor
	CPolymorphicSet();
    // copy constructor
    CPolymorphicSet(const CPolymorphicSet<C>& set);

    // destructor
	virtual ~CPolymorphicSet();

    // serialization
    virtual void Serialize(CArchive &ar);
    // invariance
    virtual void AssertValid() const;
    // dump
    virtual void Dump(CDumpContext& dc) const;

    // copy the whole set
    virtual CPolymorphicSet<C>& operator=(const CPolymorphicSet<C>& set);
    virtual CPolymorphicSet<C>& Copy     (const CPolymorphicSet<C>& set);
    // compare two sets
    // value identity
    virtual bool operator==(const CPolymorphicSet<C>& set) const;
    virtual bool EqualValue(const CPolymorphicSet<C>& set) const; 
    // object identity
    virtual bool Equal     (const CPolymorphicSet<C>* set) const;

    // returns number of stored elements
    int Card() const;

    // first stored element
    C* GetFirst();
    // next element
    C* GetNext();
    // gets the element the cursor points to
    C* GetCurrent() const;

    // inserts an element
    int  Insert(const C* element);
    // deletes current element
    void Scratch();
    // finds an element
    bool Find(const C* element);

protected:
// creates a new instance and copies all attributes
    C* Clone(const C* element) const;

    // deletes the whole set
    void ScratchAll();

    // stores all elements in a list
    CList<C*, C*> m_Set; 
    // cursor, may be altered at any time
    POSITION m_Cursor;

};


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


// default constructor
template<class C> CPolymorphicSet<C>::CPolymorphicSet()
{
    // empty set
    m_Cursor = NULL;
}


// copy constructor
template<class C> CPolymorphicSet<C>::CPolymorphicSet(const CPolymorphicSet<C>& set)
{
    operator=(set);
    m_Cursor = m_Set.GetHeadPosition();
}

    
// destructor
template<class C> CPolymorphicSet<C>::~CPolymorphicSet()
{
    ScratchAll();
}


// serialization
template<class C> void CPolymorphicSet<C>::Serialize(CArchive &ar)
{
    // do not forget to serialize CObject's data members
    CObject::Serialize(ar);

    // make use of CArchive's overloaded << and >> operators for *CObject

    if (ar.IsStoring())
    {
        // save the set

        // write cardinality
        ar << m_Set.GetCount();

        // write all elements
        POSITION pos = m_Set.GetHeadPosition();
        while (pos != NULL)
            ar << m_Set.GetNext(pos);
    }
    else
    {
        // load set

        // first, delete old set
        ScratchAll();

        int nCount;
        // load cardinality
        ar >> nCount;
        // load all elements
        for (int i=0; i<nCount; i++)
        {
            C* element;
            ar >> element;
            Insert(element);
            delete element;
        }
    }
}


// invariance
template<class C> void CPolymorphicSet<C>::AssertValid() const
{
    CObject::AssertValid();

    // if the set is empty then cursor must be NULL
    if (m_Set.IsEmpty())
    {
        ASSERT(m_Cursor == NULL);
        return;
    }

    // each element may be present in set at most once
    // cursor must point to an element
    POSITION pos = m_Set.GetHeadPosition();
    bool bValidCursor = false;
    while (pos != NULL)
    {
        // element that the cursor points to was found ?
        if (pos == m_Cursor)
            bValidCursor = true;

        // get element
        C* element = m_Set.GetNext(pos);
        POSITION posfind = pos;
        // compare to the remaining elements
        while (posfind != NULL)
        {
            C* compare = m_Set.GetNext(posfind);
            // no two equal elements are allowed
            ASSERT(!(*element == *compare));
        }
    }

    // cursor validated ?
    ASSERT(bValidCursor);
}


// dump
template<class C> void CPolymorphicSet<C>::Dump(CDumpContext& dc) const
{
    CObject::Dump(dc);

    dc << Card() << " elements, cursor points to " << m_Cursor << "\n";

    POSITION pos = m_Set.GetHeadPosition();
    while (pos != NULL)
        dc << m_Set.GetNext(pos) << "\n";
}


// copy the whole set
template<class C> CPolymorphicSet<C>& CPolymorphicSet<C>::operator=(const CPolymorphicSet<C>& set)
{
    // delete old elements
    m_Set.RemoveAll();

    POSITION pos = set.m_Set.GetHeadPosition();
    while (pos != NULL)
    {
        // save current position
        POSITION cursor = pos;

        // clone each element
        C* element = set.m_Set.GetNext(pos);
        C* copy    = Clone(element);
        m_Set.AddTail(copy);

        // set cursor
        // we can't use set.m_Cursor directly because we copied all elements 
        // and therefore lost their old memory address
        if (cursor == set.m_Cursor)
            m_Cursor = m_Set.GetTailPosition();
    }

    return *this;
}


// see operator=
template<class C> CPolymorphicSet<C>& CPolymorphicSet<C>::Copy(const CPolymorphicSet<C>& set)
{
    return operator=(set);
}


// compare two sets
template<class C> bool CPolymorphicSet<C>::operator==(const CPolymorphicSet<C>& set) const
{
    // the cursors may differ !

    // same number of elements is required
    if (m_Set.GetCount() != set.m_Set.GetCount())
        return false;

    // each element of this set must be found in the other set
    POSITION pos = m_Set.GetHeadPosition();
    while (pos != NULL)
    {
        C* element = m_Set.GetNext(pos);
        if (!set.m_Set.Find(element))
            return false;
    }

    // all elements were found, sets must be equal
    return true;
}


// see operator==
template<class C> bool CPolymorphicSet<C>::EqualValue(const CPolymorphicSet<C>& set) const
{
    return operator==(set);
}


// object identity
template<class C> bool CPolymorphicSet<C>::Equal(const CPolymorphicSet<C>* set) const
{
    return (set == this);
}


// returns number of stored elements
template<class C> int CPolymorphicSet<C>::Card() const
{
    return m_Set.GetCount();
}


// first stored element
template<class C> C* CPolymorphicSet<C>::GetFirst()
{
    // set must not be empty
    ASSERT(!m_Set.IsEmpty());

    // set cursor
    m_Cursor = m_Set.GetHeadPosition();

    // clone first element
    return GetCurrent();
}


// next element
template<class C> C* CPolymorphicSet<C>::GetNext()
{
    // set must not be empty
    ASSERT(!m_Set.IsEmpty());
    // cursor must not be at the end of the set
    ASSERT(m_Cursor != NULL); 

    // set cursor
    m_Set.GetNext(m_Cursor);

    // clone element
    return GetCurrent();
}


// gets the element the cursor points to
template<class C> C* CPolymorphicSet<C>::GetCurrent() const
{
    // cursor must not be at the end of the set
    ASSERT(m_Cursor != NULL); 

    // generate copy
    C* copy = Clone(m_Set.GetAt(m_Cursor));

    return copy;
}


// inserts an element
template<class C> int CPolymorphicSet<C>::Insert(const C* element)
{
    // don't insert an object twice
    if (Find(element))
        return -1;
    
    // add a copy to our set, change cursor
    m_Cursor = m_Set.AddTail(Clone(element));

    // return index in the set
    return m_Set.GetCount()-1;
}


// deletes current element
template<class C> void CPolymorphicSet<C>::Scratch()
{
    // cursor must not be at the end of the set
    ASSERT(m_Cursor != NULL);

    // store current cursor
    POSITION removepos = m_Cursor;
    // go on to the next element (else we lose it after erasing this element)
    m_Set.GetNext(m_Cursor);

    // remove element the cursor pointed to previously
    delete m_Set.GetAt(removepos);
    m_Set.RemoveAt(removepos);
}


// looks for an element
template<class C> bool CPolymorphicSet<C>::Find(const C* element)
{
    // only non-empty sets
    if (m_Set.IsEmpty())
        return false;

    // iterate through the whole list
    POSITION pos = m_Set.GetHeadPosition();
    while (pos != NULL)
    {
        // store position in case we find a match
        POSITION storepos = pos;

        // get an element we compare to
        C* compare  = m_Set.GetNext(pos);
        // equal ?
        if (*element == *compare)
        {
            // yes, set cursor and return "success !"
            m_Cursor = storepos;
            return true;
        }
    }

    // element is not part of the set
    return false;
}


// creates a new instance and copies all attributes
template<class C> C* CPolymorphicSet<C>::Clone(const C* element) const
{
    // create new instance (care for correct class !)
    C* copy = (C*)element->GetRuntimeClass()->CreateObject();
    // copy attributes
    *copy = *element;

    return copy;
}


// deletes the whole set
template<class C> void CPolymorphicSet<C>::ScratchAll()
{
    while (!m_Set.IsEmpty())
    {
        delete m_Set.GetHead();
        m_Set.RemoveHead();
    }
}


#endif // !defined(AFX_POLYMORPHICSET_H__BA324DAE_872B_11D5_9BB8_AB7BB57BD00C__INCLUDED_)