// Examples of circular lists and special cases where constant time
// is obtained.
// See CSE 2320 Notes 9

public class circular
{

  static class listNode
  {
    int content;
    listNode next;

    public void copy(listNode y)
    // Copies fields to y
    {
      y.content=this.content;
      y.next=this.next;
    }
  }

  static void printCircularList(listNode x)
  {
    listNode work;

    System.out.format("Printing circular list\n");
    // Can't use for-loop here
    work=x;
    while (true)
    {
      System.out.format("%d\n",work.content);
      work=work.next;
      if (work==x)
        return;
    }
  }

  static void printList(listNode x)
  {
    System.out.format("Printing ordinary list\n");
    for (listNode work=x; work!=null; work=work.next)
      System.out.format("%d\n",work.content);
  }

  public static void main(String[] args)
  {
    listNode[] garbage=new listNode[10];
    listNode[] zeeList=new listNode[5];
    listNode[] xList=new listNode[3];
    listNode[] yList=new listNode[3];

    // Allocate table entries
    for (int i=0;i<10;i++)
      garbage[i]=new listNode();
    for (int i=0;i<5;i++)
      zeeList[i]=new listNode();
    for (int i=0;i<3;i++)
      xList[i]=new listNode();
    for (int i=0;i<3;i++)
      yList[i]=new listNode();

    // Initialize garbage list
    listNode G=garbage[0];
    for (int i=0;i<9;i++)
      garbage[i].next=garbage[i+1];
    garbage[9].next=null;
    for (int i=0;i<10;i++)
      garbage[i].content=i;

    // Initialize circular list
    listNode z=zeeList[0];
    for (int i=0;i<4;i++)
      zeeList[i].next=zeeList[i+1];
    zeeList[4].next=zeeList[0];
    for (int i=0;i<5;i++)
      zeeList[i].content=(-i-1);

    printList(G);
    printCircularList(z);
    // Include zeeList on garbage list
    listNode work=z.next;
    z.next=G;
    G=work;
    printList(G);

    listNode x=xList[0];
    xList[0].content=1;
    xList[1].content=2;
    xList[2].content=3;
    xList[0].next=xList[1];
    xList[1].next=xList[2];
    xList[2].next=x;
    listNode y=yList[0];
    yList[0].content=4;
    yList[1].content=5;
    yList[2].content=6;
    yList[0].next=yList[1];
    yList[1].next=yList[2];
    yList[2].next=y;
    printCircularList(x);
    printCircularList(y);

    // Concatenate x and y by swapping first nodes.
    listNode temp=new listNode();
    x.copy(temp);
    y.copy(x);
    temp.copy(y);
    x=y;
    printCircularList(x);
  }

}