_dl_itr.cpp

EDA PCB 电路设计工具源码 c/c++ for Linux, Windows, Mac, 2008.8 最新

DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);

a_listiter->insbegin(a);
a_listiter->removehead();
\endcode
*/
template <class Dtype>
void DL_Iter<Dtype>::removehead()
{
	if (_current==0)
		Error("removehead()",NO_LIST);
	if (_list->_iterlevel > 1 )
		Error("removehead()",ITER_GT_1);
	if(NB==0)
		Error("removehead()",EMPTY);

   if (_current==HD)
		_current=_current->_next;

	_list->_iterlevel--;
   _list->removehead();
	_list->_iterlevel++;
}


/*!
//remove the object at the end of the list using an iterator
\note  The object itself is not deleted, only removed from the list. The user is responsible for memory management.

\note  The iterator level must be one to be able to use this function, else an error will be generated

\note  The list must contain objects, else an error will be generated.

\note  Use this function if an iterator is needed to do more complex things. Else use the list member functions directly.
\par Example:
   to insert integer a at end of list and remove it directly
\code
DL_List<int> _intlist; #create a list of integers

int a=123;

DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);

a_listiter->insend(a);
a_listiter->removetail();
\endcode
*/
template <class Dtype>
void DL_Iter<Dtype>::removetail()
{
	if (_current==0)
		Error("removetail()",NO_LIST);
	if (_list->_iterlevel > 1 )
		Error("removetail()",ITER_GT_1);
	if (NB==0)
		Error("removehead()",EMPTY);

   if (_current==TL)
		_current=_current->_prev;

	_list->_iterlevel--;
   _list->removetail();
	_list->_iterlevel++;

}

/*!
insert the object given at the end of the list

\note  The iterator level must be one to be able to use this function, else an error will be generated

\note  Use this function if an iterator is needed to do more complex things. Else use the list member functions directly.
\par Example:
   to insert integer a at end of list|
\code
DL_List<int> _intlist; #create a list of integers

int a=123;

DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);

a_listiter->insend(a);
\endcode
*/
template <class Dtype>
DL_Node<Dtype>* DL_Iter<Dtype>::insend(Dtype newitem)
{
	if (_current==0)
		Error("insend()",NO_LIST);
	if (_list->_iterlevel > 1)
		Error("insend()",ITER_GT_1);

	_list->_iterlevel--;
   DL_Node<Dtype>* ret = _list->insend(newitem);
	_list->_iterlevel++;
    return ret;
}


/*!
insert the object given at the begin of the list
\note  The iterator level must be one to be able to use this function, else an error will be generated

\note  Use this function if an iterator is needed to do more complex things. Else use the list member functions directly.

\par Example:
 to insert integer a at begin of list|
\code
DL_List<int> _intlist; #create a list of integers

int a=123;

DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);

a_listiter->insbegin(a);
\endcode
\param newitem an object for which the template list/iterator was generated
*/
template <class Dtype>
DL_Node<Dtype>* DL_Iter<Dtype>::insbegin(Dtype newitem)
{
	if (_current==0)
		Error("insbegin()",NO_LIST);
	if (_list->_iterlevel > 1)
		Error("insbegin()",ITER_GT_1);

	_list->_iterlevel--;
   DL_Node<Dtype>* ret = _list->insbegin(newitem);
	_list->_iterlevel++;
    return ret;    
}

/*!
//insert the object given before the current position of the iterator in list
\note  The iterator level must be one to be able to use this function, else an error will be generated
\par Example:
   to insert integer before the iterator position in the list|
\code
DL_List<int> _intlist; #create a list of integers

int a=123;

DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);
a_listiter->totail();
a_listiter->insbefore(a);   // insert before tail
\endcode
\param newitem an object for which the template list/iterator was generated
*/
template <class Dtype>
DL_Node<Dtype>* DL_Iter<Dtype>::insbefore(Dtype newitem)
{
	if (_current==0)
		Error("insbefore()",NO_LIST);
	if (_list->_iterlevel > 1)
		Error("insbefore()",ITER_GT_1);

	DL_Node<Dtype>* newnode = new DL_Node<Dtype>(newitem);

   newnode ->_next = _current;
   _current->_prev->_next = newnode;
   newnode ->_prev = _current->_prev;
   _current->_prev = newnode;

	NB++;
    return newnode;
}


