//-----------------------------------------------------------
// Copyright Christian Arnault LAL-Orsay CNRS
// arnault@lal.in2p3.fr
// See the complete license in cmt_license.txt "http://www.cecill.info". 
//-----------------------------------------------------------

#ifndef __cmt_list_h__
#define __cmt_list_h__

#include <iostream>

template <class T>
class cmt_list_node
{
public:
  cmt_list_node (const T& t) : m_left(0), m_t(t), m_right(0)
  {
  }

  ~cmt_list_node ()
  {
  }

  cmt_list_node<T>* m_left;
  T m_t;
  cmt_list_node<T>* m_right;
};

template <class T>
class cmt_list
{
public:
  typedef cmt_list_node<T> NodeV;
  typedef NodeV* Node;

  class iterator
  {
  public:
    iterator () : m_node (0)
    {
    }

    iterator (Node node) : m_node (node)
    {
    }

    iterator& operator ++ ()
    {
      if (m_node == 0) return (*this);
      m_node = m_node->m_right;
      return (*this);
    }

    iterator& operator -- ()
    {
      if (m_node == 0) return (*this);
      m_node = m_node->m_left;
      return (*this);
    }

    int operator == (const iterator& other) const
    {
      return (m_node == other.m_node);
    }

    int operator != (const iterator& other) const
    {
      const iterator& me = *this;
      return (! (me == other));
    }

    T& operator * () const
    {
      if (m_node == 0)
	{
	  static T t;

	  return (t);
	}
      else
	{
	  return (m_node->m_t);
	}
    }

    Node get_node () const
    {
      return (m_node);
    }

  private:
    Node m_node;
  };

  class const_iterator
  {
  public:
    const_iterator () : m_node (0)
    {
    }

    const_iterator (const Node node) : m_node (node)
    {
    }

    const_iterator& operator ++ ()
    {
      if (m_node == 0) return (*this);
      m_node = m_node->m_right;
      return (*this);
    }

    const_iterator& operator -- ()
    {
      if (m_node == 0) return (*this);
      m_node = m_node->m_left;
      return (*this);
    }

    int operator == (const const_iterator& other) const
    {
      return (m_node == other.m_node);
    }

    int operator != (const const_iterator& other) const
    {
      const iterator& me = *this;
      return (! (me == other));
    }

    const T& operator * () const
    {
      if (m_node == 0)
	{
	  static const T t;
	  return (t);
	}
      else
	{
	  return (m_node->m_t);
	}
    }

    const Node get_node () const
    {
      return (m_node);
    }

  private:
    const Node m_node;
  };

  cmt_list ()
  {
    m_first = 0;
    m_last = 0;
  }

  ~cmt_list ()
  {
    while (m_last != 0)
      {
	remove (m_last);
      }
  }

  void push_front (const T& t)
  {
    Node node = new NodeV (t);

    if (m_first == 0)
      {
	m_last = node;
      }
    else
      {
	m_first->m_left = node;
	node->m_right = m_first;
      }
    m_first = node;
  }

  void push_back (const T& t)
  {
    Node node = new NodeV (t);

    if (m_last == 0)
      {
	m_first = node;
      }
    else
      {
	m_last->m_right = node;
	node->m_left = m_last;
      }
    m_last = node;
  }

  void pop_front ()
  {
    remove (m_first);
  }

  void pop_back ()
  {
    remove (m_last);
  }

  void erase (iterator it)
  {
    remove (it.get_node ());
  }

  void erase (const_iterator it)
  {
    remove (it.get_node ());
  }

  int size ()
  {
    int count = 0;
    Node node = m_first;
    while (node != 0)
      {
	node = node->m_right;
	count++;
      }

    return (count);
  }

  iterator begin ()
  {
    return (iterator (m_first));
  }

  iterator last ()
  {
    return (iterator (m_last));
  }

  iterator end ()
  {
    iterator it;
    return (it);
  }

  const_iterator begin () const
  {
    return (const_iterator (m_first));
  }

  const_iterator last () const
  {
    return (const_iterator (m_last));
  }

  const_iterator end () const
  {
    const_iterator it;
    return (it);
  }

