_dl_itr.cpp

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

/*! \file kbool/include/kbool/_dl_itr.cpp
    \brief Double Linked list with Iterators on list
    \author Probably Klaas Holwerda

    Copyright: 2001-2004 (C) Probably Klaas Holwerda

    Licence: wxWidgets Licence

    RCS-ID: $Id: _dl_itr.cpp,v 1.1 2005/05/24 19:13:35 titato Exp $
*/

#ifdef __GNUG__
#pragma implementation
#endif

#ifdef __UNIX__
#include "../include/_dl_itr.h"
#endif

//=======================================================================
// implementation class DL_Node
//=======================================================================
/*! \class DL_Node
* This class is used in the class DL_List to contain the items of the list. This can be a
* pointer to an object or the object itself. The class contains a next and a previous pointer
* to connect the nodes in the list. \n
* class Dtype | Object stored at the node
*/



/*!
Construct a node for a list object
\param it Item the node will contain
*/
template <class Dtype>
DL_Node<Dtype>::DL_Node(Dtype it)	// + init nodeitem
:_item(it)
{}

/*!
 Template constructor no contents
 Construct a node for a list object
*/
template <class Dtype>
DL_Node<Dtype>::DL_Node()
:_item(0)
{}

/*!
Destruct a node object
*/
template <class Dtype>
DL_Node<Dtype>::~DL_Node()
{
}


//=======================================================================
// implementation class DL_List
//=======================================================================
/*! \class DL_List
* class is the base class for implementing a double linked list. The Root node marks the begining and end of the list. The
* lists consists of nodes double linked with a next and previous pointer DL_Node The nodes are cyclic connected to the root
* node. The list is meant to be used with an iterator class, to traverse the nodes. More then 1 iterator can be attached to the
* list. The list keeps track of the number of iterators that are attached to it. Depending on this certain operations are allowed
* are not. For instance a node can only be deleted if there is only one iterator attached to the list.
* class | Dtype | Object contaning List Nodes
*/

/*!
Construct a node object
\par Example:
    How to construct a list of type integer:
\code
	DL_List<int> * a_list = new DL_List<int>();
\endcode
*/
template <class Dtype>
DL_List<Dtype>::DL_List()
:_nbitems(0), _iterlevel(0)
{
	_root = new DL_Node<Dtype>();
   _root->_next=_root;
   _root->_prev=_root;
}


/*!
//Destruct a list object
\par Example:
    How to construct a list of type integer:
\code
   DL_List<int> * a_list = new DL_List<int>(); # declaration and allocation
   delete a_list; #delete it (must have no iterators attached to it)
\endcode
*/
template <class Dtype>
DL_List<Dtype>::~DL_List()
{
	if (_iterlevel != 0)
      throw Bool_Engine_Error("DL_List::~DL_List()\n_iterlevel > 0 ","list error", 0, 1); 

   remove_all(false);
	delete _root;
	_root=0;_nbitems=0; //reset memory used (no lost pointers)
}

/*!
Error report for list error inside DL_List class
the error function is used internally in the list class to report errors,
the function will generate a message based on the error code.
Then an exeption will be generated using the global booleng class instance. \n
tcarg: class | Dtype | item object in list
\par Example
   to call error from inside an DL_List class
\code
Error("remove_all",ITER_GT_O);
\endcode
\param function string that generated this error
\param error code to generate a message for
*/
template <class Dtype>
void DL_List<Dtype>::Error(const char* function,Lerror a_error)
{
   char buf[100];
   strcpy(buf,"DL_List<Dtype>::");
   strcat(buf,function);
   switch (a_error)
   {
		case NO_MES:             strcat(buf,""); break;
		case EMPTY:              strcat(buf,"list is empty"); break;
		case ITER_GT_0:          strcat(buf,"more then zero iter"); break;
		case NO_LIST:            strcat(buf,"no list attached"); break;
		case SAME_LIST:          strcat(buf,"same list not allowed"); break;
		case AC_ITER_LIST_OTHER: strcat(buf,"iter not allowed on other list"); break;
		default:						 strcat(buf,"unhandled error"); break;
   }

	throw Bool_Engine_Error(buf,"list error", 0, 1); 
}

/*!
is list empty (contains items or not)? \n
class | Dtype | item object in list
\return returns true is list is empty else false
\par Example
   too see if list is empty
\code
DL_List<int> _intlist; #create a list of integers

          if (_intlist.Empty())

                  cout << "empty";
\endcode
*/
template <class Dtype>
bool DL_List<Dtype>::empty()
{
	return(bool)(_nbitems==0);
}

/*!
   number of items in list \n
   class | Dtype | item object in list
\return return number of items in the list
\par Example
   too see if list contains only one object
\code
DL_List <int> _intlist; #create a list of integers

          if (_intlist.count() == 1)

                  cout << "one object in list";
\endcode
*/
template <class Dtype>
int DL_List<Dtype>::count()
{
	return _nbitems;
}

