Back to index

PHList.h

 
//----------------------------------------------------------------------------- 
//  The PHOOL's Software 
//  Copyright (C) PHENIX collaboration, 1999 
// 
//  Declaration of class PHList 
// 
//  Purpose: a template list of objects 
// 
//  Description: 
//       - The items are held internally as an array of type T. 
//       - The list is initialized with a maximum size of 2 
//       - If this size is exceeded in the append() function, 
//         the array is allocated anew with double size and the 
//         old list is copied into this new one. Note, since the 
//         items are held by value and not by pointer this can cause 
//         a lot of overhead if the list is used for lots of large 
//         objects. 
//       - clear() sets the number of items to zero. Since the items are 
//         held by value, also their destructors are called. 
//       - clearAndDestroy() does the same. 
//       - The [] operator always performs a bound-check. 
//       - removeLast() returns the last item in the array and 
//         decrements size by one. 
//       - removeAt(i) returns the item at position i and rearranges 
//         the internal list. This can cost PERFORMANCE in your application. 
//         Really, I'm serious, if you have anything else than, let's say, a 
//         list of 100 integers, this can take A LOOONG TIME.  
//       - The output operator '<<' is overloaded for this class. 
//         Therefore class T for which the PHList is instantiated must 
//         also have an overloaded output operator. 
// 
//  Author: Matthias Messer 
//----------------------------------------------------------------------------- 
#ifndef PHLIST_H 
#define PHLIST_H 
 
#include "phool.h" 
#include "PHNode.h" 
#include "PHString.h" 
 
template <class T>  
class PHList  
{  
   
public:  
  PHList();  
  ~PHList();  
 
public:  
  T            operator[](size_t) const; 
  void	   	clear(); 
  void		clearAndDestroy(); 
  size_t	length() const; 
  T 		removeLast(); 
  T 		removeAt(size_t); 
  PHBoolean    append(const T &); 
  PHBoolean    insertAt(const T &, size_t); 
   
private: 
  PHBoolean grow(); 
  void init(); 
   
private:  
  T*        items; 
  size_t    maxNItems; 
  size_t    nItems; 
}; 
 
template<class T> ostream & operator << (ostream &, const PHList<T> &); 
 
// 
// Implementation of member functions 
// 
template<class T> inline PHList<T>::PHList() 
{ 
  init(); 
} 
 
template<class T> inline void PHList<T>::init() 
{    
  maxNItems = 2; 
  items = new T[maxNItems]; 
  nItems = 0; 
} 
 
template<class T> inline PHList<T>::~PHList() 
{ 
  // 
  // This deletes the internal list of items, which also calls their destructors. 
  // 
  delete [] items; 
} 
 
template<class T> inline PHBoolean PHList<T>::grow() 
{ 
  T* buffer = items; 
  items = new T[maxNItems*2]; 
  if (items)  
    { 
      for (size_t i=0; i<maxNItems; i++) 
	{ 
	  items[i] = buffer[i]; 
	} 
      delete [] buffer; 
      maxNItems *= 2; 
    } 
  else  
    { 
      PHMessage("PHList<T>::grow", PHError, "Could not grow. Out of memory?"); 
      return False; 
    } 
 
  return True; 
} 
 
template<class T> inline T PHList<T>::operator[](size_t i) const 
{ 
  if (i < nItems)  
    { 
      return items[i]; 
    } 
  else  
    { 
      PHMessage("PHList<T>::operator[]", PHError, "nItems exceeded"); 
      return 0; 
    } 
} 
 
template<class T> inline PHBoolean PHList<T>::append(const T& item) 
{ 
  if (nItems < maxNItems)  
    { 
      items[nItems] = item; 
      nItems++; 
      return True; 
    } 
  else  
    { 
      if (grow())  
	{ 
	  items[nItems] = item; 
	  nItems++; 
	  return True; 
	} 
      else  
	{ 
	  PHMessage("PHList<T>::append", PHError, "max nItems exceeded"); 
	  return False; 
	} 
    } 
} 
 
template<class T> inline PHBoolean PHList<T>::insertAt(const T& item, size_t pos) 
{ 
  // 
  // This function inserts item at pos in the internal list 
  // 
  if (pos > nItems)  
    { 
      PHMessage("PHList<T>::insertAt", PHError, "insert beyond nItems"); 
      return False; 
     } 
    
   // 
   // Append is used here as a convenient way to let the list grow, if necessary. 
   // 
   append(item); 
    
   // 
   // Now all items are shifted upwards in the list by one, starting at pos. 
   // 
   for (size_t i = nItems; i > pos; i--) 
     { 
       items[i] = items[i-1]; 
     } 
 
   items[pos] = item; 
 
   return True; 
} 
 
template<class T> inline void PHList<T>::clear() 
{ 
   clearAndDestroy(); 
} 
 
template<class T> inline void PHList<T>::clearAndDestroy() 
{ 
   delete [] items; 
   init(); 
} 
 
template<class T> inline size_t PHList<T>::length() const 
{ 
   return nItems; 
} 
 
template<class T> inline T PHList<T>::removeLast() 
{ 
   if (nItems > 0)  
     { 
       return items[nItems--]; 
     } 
   else  
     { 
       PHMessage("PHList<T>::removeLast", PHError, "no items in list"); 
       T dummy; 
       return dummy; 
     }   
} 
 
 
template<class T> inline T PHList<T>::removeAt(size_t i) 
{ 
  if (i > nItems)  
    { 
      T nullItem; 
      return nullItem; 
    } 
 
  T item = items[i]; 
   
  size_t j; 
  for (j = i; j < nItems-1; j++) 
    { 
      items[j] = items[j+1]; 
    } 
  nItems--; 
   
  return item; 
} 
 
// 
// Implementation of external functions. 
// 
template<class T> ostream & operator << (ostream & stream , const PHList<T> & list) 
{ 
  size_t i; 
  for (i = 0; i < list.length(); i++)  
    { 
      stream << list[i] << endl; 
    } 
  return stream; 
} 
 
#endif /* PHLIST_H */  

Back to index