/*!
insert the object given after the current position of the iterator in list
\note  The iterator level must be one to be able to use this function, else an error will be generated
\par Example:  to insert integer after the iterator position in the list|
\code
DL_List<int> _intlist; #create a list of integers

int a=123;

DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);
a_listiter->tohead();
a_listiter->insafter(a);   // insert after head
\endcode
\param newitem an object for which the template list/iterator was generated
*/
template <class Dtype>
DL_Node<Dtype>* DL_Iter<Dtype>::insafter(Dtype newitem)
{
	if (_current==0)
		Error("insafter()",NO_LIST);
	if (_list->_iterlevel > 1)
		Error("insafter()",ITER_GT_1);

	DL_Node<Dtype>* newnode = new DL_Node<Dtype>(newitem);

   newnode ->_next = _current->_next;
   newnode ->_prev = _current;
   _current->_next->_prev = newnode;
   _current->_next = newnode;

	NB++;
    return newnode;
}

/*!
sort all items in the list according to the compare function.
when items need to be swapped to reach the right order the swap function will be called also.
\note  There are no restrictions on the internal decision in the compare function when to return -1,0,1.

\note  The swap function can be used to change items when they are swapped.
       fcmp (function, fcmp)
\verbatim

          Declaration: int (*fcmp) (Dtype,Dtype)

          compare function pointer, the function takes two objects in the list. It must return -1, 0, 1, to sort the list in upgoing
          order the function should return:

               -1 is returned if the first object is bigger then the second.
               0 is returned if the objects are equal.
               1 is returned if the first object is smaller then the second.

          To sort the list in downgoing order:

               1 is returned if the first object is bigger then the second.
               0 is returned if the objects are equal.
               -1 is returned if the first object is smaller then the second.

          fswap (function, fswap)

          Declaration: void (*fswap) (Dtype,Dtype)

          swap function pointer, the function takes two objects in the list. It will be called when the objects are swapped to
          reach the right order. If it is NULL, it will not be called.
\endverbatim
\par Example:  sort the list in upgoing order using cocktailsort and the function numbersorter|
\code
int numbersorter(int a,int b)
{
      if(a < b) return(1);
      else
      if(a == b) return(0);
      return(-1);
}

DL_List <int> _intlist; #create a list of integers
DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);

a_listiter->insend(2345);
a_listiter->insend(3456);
a_listiter->insend(1234);
a_listiter->cocktailsort(numbersorter,NULL);
\endcode
\param fcmp sortfunction
\param fswap swapfunction
*/
template <class Dtype>
int DL_Iter<Dtype>::cocktailsort(int (*fcmp) (Dtype, Dtype), bool (*fswap)(Dtype, Dtype))
{
	if (_current==0)
		Error("cocktailsort()",NO_LIST);
	if (NB <= 1)
		return 0;

	DL_Node<Dtype>* cursor;
	Dtype swap;
    
    int swapResult = 0;

	// boven/ondergrens setten
	DL_Node<Dtype> *bg = TL, *bgold = TL;
	DL_Node<Dtype> *og = HD, *ogold = HD;

	bool swapped = true;

	// while swaping is done  &  lowerborder upperborder don't touch
	while (swapped && (og!=bg))
	{
		swapped = false;

		// BUBBELSLAG  lowerborder--->> upperborder
		cursor=og;
		while(!(cursor == bgold))
		{
			// (current.next < current)?
			if( fcmp(cursor->_next->_item, cursor->_item)==1)
			{
				// user function
				if ( fswap != NULL )
					if ( fswap(cursor->_item, cursor->_next->_item) )
                    swapResult++;
				// update swap-flag en upperborder
				swapped = true;
				bg = cursor;
				// swap the items of the nodes
				swap = cursor->_item;
				cursor->_item = cursor->_next->_item;
				cursor->_next->_item = swap;
			}
			cursor=cursor->_next;
		}// end bubbelslag
		bgold = bg;

		// BRICKSLAG   lowerborder <<---upperborder
		cursor=bg;
		while(!(cursor == ogold))
		{
			// (current < current.next)?
			if( fcmp(cursor->_item, cursor->_prev->_item)==1)
			{
				// user function
				if ( fswap != NULL )
					if (  fswap(cursor->_item, cursor->_prev->_item) )
                        swapResult++;
				// update swap-flag and lowerborder
				swapped = true;
				og = cursor;
				// swap de items van de nodes
				swap = cursor->_item;
				cursor->_item = cursor->_prev->_item;
				cursor->_prev->_item = swap;
			}
			cursor=cursor->_prev;
		}// end brickslag
		ogold = og;
	}// end while(ongesorteerd)
    
    return swapResult;
}