  void exchange (iterator it1, iterator it2)
  {
    if (it1 == it2) return;

    Node node1 = it1.get_node ();
    if (node1 == 0) return;
    Node node2 = it2.get_node ();
    if (node2 == 0) return;

    Node l1 = node1->m_left;
    Node r1 = node1->m_right;
    Node l2 = node2->m_left;
    Node r2 = node2->m_right;

    Node f = m_first;
    Node l = m_last;

    if ((l2 != 0) && (l2 != node1)) l2->m_right = node1;
    if ((r2 != 0) && (r2 != node1)) r2->m_left = node1;
    if ((l1 != 0) && (l1 != node2)) r1->m_right = node2;
    if ((r1 != 0) && (r1 != node2)) r1->m_left = node2;

    node1->m_left  = l2;
    node1->m_right = r2;
    node2->m_left  = l1;
    node2->m_right = r1;

    if (node1 == f)
      {
	m_first = node2;
      }

    if (node1 == l)
      {
	m_last = node2;
      }

    if (node2 == f)
      {
	m_first = node1;
      }

    if (node2 == l)
      {
	m_last = node1;
      }
  }

  void insert_before (iterator it, const T& t)
  {
    Node node = it.get_node ();

    if (node == 0)
      {
	push_front (t);
      }
    else
      {
	Node new_node = new NodeV (t);

	new_node->m_right = node;
	new_node->m_left = node->m_left;

	if (node->m_left != 0)
	  {
	    node->m_left->m_right = new_node;
	  }

	node->m_left = new_node;

	if (node == m_first)
	  {
	    m_first = new_node;
	  }
      }
  }

  void insert_after (iterator it, const T& t)
  {
    Node node = it.get_node ();

    if (node == 0)
      {
	push_back (t);
      }
    else
      {
	Node new_node = new NodeV (t);

	new_node->m_left = node;
	new_node->m_right = node->m_right;

	if (node->m_right != 0)
	  {
	    node->m_right->m_left = new_node;
	  }

	node->m_right = new_node;

	if (node == m_last)
	  {
	    m_last = new_node;
	  }
      }
  }

  void move_to_front (iterator source_it)
  {
    move_before (source_it, begin ());
  }

  void move_to_back (iterator source_it)
  {
    move_before (source_it, end ());
  }

  void move_before (iterator source_it, iterator dest_it)
  {
    if (source_it == dest_it) return;

    Node source = source_it.get_node ();
    if (source == 0) return;

    Node dest = dest_it.get_node ();

    // First remove the source

    if (source == m_first)
      {
	m_first = source->m_right;
      }

    if (source == m_last)
      {
	m_last = source->m_left;
      }

    if (source->m_right != 0) source->m_right->m_left = source->m_left;
    if (source->m_left != 0) source->m_left->m_right = source->m_right;

    source->m_right = 0;
    source->m_left = 0;

    if (dest == 0)
      {
	// = move_to_back
	
	source->m_right = 0;
	source->m_left = m_last;

	if (m_last != 0)
	  {
	    m_last->m_right = source;
	  }

	m_last = source;

	if (m_first == 0) m_first = source;
      }
    else
      {
	source->m_right = dest;
	source->m_left = dest->m_left;

	if (dest->m_left != 0)
	  {
	    dest->m_left->m_right = source;
	  }

	dest->m_left = source;

	if (dest == m_first)
	  {
	    m_first = source;
	  }
      }
  }

  void move_after (iterator source_it, iterator dest_it)
  {
    if (source_it == dest_it) return;

    Node source = source_it.get_node ();
    if (source == 0) return;

    Node dest = dest_it.get_node ();

    // First remove the source

    if (source == m_first)
      {
	m_first = source->m_right;
      }

    if (source == m_last)
      {
	m_last = source->m_left;
      }

    if (source->m_right != 0) source->m_right->m_left = source->m_left;
    if (source->m_left != 0) source->m_left->m_right = source->m_right;

    source->m_right = 0;
    source->m_left = 0;

    if (dest == 0)
      {
	// = move_to_front

	source->m_left = 0;
	source->m_right = m_first;

	if (m_first != 0)
	  {
	    m_first->m_left = source;
	  }

	m_first = source;

	if (m_last == 0) m_last = source;
      }
    else
      {
	source->m_left = dest;
	source->m_right = dest->m_right;

	if (dest->m_right != 0)
	  {
	    dest->m_right->m_left = source;
	  }

	dest->m_right = source;

	if (dest == m_last)
	  {
	    m_last = source;
	  }
      }
  }

private:
  void remove (Node node)
  {
    if (node == 0) return;

    if (node == m_first)
      {
	m_first = node->m_right;
      }

    if (node == m_last)
      {
	m_last = node->m_left;
      }

    if (node->m_right != 0) node->m_right->m_left = node->m_left;
    if (node->m_left != 0) node->m_left->m_right = node->m_right;

    node->m_right = 0;
    node->m_left = 0;

    delete node;
  }

  Node m_first;
  Node m_last;
};

class A
{
public:
  A ()
  {
    static int id = 0;
    i = id;
    id++;
  }

  ~A ()
  {
    std::cout << "kill A i=" << i << std::endl;
  }

  int i;
};

#endif