import outbuffer;
template LinkedListTemplate(T){
  class LinkedList {
    T item;
    LinkedList next;
    uint count;
    private LinkedList head;
    private LinkedList last; 

    private int in_range (int val){
      return (val >= 0 && val < count);
    }

    public this (){
      // dummy for an empty list
    }


    public this (T [] t_array){
      this();
      for (int i = 0; i < t_array.length; ++i){
        insert_last(t_array[i]);
      }
    }
    
    public this (T val){
      this();
      item = val;
    
    }


    public char[] toString(){
      OutBuffer buf = new OutBuffer();
      buf.reserve(256);
      
      LinkedList cursor = head;
      buf.write("(");
      while(cursor){
        printf("buf = %*.s\n", buf.toString());
        buf.write(cursor.item);
        cursor = cursor.next;
        if (cursor){
          buf.write(", ");
        }
      }
      buf.write(")");
      return buf.toString();
    }

       
    public int eq (LinkedList other){
      LinkedList cursor_1 = head;
      LinkedList cursor_2 = other.head;
      if (count != other.count){
        return 0;
      }
      while(cursor_1 && cursor_2){
        if (cursor_1.item != cursor_2.item){
          return 0;
        }
        cursor_1 = cursor_1.next;
        cursor_2 = cursor_2.next;
      }
      return 1;
    }
              
    public void set_item(T val)
      out
      {
        assert(item == val);
      }
    body
      {
        item = val;
      }
    
    public void set_next (LinkedList val)
    out 
      {
        assert((val && next == val) || ! next);
        //assert(val == next);
      }
    body
      {
        // printf("in set_next, val = %p\n", val);
        next = val;
        // printf("next = %p", next);
      }

    
    public LinkedList insert_front(T an_item){
      // printf("in insert_front\n");
      LinkedList result = new LinkedList;
      // printf("after new\n");
      result.set_item(an_item);
      // printf("result.item = %d\n", result.item);
      //result.next = head;
      result.set_next(head);
      head = result;
      ++count;
      if (1 == count){
        last = head;
      }
      return result;
    }

    public LinkedList insert_last (T an_item){
      LinkedList result = new LinkedList(an_item);
      ++count;
      if (1 != count){
            last.set_next(result);
            last = result;
      } else {
        last = result;
        head = result;
      }
      return result;
    }
    private void go_to (int position, LinkedList *pre_cursor ){
      LinkedList cursor = head;
      LinkedList pc = cursor;
      int i = 0;
      while (i < position){
        pc = cursor;
        printf("i = %d, pc = %p, pc.item = %d, pc.next = %p\n",
               i, pc, pc.item, pc.next);
        cursor = cursor.next;
        ++i;
      }
      *pre_cursor = pc;
    }
        
        
    public LinkedList insert_at (T an_item, int position){
      printf("position = %d\n", position);
      
      if (0 ==  position){
        return (insert_front(an_item));
      }
      if (position >= count){
        return (insert_last(an_item));
      }
      LinkedList new_element;
      LinkedList pre_cursor;
      go_to(position, &pre_cursor);
      puts("before pre_cursor.set_next");
      new_element = new LinkedList(an_item);
      printf("new_element = %p\n", (void*) new_element);
      LinkedList cursor = pre_cursor.next;
      pre_cursor.set_next(new_element);
      printf("pre_cursor = %p\n", (void*) pre_cursor);
      printf("pre_cursor.next = %p\n", (void*) pre_cursor.next);
      new_element.set_next(cursor);
      ++count;
      return new_element;
    }
      
    
    public T item_at (int position)
      in {
      assert(in_range(position));
    }
    body {
      LinkedList pre_cursor;
      LinkedList cursor = head;
      if (position > 0){
        go_to(position, &pre_cursor);
        cursor = pre_cursor.next;
      }
      return cursor.item;
    }
      

    public void map (void (*fun)(T item)){
      LinkedList cursor = head;
      while(cursor){
        fun(cursor.item);
        cursor = cursor.next;
      }
    }
    
    public LinkedList maplist (T (*fun) (T item)){
      LinkedList result = new LinkedList();
      LinkedList cursor = head;
      while(cursor){
        result.insert_last(fun(cursor.item));
        cursor = cursor.next;
      }
      return result;
    }
    
    public T [] maparray (T (*fun) (T item)){
      LinkedList cursor = head;
      T [] result = new T[count];
      // printf("length = %d\n", result.length);
      int i = 0;
      while (cursor){
        result[i] = fun(cursor.item);
        // printf("result[%d] = %d\n", i, result[i]);
        ++i;
        cursor = cursor.next;
      }
      return result;
    }
    
        
     
    public T [] as_array(){
      T [] result = new T[count];
      LinkedList cursor = head;
      int i = 0;
      while (cursor){
        result[i] = cursor.item;
        ++i;
        cursor = cursor.next;
      }
      return result;
    }


    public LinkedList reverse(){
      LinkedList result = new LinkedList();
      LinkedList cursor = head;
      while(cursor){
        result.insert_front(cursor.item);
        cursor = cursor.next;
      }
      return result;
    }
      
    
    
    public void PrintIntList(){
      LinkedList cursor = head;
      if (! cursor){
        printf("No elements in list");
      }  else {
        while(cursor){
          printf("(at %p val: %d, %p)", cursor, cursor.item, cursor.next);
          cursor = cursor.next;
          if (cursor){
            printf("-> ");
          }
        }
      }
      printf("\n");
    }
  }
}

