//moves onto the next value in the current node's list. Returns NULL if no more
CLTANode* CLTANodeIterator::NextValueShallow()
{
	ASSERT(m_nStackPos > 0);

	for(	uint32 nCurrElem = GetElementIndex(); 
			nCurrElem < GetHead()->GetNumElements(); 
			nCurrElem++)
	{
		if(GetHead()->GetElement(nCurrElem)->IsAtom())
		{
			//found it

			//save this new offset
			SetElementIndex(nCurrElem + 1);

			//return the element
			return GetHead()->GetElement(nCurrElem);
		}
	}

	//didn't find it

	//set the offset to the end
	SetElementIndex(GetHead()->GetNumElements());

	//indicate failure
	return NULL;
}

int UnSelectAllObjects(piObject *w)
{
	piObject *o;
	struct List *l;
	ULONG sel,s=0;

	piGetAttr(w,WNOBJ_GadgetList,(ULONG *)&l);
	for(o=(piObject *)GetHead(l);GetSucc(o);o=(piObject *)GetSucc(o))
	{
		piGetAttr(o,OBJ_Select,(ULONG *)&sel);
		if(sel)
		{
			s=1;
			piSetAttrs(o,OBJ_Select,FALSE,TAG_DONE);
			piRenderObject(o);
		}
	}
	piGetAttr(w,WNOBJ_FrameList,(ULONG *)&l);
	for(o=(piObject *)GetHead(l);GetSucc(o);o=(piObject *)GetSucc(o))
	{
		piGetAttr(o,OBJ_Select,(ULONG *)&sel);
		if(sel)
		{
			s=1;
			piSetAttrs(o,OBJ_Select,FALSE,TAG_DONE);
			piRenderObject(o);
		}
	}
	return (int)s;
}

//moves onto the next list in the current node's list. Returns NULL if no more
CLTANode* CLTANodeIterator::NextListShallow()
{

	for(	uint32 nCurrElem = GetElementIndex(); 
			nCurrElem < GetHead()->GetNumElements(); 
			nCurrElem++)
	{
		if(GetHead()->GetElement(nCurrElem)->IsList())
		{
			//found it

			//save this new offset
			SetElementIndex(nCurrElem + 1);

			//return the element
			return GetHead()->GetElement(nCurrElem);
		}
	}

	//didn't find it

	//set the offset to the end
	m_nElemStack[m_nStackPos] = GetHead()->GetNumElements();

	//indicate failure
	return NULL;
}

int main()
{
	int i;
	QElemType d;
	LinkQueue q;
	i=InitQueue(&q);
	if(i)
		printf("成功地构造了一个空队列!\n");
	printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
	printf("队列的长度为%d\n",QueueLength(q));
	EnQueue(&q,-5);
	EnQueue(&q,5);
	EnQueue(&q,10);
	printf("插入3个元素(-5,5,10)后,队列的长度为%d\n",QueueLength(q));
	printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
	printf("队列的元素依次为：");
	QueueTraverse(q);
	i=GetHead(q,&d);
	if(i==OK)
	 printf("队头元素是：%d\n",d);
	DeQueue(&q,&d);
	printf("删除了队头元素%d\n",d);
	i=GetHead(q,&d);
	if(i==OK)
		printf("新的队头元素是：%d\n",d);
	ClearQueue(&q);
	printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
	DestroyQueue(&q);
	printf("销毁队列后,q.front=%u q.rear=%u\n",q.front, q.rear);
	
	return 0;
}

/**
 * 算法2.21
 */