/*!
   sort all items in the list according to the compare function.

\note
   There are no restrictions on the internal decision in the compare function when to return -1,0,1.

\note
   For the mergesort function the objects will be swapped when the return value is -1.

\note
\verbatim

      fcmp (function, fcmp)

         Declaration: int (*fcmp) (Dtype,Dtype)

          compare function pointer, the function takes two objects in the list. It must return -1, 0, 1, to sort the list in upgoing
          order the function should return:

               -1 is returned if the first object is bigger then the second.
               0 is returned if the objects are equal.
               1 is returned if the first object is smaller then the second.

          To sort the list in downgoing order:

               1 is returned if the first object is bigger then the second.
               0 is returned if the objects are equal.
               -1 is returned if the first object is smaller then the second.
\endverbatim

!tcarg: class | Dtype | list item object
\par example
   sort the list in upgoing order using mergesort and the function numbersorter|
\code
int numbersorter(int a,int b)
{
      if(a < b) return(1);
      else
      if(a == b) return(0);
      return(-1);
}

DL_List <int> _intlist; #create a list of integers
DL_Iter<int>*  a_listiter=new DL_Iter<int>(&_intlist);

a_listiter->insend(2345);
a_listiter->insend(3456);
a_listiter->insend(1234);
a_listiter->mergesort(numbersorter);
\endcode
*/
template <class Dtype>
void DL_Iter<Dtype>::mergesort(int (*fcmp) (Dtype, Dtype))
{
	if (_current==0)
		Error("mergesort()",NO_LIST);
 	mergesort_rec(fcmp, RT, NB);
}


template <class Dtype>
void DL_Iter<Dtype>::mergesort_rec(int (*fcmp)(Dtype,Dtype), DL_Node<Dtype> *RT1, int n1)
{
   if (n1 > 1)  //one element left then stop
   {
		DL_Node<Dtype>       RT2;
	   int n2;

      RT2._prev=RT1->_prev;
      RT2._next=RT1->_next;
      // goto middle
      n2=n1;n1>>=1;n2-=n1;
      for (int i=0; i <n1;i++)
         RT2._next=RT2._next->_next;

      //RT2 is at half
      RT1->_prev->_next=&RT2;
      RT2._prev=RT1->_prev;
      RT1->_prev=RT2._next->_prev;
      RT2._next->_prev->_next=RT1;

     	mergesort_rec(fcmp,RT1,n1);
     	mergesort_rec(fcmp,&RT2,n2);
     	mergetwo(fcmp,RT1,&RT2);
   }
}

template <class Dtype>
void DL_Iter<Dtype>::mergetwo(int (*fcmp)(Dtype,Dtype), DL_Node<Dtype> *RT1,DL_Node<Dtype> *RT2)
{
	DL_Node<Dtype>       *c,*a,*b;
   a=RT1->_next;b=RT2->_next;
   c=RT1;
   do
   {
      if (fcmp(a->_item , b->_item) > -1)
      { c->_next=a;a->_prev=c;c=a;a=a->_next;}
      else
      { c->_next=b;b->_prev=c;c=b;b=b->_next;}
      if (a == RT1)
      { 	c->_next=
          b;b->_prev=c; //connect list b to the list made sofar
         RT1->_prev=RT2->_prev;
         RT1->_prev->_next=RT1;
      	break;
      }
      if (b == RT2)
      { 	c->_next=a;a->_prev=c; //connect list a to the list made sofar
      	break;
      }
   }
   while (true);
}