private int test_fun (int item){
  return item;
}


unittest {
  alias instance LinkedListTemplate(int).LinkedList IntList;
  int [] result;
  IntList res_list;
  res_list = new IntList();
  res_list.insert_last(1);
  res_list.insert_last(2);
  res_list.insert_last(3);
  assert(res_list.item_at(0) == 1);
  assert(res_list.item_at(1) == 2);
  assert(res_list.item_at(2) == 3);
  // assert(res_list.toString() == "(1, 2, 3)");
  static int[3] res_array = [1,2,3];
  result = res_list.maparray(&test_fun);
  assert(result == res_array);
  assert(res_list.as_array() == res_array);
  static int [3] res_array1 = [2,4,6];
  IntList t_list = new IntList(res_array1);
  IntList t2_list = res_list.maplist(double_it);
  assert(t_list.as_array() == t2_list.as_array());
  assert(t_list == t2_list);
  res_list = new IntList();
  res_list.insert_at(1, 0);
  res_list.insert_at(2, 0);
  res_list.insert_at(3, 0);
  // res_list.PrintIntList();
  assert(res_list.item_at(0) == 3);
  assert(res_list.item_at(1) == 2);
  assert(res_list.item_at(2) == 1);
  assert(res_list == res_list.reverse().reverse());
  res_list = new IntList();
  res_list.insert_at(1, 0);
  res_list.insert_at(2, 1);
  res_list.insert_at(3, 1);
  printf("rest_list.item_at(0) = %d\n", res_list.item_at(0));
  printf("rest_list.item_at(1) = %d\n", res_list.item_at(1));
  printf("res_list.item_at(2) = %d\n", res_list.item_at(2));
  assert(res_list.item_at(0) == 1);
  assert(res_list.item_at(1) == 3);
  assert(res_list.item_at(2) == 2);
  res_list.insert_at(20, 10);
  res_list.insert_at(10, 2);
  printf("count = %d, res_list.item_at(count-1) = %d\n", 
         res_list.count, res_list.item_at(res_list.count-1));
  assert(res_list.item_at(res_list.count-1) == 20);
  assert(res_list.item_at(2) == 10);
  res_list.insert_at(30, 1);
  assert(res_list.item_at(1) == 30);
  
  

}


static  int double_it(int val){
  return 2 * val;
}

void show_1(){
  alias instance LinkedListTemplate(int).LinkedList IntList;
  IntList some_int_list;
  static int[] t_arr = [1,2,3];
  some_int_list   = new IntList(t_arr);
  some_int_list.PrintIntList();
}


import stream;
int main(){
  alias instance LinkedListTemplate(int).LinkedList IntList;
  IntList ll, ll_1;

  show_1();
  ll = new IntList;
  printf("after new LinkedList\n");
  ll.insert_front(1);
  ll.insert_front(2);
  ll.insert_front(3);
  printf("ll = %*.s\n", ll.toString());
 
  printf("ll.count = %d\n", ll.count);
  
  int [3] arr = ll.maparray(&double_it);
  for (int i = 0; i < 3; ++i){
    printf("%d, ", arr[i]);
  }
  putchar('\n');
  static int[] t_arr = [1,2,3];
  ll   = new IntList(t_arr);
  ll_1 = new IntList(t_arr);
  printf("ll == ll_1 = %d\n", ll == ll_1);
  
  
  return 0;
}