/*******************************************************************
*  Revised By: Qi (Jacky) Liu
*
*  EMAIL: mailto://liuqi@sce.carleton.ca
*
*  Revision Date: Sept. 6, 2005
*******************************************************************/

//-*-c++-*-
#ifndef MULTILIST_CC
#define MULTILIST_CC
// Copyright (c) 1994-1996 Ohio Board of Regents and the University of
// Cincinnati.  All Rights Reserved.

// BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY 
// FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT 
// PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, 
// EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE 
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 
// PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE 
// PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME 
// THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. 

// IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING 
// WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR 
// REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR 
// DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL 
// DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM 
// (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED 
// INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF 
// THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER 
// OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. 

//
// $Id: MultiList.cc,v 1.1.1.1 2007/03/15 15:45:06 rmadhoun Exp $
//
//
//---------------------------------------------------------------------------

#include "../../../JackyDebugStream.h"  //for jacky-debug-mode

template < class Element >
inline
MultiList< Element >::MultiList(){
}


template < class Element >
inline void
MultiList< Element >::initialize(int numObj) {
  numObjects = numObj;
  listSize  = new int[numObj];
  headObj   = new BasicEvent* [numObj];
  tailObj   = new BasicEvent* [numObj];
  findObj   = new BasicEvent* [numObj];
  insertObj = new BasicEvent* [numObj];
  currentObj = new BasicEvent* [numObj];
  lVTArray = new VTime[numObj];
  idleObjArray = new bool[numObj];

  for (int i = 0; i < numObj; i++) {
    listSize[i]  = 0;
    headObj[i]   = NULL;
    tailObj[i]   = NULL;
    findObj[i]   = NULL;
    insertObj[i] = NULL;
    currentObj[i] = NULL;
    lVTArray[i] = ZERO;
    idleObjArray[i] = false;
  }
}

template < class Element >
inline
MultiList< Element >::~MultiList(){
	delete [] listSize;
	delete [] headObj;
	delete [] tailObj;
	delete [] findObj;
	delete [] insertObj;
	delete [] currentObj;
	delete [] lVTArray;
	delete [] idleObjArray;
}

template < class Element >
inline Element*
MultiList< Element >::findFirstAtTime(Element* current){
  Element* firstGuy = current;

  while(firstGuy->prev != NULL &&
	current->recvTime == firstGuy->prev->recvTime) {
    firstGuy = firstGuy->prev;
  }
  findPos = firstGuy;
  return firstGuy;
}

template < class Element >
inline VTime
MultiList< Element >::findPrevTime(int i){
#ifdef MATTERNGVTMANAGER
  VTime retval = PINFINITY;  
  if (currentObj[i] != NULL){
    if(currentObj[i]->prevObj != NULL ) {
      retval = currentObj[i]->prevObj->recvTime;
    }
    else {
      retval = currentObj[i]->recvTime;
    }
  }
  return retval;
#else
  return lVTArray[i];
#endif
}

template <class Element >
inline Element*
MultiList< Element >::peekPrevObj(){
  Element* retval;
  if (currentPos != NULL) {
    if(currentPos->prevObj == NULL) {
      retval = NULL;
    }
    else {
      retval = currentPos->prevObj;
    }
  }
  else {
    retval = NULL;
  }
  return retval;
}

template <class Element >
inline Element*
MultiList< Element >::getObj(int id){
  Element *retval;
  if (currentObj[id] == NULL) {
    retval = NULL;
  }
  else {
    retval = currentObj[id];
  }
  return retval;
}

template <class Element >
inline Element*
MultiList< Element >::setCurrentObjToFindObj(int id) {
  Element *retval;
  currentObj[id] = findObj[id];
  if (currentObj[id] == NULL) {
    retval = NULL;
  }
  else {
    retval = currentObj[id];
  }

  return retval;
}

#ifdef JACKY_INFREQ_STATEMANAGER //[2006-03-15]

//function to reset CurrentObj[localId] to a given position in the miniList
//this is used in TW::coastForward()
template <class Element >
inline void MultiList< Element >::setCurrentObjTo(int localId, Element* target){
	currentObj[localId] = target;
}

#endif //end JACKY_INFREQ_STATEMANAGER [2006-03-15]

template <class Element >
inline bool
MultiList< Element >::testCurrentObj(int id){
  if(currentObj[id] != NULL ){
    return true;
  }
  else {
    return false;
  }
}


// resetMiniHead moves the head of minilist 'i' to the new position for 
// garbage collection
template < class Element >
inline void 
MultiList< Element >::resetMiniHead(int id, VTime& gtime) {

  while (headObj[id] != NULL && 
	 headObj[id]->recvTime < gtime) {
    headObj[id] = headObj[id]->nextObj;
  }
  if (headObj[id] == NULL) {
    tailObj[id] = NULL;
    findObj[id] = NULL;
    insertObj[id] = NULL;
    listSize[id] = 0;
  }
  else {
		//headObj[id]->prevObj = NULL;
    insertObj[id] = tailObj[id];
    findObj[id] = tailObj[id];
  }
}