Status MergeList(LinkList &La, LinkList &Lb, LinkList &Lc, 
				int (*compare)(ElemType, ElemType))
{
	Link ha, hb, pa, pb, q;
	ElemType a, b;
	if (!InitList(Lc))
		return ERROR;
	ha = GetHead(La);
	hb = GetHead(Lb);
	pa = NextPos(La, ha);
	pb = NextPos(Lb, hb);
	while (pa && pb) {
		a = GetCurElem(pa);
		b = GetCurElem(pb);
		if (compare(a, b) <= 0) {   // a<=b
			DelFirst(ha, q);
			Append(Lc, q);
			pa = NextPos(La, ha);
		} else {    // a>b
			DelFirst(hb, q);
			Append(Lc, q);
			pb = NextPos(Lb, hb);
		}   
	} // while
	if (pa)
		Append(Lc, pa);
	else
		Append(Lc, pb);
	FreeNode(ha);
	FreeNode(hb);
	return OK;
}

		vptr FreeListAllocator::Allocate(usize Size, uint8 Alignment) const
		{
			vptr pointer = nullptr;
			Size += (((uptr)m_Next) + Size) % Alignment;
			FreeChunk *header = FindFreeChunk(Size);
			if(header == nullptr)
			{
				header = AllocateHeader();
				pointer = m_Next;
				m_LastHeader = header;
				m_Next = (vptr)((uptr)m_Next + Size);
				if((uptr)m_Next > m_Tail || (uptr)m_Next < (uptr)GetHead())
				{
					DAMN_ERROR("Free list allocator ran out of memory.\n"
						   "It asked for %u bytes more than the %u bytes that were "
						   "previously allocated.",
						   (uint32)((uptr)m_Next - m_Tail),
						   (uint32)(m_Tail - (uptr)GetHead()));
				}
			}
			else
			{
				pointer = (vptr)((uptr)header + s_FreeChunkSize);
			}
			header->m_Size = (uint32)Size;
			header->m_Used = true;
			m_AllocCount += 1;
			m_Used += header->m_Size;
			return pointer;
		}

		FreeChunk *FreeListAllocator::FindFreeChunk(usize Size) const
		{
			FreeChunk *node = (FreeChunk*)GetHead();
			int32 count = 0;
			FreeChunk *last;
			while(node != nullptr && node->m_Size != Size && m_LastHeader != node)
			{
				node = (FreeChunk*)((uptr)node + s_FreeChunkSize + (node->m_Size));
				if(count >= m_AllocCount)
				{
					return nullptr;
				}
				if((uptr)node > m_Tail || (uptr)node < (uptr)GetHead())
				{
					DAMN_ERROR("Free list allocator ran out of memory.\n"
						   "It asked for %u bytes more than the %u bytes that were "
						   "previously allocated.",
						   (uint32)((uptr)node - m_Tail),
						   (uint32)(m_Tail - (uptr)GetHead()));
				}
				if(node->m_Size == Size && !node->m_Used)
				{
					break;
				}
				last = node;
				++count;
			}
			if(node == nullptr || node->m_Used) return nullptr;
			return node;
		}

void test_GetHead(void) {
	GENERALIZED_LIST_TYPE list = NULL;
	CU_ASSERT_EQUAL(GetHead(list), NULL);

	list = getGeneralizedList("(1,2)");
	assertEqual(GetHead(list), "(1)");

	list = getGeneralizedList("((11,12,13),(21,22,23,24,25),3)");
	assertEqual(GetHead(list), "(11,12,13)");
}

//----------------------------------------------------------------------------------------------------------------
void CClient::PreThink()
{
    int iLastWaypoint = iCurrentWaypoint;
    CPlayer::PreThink();

    // Client don't have access to waypoint modification.
    if ( FLAG_CLEARED(FCommandAccessWaypoint, iCommandAccessFlags) )
        return;

    // Check if lost waypoint, in that case add new one.
    if ( bAutoCreateWaypoints && m_bAlive &&
         ( !CWaypoint::IsValid(iCurrentWaypoint) ||
           (GetHead().DistToSqr(CWaypoints::Get(iCurrentWaypoint).vOrigin) >= SQR(CWaypoint::iDefaultDistance)) ) )
    {
        Vector vOrigin( GetHead() );

        // Add new waypoint, but distance from previous one must not be bigger than iDefaultDistance.
        if ( CWaypoint::IsValid(iLastWaypoint) )
        {
            CWaypoint& wLast = CWaypoints::Get(iLastWaypoint);
            vOrigin -= wLast.vOrigin;
            vOrigin.NormalizeInPlace();
            vOrigin *= CWaypoint::iDefaultDistance;
            vOrigin += wLast.vOrigin;
        }

        // Add new waypoint.
        iCurrentWaypoint = CWaypoints::Add(vOrigin);

        // Add paths from previous to current.
        if ( CWaypoint::IsValid(iLastWaypoint) )
        {
            float fHeight = GetPlayerInfo()->GetPlayerMaxs().z - GetPlayerInfo()->GetPlayerMins().z + 1;
            bool bIsCrouched = (fHeight < CMod::iPlayerHeight);

            CWaypoints::CreatePathsWithAutoFlags(iLastWaypoint, iCurrentWaypoint, bIsCrouched);
            iDestinationWaypoint = iLastWaypoint;
        }
    }

    // Calculate destination waypoint according to angles. Path's should be drawn.
    if ( !bLockDestinationWaypoint && (iPathDrawFlags != FPathDrawNone) &&
         (CWaypoints::fNextDrawWaypointsTime >= CBotrixPlugin::fTime) )
    {
        QAngle ang;
        GetEyeAngles(ang);
        iDestinationWaypoint = CWaypoints::GetAimedWaypoint( GetHead(), ang );
    }

    // Draw waypoints.
    CWaypoints::Draw(this); // TODO: should not draw for several admins...

    // Draw entities.
    CItems::Draw(this);
}