/*!
 remove all objects from the list\n
 class | Dtype | item object in list
\note
 The objects itself are not deleted, only removed from the list.
 The user is responsible for memory management.

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

\note
   Use this function if an iterator is not needed to do more complex things.
   This will save time, since the iterator does not have to be created.
\par Example
   too insert integer a and b into list and remove_all directly
\code
   DL_List<int> _intlist; #create a list of integers
   int a=123;

   int b=345;

   _intlist.insbegin(a);

   _intlist.insbegin(b);

   _intlist.remove_all();
\endcode
*/
template <class Dtype>
void DL_List<Dtype>::remove_all( bool deleteObject )
{
	if (_iterlevel > 0 )
		Error("remove_all()",ITER_GT_0);

   Dtype* obj; 

	DL_Node<Dtype> *node;
	for (int i=0; i<_nbitems; i++)
	{
		node = _root->_next;
		_root->_next = node->_next;
      if ( deleteObject == true )
      {    
         obj=(Dtype*)(node->_item);
         delete obj; 
      }
		delete node;
	}
	_nbitems=0;_iterlevel=0;  //reset memory used (no lost pointers)
   _root->_prev=_root;
}

/*!
remove the object at the begin of the list (head).
\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 zero 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 not needed to do more complex things. This will save time, since the iterator does not
have to be created.

\par Example:
    too insert integer a at begin of list and remove it directly.
\code
DL_List<int> _intlist; #create a list of integers

         int a=123;

         _intlist.insbegin(a)

         _intlist.removehead();

\endcode
*/
template <class Dtype>
void DL_List<Dtype>::removehead()
{
	if (_iterlevel > 0 )
		Error("removehead()",ITER_GT_0);
	if(_nbitems==0)
		Error("removehead()",EMPTY);

	DL_Node<Dtype>* node=_root->_next;

	node->_prev->_next = node->_next; // update forward link
	node->_next->_prev = node->_prev; // update backward link

	_nbitems--;
	delete node;                      // delete list node
}


/*!
remove the object at the begin of the list (head).

\note
   - The object itself is not deleted, only removed from the list.
     The user is responsible for memory management.
   - The iterator level must be zero to be able to use this function,
     else an error will be generated
   - The list must contain objects, else an error will be generated.
   - Use this function if an iterator is not needed to do more complex things.
     This will save time, since the iterator does not have to be created.

\par Example:
    too insert integer a at end of list and remove it directly.
\code
DL_List<int> _intlist; #create a list of integers

         int a=123;

         _intlist.insend(a)

         _intlist.removetail();

\endcode
*/
template <class Dtype>
void DL_List<Dtype>::removetail()
{
	if (_iterlevel > 0)
		Error("removetail()",ITER_GT_0);
	if (_nbitems==0)
		Error("removehead()",EMPTY);

	DL_Node<Dtype>* node=_root->_prev;

   node->_prev->_next = node->_next; // update forward link
   node->_next->_prev = node->_prev; // update backward link

   _nbitems--;
   delete node;                      // delete list node
}

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

\note
Use this function if an iterator is not needed to do more complex things.
This will save time, since the iterator does not have to be created.
\par Example:
too insert integer a at end of list
\code
			DL_List<int> _intlist; #create a list of integers

         int a=123;

         _intlist.insend(a)
\endcode
\param newitem an object for which the template list was generated
*/
template <class Dtype>
DL_Node<Dtype>* DL_List<Dtype>::insend(Dtype newitem)
{
	if (_iterlevel > 0)
		Error("insend()",ITER_GT_0);

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

   newnode ->_next = _root;
   newnode ->_prev = _root->_prev;
   _root->_prev->_next = newnode;
   _root->_prev = newnode;

	_nbitems++;
    
    return newnode;
}

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

\note
Use this function if an iterator is not needed to do more complex things.
This will save time, since the iterator does not have to be created.

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

         int a=123;

         _intlist.insbegin(a)
\endcode
\param newitem an object for which the template list was generated
*/
template <class Dtype>
DL_Node<Dtype>* DL_List<Dtype>::insbegin(Dtype newitem)
{
	if (_iterlevel > 0)
		Error("insbegin()",ITER_GT_0);

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

   newnode ->_prev = _root;
   newnode ->_next = _root->_next;
   _root->_next->_prev = newnode;
   _root->_next = newnode;

	_nbitems++;
    return newnode;
}

/*!
get head item
\return returns the object at the head of the list.
\par Example:
   too insert integer a and b into list and make c be the value of b
   which is at head of list|
\code
				DL_List<int> _intlist; #create a list of integers

          int a=123;

          int b=345;

          int c;

          _intlist.insbegin(a)

          _intlist.insbegin(b)
          c=_intlist.headitem()
\endcode
*/
template <class Dtype>
Dtype DL_List<Dtype>::headitem()
{
	return _root->_next->_item;
}

/*!
get tail item
\return returns the object at the tail/end of the list.
\par Example:
   too insert integer a and b into list and make c be the value of b which
   is at the tail of list
\code
				DL_List<int> _intlist; #create a list of integers

          int a=123;

          int b=345;

          int c;
          _intlist.insbegin(a)
          _intlist.insbegin(b)

          c=_intlist.headitem()
\endcode
*/
template <class Dtype>
Dtype DL_List<Dtype>::tailitem()
{
	return _root->_prev->_item;
}

