module clist;

import std.stdarg;


// Minimal Circular list

/*
  Circular lists are efficient, concise and useful!
  1. Walk the list forward and use append , the list is a stack
  2. Walk the list backward and use append, the list is a queue
  3. Keep a max/min/mid and you know which way to walk list for searches/sorted inserts
  4. Reinsert search results to head of the list = MRU cache
*/



class CList(T)
{
  protected:
  alias typeof(this)    clist;
  clist                 next, prev;
  T                     data;

  public:
  this( T val ) { data = val; next = prev = this; }

  T value() { return data; }
  T value( T newval ) { return data=newval; }
  T*  ptr()   { return &data; }


  // static initializer function
  static clist opCall(...)
  {
    clist result = null;
    for (int i = 0; i < _arguments.length; i++)
    {
      if ( _arguments[i]==typeid(T) )
      {
        result = append( result, va_arg!(T)(_argptr) )[0];
      }
      else if ( _arguments[i]==typeid(clist) )
      {
        clist tmp = va_arg!(clist)(_argptr);
        result = append( result, tmp.data );
      }
      else break;
    }
    return result.next;
  }

  static clist insert( clist list,T val )
  {
    clist tmp = new clist( val );
    if ( list is null ) return tmp;
    tmp.prev = list.prev;
    tmp.next = list;
    list.prev.next = tmp;
    list.prev = tmp;
    return tmp;
  }

  static clist append( clist list,T data )
  {
    if ( list is null ) return new clist(data);
    return insert( list.next, data );
  }

  static void remove( CList node )
  {
    if ( node.next is node ) return;
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = node.next = node;
  }

  static clist copy( clist list )
  {
    if ( list is null ) return null;
    clist cur =  list;
    clist result = null;
    do {
      result= append(result, cur.data);
      cur = cur.next;
    }
    while( !( cur is list ) ) ;
    return result;
  }

  clist   reverse()
  {
    clist cur = this;
    clist result = null;

    do
    {
      result = insert( result, cur.data );
      cur = cur.next;
    }
    while( cur!=this );
    return result;
  }


  clist opCat( T val )   { return append( copy(this),val ); }
  clist opCat_r( T val ) { return insert( copy(this),val ); }

  clist opCat( clist other )
  {
    clist cur = null;
    foreach( T val; this )  cur = append( cur, val );
    foreach( T val; other ) cur = append( cur, val );
    return cur.next;
  }

  clist find( T val )
  {
    clist cur = this;
    while( cur.data != val )
    {
      cur = cur.next;
      if ( cur is this ) return null; // was not found
    }
    return cur;
  }


  clist opIndex( int n )
  {
    clist cur = this;
    while( n>0 ) { cur = cur.next; n--; }
    while( n<0 ) { cur = cur.prev; n++; }
    return cur;
  }

  void    detach() { remove( this ); }

  uint  count()
  {
    uint result = 1;
    clist cur = this.next;
    while( ( cur is this )==false )
    {
      result++;
      cur = cur.next;
    }
    return result;
  }

  int    opApply( int delegate( inout T val ) dg )
  {
    clist   cur = this;
    int result ;
    do  {
      result= dg( cur.data );
      if ( result==0 ) cur = cur.next;
      else break;
    }
    while( ( cur is this )==false )

    return result;
  }
}


version(Test)
{
  import std.stdio;

  alias CList!(int)     ilist;
  alias CList!(char[])  strlist;

  void main( char[][] arg )
  {
    ilist a = ilist(100) ~ 200 ~ 300;

    writefln( "Count is %s", a.count );

    foreach( int i; a ) { writefln("A Item= %s", i ); }

    ilist b = ilist( 200,300,400,500,600 );
    foreach( int i; b ) { writefln("B Item= %s", i ); }

    ilist c = a ~ b;
    c[-1].detach();
    foreach( int i; c ) { writefln("C Item= %s", i ); }

    c = c.find(200);
    if ( c is null ) {} else writefln("found 200 in C, %s = next", c.value );

    strlist s = strlist( "Hello", "World", "!" );
    foreach( char[] st ; s ) writefln(" S : %s", st );

    s = strlist(s[0], "Cruel" , s[1] , s[2] );
    foreach( char[] st ; s ) writefln(" S2 : %s", st );

    s = s.reverse();
    foreach( char[] st ; s ) writefln(" S2 Reversed : %s", st );
  }
}