/******************************************************************************
void IFXKeyTrack::CalcInstantConst(F32 time,IFXInstant *instant,
											IFXListContext *context) const

	FUTURE perhaps something better than linear interpolation on locations

******************************************************************************/
void IFXKeyTrack::CalcInstantConst(
								   F32 time,
								   IFXInstant *instant,
								   IFXListContext *context) const
{
	if(context==NULL)
		context=(IFXListContext *)&m_current;

	Sync(time,context);

	IFXKeyFrame *after=GetCurrent(*context);
	IFXKeyFrame *before=PreDecrement(*context);

	PreIncrement(*context); // put back

	if(!before && !after)
	{
		if(GetHead())
		{
			*instant= *GetHead();
			return;
		}
		else
			instant->Reset();
	}
	else if(!before)
	{
		*instant= *after;
		return;
	}
	else if(!after)
	{
		*instant= *before;
		return;
	}
	else
	{
		F32 fraction= (time-before->Time()) /
			(after->Time()-before->Time());

		instant->Location().Interpolate(fraction,
			before->LocationConst(),after->LocationConst());
		instant->Rotation().Interpolate(fraction,
			before->RotationConst(),after->RotationConst());
		instant->Scale().Interpolate(fraction,
			before->ScaleConst(),after->ScaleConst());
	}
}

void    *GDList::rem_del(position rel,int mode)
{
    NIDNode *node = 0;
    switch(rel)
    {
        case GDBase::liststart: node=GetHead();  break;
        case GDBase::listend:   node=GetTail();  break;
        case GDBase::current:   node=GetCurr();  break;
        case GDBase::before:    if((node=GetCurr()) != 0)
                                    node = node->GetPrev();
                                break;
        case GDBase::after:     if((node=GetCurr()) != 0)
                                    node = node->GetNext();
                                break;
    }
    if(node)
    {
        void *obj = node->object;
        remove(node);
        if(mode && cleanup() == ListBase::active)
            zap_object(obj);
        return obj;
    }
    return 0;
}

//*****************************************************************************
void BBlockRing::RemoveAll() {
  BTerrainBlock *pBlock;
  while(pBlock = GetHead()) {
    Remove(pBlock);
    delete pBlock;
  }
}

LIBFUNC2(APTR, AllocMem, ULONG, size, ULONG, flags, struct ExecBase *,SysBase)
{
	struct	MemHeader *mh;
	struct	MemBlock *mb;
	ULONG	realsize=size+sizeof(struct MemHeader);

	Forbid();	
	mb=(struct MemBlock *) GetHead(&SysBase->FreeMemList);
	
	if(!mb) return (NULL);

	while(mb->mb_Size<realsize) {
		mb=(struct MemBlock *) GetNext(mb);
		if(!mb) return (NULL);
	}
	
	realsize=realsize+(realsize%MEM_BLOCKSIZE);
	mb->mb_Size -= realsize;
	mh=(struct MemHeader *) (mb+mb->mb_Size);
	mh->mh_Node.mln_Prev = NULL;
	mh->mh_Node.mln_Next = NULL;
	mh->mh_Magic = MEMF_MAGIC;
	mh->mh_Size = realsize;
	Permit();
	return ((APTR) mh);

}

void SLList::Insert(int contents) {
	if(head_ == NULL) {
		InsertHead(contents);
	}
	else if(contents < GetHead()) {
		InsertHead(contents);
	}
	else if (head_->next_node() == NULL && head_ != NULL) {
		InsertTail(contents);
	}
	else if(contents > GetTail()) {
		InsertTail(contents);
	}
	else {
		SLNode* node = new SLNode(contents);
		SLNode* i = head_;
		SLNode* j = NULL;
		while(i->contents() <= contents && i->next_node() != NULL) {
			j = i;
			i = i->next_node();
		}
		j->set_next_node(node);
		node->set_next_node(i);
		size_++;
	}
}