// seekid moves currentPos to one of the following
//   START + offset    : starting from head of minilist spec. by id
//   CURRENT + offset  : starting from currentpos -- no relation to id
//   END + offset      : starting from tail of minilist spec. by id
template < class Element >
inline Element*
MultiList< Element >::seekId(int offset, listMode_t mode, int id){
  Element* retval;
  int i;
  
  if(abs(offset) < listSize[id]) { 
    // check if offset greater than no. of elmts.
    
    switch (mode) {
    	case START:
      		if ((headObj[id] != NULL) && (offset >= 0)) {
			// start at head, move forward by offset elements
			currentPos = headObj[id];
			for (i = 0; i < offset; i++) {
	  			currentPos = currentPos->nextObj;
			}
			retval = currentPos;
      		} else {
			retval = NULL;
			currentPos = NULL;
      		}
      		break;
    	case CURRENT:
      		if (currentPos != NULL) {
			i = offset;
			if (offset >= 0) {
	  			while ((i > 0) && (currentPos != NULL)) {
	    				// seek forward either the number of steps or until the end
	    				currentPos = currentPos->nextObj;
	    				i--;
	  			}
			} else { // offset < 0
	  			while ((i < 0) && (currentPos != NULL)) {
	    			// seek backward either the number of steps or until the end
	    			currentPos = currentPos->prevObj;
	    			i++;
		  		}
			}
      		}
      		// Now currentPos is either the desired element, or NULL
      		if (currentPos != NULL) {
			retval = currentPos;
      		} else {
			retval = NULL;
			currentPos = NULL;
      		}
      		break;
    	case END:
      		if ((tailObj[id] != NULL) && (offset <= 0)) {
			currentPos = tailObj[id];
			for (i = offset; i < 0; i++) {
		  		currentPos = currentPos->prevObj;
			}
			retval = currentPos;
      		} else {
			retval = NULL;
			currentPos = NULL;
      		}
      		break;
    	default:
      		cerr << "ERROR in MultiList::Seek--Invalid seek mode" << endl;
      		exit(-1);
    } //end switch
  } else { // seek is longer than list size
    retval = NULL;
    currentPos = NULL;
  }
  return retval;
} 


#ifndef JACKY_REVISION

// insert newelem into the main list and adjust minilist pointers
//    insert element means insertion as defined by the compare function
//    both main and minilist are sorted.
// insertPos will point to inserted element.
template < class Element >
inline void
MultiList< Element >::insert(Element* newelem, int listId) {

	  // Mainlist update
	  if (listsize == 0) {
		    // empty list
		    head = newelem;
		    head->prev = NULL;
		    tail = newelem;
		    tail->next = NULL;
	  } else {
		    // insertPos can not be NULL because at least one element exists
		    if(compare(newelem, insertPos) > 0) {    // after insertPos //Jacky: newelem >= insertPos

			      // two cases to consider here
			      //[a] newelem has to be inserted after insertPos as compare
			      //    returned value > 0
			      //[b] compare returned 0. In this case, we have to search
			      //    for the first element with the same id and time

			      while(insertPos != NULL &&  compare(newelem, insertPos) > 0) {
					insertPos = insertPos->next; 
			      }
         		      //Jacky: now insertPos points to the FIRST element > newelem, or NULL
		      
			      if(insertPos==NULL){ // tail reached
					newelem->prev = tail;
					tail->next = newelem;
					tail = newelem;
					newelem->next = NULL;
			      }
		    } else {     // before insertPos  //Jacky: newelem < insertPos

			      while(insertPos != NULL && compare(newelem, insertPos) <= 0) {
					insertPos = insertPos->prev; 
			      }
			      
			      //Jacky: now insertPos points to thhttp://www.zaobao.com/e LAST element < newelem, or NULL

			      if(insertPos == NULL){	// head reached
					newelem->next = head;
					head->prev = newelem;
					head = newelem;
					newelem->prev = NULL;
			      } else {
					insertPos = insertPos->next;
					
					//Jacky: now insertPos points to 1st element >= newelem
			      }
		    }
	  }

	  // insertPos is pointing to NULL if tail or head
	  // and otherwise it is pointing to the element behind insertion point
	  if( insertPos != NULL ){
		    newelem->next = insertPos;
		    newelem->prev = insertPos->prev;
		    insertPos->prev->next = newelem;
		    insertPos->prev = newelem;
	  }
  
	//Jacky: MainList done!
  
	  // Minilist update
	  if (listSize[listId] == 0){    // empty list
		    headObj[listId] = newelem;
		    tailObj[listId] = newelem;
		    headObj[listId]->prevObj = NULL;
		    tailObj[listId]->nextObj = NULL;
	  } else {
		    // insertObj can not be NULL because at least one element exists

		    if(compare(newelem, insertObj[listId]) > 0) {     // after insertPos
			      while(insertObj[listId] != NULL && compare(newelem, insertObj[listId]) > 0) {
					insertObj[listId] = insertObj[listId]->nextObj; 
			      }
			      if(insertObj[listId]==NULL){// tail reached
					newelem->prevObj = tailObj[listId];
					tailObj[listId]->nextObj = newelem;
					tailObj[listId] = newelem;
					newelem->nextObj = NULL;
			      }
		    } else {      // before insertPos

			      while(insertObj[listId] != NULL && compare(newelem, insertObj[listId]) <= 0) {
					if(insertObj[listId]->prevObj != NULL){
						  insertObj[listId] = insertObj[listId]->prevObj; 
					} else {
						  insertObj[listId] = NULL ;
					}
			      }

			      if(insertObj[listId]==NULL){// head reached
					newelem->nextObj = headObj[listId];
					headObj[listId]->prevObj = newelem;
					headObj[listId] = newelem;
					newelem->prevObj = NULL;
			      } else {
					insertObj[listId] = insertObj[listId]->nextObj;
			      }
		    }
  	}
	
	  // insertPos is pointing to NULL if tail or head
	  // and otherwise it is pointing to the element behind insertion point
	  if( insertObj[listId] != NULL ){
		    newelem->nextObj = insertObj[listId];
		    newelem->prevObj = insertObj[listId]->prevObj;
		    insertObj[listId]->prevObj->nextObj = newelem;
		    insertObj[listId]->prevObj = newelem;
	  }
	
	  insertPos = newelem;
	  listsize++;
	
	  insertObj[listId] = newelem;
	  listSize[listId]++;
}

