/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
	/*                                                                           */
	/*                  This file is part of the class library                   */
	/*       SoPlex --- the Sequential object-oriented simPlex.                  */
	/*                                                                           */
	/*    Copyright (C) 1996-2022 Konrad-Zuse-Zentrum                            */
	/*                            fuer Informationstechnik Berlin                */
	/*                                                                           */
	/*  SoPlex is distributed under the terms of the ZIB Academic Licence.       */
	/*                                                                           */
	/*  You should have received a copy of the ZIB Academic License              */
	/*  along with SoPlex; see the file COPYING. If not email to soplex@zib.de.  */
	/*                                                                           */
	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
	
	/**@file  islist.h
	 * @brief Generic single linked list.
	 */
	#ifndef _ISLIST_H_
	#define _ISLIST_H_
	
	#include <assert.h>
	#include <stddef.h>
	#include <iostream>
	
	
	namespace soplex
	{
	
	//---------------------------------------------------------------------
	//  class IsElement<T>
	//---------------------------------------------------------------------
	
	/**@brief   Elements for \ref soplex::IsList "IsList"s.
	   @ingroup Elementary
	
	   Class IsElement allows to easily construct list elements for an intrusive
	   single linked list IsList out of a template class T. It adds a next
	   pointer to each element. An instance of IdElement<T> a can be used just
	   like an instance of T itself, except that method next() has been
	   added (thereby overriding any method next() defined in T).
	 */
	template < class T >
	class IsElement : public T
	{
	protected:
	
	   //--------------------------
	   /**@name Data */
	   ///@{
	   IsElement<T>* the_next;       ///< pointer to next element in the IsList.
	   ///@}
	
	public:
	
	   //---------------------------------
	   /**@name Successor */
	   ///@{
	   ///
	   IsElement<T>*& next()
	   {
	      return the_next;
	   }
	   /// returns the next element in the IsList.
	   IsElement<T>* next() const
	   {
	      return the_next;
	   }
	   ///@}
	
	   //------------------------------------
	   /**@name Constructors / destructors */
	   ///@{
	
	   /// default constructor.
	   IsElement()
	   {}
	
	   ///
	   explicit
	   IsElement(const T& old)
	      : T(old)
	      , the_next(0)
	   {}
	
	   /// copy constructor.
	   /** Only the element itself is copied, while the link to the next list
	       element is set to a zero pointer.
	   */
	   IsElement(const IsElement<T>& old)
	      : T(old)
	      , the_next(0)
	   {}
	};
	
	//---------------------------------------------------------------------
	// class IsList<T>
	//---------------------------------------------------------------------
	
	/**@brief   Generic single linked list.
	   @ingroup Elementary
	
	   Class IsList implements an intrusive single linked list of elements of a
	   template class T. As an \em intrusive list, the objects of type T
	   must provide methods next() for setting and inquiring a pointer to the
	   next element in a list. The user is responsible for not modifying the
	   next() pointer of elements currently residing in a list, which may destroy
	   the lists integrity. For this, class IsList provides enough methods for
	   modifying a list in a save way. See the method list for a description.
	 */
	template < class T >

	class IsList
	{
	protected:
	   T* the_first;   ///< the first element in the IsList.
	   T* the_last;    ///< the last element in the IsList.
	   bool destroyElements;
	   ///< should the destructor be called for each element when the list is destroyed?
	
	public:
	   typedef IsElement<T> Element;
	
	   //--------------------------
	   /**@name Extension */
	   ///@{
	   /// appends \p elem to IsList.
	   void append(T* elem)
	   {
	      if(the_last)
	         the_last->next() = elem;
	      else
	         the_first = elem;
	
	      the_last = elem;
	   }
	
	   /// prepends \p elem to IsList.
	   void prepend(T* elem)
	   {
	      if(the_first)
	         elem->next() = the_first;
	      else
	         the_last = elem;
	
	      the_first = elem;
	   }
	
	   /// inserts \p elem to IsList after its element \p after.
	   void insert(T* elem, T* after)
	   {
	      assert(find(after));
	
	      if(after == the_last)
	         append(elem);
	      else
	      {
	         elem->next() = after->next();
	         after->next() = elem;
	      }
	   }
	
	   /// appends all elements of \p list to IsList.
	   /** Appending one list to another keeps the appended \p list. Instead,
	       \p list remains an own IsList which is then part of the
	       concatenated list. This means that modifying \p list will modify the
	       concateneted list as well and vice versa. The programmer is
	       responsible for such changes not to yield inconsistent lists.
	    */
	   void append(IsList<T>& list)
	   {
	      if(list.the_first)
	      {
	         append(list.the_first);
	         the_last = list.the_last;
	      }
	   }
	
	   /// prepends all elements of \p list to IsList.
	   /** Appending one list to another keeps the appended \p list.  Instead,
	       \p list remains an own IsList which is then part of the
	       concatenated list. This means that modifying \p list will modify the
	       concateneted list as well and vice versa. The programmer is
	       responsible for such changes not to yield inconsistent lists.
	   */
	   void prepend(IsList<T>& list)
	   {
	      if(list.the_first)
	      {
	         prepend(list.the_last);
	         the_first = list.the_first;
	      }
	   }
	
	   /// inserts all elements of \p list after element \p after of an IsList.
	   /** Inserting one list into another keeps the appended \p list. Instead,
	       \p list remains an own IsList which is then part of the
	       concatenated list. This means that modifying \p list will modify the
	       concateneted list as well and vice versa. The programmer is
	       responsible for such changes not to yield inconsistent lists.
	   */
	   void insert(IsList<T>& list, T* after)
	   {
	      assert(find(after));
	
	      if(list.the_first)
	      {
	         list.the_last->next() = after->next();
	         after->next() = list.first();
	
	         if(after == last())
	            the_last = list.last();
	      }
	   }
	   ///@}
	
	   //--------------------------
	   /**@name Removal */
	   ///@{
	   /// removes the successor of \p after from an IsList.
	   void remove_next(T* after)
	   {
	      assert(find(after));
	
	      if(after->next())
	      {
	         if(after->next() == last())
	            the_last = after;
	
	         after->next() = after->next()->next();
	      }
	   }
	
	   /// removes element \p elem from an IsList.
	   void remove(const T* elem)
	   {
	      if(the_first)
	      {
	         if(elem == the_first)
	         {
	            the_first = next(elem);
	
	            if(the_first == 0)
	               the_last = 0;
	         }
	         else
	         {
	            T* after = the_first;
	
	            for(; after != the_last; after = after->next())
	               if(after->next() == elem)
	               {
	                  remove_next(after);
	                  return;
	               }
	         }
	      }
	   }
	
	   /// removes all elements of \p list from an IsList.
	   /** Removing \p list from an IsList requires \p list to be part of the
	       IsList. Such a situation can be achieved by previously adding
	       (i.e., #append%ing, #insert%ing or #prepend%ing) a list or
	       explicitely constructing a sublist with method sublist().
	   */
	   void remove(IsList<T>& list)
	   {
	      if(the_first != 0 && list.the_first != 0)
	      {
	         assert(find(list.first()));
	         assert(find(list.last()));
	
	         if(the_first == list.the_first)
	         {
	            if(the_last == list.the_last)
	               the_first = the_last = 0;
	            else
	               the_first = list.the_last->next();
	         }
	         else
	         {
	            T* after = the_first;
	
	            for(; after->next() != list.the_first; after = after->next())
	               ;
	
	            if(the_last == list.the_last)
	               the_last = after;
	            else
	               after->next() = list.the_last->next();
	         }
	      }
	   }
	
	   /// removes all elements from an IsList.
	   void clear(bool pDestroyElements = false)
	   {

	      if(pDestroyElements)
	      {
	         T* nextElement;
	

	         for(T* it = the_first; it; it = nextElement)
	         {
	            nextElement = next(it);
	            it->~T();

	            spx_free(it);
	         }
	      }
	
	      the_first = the_last = 0;
	   }
	   ///@}
	
	   //--------------------------
	   /**@name Access */
	   ///@{
	   /// returns the IsList's first element.
	   T* first() const
	   {
	      return the_first;
	   }
	
	   /// returns the IsList's last element.
	   T* last() const
	   {
	      return the_last;
	   }
	
	   /// returns successor of \p elem in an IsList.
	   /** The successor of \p elem in a list generally corresponds to the
	       element returned by elem->next(). However, if \p elem is the last
	       element in an IsList, this method will return 0, whereas
	       elem->next() may yield an arbitrary value. For example, if the
	       current list is actually a sublist of another, larger IsList,
	       elem->next() returns the successor of \p elem in this larger
	       IsList.
	    */
	   T* next(const T* elem) const
	   {
	      return (elem == the_last) ? 0 : elem->next();
	   }
	
	   /// returns the number of elements in IsList.
	   int length() const
	   {
	      int num;
	
	      if(the_first)
	      {
	         T* test = the_first;
	
	         for(num = 1; test != the_last; test = test->next())
	            ++num;
	
	         return num;
	      }
	
	      return 0;
	   }
	
	   /// returns the position of element \p elem within IsList.
	   int find(const T* elem) const
	   {
	      const T* test;
	
	      assert(elem != 0);
	
	      for(test = the_first; test != 0; test = next(test))
	         if(test == elem)
	            return 1;
	
	      return 0;
	   }
	
	   /// constructs sublist of an IsList.
	   /** Returns a new IsList containing a sublist of an IsList starting
	       with element \p start and reaching up to element \p end. Both must be
	       members of the IsList or 0, in which case the first and last
	       element are used, respectively.
	    */
	   IsList<T>sublist(const T* start = 0, const T* end = 0) const
	   {
	      IsList<T>part = *this;
	
	      if(start)
	      {
	         assert(find(start));
	         part.the_first = const_cast<T*>(start);
	      }
	
	      if(end)
	      {
	         assert(part.find(end));
	         part.the_last = const_cast<T*>(end);
	      }
	
	      return part;
	   }
	   ///@}
	
	   //--------------------------
	   /**@name Miscellaneous */
	   ///@{
	   /// adjusts list pointers to a new memory address.
	   /** This method is of a rather technical nature. If all list elements
	       are taken form one array of elements, in certain circumstances the
	       user may be forced to realloc this array. As a consequence all
	       next() pointers of the list elements would become invalid.
	       However, all addresses will be changed by a constant offset \p delta.
	       Then move( \p delta ) may be called, which adjusts the next()
	       pointers of all elements in the list.
	   */
	   void move(ptrdiff_t delta)
	   {
	      if(the_first)
	      {
	         T* elem;
	         the_last  = reinterpret_cast<T*>(reinterpret_cast<char*>(the_last) + delta);
	         the_first = reinterpret_cast<T*>(reinterpret_cast<char*>(the_first) + delta);
	
	         for(elem = first(); elem; elem = next(elem))
	            if(elem != last())
	               elem->next() = reinterpret_cast<T*>(reinterpret_cast<char*>(elem->next()) + delta);
	      }
	   }
	
	   /// consistency check.
	   bool isConsistent() const
	   {
	#ifdef ENABLE_CONSISTENCY_CHECKS
	
	      if(first() != 0 && last() == 0)
	         return MSGinconsistent("IsList");
	
	      if(first() == 0 && last() != 0)
	         return MSGinconsistent("IsList");
	
	      if(first() && find(last()) == 0)
	         return MSGinconsistent("IsList");
	
	#endif
	
	      return true;
	   }
	   ///@}
	
	   //------------------------------------
	   /**@name Constructors / Destructors */
	   ///@{
	   /// default constructor.
	   /** The default constructor may be used to setup a (sub-)list, by
	       specifying a \p first and \p last element. Then \p last must be a
	       successor of \p first.
	   */
	   explicit
	   IsList(T* pfirst = 0, T* plast = 0, bool pDestroyElements = false)
	      : the_first(pfirst)
	      , the_last(plast)
	      , destroyElements(pDestroyElements)
	   {
	      if(pfirst)
	      {
	         assert(plast != 0);
	         assert(find(plast));
	      }
	
	      assert(isConsistent());
	   }
	
	   /// destructor
	   ~IsList()
	   {

	      clear(destroyElements);
	   }
	   ///@}
	};
	
	} // namespace soplex
	#endif // _ISLIST_H_