BOOL PlugInPathList::RemoveHiddenItems()
{
	// Go through all the paths in the list and remove all those with the hidden
	// attribute set.
	PlugInPath* pPath = (PlugInPath *)GetHead();
	while (pPath)
	{
		if (pPath->IsHidden())
		{
			// The item is hidden so remove it
			// First, find the next item, if there is one
			PlugInPath* pNextPath = (PlugInPath *)GetNext(pPath);

			RemoveItem(pPath);
			// remove item returns NULL if problem
			if (pPath == NULL)
				return FALSE;
			
			// remove the old path item from memory
			delete pPath;
			// move to considering the next item
			pPath = pNextPath;
		}
		else
		{
			// Try the next pathname in the list
			pPath = (PlugInPath *)GetNext(pPath);
		}
	}

	return TRUE;
}

void OverrideList::AddHead( OverrideListItem* poliToAdd)
{
	if (poliToAdd==NULL)
	{
		ERROR2RAW("OverrideList::AddHead - NULL parameter");
		return;
	}

	//Get the first item in the list
	OverrideListItem* pliFirst=(OverrideListItem*) GetHead();

	//Was there anything in the list?
	if (pliFirst!=NULL)				 
	{
		//Yes. So call our InsertBefore function
		InsertBefore(pliFirst, poliToAdd);
	}
	else
	{
		//No. So we need do no special checking - simply insert
		//the list item
		List::AddHead(poliToAdd);
	}
	
}

/**
 * \brief remove the end of the list, and return it
 * \returns shared ptr to what was the end of the list
 */
std::shared_ptr<CSnowflake> CSnowflakeLinkedList::pop()
{
	auto snowflake = GetHead();
	if (snowflake != nullptr)
	{
		//check if we are already at last node (singly linked list is size 1)
		if (snowflake->Next() == nullptr)
		{
			mStartSnowflake = nullptr;
			return snowflake;
		}
		else
		{
			//Get to one before the end
			while (snowflake->Next()->Next() != nullptr)
			{
				snowflake = snowflake->Next();
			}
			auto last = snowflake->Next();
			snowflake->SetNext(nullptr);
			return last;
		}
	}
	else
	{
		return nullptr;
	}
}

int CItemStone::FixWeirdness()
{
	ADDTOCALLSTACK("CItemStone::FixWeirdness");
	// Check all my members. Make sure all wars are reciprocated and members are flaged.

	int iResultCode = CItem::FixWeirdness();
	if ( iResultCode )
	{
		return( iResultCode );
	}

	bool fChanges = false;
	CStoneMember * pMember = STATIC_CAST <CStoneMember *>(GetHead());
	while ( pMember != NULL )
	{
		CStoneMember * pMemberNext = pMember->GetNext();
		if ( ! CheckValidMember(pMember))
		{
			IT_TYPE oldtype = GetType();
			SetAmount(0);	// turn off validation for now. we don't want to delete other members.
			delete pMember;
			SetAmount(1);	// turn off validation for now. we don't want to delete other members.
			SetType( oldtype );
			fChanges = true;
		}
		pMember = pMemberNext;
	}

	if ( fChanges )
	{
		ElectMaster();	// May have changed the vote count.
	}
	return( 0 );
}

void GSRasterizerList::PrintStats()
{
	if(!IsEmpty())
	{
		GetHead()->PrintStats();
	}
}

void eFBCTunerManager::Unlink(eDVBRegisteredFrontend *fe) const
{
	eDVBRegisteredFrontend *simul_fe;
	bool simulate;

	simulate = fe->m_frontend->is_simulate();

	if (IsRootFE(fe) || IsFEUsed(fe, simulate) || IsSCR(fe) || !IsLinked(fe))
		return;

	//PrintLinks(fe);

	DisconnectLink(fe, FrontendGetLinkPtr(fe, link_prev), FrontendGetLinkPtr(fe, link_next), simulate);
	fe->m_frontend->setEnabled(false);

	if(!simulate) // also act on the simulation frontends
	{
		if((simul_fe = GetSimulFE(fe)) && !IsRootFE(simul_fe) && !IsFEUsed(simul_fe, true) &&
				!IsSCR(simul_fe) && IsLinked(simul_fe))
		{
			DisconnectLink(simul_fe, FrontendGetLinkPtr(simul_fe, link_prev), FrontendGetLinkPtr(simul_fe, link_next), true);
			simul_fe->m_frontend->setEnabled(false);
		}
	}

	//PrintLinks(fe);

	//setDefaultFBCID(link_fe);
	UpdateLNBSlotMask(FESlotID(fe), FESlotID(GetHead(fe)), /*remove*/true);
}