#else //this is Jacky's revision (new element will be inserted at the end of all list elements that are EQUAL)

template < class Element >
inline void
MultiList< Element >::insert(Element* newelem, int listId) {

/*
#ifdef JACKY_DEBUG
        ostream& jacky_os = JackyDebugStream::Instance().Stream();
	jacky_os << endl << "----------------------------------------------------------------------------" << endl << flush;
	jacky_os << "\tMultiList::insert() -> toInsert = {" << *newelem << "}" << endl << flush;
	if(insertPos != NULL){
		jacky_os << "\tMultiList::insert() -> insertPos = {" << *insertPos << "}" << endl << flush;
	} else {
		jacky_os << "\tMultiList::insert() -> insertPos = NULL!" << endl << flush;
	}
#endif
*/
	  // Mainlist update
	  if (listsize == 0) {
		    // empty list
		    head = newelem;
		    head->prev = NULL;
		    tail = newelem;
		    tail->next = NULL;
	  } else {
		    // insertPos can not be NULL because at least one element exists
		    if(compare(newelem, insertPos) >= 0) {    // after insertPos //Jacky: newelem >= insertPos
/*
#ifdef JACKY_DEBUG	
	jacky_os << "\tMultiList::insert() -> toInsert >= insertPos ... move >>>>>>>>" << endl << flush;

#endif
*/
			      // two cases to consider here
			      //[a] newelem has to be inserted after insertPos as compare
			      //    returned value > 0
			      //[b] compare returned 0. In this case, we have to search
			      //    for the first element with the same id and time

			      while(insertPos != NULL &&  compare(newelem, insertPos) >= 0) {
					insertPos = insertPos->next; 
			      }
         		      //Jacky: now insertPos points to the FIRST element > newelem, or NULL
/*
#ifdef JACKY_DEBUG
   
        if(insertPos != NULL){
                jacky_os << "\tMultiList::insert() -> insertPos = {" << *insertPos << "}" << endl << flush;
        } else {
                jacky_os << "\tMultiList::insert() -> insertPos is beyond the TAIL ..." << endl << flush;
        }
#endif
*/		      
			      if(insertPos==NULL){ // tail reached
					newelem->prev = tail;
					tail->next = newelem;
					tail = newelem;
					newelem->next = NULL;
/*
#ifdef JACKY_DEBUG
                jacky_os << "\tMultiList::insert() -> add toInsert to the end of the list." << endl << flush;
#endif
*/
			      }
			
			      //now, insertPos points to the 1st list element that is GREATER than newelem

		    } else {     // before insertPos, i.e. newelem < insertPos
/*
#ifdef JACKY_DEBUG

        jacky_os << "\tMultiList::insert() -> toInsert < insertPos ... move <<<<<<<<" << endl << flush;

#endif
*/
			      while(insertPos != NULL && compare(newelem, insertPos) < 0) {
					insertPos = insertPos->prev; 
			      }
			      
			      //Jacky: now insertPos points to the LAST element <= newelem, or NULL
/*
#ifdef JACKY_DEBUG

        if(insertPos != NULL){
                jacky_os << "\tMultiList::insert() -> insertPos = {" << *insertPos << "}" << endl << flush;
        } else {
                jacky_os << "\tMultiList::insert() -> insertPos is before the HEAD ..." << endl << flush;
        }
#endif
*/
			      if(insertPos == NULL){	// head reached
					newelem->next = head;
					head->prev = newelem;
					head = newelem;
					newelem->prev = NULL;
/*
#ifdef JACKY_DEBUG
                jacky_os << "\tMultiList::insert() -> add toInsert before the head." << endl << flush;
#endif
*/
			      } else {
					insertPos = insertPos->next;
					
					//Jacky: now insertPos points to 1st element > newelem
			      }
		    }
	  }
/*
#ifdef JACKY_DEBUG
        if(insertPos != NULL){
                jacky_os << "\tMultiList::insert() -> should insert BEFORE insertPos = {" << *insertPos 
			 << "}" << endl << flush;
        } else {
		jacky_os << "\tMultiList::insert() -> insertPos = NULL " << endl << flush;
        }

#endif
*/
	  // insertPos is pointing to NULL if tail or head
	  // and otherwise it is pointing to the element behind insertion point
	  if( insertPos != NULL ){
		    newelem->next = insertPos;
		    newelem->prev = insertPos->prev;
		    insertPos->prev->next = newelem;
		    insertPos->prev = newelem;
/*
#ifdef JACKY_DEBUG
                jacky_os << "\tMultiList::insert() -> add toInsert before the insertPos." << endl << flush;
#endif
*/
	  }
  
	//Jacky: MainList done!
/*
#ifdef JACKY_DEBUG
                jacky_os << "\tMultiList::insert() -> Main List done!----------------." << endl << flush;
#endif
*/  
	  // Minilist update
	  if (listSize[listId] == 0){    // empty list
		    headObj[listId] = newelem;
		    tailObj[listId] = newelem;
		    headObj[listId]->prevObj = NULL;
		    tailObj[listId]->nextObj = NULL;
	  } else {
		    // insertObj can not be NULL because at least one element exists
/*
#ifdef JACKY_DEBUG
	if(insertObj[listId] != NULL){	
	        jacky_os << "\tMultiList::insert() -> insertObj[listId] = {" << *insertObj[listId] << "}"<< endl << flush;
	} else {
		jacky_os << "\tMultiList::insert() -> insertObj[listId] = NULL! WRONG!!!!!" << endl << flush;
	}
#endif
*/
		    if(compare(newelem, insertObj[listId]) >= 0) {     // after insertPos
			      while(insertObj[listId] != NULL && compare(newelem, insertObj[listId]) >= 0) {
					insertObj[listId] = insertObj[listId]->nextObj; 
			      }
			      if(insertObj[listId]==NULL){// tail reached
					newelem->prevObj = tailObj[listId];
					tailObj[listId]->nextObj = newelem;
					tailObj[listId] = newelem;
					newelem->nextObj = NULL;
			      }
		    } else {      // before insertPos

			      while(insertObj[listId] != NULL && compare(newelem, insertObj[listId]) < 0) {
					if(insertObj[listId]->prevObj != NULL){
						  insertObj[listId] = insertObj[listId]->prevObj; 
					} else {
						  insertObj[listId] = NULL ;
					}
			      }

			      if(insertObj[listId]==NULL){// head reached
					newelem->nextObj = headObj[listId];
					headObj[listId]->prevObj = newelem;
					headObj[listId] = newelem;
					newelem->prevObj = NULL;
			      } else {
					insertObj[listId] = insertObj[listId]->nextObj;
			      }
		    }
  	}
	
	  // insertPos is pointing to NULL if tail or head
	  // and otherwise it is pointing to the element behind insertion point
	  if( insertObj[listId] != NULL ){
		    newelem->nextObj = insertObj[listId];
		    newelem->prevObj = insertObj[listId]->prevObj;
		    insertObj[listId]->prevObj->nextObj = newelem;
		    insertObj[listId]->prevObj = newelem;
	  }
	
	  insertPos = newelem;
	  listsize++;
	
	  insertObj[listId] = newelem;
	  listSize[listId]++;
}

