1088 lines
32 KiB
C++
1088 lines
32 KiB
C++
//-----------------------------------------------------------------------------
|
|
// Microsoft OLE DB RowsetViewer
|
|
// Copyright (C) 1994 - 2000 By Microsoft Corporation.
|
|
//
|
|
// @doc
|
|
//
|
|
// @module LIST.H
|
|
//
|
|
//-----------------------------------------------------------------------------------
|
|
|
|
#ifndef _LIST_H_
|
|
#define _LIST_H_
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// Includes
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
#include <limits.h> ///ULONG_MAX
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// Defines
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
typedef void* POSITION;
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CNode
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE> class CNode
|
|
{
|
|
public:
|
|
// constructors
|
|
CNode(CNode* pPrevNode, CNode* pNextNode);
|
|
virtual ~CNode();
|
|
|
|
// members
|
|
TYPE m_data; // element data
|
|
CNode* m_pNext; // next CNode
|
|
CNode* m_pPrev; // prev CNode
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CNode::CNode
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE> CNode<TYPE>::CNode(CNode* pPrevNode, CNode* pNextNode)
|
|
{
|
|
//Constructor
|
|
m_pPrev = pPrevNode;
|
|
m_pNext = pNextNode;
|
|
|
|
//NOTE: The constructor doesn't have an element passed in for
|
|
//data. This is so we don't have a copy of the parameter and then
|
|
//need to copy it for assignment...
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CNode::~CNode
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE> CNode<TYPE>::~CNode()
|
|
{
|
|
//Destructor
|
|
m_pPrev = NULL;
|
|
m_pNext = NULL;
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> class CList
|
|
{
|
|
public:
|
|
|
|
//constructors
|
|
CList();
|
|
virtual ~CList();
|
|
|
|
//members
|
|
private:
|
|
//data
|
|
CNode<TYPE>* m_pNodeHead; // Head of CList
|
|
CNode<TYPE>* m_pNodeTail; // Tail of CList
|
|
|
|
ULONG m_ulElements; // Elements in the list
|
|
|
|
public:
|
|
//list modifying operations
|
|
virtual POSITION AddHead(ARG_TYPE element); // Add to Head
|
|
virtual POSITION AddTail(ARG_TYPE element); // Add to Tail
|
|
|
|
virtual POSITION InsertBefore(POSITION position, ARG_TYPE element); // Add before position
|
|
virtual POSITION InsertAfter(POSITION position, ARG_TYPE element); // Add after position
|
|
|
|
virtual TYPE RemoveHead(); // Remove from Head
|
|
virtual TYPE RemoveTail(); // Remove from Tail
|
|
virtual TYPE RemoveAt(POSITION position); // RemoveAt position
|
|
void RemoveAll(); // Remove all elements
|
|
|
|
//Peek methods
|
|
inline POSITION GetHeadPosition() const { return m_pNodeHead; }
|
|
inline POSITION GetTailPosition() const { return m_pNodeTail; }
|
|
|
|
inline TYPE GetHead() const { ASSERT(m_pNodeHead); return m_pNodeHead->m_data; }
|
|
inline TYPE& GetHead() { ASSERT(m_pNodeHead); return m_pNodeHead->m_data; }
|
|
inline TYPE GetTail() const { ASSERT(m_pNodeTail); return m_pNodeTail->m_data; }
|
|
inline TYPE& GetTail() { ASSERT(m_pNodeTail); return m_pNodeTail->m_data; }
|
|
|
|
virtual TYPE GetNext(POSITION& position) const; // Next element
|
|
virtual TYPE& GetNext(POSITION& position); // Next element
|
|
virtual TYPE GetPrev(POSITION& position) const; // Prev element
|
|
virtual TYPE& GetPrev(POSITION& position); // Prev element
|
|
|
|
//Data methods
|
|
virtual TYPE GetAt(POSITION position) const; //Get element value
|
|
virtual TYPE& GetAt(POSITION position); //Get element value
|
|
virtual void SetAt(POSITION position, ARG_TYPE element); //Set element value
|
|
|
|
//Array-like methods
|
|
virtual POSITION FindIndex(ULONG iIndex) const; //Index element
|
|
virtual POSITION Find(ARG_TYPE element, POSITION startAfter = NULL) const;
|
|
|
|
//informational methods
|
|
inline BOOL IsEmpty() const { return m_ulElements==0; }
|
|
inline ULONG GetCount() const { return m_ulElements; }
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::CList
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> CList<TYPE, ARG_TYPE>::CList()
|
|
{
|
|
//constructor
|
|
m_pNodeHead = NULL;
|
|
m_pNodeTail = NULL;
|
|
m_ulElements = 0;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::~CList
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> CList<TYPE, ARG_TYPE>::~CList()
|
|
{
|
|
//Remove all elements
|
|
RemoveAll();
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::AddHead
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> POSITION CList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE element)
|
|
{
|
|
//Add to the Head of the CList, (stack)
|
|
CNode<TYPE>* pNewNode = new CNode<TYPE>(NULL, m_pNodeHead);
|
|
if(pNewNode)
|
|
{
|
|
pNewNode->m_data = element;
|
|
|
|
//If there was a list hook the head->prev to the new head
|
|
if(m_pNodeHead)
|
|
m_pNodeHead->m_pPrev = pNewNode;
|
|
else
|
|
m_pNodeTail = pNewNode;
|
|
|
|
m_pNodeHead = pNewNode;
|
|
m_ulElements++;
|
|
}
|
|
return pNewNode;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::AddTail
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> POSITION CList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE element)
|
|
{
|
|
//Add to the m_pNodeTail of the CList
|
|
CNode<TYPE>* pNewNode = new CNode<TYPE>(m_pNodeTail, NULL);
|
|
if(pNewNode)
|
|
{
|
|
pNewNode->m_data = element;
|
|
|
|
if(m_pNodeTail != NULL)
|
|
m_pNodeTail->m_pNext = pNewNode;
|
|
else
|
|
m_pNodeHead = pNewNode;
|
|
|
|
m_pNodeTail = pNewNode;
|
|
m_ulElements++;
|
|
}
|
|
return pNewNode;
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::GetNext
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE CList<TYPE, ARG_TYPE>::GetNext(POSITION& position) const
|
|
{
|
|
ASSERT(position);
|
|
|
|
//Set position to the next element
|
|
CNode<TYPE>* pNode = (CNode<TYPE>*)position;
|
|
position = pNode->m_pNext;
|
|
|
|
//return the current element
|
|
return pNode->m_data;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::GetNext
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE& CList<TYPE, ARG_TYPE>::GetNext(POSITION& position)
|
|
{
|
|
ASSERT(position);
|
|
|
|
//Set position to the next element
|
|
CNode<TYPE>* pNode = (CNode<TYPE>*)position;
|
|
position = pNode->m_pNext;
|
|
|
|
//return the current element
|
|
return pNode->m_data;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::GetPrev
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE CList<TYPE, ARG_TYPE>::GetPrev(POSITION& position) const
|
|
{
|
|
ASSERT(position);
|
|
|
|
//Set position to the next element
|
|
CNode<TYPE>* pNode = (CNode<TYPE>*)position;
|
|
position = pNode->m_pPrev;
|
|
|
|
//return the current element
|
|
return pNode->m_data;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::GetPrev
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE& CList<TYPE, ARG_TYPE>::GetPrev(POSITION& position)
|
|
{
|
|
ASSERT(position);
|
|
|
|
//Set position to the next element
|
|
CNode<TYPE>* pNode = (CNode<TYPE>*)position;
|
|
position = pNode->m_pPrev;
|
|
|
|
//return the current element
|
|
return pNode->m_data;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::GetAt
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE CList<TYPE, ARG_TYPE>::GetAt(POSITION position) const
|
|
{
|
|
ASSERT(position);
|
|
CNode<TYPE>* pNode = (CNode<TYPE>*)position;
|
|
return pNode->m_data;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::GetAt
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE& CList<TYPE, ARG_TYPE>::GetAt(POSITION position)
|
|
{
|
|
ASSERT(position);
|
|
CNode<TYPE>* pNode = (CNode<TYPE>*)position;
|
|
return pNode->m_data;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::SetAt
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> void CList<TYPE, ARG_TYPE>::SetAt(POSITION position, ARG_TYPE element)
|
|
{
|
|
ASSERT(position);
|
|
|
|
//Save the old data
|
|
CNode<TYPE>* pNode = (CNode<TYPE>*)position;
|
|
|
|
//Store new data
|
|
pNode->m_data = element;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::RemoveHead
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE CList<TYPE, ARG_TYPE>::RemoveHead()
|
|
{
|
|
//Remove and return from the Head of the List
|
|
ASSERT(m_pNodeHead);
|
|
|
|
CNode<TYPE>* pOldHead = m_pNodeHead; // pointer to the Removed node
|
|
TYPE element = GetHead(); //make a copy, before deleteing
|
|
|
|
m_pNodeHead = pOldHead->m_pNext; // reroute Head to exclude the first element
|
|
if(m_pNodeHead)
|
|
{
|
|
ASSERT(m_pNodeTail);
|
|
m_pNodeHead->m_pPrev = NULL;
|
|
}
|
|
else
|
|
{
|
|
m_pNodeTail = NULL;
|
|
}
|
|
|
|
m_ulElements--;
|
|
delete pOldHead; // delete head
|
|
return element;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::RemoveTail
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE CList<TYPE, ARG_TYPE>::RemoveTail()
|
|
{
|
|
//Remove and return from the m_pNodeTail of the CList
|
|
ASSERT(m_pNodeTail);
|
|
|
|
CNode<TYPE>* pOldTail = m_pNodeTail;
|
|
TYPE element = GetTail(); //make a copy before deleteing
|
|
|
|
m_pNodeTail = pOldTail->m_pPrev;
|
|
if(m_pNodeTail)
|
|
{
|
|
ASSERT(m_pNodeHead);
|
|
m_pNodeTail->m_pNext = NULL;
|
|
}
|
|
else
|
|
{
|
|
m_pNodeHead = NULL;
|
|
}
|
|
|
|
m_ulElements--;
|
|
delete pOldTail;
|
|
return element;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::RemoveAt
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> TYPE CList<TYPE, ARG_TYPE>::RemoveAt(POSITION position)
|
|
{
|
|
//Remove CList[position]
|
|
ASSERT(position);
|
|
CNode<TYPE>* pOldNode = (CNode<TYPE>*)position;
|
|
TYPE element = GetAt(position); //make a copy before deleteing
|
|
|
|
// If removing the head
|
|
if(pOldNode == m_pNodeHead)
|
|
{
|
|
m_pNodeHead = pOldNode->m_pNext;
|
|
}
|
|
else
|
|
{
|
|
pOldNode->m_pPrev->m_pNext = pOldNode->m_pNext;
|
|
}
|
|
|
|
if (pOldNode == m_pNodeTail)
|
|
{
|
|
m_pNodeTail = pOldNode->m_pPrev;
|
|
}
|
|
else
|
|
{
|
|
pOldNode->m_pNext->m_pPrev = pOldNode->m_pPrev;
|
|
}
|
|
|
|
m_ulElements--;
|
|
delete pOldNode;
|
|
return element;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::RemoveAll
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> void CList<TYPE, ARG_TYPE>::RemoveAll()
|
|
{
|
|
// Remove all items from the CList
|
|
CNode<TYPE>* pNode = m_pNodeHead;
|
|
while(pNode)
|
|
{
|
|
CNode<TYPE>* pTemp = pNode;
|
|
pNode = pNode->m_pNext;
|
|
delete pTemp;
|
|
}
|
|
|
|
m_pNodeHead = NULL;
|
|
m_pNodeTail = NULL;
|
|
m_ulElements = 0;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::InsertBefore
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> POSITION CList<TYPE, ARG_TYPE>::InsertBefore(POSITION position, ARG_TYPE element)
|
|
{
|
|
//insert before the position
|
|
if(position == m_pNodeHead) // Add before Head
|
|
return AddHead(element);
|
|
|
|
CNode<TYPE>* pOldNode = (CNode<TYPE>*)position;
|
|
|
|
//otherwise a little more difficult
|
|
CNode<TYPE>* pNewNode = new CNode<TYPE>(pOldNode->m_pPrev, pOldNode);
|
|
if(pNewNode)
|
|
{
|
|
pNewNode->m_data = element;
|
|
|
|
//Hook up before after nodes to it
|
|
if(pOldNode->m_pPrev)
|
|
{
|
|
pOldNode->m_pPrev->m_pNext = pNewNode;
|
|
}
|
|
else
|
|
{
|
|
m_pNodeHead = pNewNode;
|
|
}
|
|
|
|
m_ulElements++;
|
|
}
|
|
return pNewNode;
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::InsertAfter
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> POSITION CList<TYPE, ARG_TYPE>::InsertAfter(POSITION position, ARG_TYPE element)
|
|
{
|
|
//insert after the position
|
|
if(position == m_pNodeTail) // Add after the m_pNodeTail
|
|
return AddTail(element);
|
|
|
|
CNode<TYPE>* pOldNode = (CNode<TYPE>*)position;
|
|
|
|
//other wise a little more difficult
|
|
CNode<TYPE>* pNewNode = new CNode<TYPE>(pOldNode, pOldNode->m_pNext);
|
|
if(pNewNode)
|
|
{
|
|
pNewNode->m_data = element;
|
|
|
|
//Hook up before after nodes to it
|
|
if(pOldNode->m_pNext)
|
|
{
|
|
pOldNode->m_pNext->m_pPrev = pNewNode;
|
|
}
|
|
else
|
|
{
|
|
m_pNodeTail = pNewNode;
|
|
}
|
|
|
|
m_ulElements++;
|
|
}
|
|
return pNewNode;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::FindIndex
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> POSITION CList<TYPE, ARG_TYPE>::FindIndex(ULONG iIndex) const
|
|
{
|
|
ASSERT(iIndex>=0 && iIndex<m_ulElements);
|
|
|
|
CNode<TYPE>* pNode = m_pNodeHead;
|
|
|
|
//Find the specified index
|
|
while(iIndex--)
|
|
pNode = pNode->m_pNext;
|
|
|
|
return (POSITION)pNode;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CList::Find
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class ARG_TYPE> POSITION CList<TYPE, ARG_TYPE>::Find(ARG_TYPE element, POSITION pPosAfter) const
|
|
{
|
|
CNode<TYPE>* pNode = m_pNodeHead;
|
|
if(pPosAfter)
|
|
pNode = ((CNode<TYPE>*)pPosAfter)->m_pNext;
|
|
|
|
//return pointer to found element
|
|
for(CNode<TYPE>* p = pNode; p != NULL; p = p->m_pNext)
|
|
if(p->m_data == element)
|
|
return p; // return position to found CNode
|
|
|
|
return NULL; // return NULL if not found
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CAssoc
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class KEY, class VALUE> class CAssoc
|
|
{
|
|
public:
|
|
// constructors
|
|
CAssoc();
|
|
virtual ~CAssoc();
|
|
|
|
// members
|
|
KEY m_key; // key
|
|
VALUE m_value; // element data
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CAssoc::CAssoc
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class KEY, class VALUE> CAssoc<KEY, VALUE>::CAssoc()
|
|
{
|
|
//Constructor
|
|
// m_key = key;
|
|
// m_value = value; // element data
|
|
|
|
//NOTE: The constructor doesn't have an element passed in for
|
|
//data. This is so we don't have a copy of the parameter and then
|
|
//need to copy it for assignment...
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CAssoc::~CAssoc
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class KEY, class VALUE> CAssoc<KEY, VALUE>::~CAssoc()
|
|
{
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
class CMap
|
|
{
|
|
public:
|
|
// Construction
|
|
CMap();
|
|
virtual ~CMap();
|
|
|
|
// number of elements
|
|
int GetCount();
|
|
BOOL IsEmpty();
|
|
|
|
// Lookup
|
|
BOOL Lookup(ARG_KEY key, VALUE& rValue);
|
|
|
|
// add a new (key, value) pair
|
|
BOOL SetAt(ARG_KEY key, ARG_VALUE newValue);
|
|
|
|
// removing existing (key, ?) pair
|
|
BOOL RemoveKey(ARG_KEY key);
|
|
void RemoveAll();
|
|
|
|
// iterating all (key, value) pairs
|
|
POSITION GetStartPosition();
|
|
void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue);
|
|
|
|
// Implementation
|
|
protected:
|
|
POSITION GetPosition(ARG_KEY key);
|
|
CAssoc<KEY, VALUE>* AssocFromPos(POSITION);
|
|
|
|
CList<CAssoc<KEY, VALUE>*, CAssoc<KEY, VALUE>*> m_listValues;
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CMap()
|
|
{
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// ~CMap
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CMap()
|
|
{
|
|
m_listValues.RemoveAll();
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::GetPosition
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
POSITION CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetPosition(ARG_KEY key)
|
|
{
|
|
//Find this "key" in the list...
|
|
//NOTE: This is an extremly slow process for a CMap class.
|
|
//This is a linear search to just make the code simple and quick,
|
|
//This really should be a hashtable lookup
|
|
POSITION pos = m_listValues.GetHeadPosition();
|
|
while(pos)
|
|
{
|
|
if(AssocFromPos(pos)->m_key == key)
|
|
return pos;
|
|
m_listValues.GetNext(pos);
|
|
}
|
|
|
|
return NULL;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::AssocFromPos
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
CAssoc<KEY, VALUE>* CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssocFromPos(POSITION pos)
|
|
{
|
|
if(!pos)
|
|
return NULL;
|
|
|
|
CNode<CAssoc<KEY, VALUE>*>* pNode = (CNode<CAssoc<KEY, VALUE>*>*)pos;
|
|
return pNode->m_data;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::GetStartPosition
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
POSITION CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition()
|
|
{
|
|
return m_listValues.GetHeadPosition();
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::GetCount
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
int CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount()
|
|
{
|
|
return m_listValues.GetCount();
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::IsEmpty
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::IsEmpty()
|
|
{
|
|
return m_listValues.IsEmpty();
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::Lookup
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue)
|
|
{
|
|
POSITION pos = GetPosition(key);
|
|
if(!pos)
|
|
return FALSE;
|
|
|
|
rValue = AssocFromPos(pos)->m_value;
|
|
return TRUE;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::RemoveAll
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
|
|
{
|
|
m_listValues.RemoveAll();
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::RemoveKey
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveKey(ARG_KEY key)
|
|
// remove key - return TRUE if removed
|
|
{
|
|
//Find the key in the List...
|
|
POSITION pos = GetPosition(key);
|
|
if(pos == NULL)
|
|
return FALSE;
|
|
|
|
//Remove this Node...
|
|
m_listValues.RemoveAt(pos);
|
|
return TRUE;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::SetAt
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::SetAt(ARG_KEY key, ARG_VALUE value)
|
|
{
|
|
//Try to find this key...
|
|
POSITION pos = GetPosition(key);
|
|
if(pos)
|
|
{
|
|
//Found already, just change the value...
|
|
AssocFromPos(pos)->m_value = value;
|
|
}
|
|
else
|
|
{
|
|
//Not found, just need to add to the list...
|
|
CAssoc<KEY, VALUE>* pCAssoc = new CAssoc<KEY, VALUE>;
|
|
if(!pCAssoc)
|
|
return FALSE;
|
|
|
|
pCAssoc->m_key = key;
|
|
pCAssoc->m_value = value;
|
|
|
|
//Add it to the list...
|
|
m_listValues.AddTail(pCAssoc);
|
|
}
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CMap::GetNextAssoc
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
|
|
void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(POSITION& rNextPosition,
|
|
KEY& rKey, VALUE& rValue)
|
|
{
|
|
if(rNextPosition)
|
|
{
|
|
CAssoc<KEY, VALUE>* pCAssoc = AssocFromPos(rNextPosition);
|
|
rKey = pCAssoc->m_key;
|
|
rValue = pCAssoc->m_value;
|
|
|
|
//Update the position to the next item, for iteration...
|
|
m_listValues.GetNext(rNextPosition);
|
|
}
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX = ULONG> class CVector
|
|
{
|
|
public:
|
|
|
|
//constructors
|
|
CVector(IDX ulLowerBound = 0, IDX ulGrowSize = 10);
|
|
virtual ~CVector();
|
|
|
|
//array modifying operations
|
|
virtual TYPE* AddElement(TYPE element);
|
|
virtual void RemoveAll();
|
|
|
|
//insertion deletion routines
|
|
virtual TYPE* InsertAt(IDX iIndex, TYPE element); // Insert element at index
|
|
virtual void RemoveAt(IDX iIndex); // Remove element at index
|
|
|
|
//Attaching
|
|
virtual void Attach(CVector& rVector);
|
|
virtual void Attach(IDX cElements, TYPE* rgElements);
|
|
virtual void Detach(IDX* pcElements, TYPE** prgElements);
|
|
|
|
//Array-like methods
|
|
virtual TYPE& GetElement(IDX iIndex);
|
|
virtual TYPE& operator[](IDX iIndex) { return GetElement(iIndex); }
|
|
|
|
//informational methods
|
|
virtual const IDX GetCount() { return m_cElements; }
|
|
virtual const TYPE* GetElements() const { return m_rgElements; }
|
|
|
|
protected:
|
|
//data
|
|
IDX m_ulMaxSize; // MAX sizeof array
|
|
IDX m_ulGrowSize; // Size to Grow for each allocation
|
|
IDX m_ulLowerBound; // LowerBound of array
|
|
IDX m_cElements; // Number of elements
|
|
TYPE* m_rgElements; // Array of elements
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector::CVector
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> CVector<TYPE, IDX>::CVector(IDX ulLowerBound, IDX ulGrowSize)
|
|
{
|
|
//construct the array
|
|
m_ulLowerBound = ulLowerBound;
|
|
m_ulMaxSize = 0;
|
|
m_ulGrowSize = ulGrowSize;
|
|
|
|
m_cElements = 0;
|
|
m_rgElements = NULL;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector::~CVector
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> CVector<TYPE, IDX>::~CVector()
|
|
{
|
|
//Delete the Array
|
|
CoTaskMemFree(m_rgElements);
|
|
m_rgElements = NULL;
|
|
m_cElements = 0;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////
|
|
// TPropSets::Attach
|
|
//
|
|
///////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> void CVector<TYPE, IDX>::Attach(CVector& rVector)
|
|
{
|
|
//Detach from passed in object
|
|
IDX cElements = 0;
|
|
TYPE* rgElements = NULL;
|
|
rVector.Detach(&cElements, &rgElements);
|
|
|
|
//Now Attch them to our object
|
|
Attach(cElements, rgElements);
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////
|
|
// CVector::Attach
|
|
//
|
|
///////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> void CVector<TYPE, IDX>::Attach(IDX cElements, TYPE* rgElements)
|
|
{
|
|
RemoveAll();
|
|
CoTaskMemFree(m_rgElements);
|
|
|
|
m_ulMaxSize = cElements;
|
|
m_cElements = cElements;
|
|
m_rgElements = rgElements;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////
|
|
// CVector::Detach
|
|
//
|
|
///////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> void CVector<TYPE, IDX>::Detach(IDX* pcElements, TYPE** prgElements)
|
|
{
|
|
ASSERT(pcElements);
|
|
ASSERT(prgElements);
|
|
|
|
//Give our elements to the user...
|
|
*pcElements = m_cElements;
|
|
*prgElements = m_rgElements;
|
|
|
|
//We are done with them (consumer owns them...)
|
|
m_ulMaxSize = 0;
|
|
m_cElements = 0;
|
|
m_rgElements = NULL;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector::RemoveAll
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> void CVector<TYPE, IDX>::RemoveAll()
|
|
{
|
|
//NOTE: We don't actually free the array, for optmizations.
|
|
//We just reset the count of elements, and m_ulMaxSize records the amount of
|
|
//memory that can be reused without needing reallocations...
|
|
m_cElements = 0;
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector::RemoveAt
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> void CVector<TYPE, IDX>::RemoveAt(IDX iIndex)
|
|
{
|
|
//Remove CVector[position]
|
|
iIndex -= m_ulLowerBound;
|
|
ASSERT(iIndex < m_cElements);
|
|
|
|
//May Need to shift the entire array after this element up
|
|
//If it is not the last row in the vector
|
|
if(iIndex < m_cElements)
|
|
memmove(m_rgElements + iIndex, m_rgElements + iIndex + 1, (m_cElements-iIndex) * sizeof(TYPE));
|
|
|
|
m_cElements--;
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector::AddElement
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> TYPE* CVector<TYPE, IDX>::AddElement(TYPE element)
|
|
{
|
|
//Add an element to the end of the list
|
|
|
|
//Just delegate out to our InsertAt method, since we may need
|
|
//to enlarge the buffer size...
|
|
return InsertAt(m_cElements + m_ulLowerBound, element);
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector::InsertAt
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> TYPE* CVector<TYPE, IDX>::InsertAt(IDX iIndex, TYPE element)
|
|
{
|
|
iIndex -= m_ulLowerBound;
|
|
ASSERT(iIndex <= m_cElements); //Could be adding at end
|
|
|
|
//May need to alloc more room (if needed)
|
|
if(m_cElements == m_ulMaxSize)
|
|
{
|
|
m_ulMaxSize += 1 + m_ulGrowSize;
|
|
m_rgElements = (TYPE*)CoTaskMemRealloc(m_rgElements, m_ulMaxSize * sizeof(TYPE));
|
|
|
|
//Check Allocation
|
|
if(!m_rgElements)
|
|
return NULL;
|
|
}
|
|
|
|
//At this point we need an array...
|
|
ASSERT(m_rgElements);
|
|
|
|
//May Need to shift the entire array after this element down
|
|
//If not inserting at the end of the list
|
|
if(iIndex < m_cElements)
|
|
memmove(&m_rgElements[iIndex+1], &m_rgElements[iIndex], (m_cElements-iIndex) * sizeof(TYPE));
|
|
|
|
//Set new value
|
|
m_rgElements[iIndex] = element;
|
|
m_cElements++;
|
|
return &m_rgElements[iIndex];
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVector::GetElements
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> TYPE& CVector<TYPE, IDX>::GetElement(IDX iIndex)
|
|
{
|
|
iIndex -= m_ulLowerBound;
|
|
|
|
ASSERT(m_rgElements && iIndex < m_cElements);
|
|
return m_rgElements[iIndex];
|
|
}
|
|
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVectorEx
|
|
//
|
|
// NOTE: This Vector class requires the operator== to be defined for the type
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX = ULONG> class CVectorEx : public CVector<TYPE, IDX>
|
|
{
|
|
public:
|
|
|
|
//constructors
|
|
CVectorEx(IDX ulLowerBound = 0, IDX ulGrowSize = 10);
|
|
virtual ~CVectorEx();
|
|
|
|
//Helpers - require the operator== to be defined
|
|
virtual void RemoveElement(TYPE element);
|
|
virtual IDX FindElement(TYPE element); // Find index of element
|
|
|
|
protected:
|
|
//data
|
|
};
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVectorEx::CVectorEx
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> CVectorEx<TYPE, IDX>::CVectorEx(IDX ulLowerBound, IDX ulGrowSize)
|
|
: CVector<TYPE, IDX>(ulLowerBound, ulGrowSize)
|
|
{
|
|
}
|
|
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVectorEx::~CVectorEx
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> CVectorEx<TYPE, IDX>::~CVectorEx()
|
|
{
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVectorEx::RemoveElement
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> void CVectorEx<TYPE, IDX>::RemoveElement(TYPE element)
|
|
{
|
|
//Try to find the index of the element
|
|
IDX iIndex = FindElement(element);
|
|
|
|
//Deletgate to our RemoveAt method
|
|
RemoveAt(iIndex);
|
|
}
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// CVectorEx::FindElement
|
|
//
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
template <class TYPE, class IDX> IDX CVectorEx<TYPE, IDX>::FindElement(TYPE element)
|
|
{
|
|
//return pointer to found element
|
|
for(IDX i=0; i<m_cElements; i++)
|
|
if(m_rgElements[i] == element)
|
|
return i + m_ulLowerBound; // return position to found element
|
|
|
|
return ULONG_MAX;
|
|
}
|
|
|
|
|
|
|
|
#endif //_LIST_H_
|