//=======================================================================
// implementation class DL_StackIter
//=======================================================================
/*! \class DL_StackIter
*  template class DL_StackIter class for stack iterator on DL_List
*  template stack iterator for any list/node type \n
*  This class is the base class to attach/instantiate a stack iterator on a double linked list
*  DL_List. The stack iterator is used to push and pop objects
*  to and from the beginning of a list.
*  class | Dtype | Object for traversing a DL_List of the same Dtype
*\par Example
   How to work with a stack iterator for a list of type integer \n
   to push a and b, pop a into list and remove_all directly using a stack iterator
*
*\code     DL_List<int>* a_list = new DL_List<int>();# declaration and allocation
*
*     int a=123;
*
*     int b=345;
*
*     {
*
*             DL_StackIter<int>*  a_listiter=new DL_StackIter<int>(a_list);
*
*             a_listiter->push(a)
*
*             a_listiter->push(b)
*
*             a_listiter->pop()
*
*             a_listiter->remove_all()
*
*     } //to destruct the iterator before the list is deleted
*
*     delete a_list; #delete it (must have no iterators attached to it)
*\endcode
*/

// constructor
template <class Dtype>
DL_StackIter<Dtype>::DL_StackIter(DL_List<Dtype> *newlist)
:DL_Iter<Dtype>(newlist)  // initialiseer BaseIter
{}


// destructor
template <class Dtype>
DL_StackIter<Dtype>::~DL_StackIter()
{
}

// plaats nieuw item op stack
template <class Dtype>
void DL_StackIter<Dtype>::push(Dtype newitem)
{
	DL_Iter<Dtype>::insbegin(newitem);
}
// remove current item
template <class Dtype>
void DL_StackIter<Dtype>::remove_all()
{
	DL_Iter<Dtype>::remove_all();
}

// is stack leeg?
template <class Dtype>
bool DL_StackIter<Dtype>::empty()
{
	return DL_Iter<Dtype>::empty();
}

// aantal items op stack
template <class Dtype>
int  DL_StackIter<Dtype>::count()
{
	return DL_Iter<Dtype>::count();
}

// haal bovenste item van stack
template <class Dtype>
Dtype DL_StackIter<Dtype>::pop()
{
	if(DL_Iter<Dtype>::empty())
		this->Error("pop()",EMPTY);

	DL_Iter<Dtype>::tohead();
	Dtype temp = DL_Iter<Dtype>::item();
	DL_Iter<Dtype>::removehead();
	return temp;
}

//=======================================================================
// implementation class DL_SortIter
//=======================================================================
/*! \class DL_SortIter
* template class DL_SortIter
* class for sort iterator on DL_List
* template sort iterator for any list/node type
* This class is a derived class to attach/instantiate a sorted iterator on a double linked list
* DL_List. The iterator is used to insert items in sorted order into a list.
//!tcarg: class | Dtype | Object for traversing a DL_List of the same Dtype
*/

// constructor
template <class DType>
DL_SortIter<DType>::DL_SortIter(DL_List<DType>* nw_list, int (*new_func)(DType ,DType ))
:DL_Iter<DType>(nw_list), comparef(new_func)
{}

// destructor
template <class DType>
DL_SortIter<DType>::~DL_SortIter()
{}

// general function to insert item
template <class DType>
void DL_SortIter<DType>::insert(DType new_item)
{
	DL_Node<DType>* cursor=this->_current; //can be 0 if empty  //node is a temporary cursor

	// if list is empty directly insert
	if (DL_Iter<DType>::empty())
	{
		DL_Iter<DType>::insend(new_item);
	}
	else
	{
		// put new item left of item
		DL_Iter<DType>::tohead();
		while(!DL_Iter<DType>::hitroot())
		{
			if (!(*comparef)(DL_Iter<DType>::item(), new_item))
				break;
			DL_Iter<DType>::next();
		}

		//if at root
		DL_Iter<DType>::insbefore(new_item);
	}

	this->_current=cursor; //set to old cursor position
}

template <class DType>
void DL_SortIter<DType>::sortitererror()
{
 		this->Error("sortiter()",NOT_ALLOW);
}