/*!
* \note
  The iterator level must be zero to be able to use this function, else an error will be generated

* \note  The list may not be the same list as this list
* \param otherlist the list to take the items from
*/
template <class Dtype>
void DL_List<Dtype>::takeover(DL_List<Dtype>* otherlist)
{
	if (otherlist==0)
		Error("takeover(DL_List*)",NO_LIST);
	// no iterators allowed on otherlist
	if (otherlist->_iterlevel > 0)
		Error("takeover(DL_List*)",AC_ITER_LIST_OTHER);
	// otherlist not this list
	else if (otherlist == this)
		Error("takeover(DL_List*)",SAME_LIST);

	if (otherlist->_nbitems == 0)
		return;

	//link other list into this list at the end
   _root->_prev->_next=otherlist->_root->_next;
   otherlist->_root->_next->_prev=_root->_prev;
   otherlist->_root->_prev->_next=_root;
   _root->_prev=otherlist->_root->_prev;

	//empty other list
	_nbitems+=otherlist->_nbitems;
	otherlist->_nbitems=0;
	otherlist->_root->_next=otherlist->_root;
	otherlist->_root->_prev=otherlist->_root;
}

//=======================================================================
// implementation class DL_Iter
//=======================================================================
/*! \class DL_Iter
 template iterator for any list/node type\n
 This class is the base class to attach/instantiate an iterator on a double linked list. \n
 DL_List The iterator is used to traverse and perform functions on the nodes of a list.  \n
 More then 1 iterator can be attached to a list. The list keeps track of the
 number of iterators that are attached to it. \n
 Depending on this certain operations are allowed are not. For instance a node can
 only be deleted if there is only one iterator attached to the list. \n
 class | Dtype | Object for traversing a DL_List of the same Dtype
// \par Example
   to insert integer a and b into list and remove_all directly using an iterator
\code
     DL_List<int>* a_list = new DL_List<int>(); // declaration and allocation

     int a=123;

     int b=345;

     {

             DL_Iter<int>*  a_listiter=new DL_Iter<int>(a_list);

             a_listiter->insbegin(a)

             a_listiter->insbegin(b)

             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
*/

/*!
 Error report for list error inside DL_Iter class
 the error function is used internally in the iterator class to report errors,
 the function will generate a message based on the error code.
 Then an exception will be generated using the global booleng class instance.|
 \par Example
 to call error from inside an DL_List class|
 \code
 Error("remove_all",ITER_GT_O);
 \endcode
 \param function: function string that generated this error
 \param a_error:  error code to generate a message for
*/
template <class Dtype>
void DL_Iter<Dtype>::Error(const char* function,Lerror a_error)
{
   char buf[100];
   strcpy(buf,"DL_Iter<Dtype>::");
   strcat(buf,function);
   switch (a_error)
   {
		case NO_MES:             strcat(buf,""); break;
		case NO_LIST:            strcat(buf,"no list attached"); break;
		case NO_LIST_OTHER:      strcat(buf,"no list on other iter"); break;
		case AC_ITER_LIST_OTHER: strcat(buf,"iter not allowed on other list"); break;
		case SAME_LIST:          strcat(buf,"same list not allowed"); break;
		case NOT_SAME_LIST:      strcat(buf,"must be same list"); break;
		case ITER_GT_1:          strcat(buf,"more then one iter"); break;
		case ITER_HITROOT:          strcat(buf,"iter at root"); break;
		case NO_ITEM:            strcat(buf,"no item at current"); break;
		case NO_NEXT:            strcat(buf,"no next after current"); break;
		case NO_PREV:            strcat(buf,"no prev before current"); break;
		case EMPTY:              strcat(buf,"list is empty"); break;
		case NOT_ALLOW:          strcat(buf,"not allowed"); break;
		case ITER_NEG:           strcat(buf,"to much iters deleted"); break;
		default:						 strcat(buf,"unhandled error"); break;
   }
   throw Bool_Engine_Error(buf,"list error", 0, 1); 
}

/*!
   Construct an iterator object for a given list of type Dtype \n
   tcarg: class | Dtype | list item object
\par Example
    How to construct a list of type integer and an iterator for it:
\code
    DL_List<int>* IntegerList;
    IntegerList = new DL_List<int>();
    DL_Iter<int>*  a_listiter=new DL_Iter<int>(IntegerList);
\endcode
\param newlist: list for the iterator
*/
template <class Dtype>
DL_Iter<Dtype>:: DL_Iter(DL_List<Dtype>* newlist)
:_list(newlist), _current(RT)
{
	_list->_iterlevel++;                    // add 1 to  DL_Iters on list
}

/*!
This constructs an iterator for a list using an other iterator on the same list,
The new iterator will be pointing to the same list item as the other iterator.\n
tcarg: class | Dtype | list item object
\par Example
   How to construct a list of type integer and a second iterator for it:|
\code
	DL_List<int>* IntegerList;

  IntegerList = new DL_List<int>();