#endif //JACKY_REVISION

// remove container pointed to by currentPos, returns object pointer 
// ATTENTION: The minilist pointers need to be updated correctly.
// actually resetminihead updates the minilist for us, so this
// allows us to blindly call remove

template < class Element >
inline Element*
MultiList< Element >::removeCurrentObj() {
  return MultiList<Element>::remove(currentPos);
  
}


// remove container pointed to by findObj spec. by id, 
// returns object pointer and 
// resets findObj of id to NULL
template < class Element >
inline Element*
MultiList< Element >::removeFind(int id) {
  Element *removeObj = MultiList<Element>::remove(findObj[id],id);
  findObj[id] = NULL;
  return removeObj;
}

// the argument delptr points to an existing element in the list.
// also, it is assumed that id matches to the minilist id to which 
// delptr is pointing. If no id is specified the default argument for
// id is -1. Note: This implies no minilist update is done.
template < class Element >
inline Element*
MultiList< Element >::remove(Element* delptr, int id) {

  Element *retval;

#ifdef JACKY_DEBUG
        ostream& jacky_os = JackyDebugStream::Instance().Stream();
#endif

#ifdef LPDEBUG
  if(id >= 0) {
    //    printSmallQ(id);
    //    cout << "Id = " << id << " delptr = " << delptr << endl;
  }
#endif

  if ((delptr == NULL) || (listsize == 0)) {
	cerr << "ERROR: MultiList::remove--can't remove NULL elements!" << endl; 
    	retval = NULL;

#ifdef JACKY_DEBUG
	if(delptr == NULL){
		jacky_os << "ERROR: MultiList::remove -- try to remove a NULL pointer, removal failed, NULL returned!" 
			 << endl << flush;
	}
	if(listsize == 0){
		jacky_os << "ERROR: MultiList::remove -- try to remove element from an EMPTY list, removal failed, "
			 << "NULL returned!" << endl << flush;
	}
#endif
    	
  } else { //delptr != NULL && listsize != 0
    // list has at least one element and the pointer which is given 
    // as argument is a pointer in the list

//Jacky: in fact, we cannot guarantee that the delptr pointing to an element that exists in the list
//       the contain() function is defined for this purpose

#ifdef JACKY_DEBUG
	
	if(!contain(delptr)){ //the pointer
		cerr << "ERROR: MultiList::remove -- try to remove an element that does NOT exist in the list!" << endl;
		jacky_os << "ERROR: MultiList::remove -- try to remove an element that does NOT exist in the list!" 
			 << endl << flush;	
		abort();
	}
	
#endif    	

//Jacky: now we are sure that the ptr to be removed does exist in the list!

    	// Main list
#ifndef JACKY_REVISION
   	
	if (head == tail) { // only one element
#else 
	if ((listsize == 1) && (head == tail)) { // only one element
#endif		
      		// sanity check - can be removed later....
      		if (delptr != head) {
			cout << "MultiList: ERROR!  Removing element not in list!" << endl;
			cout << "Element being removed: " << delptr << " " << *(delptr) << endl;
			print();
			abort();
		} else {
			head = NULL;
			tail = NULL;
			insertPos = NULL;
			currentPos = NULL;
			findPos = NULL;
      		} 
    	} else if (head == delptr) { // first element
      		head = delptr->next;
      		head->prev = NULL;
      		if(insertPos == delptr) {
			insertPos = head;
      		}
      		if(currentPos == delptr){
			currentPos = head;
      		}
      		
#ifdef JACKY_REVISION
//Jacky: I think the findPos should be set to NULL if it is removed!
		if(findPos == delptr){
			findPos = NULL;
      		}
#endif      	
	
    	} else if (tail == delptr) { // last element
      		tail = delptr->prev;
      		tail->next = NULL;
      		if(insertPos == delptr) {
			insertPos = tail;
      		}
      		if(currentPos == delptr){
			currentPos = tail;
      		}
#ifdef JACKY_REVISION
//Jacky: I think the findPos should be set to NULL if it is removed!
		if(findPos == delptr){
			findPos = NULL;
      		}
#endif      		
    	} else { // middle
      		delptr->prev->next = delptr->next;
      		delptr->next->prev = delptr->prev;
      		if (insertPos == delptr) {
			insertPos = delptr->next;
      		}
      		if (currentPos == delptr) {
			currentPos = delptr->next;
      		}
      		
#ifndef JACKY_REVISION      		
      		if (findPos == delptr) {
			findPos = delptr->next;
      		}
#else
//Jacky: I think the findPos should be set to NULL if it is removed!
		if(findPos == delptr){
			findPos = NULL;
      		}
#endif      	
    	}
    	
    	//still in if (delptr != NULL && listsize != 0)
    
    	// mini list
    	if (id >= 0) { // is this if test necessary ?

//Jacky: this is a BUG!!! listsize > 0 does NOT necessarily mean that each MiniList is also
//       non-empty!!!
#ifndef JACKY_REVISION    		

      		if (headObj[id] == tailObj[id]) { // only one element

#else //Jacky's revision

#ifdef JACKY_DEBUG
		//First, we need to make sure that the delptr pointing to an element in the minilist 
		if( (listSize[id] == 0) || !contain(delptr, id) ){ //empty minilist or delptr does not exist in it
			cerr << "ERROR: MultiList::remove -- "
			     << "try to remove an element that does NOT exist in the minilist!" << endl;
			jacky_os << "ERROR: MultiList::remove -- " 
				 << "try to remove an element that does NOT exist in the minilist!" << endl << flush;
			abort();
		}
#endif
		
		if ( (listSize[id] == 1) && (headObj[id] == tailObj[id]) ){
#endif      			
			// sanity check - can be removed later....
			if (delptr != headObj[id]) {
	  			cout << "MultiList: ERROR!  Element not in minilist!" << endl;
	  			cout << "Element being removed: " << delptr << " " << *(delptr) << endl;
	  			print();
	  			abort();
			} else {
	  			headObj[id] = NULL;
	  			tailObj[id] = NULL;
		  		insertObj[id] = NULL;
		  		currentObj[id] = NULL;
	  			findObj[id] = NULL;
	  			listSize[id] = 0;
			}
      		} else {  //more than one elements
			if (headObj[id] == delptr) { // first element
	  			headObj[id] = delptr->nextObj;
		  		headObj[id]->prevObj = NULL;
		  		if (insertObj[id] == delptr) {
	    				insertObj[id] = headObj[id];
	  			}
	  			if(currentObj[id] == delptr){
		    			currentObj[id] = headObj[id];
		  		}
#ifndef JACKY_REVISION		  		
	  			if(findObj[id] == delptr){
	    				findObj[id] = headObj[id];
		  		}
#else
				if(findObj[id] == delptr){
	    				findObj[id] = NULL;
		  		}
#endif		  		
			} else if (tailObj[id] == delptr) { // last element
	  			tailObj[id] = delptr->prevObj;
	  			tailObj[id]->nextObj = NULL;
	  			if (insertObj[id] == delptr) {
		    			insertObj[id] = tailObj[id];
	  			}
	  			if(currentObj[id] == delptr){
		    			currentObj[id] = tailObj[id];
	  			}
#ifndef JACKY_REVISION	  			
	  			if(findObj[id] == delptr){
		    			findObj[id] = tailObj[id];
	  			}
#else
				if(findObj[id] == delptr){
	    				findObj[id] = NULL;
		  		}
#endif	  			
			} else { // middle
#ifndef JACKY_REVISION				
		  		if (delptr->prevObj != NULL){		  			
	 				delptr->prevObj->nextObj = delptr->nextObj;
				}
#else

				delptr->prevObj->nextObj = delptr->nextObj;
				
#endif				
	  			delptr->nextObj->prevObj = delptr->prevObj;
	  			if (insertObj[id] == delptr) {
		    			insertObj[id] = delptr->nextObj;
	  			}
	  			if (currentObj[id] == delptr) {
		    			currentObj[id] = delptr->nextObj;
	  			}
#ifndef JACKY_REVISION	  			
	  			if (findObj[id] == delptr) {
		    			findObj[id] = delptr->nextObj;
	  			}
#else
				if (findObj[id] == delptr) {
		    			findObj[id] = NULL;
	  			}
#endif	  			
			}
			listSize[id]--;
      		} //end more than one elements
    	} //end if id >= 0
    
    	retval = delptr;
    	listsize--;
  } //end delptr != NULL && listsize != 0
  
  return retval;
}


// This function calls the backwards search function to find an event
// which satisfies the find mode with respect to time and id as given 
// in the compare function. It is using the findObj pointer if given, 
// otherwise starts at the tail of the minilist. Note: The function is 
// using the minilist not the main list.
template < class Element >
inline Element*
MultiList< Element >::find(Element *element, findMode_t mode, int id){ 
	
#ifdef JACKY_DEBUG
	ostream& jacky_os = JackyDebugStream::Instance().Stream();
#endif	

	  if( findObj[id] == NULL ) {

#ifdef JACKY_DEBUG
	jacky_os << "\tMultiList::find() --> findObj[" << id << "] == NULL, search from tailObj[id]" << endl << flush;
#endif	  	

		    return findBackwards(element, tailObj[id], mode,id);
	  } else {

#ifdef JACKY_DEBUG
	jacky_os << "\tMultiList::find() --> findObj[" << id << "] != NULL, search from findObj[id]" << endl << flush;
#endif
	  	
		    return findBackwards(element, findObj[id], mode,id);
	  }
}


// This function steps further through the minilist specified by the id,
// starting with the element specified in findObj[id]. It steps through 
// the list only as long as there are more events at the same time for this 
// id. End is signalled by returning NULL.
template < class Element >
inline Element* 
MultiList< Element >::findNext(int id) {
  Element *retval;

  // start at list head, if no valid find ptr
  if (findObj[id] == NULL) {
    retval = NULL;
  }
  else {
    // if findPos->next is the time we're looking for, return it
    if (findObj[id]->nextObj == NULL) {
      findObj[id] = NULL;
      retval = NULL;
    }
    else {
      if (compare(findObj[id], findObj[id]->nextObj) == 0) {
				findObj[id] = findObj[id]->nextObj;
				retval = findObj[id];
      }
      else {
				findObj[id] = NULL;
				retval = NULL;
      }
    }
  }
  return retval;
}


// Starting from the startFrom pointer in the list this function finds
// the first occurance of an event with this id and time. From where it 
// moves depending on the mode.
//  [10] - [15] - [15] - [16] = all in the same id list
//                  ^
//                  startFrom and element searched for is 15 EQUAL
//           ^ = result
template < class Element >
inline Element*
MultiList< Element >::findBackwards(Element *element, 
				    Element *startFrom,
				    findMode_t mode, int id){

#ifdef JACKY_DEBUG
	ostream& jacky_os = JackyDebugStream::Instance().Stream();
	jacky_os << "\tMultiList::findBackwards() --> " << endl << flush; 
	jacky_os << "\t\t toFind = {" << (*element) << "}" << endl << flush;
	if(startFrom != NULL){
		jacky_os << "\t\t startFrom = {" << (*startFrom) << "}" << endl << flush;
	} else {
		jacky_os << "\t\t startFrom = {NULL}" << endl << flush;
	}
	jacky_os << "\t\t localId = " << id << endl << flush;	

	//let's print out the current inputQ
	BasicEvent* cursor;
/*
	jacky_os << "-------------------- Current inputQ ----------------------------" << endl << flush;
	cursor = (BasicEvent*)head;
	while(cursor != NULL){
            jacky_os << "<"            		 
            	     << " id=" << cursor->eventId 
            	     << " sign=" << cursor->sign
                     << " " << cursor->sender << "@" << cursor->sendTime 
                     << " => " << cursor->dest << "@" << cursor->recvTime
                     << " alreadyProcessed?" << cursor->alreadyProcessed  << " >" << endl << flush;
            cursor = cursor->next;
        }
	jacky_os << endl << flush;
        jacky_os << "-------------------- miniList pointers for localId = " << id << " ---------------------" 
		 << endl << flush;
        if(headObj[id] != NULL){
        	jacky_os << "\t headObj[" << id << "] = {" << *(headObj[id]) << "}" << endl << flush;
        } else {
        	jacky_os << "\t headObj[" << id << "] = NULL" << endl << flush;
        }
        if(tailObj[id] != NULL){
        	jacky_os << "\t tailObj[" << id << "] = {" << *(tailObj[id]) << "}" << endl << flush;
        } else {
        	jacky_os << "\t tailObj[" << id << "] = NULL" << endl << flush;
        }
        if(findObj[id] != NULL){
        	jacky_os << "\t findObj[" << id << "] = {" << *(findObj[id]) << "}" << endl << flush;
        } else {
        	jacky_os << "\t findObj[" << id << "] = NULL" << endl << flush;
        }
	jacky_os << endl << flush;
*/
	jacky_os << "++++++++++++++++++++++++++ miniList for localId = " << id << "  ++++++++++++++++++++++++++++++++" 
		 << endl << flush;

	//get how many elements in the miniList that are EQUAL to the element
	if(headObj[id] != NULL){
		int equalCount = 0;
		cursor = (BasicEvent*)headObj[id];

		while(cursor != NULL){

			jacky_os << "<"
        	             << " id=" << cursor->eventId
                	     << " sign=" << cursor->sign
	                     << " " << cursor->sender << "@" << cursor->sendTime
        	             << " => " << cursor->dest << "@" << cursor->recvTime
                	     << " alreadyProcessed?" << cursor->alreadyProcessed  << " >" << endl << flush;
			
			
			if(compare(cursor, element) == 0){
				equalCount++;
				jacky_os << "\tEQUAL!" << endl << flush;
			}
			
			cursor = cursor->nextObj;
		}
		jacky_os << "++++++++++++++ " << equalCount  << " EQUAL with toFind in the miniList for localId " << id
                         << "++++++++++++++" << endl << flush;
	} else {
		jacky_os << "+++++++++++++ There are 0 EQUAL with toFind in the miniList for localId " << id 
			 << "+++++++++++++" << endl << flush;
	}
#endif

	  Element *current;

	  current = startFrom;

	  if (current == NULL) {
		    findObj[id] = NULL;
		    findPos = NULL ;
		    
#ifdef JACKY_DEBUG
	jacky_os << "\t\tMultiList::findBackwards() --> startFrom = NULL! return NULL" << endl << flush;
#endif

	  } else {

/*
#ifdef JACKY_DEBUG
        jacky_os << "\t\t^^^ MultiList::findBackwards() -> current = startFrom = {" << *current << "}" << endl << flush;
#endif
*/

		    if( compare(current, element ) >= 0 ) {
			      // the current is greater than or equal to the element we're
			      // looking for - go left..
			      while((current != NULL) && (compare(current, element) >= 0)) {
					current=current->prevObj;
			      }
/*			      
#ifdef JACKY_DEBUG
	if(current != NULL){
	        jacky_os << "\t\t^^^ MultiList::findBackwards() -> current>=toFind, move current <<< to {" 
			 << *current << "}" << endl << flush;
	} else {
		jacky_os << "\t\t^^^ MultiList::findBackwards() -> current>=toFind, move current <<< to NULL (before HEAD)"
			 << endl << flush;
	}
#endif
*/
			      // kludge alert...  The case stuff (below) needs to be fixed instead
			      // of the following 6 lines...  I'l do it later...
			      if(current == NULL) {
					current = headObj[id];
			      } else {
					current = current->nextObj;
			      }
/*			      
#ifdef JACKY_DEBUG
        jacky_os << "\t\t^^^ MultiList::findBackwards() -> current adjusted to {" << *current << "}" 
	    	 << endl << flush;
	//jacky_os << "\t\t^^^ MultiList::findBackwards() -> toFind = {" << (*element) << "}" << endl << flush;
	//jacky_os << "\t^^^ MultiList::findBackwards() -> compare(current, element) = " << compare(current, element) 
	//	 << endl << flush;
#endif
*/
		    } else {
			      // the current is less than the element we're looking for...
			      while( (current !=NULL) && compare(current, element ) < 0 ) {
					current=current->nextObj;
			      }
/*			      
#ifdef JACKY_DEBUG
	if(current != NULL){
	        jacky_os << "\t\t^^^ MultiList::findBackwards() -> current<toFind, move current >>> to {" 
			 << *current << "}" << endl << flush;
	} else {
		jacky_os << "\t\t^^^ MultiList::findBackwards() -> current<toFind, move current >>> to NULL (after TAIL)"
                         << endl << flush;
	}
#endif
*/
		    }

/*
#ifdef JACKY_DEBUG
        jacky_os << endl << "\t\t^^^ MultiList::findBackwards() --> after moving current to the 1st >= toFind or NULL --> " 
		 << endl << flush;

	if(current != NULL){
		jacky_os << "\t\t^^^ current = " << *current << endl << flush;
		jacky_os << "\t\t^^^ compare(current, element) = " << compare(current, element)
	                 << endl << flush;
	} else {
		jacky_os << "\t\t^^^ current = NULL" << endl << flush;
	}
#endif
*/
    
		    // current is now either the first listelem equal to element (if it 
		    // exists), or the first listelem greater than element (if there is 
		    // no equal in the list). //Jacky: or NULL if all listelems are less 
		    // than element
		    switch (mode) {
			    case LESS:
				      if (current == NULL) { // at end of list
						findObj[id] = tailObj[id];
						findPos = findObj[id];
				      } else {
						findObj[id] = current->prevObj;
						findPos = findObj[id];
				      }
				      break;
			    case LESSEQUAL:
				      if (current == NULL) { // at end of list
						findObj[id] = tailObj[id];
						findPos = findObj[id];
				      } else if (compare(element, current) == 0) {
						findObj[id] = current;
						findPos = findObj[id];
				      } else {
						findObj[id] = current->prevObj;
						findPos = findObj[id];
				      }
				      break;
			    case EQUAL:
				      if (current == NULL) {
#ifdef JACKY_DEBUG
        jacky_os << "\t\t^^^ MultiList::findBackwards() -> current == NULL, No EQUAL! =========" << endl << flush;
#endif
						findObj[id] = NULL;
						findPos = findObj[id];
				      } else if (compare(element, current) == 0) {

						//Jacky Note: in the previous version, the compare function will 
						//            NEVER return 0! So here is unreachable!!!
						//            This will cause that when we try to find the equivalent
						//	      (+) msg in the inputQ according to the (-) msg, the
						//            findPos always return NULL (see LTSFInputQueue.cc line
						//	      322). Thus, no msg implosion can be done!!!
						//I think we have to modify the compare function to return 0 when 2 events
						//are equal!!! 
#ifdef JACKY_DEBUG
        jacky_os << "\t\t^^^ MultiList::findBackwards() -> EQUAL! findPos = findObj[id] = " << (*current)
		 << endl << flush;
#endif

						findObj[id] = current;
						findPos = findObj[id];
				      } else { // element is greater; so, nothing was found.
#ifdef JACKY_DEBUG
        jacky_os << "\t\t^^^ MultiList::findBackwards() -> No EQUAL! return NULL =========" << endl << flush;
#endif

						findObj[id] = NULL;
						findPos = findObj[id];
				      }
				      break;
			    case GREATEREQUAL:
				      if (current == NULL) {
						findObj[id] = NULL;
						findPos = findObj[id];
				      } else {
						findObj[id] = current;
						findPos = findObj[id];
				      }
				      break;
			    case GREATER:
				      // Adjust the list to skip over all list elements equal to element
				      while ((current != NULL) && (compare(current,element) == 0)) {
						current = current->nextObj;
				      }
				      if (current == NULL) {
						findObj[id] = NULL;
						findPos = findObj[id];
				      } else if (compare(current, element) > 0) {
						findObj[id] = current;
						findPos = findObj[id];
				      } else { 
				      		//Jacky: I don't this there is such a case!
						findObj[id] = NULL;
						findPos = findObj[id];
				      }
				      break;
			    default:
				      cerr << "ERROR: SortedList::findElement--invalid find mode" << endl;
				      exit(-2);
				      break;
		    }  //end switch
	  }  //end startFrom != NULL

	  if (findObj[id] == NULL) {
		    return NULL;
	  } else {
		    return findObj[id];
	  }
}

template < class Element >
ostream&
operator<< (ostream& os, const MultiList<Element>& ml) {
  register Element *ptr;
  register unsigned i = 0;
  int id, j, col;

  os << (SortedListOfEvents<BasicEvent>&) ml << "\n\n";

  for (i = 0, id = 0; id < ml.numObjects; id++) {
    os << "MiniList " << id << ": length = " << ml.listSize[id] << "\n";
    for (ptr = ml.headObj[id]; ptr != NULL; ptr = ptr->nextObj) {
      os << "MiniList[" << i << "] = " << ptr << " " 
				 << *(ptr) << "\n";
      i++;
    }
    if(ml.currentObj[id]) {
      os << "currentPos : " << ml.currentObj[id] << " " 
				 << *(ml.currentObj[id]) <<endl;
    }
    if(ml.insertObj[id]){
      os << "insertPos : " << ml.insertObj[id] << " " 
				 << *(ml.insertObj[id]) <<endl;
    }
    if(ml.findObj[id]) {
      os << "findPos : " << ml.findObj[id] << " " 
				 << *(ml.findObj[id]) <<endl;
    }
    os << "-----\n" << endl;
  }
	
  col = 0;
  os << "\n\ncurrentObjArray:\n";
  for(j=0; j< ml.numObjects; j++){
    if (col >= 64) {
      os << "\n";
      col = 0;
    }
    if(ml.currentObj[j] != NULL){
      // Chris: This was lVTArray, but I changed it because that was not
      // being set consistently and I think printCurrentObj should print
      // either the pointer or some value referenced through currentObj.
      os << "(" << j << ")" << ml.currentObj[j] << "["
				 << ml.currentObj[j]->recvTime << "] ";
      col += 16;
    }
    else {
      col += 5;
      os << "NULL ";
    }
  }
  os << "\n\nlVTarray:\n";
	
  for(j=0; j< ml.numObjects; j++){
    if (j%8 == 0) {
      os << "\n";
    }
    os << "(" << j << ")" << ml.lVTArray[j] << " ";
  }
  os << endl;
	
  return( os );
	
}

template < class Element >
inline void
MultiList < Element >::printSmallQ(ostream& out,int id) {
  register Element *ptr;
  register unsigned i = 0;
	
  out << "MiniList " << id << endl;
  out << "length = " << listSize[id] << "\n";
  for (ptr = headObj[id]; ptr != NULL; ptr = ptr->nextObj) {
    out << "MiniList[" << i << "] = " << ptr << " " 
				<< *(ptr) << "\n";
    i++;
  }
  if(currentObj[id]) {
    out << "currentPos : " << currentObj[id] << " " 
				<< *(currentObj[id]) <<endl;
  }
  if(insertObj[id]){
    out << "insertPos : " << insertObj[id] << " " 
				<< *(insertObj[id]) <<endl;
  }
  if(findObj[id]) {
    out << "findPos : " << findObj[id] << " " 
				<< *(findObj[id]) <<endl;
  }
  if(tailObj[id]) {
    out << "tailPos : " << tailObj[id] << " " 
				<< *(tailObj[id]) <<endl;
  }
	out << "-----\n" << endl;
}

template < class Element >
inline void
MultiList < Element >::printCurrentObj() {
	//  for(int i =0; i< numObjects; i++){
	//    if(currentObj[i] != NULL && currentObj[i]->prevObj != NULL)
	//    cout << currentObj[i]->prevObj->object->recvTime << " ";
	//  }
	//  cout << endl;
  int j, col;
  col = 0;
  for(j=0; j< numObjects; j++){
    if (col >= 64) {
      cout << "\n";
      col = 0;
    }
    if(currentObj[j] != NULL){
      // Chris: This was lVTArray, but I changed it because that was not
      // being set consistently and I think printCurrentObj should print
      // either the pointer or some value referenced through currentObj.
      cout << "(" << j << ")" << currentObj[j] << "["
					 << currentObj[j]->recvTime << "] ";
      col += 16;
    }
    else {
      col += 5;
      cout << "NULL ";
    }
  }
  cout << endl;
}

template < class Element >
inline void
MultiList < Element >::printlVTArray() {
  int j;
  for(j=0; j< numObjects; j++){
    if (j%8 == 0) {
      cout << "\n";
    }
    cout << "(" << j << ")" << lVTArray[j] << " ";
  }
  cout << endl;

}

template <class Element>
inline Element*
MultiList <Element>::getHead(int id) {
  return headObj[id];
}


#ifdef JACKY_REVISION  //=========================================================================

//this function is to test whether the given pointer really pointing to an element in the list
//used for debugging purpose in remove() function
template <class Element>
bool MultiList <Element>::contain(Element* ptr){
	int result = 0; //result = 0, default is FALSE
	if(listsize == 0) { //empty list
		return false;	
	} else { //non-empty list
		Element* tempPtr = head;
		while(tempPtr != NULL){
			if(tempPtr == ptr){ //one element found
				++result; 
			}
			tempPtr = tempPtr->next;
		}
	}
	
	if(result > 1){ //strange: there are 2 or more elements in the list with the same address
		cerr << "MultiList::contain(ptr) --> more than one elements in the list have the same address!" << endl;
		abort();	
	}
	
	if(result == 1) {
		return true;	
	} else { //result = 0
		return false;
	}
}

//this function is to test whether the given pointer really pointing to an element in the minilist
//identified by localId for debugging purpose in remove() function
template <class Element>
bool MultiList <Element>::contain(Element* ptr, int localId){
	int result = 0; //result = 0, default is FALSE
	if(listSize[localId] == 0) { //empty minilist
		return false;	
	} else { //non-empty minilist
		Element* tempPtr = headObj[localId];
		while(tempPtr != NULL){
			if(tempPtr == ptr){ //one element found
				++result; 
			}
			tempPtr = tempPtr->nextObj;
		}
	}
	
	if(result > 1){ //strange: there are 2 or more elements in the minilist with the same address
		cerr << "MultiList::contain(ptr, int) --> more than one elements in the minilist have the same address!" << endl;
		abort();	
	}
	
	if(result == 1) {
		return true;	
	} else { //result = 0
		return false;
	}
}

#endif  //end JACKY_REVISION ==============================================================================

#endif  //end MULTILIST_CC