linkedarray.h

来自「用bcg库编写的java IDE 源码」· C头文件 代码 · 共 376 行

template<typename TYPE>
class CLinkedArray
{
    struct _arraySegment
    {
      CArray<TYPE,TYPE> m_arrSegData;
	  _arraySegment     *m_pNext;
	  _arraySegment     *m_pPrev;

	  _arraySegment(long nSize)
	  {
        m_arrSegData.SetSize(nSize);
		m_pNext = NULL;m_pPrev = NULL;
	  }
    };

	long           m_nGrowBy;
	long           m_nActualLength;
	long           m_nArrayLength;
	_arraySegment* m_pHeadNode;
	_arraySegment* m_pTailNode;
public:
	CLinkedArray();
	CLinkedArray(long nInitSize);
	virtual ~CLinkedArray();

	//attributes
	void SetSize(long nNewSize,long nGrowBy = -1);
	long GetCount();
	long GetSize();
	long GetUpperBound();
	bool IsEmpty();

	//operations
	void FreeExtra();
	void RemoveAll();

	//element access
	TYPE& ElementAt(long nIndex);
	TYPE& GetAt(long nIndex);
	TYPE* GetData();
	void  SetAt(long nIndex,TYPE newItem);

	//growing array
	long Add(TYPE data);
	long Append(CLinkedArray& arrSrc);
	void Copy(CLinkedArray& arrSrc);
	void SetAtGrow(long nIndex, TYPE newItem);

	//insertion\removal
    void InsertAt(long nIndex,TYPE newItem,long nCount = 1);
    void InsertAt(long nStartIndex,CLinkedArray* pNewArray);
    void RemoveAt(long nIndex,long nCount = 1);

	//operator
	TYPE& operator[](long nIndex);
};

template<typename TYPE>
CLinkedArray<TYPE>::CLinkedArray()
{
  m_pHeadNode     = NULL;
  m_pTailNode     = NULL;
  m_nArrayLength  = 0;
  m_nActualLength = 0;
  m_nGrowBy       = 0;
}


template<typename TYPE>
CLinkedArray<TYPE>::CLinkedArray(long nInitSize)
{
  m_pHeadNode     = new _arraySegment(nInitSize);
  m_pTailNode     = m_pHeadNode;
  m_nArrayLength  = 0;
  m_nActualLength = nInitSize;
  m_nGrowBy       = 0;
}

template<typename TYPE>
CLinkedArray<TYPE>::~CLinkedArray()
{


}

template<typename TYPE>
void CLinkedArray<TYPE>::SetSize(long nNewSize,long nGrowBy /*= -1*/)
{
  if(nGrowBy != -1)
    m_nGrowBy = nGrowBy;

  if(nNewSize == 0)//remove all objects
  {
	RemoveAll();
    m_nArrayLength = 0;
  }
  else
  if(m_pHeadNode == NULL)//array empty
  {
    m_pHeadNode     = new _arraySegment(nNewSize);
    m_pTailNode     = m_pHeadNode;
    m_nArrayLength  = 0;
    m_nActualLength = nNewSize;
  }
  else
  if(nNewSize<=m_nActualLength)
	m_nArrayLength = nNewSize;
  else
  {
		// otherwise, grow array
	  int nGrowBy = m_nGrowBy;
	  if(nGrowBy == 0)
	  {
		//heuristically determine growth when nGrowBy == 0
		//(this avoids heap fragmentation in many situations)
		nGrowBy = m_nArrayLength / 8;
		nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
	  }

      //allocate new segment
	  CLinkedArray::_arraySegment* pArraySeg = new 
		  CLinkedArray::_arraySegment(nGrowBy);

	  if(m_pTailNode != NULL)
	    m_pTailNode->m_pNext =  pArraySeg;

      pArraySeg->m_pPrev   =  m_pTailNode;
	  m_pTailNode          =  pArraySeg;
      TYPE* pData          =  pArraySeg->m_arrSegData.GetData();
	  long  nCapacity      =  sizeof(pData);
      m_nActualLength      += nCapacity;
  }
}


template<typename TYPE>
long CLinkedArray<TYPE>::GetCount()
{
   return m_nArrayLength;
} 


template<typename TYPE>
long CLinkedArray<TYPE>::GetSize()
{
  return m_nArrayLength;
}


template<typename TYPE>
long CLinkedArray<TYPE>::GetUpperBound()
{
  return m_nArrayLength;
}

template<typename TYPE>
bool CLinkedArray<TYPE>::IsEmpty()
{
  return (m_nArrayLength == 0);
}

//operations
template<typename TYPE>
void CLinkedArray<TYPE>::FreeExtra()
{
  m_pTailNode->m_arrSegData.FreeExtra();
}


template<typename TYPE>
void CLinkedArray<TYPE>::RemoveAll()
{
	for(CLinkedArray::_arraySegment* pCur = m_pHeadNode; pCur != NULL;)
	{
      pCur->m_arrSegData.RemoveAll();
      CLinkedArray::_arraySegment* pNext = pCur->m_pNext;
	  delete pCur;
	  pCur = pNext;
	}
	m_pHeadNode     = NULL;
	m_pTailNode     = NULL;
	m_nArrayLength  = 0;
	m_nActualLength = 0;
}
											 
//element access
template<typename TYPE>
TYPE& CLinkedArray<TYPE>::ElementAt(long nIndex)
{
	ASSERT(nIndex<GetCount());

	long nAccuCount = 0;
	for(CLinkedArray::_arraySegment* pCur = m_pHeadNode; pCur != NULL; 
	                                          pCur = pCur->m_pNext)
	{
       nAccuCount += pCur->m_arrSegData.GetSize();
	   if(nAccuCount>nIndex)
		   break;
	}
    int nSegIndex = nIndex-(nAccuCount-pCur->m_arrSegData.GetSize());
    return pCur->m_arrSegData[nSegIndex];
}

template<typename TYPE>
TYPE& CLinkedArray<TYPE>::GetAt(long nIndex)
{
  return ElementAt(nIndex);
}


template<typename TYPE>
TYPE* CLinkedArray<TYPE>::GetData()
{
  return (TYPE)NULL;
}

template<typename TYPE>
void  CLinkedArray<TYPE>::SetAt(long nIndex,TYPE newItem)
{
   ASSERT(nIndex<GetCount());
   InsertAt(nIndex,newItem);
}

//growing array
template<typename TYPE>
long CLinkedArray<TYPE>::Add(TYPE newElement)
{
  int nIndex = m_nArrayLength;
  SetAtGrow(nIndex, newElement);
  return nIndex;
}

template<typename TYPE>
long CLinkedArray<TYPE>::Append(CLinkedArray& arrSrc)
{
  return 0;
}

template<typename TYPE>
void CLinkedArray<TYPE>::Copy(CLinkedArray& arrSrc)
{

}

template<typename TYPE>
void CLinkedArray<TYPE>::SetAtGrow(long nIndex, TYPE newElement)
{
	//ASSERT_VALID(this);
	ASSERT(nIndex >= 0);

	if(nIndex >= m_nArrayLength)
		SetSize(nIndex+1, -1);

	long nAccuCount = 0;
	for(CLinkedArray::_arraySegment* pCur = m_pHeadNode; pCur != NULL; 
	                                          pCur = pCur->m_pNext)
	{
       nAccuCount += pCur->m_arrSegData.GetSize();
	   if(nAccuCount>nIndex) break;
	}


    int nSegIndex = nIndex-(nAccuCount-pCur->m_arrSegData.GetSize());
	pCur->m_arrSegData[nSegIndex] = newElement;
}

//insertion\removal
template<typename TYPE>
void CLinkedArray<TYPE>::InsertAt(long nIndex,TYPE newItem,long nCount /*= 1*/)
{
	ASSERT(nIndex<GetCount());

	long nAccuCount = 0;
	for(CLinkedArray::_arraySegment* pCur = m_pHeadNode; pCur != NULL; 
	                                          pCur = pCur->m_pNext)
	{
       nAccuCount += pCur->m_arrSegData.GetSize();
	   if(nAccuCount>nIndex) break;
	}


    int nSegIndex = nIndex-(nAccuCount-pCur->m_arrSegData.GetSize());

    TYPE* pData = pCur->m_arrSegData.GetData();
	long  nCapacity  = sizeof(pData);
	long  nSize      = pCur->m_arrSegData.GetSize();
	long  nFreeSlots = nCapacity - nSize;

	if(nCount>nFreeSlots)
	{            
      pCur->m_arrSegData.InsertAt(nSegIndex,newItem,nFreeSlots);

	  m_nArrayLength += nFreeSlots;
	  long nExtra     = nCount-nFreeSlots;

	  for(int I=0; I<nExtra; I++)//allocate new segment and add remaining items
		  Add(newItem);
	}
	else
	{
	  pCur->m_arrSegData.InsertAt(nSegIndex,newItem,nCount);
	  m_nArrayLength += nCount;
	}
}

template<typename TYPE>
void CLinkedArray<TYPE>::InsertAt(long nStartIndex,CLinkedArray* pNewArray)
{
    ASSERT(pNewArray != NULL);
}

template<typename TYPE>
void CLinkedArray<TYPE>::RemoveAt(long nIndex,long nCount /*= 1*/)
{
	ASSERT(nIndex<GetCount());

	long nAccuCount = 0;
	for(CLinkedArray::_arraySegment* pCur = m_pHeadNode; pCur != NULL; 
	                                          pCur = pCur->m_pNext)
	{
       nAccuCount += pCur->m_arrSegData.GetSize();
	   if(nAccuCount>nIndex) break;
	}


	long  nSize      = pCur->m_arrSegData.GetSize();
    int nSegIndex = nIndex-(nAccuCount-nSize);

	if(nCount>=nSize)
	{
	  int nDelCount = nCount;
	  for(pCur;pCur != NULL;)
	  {        
        nSize            = pCur->m_arrSegData.GetSize();
        TYPE* pData      = pCur->m_arrSegData.GetData();
	    long  nCapacity  = sizeof(pData);

        if(nDelCount>=nSize)
		{
          nDelCount       -= nSize;
          nAccuCount      -= nSize;
		  m_nArrayLength  -= nSize;
		  m_nActualLength -= nCapacity;//remove this nodes's size
	      pCur->m_arrSegData.RemoveAll();
		}
		else
		if(nDelCount>0)
		{
		   nSegIndex        = nIndex-nAccuCount;
           m_nArrayLength  -= nDelCount;
           pCur->m_arrSegData.RemoveAt(nSegIndex,nDelCount);
           break;
		}
		else
		break;

        CLinkedArray::_arraySegment* pPrev = pCur->m_pPrev;
	    delete pCur;
	    pCur = pPrev;
	  }
	}
	else
	{
	  m_nArrayLength  -= nCount;
	  pCur->m_arrSegData.RemoveAt(nSegIndex,nCount);
	}
}

//operator
template<typename TYPE>
TYPE& CLinkedArray<TYPE>::operator[](long nIndex)
{
  return ElementAt(nIndex);
}