// See notes 9.  Maintains free/allocated elements 0 . .  n-1 in O(1)
// time, but can also find a free element.

public class circularFree
{

  public static class circularFreeFails extends Exception
  {
    public circularFreeFails()
    {
      super();
    }

    public circularFreeFails(String message)
    {
      super(message);
    }
  }

  private int n,numberFree;
  private int[] prev,next;

  public boolean testFree(int x) throws circularFreeFails
  // Returns TRUE iff x is free
  {
    if (x<0 || x>=n)
      throw new circularFreeFails("Range error");
    return next[x]!=(-1);
}

  public int freeCount()
  // Returns the number of values available for allocation.
  {
    return numberFree;
  }

  public void allocate(int x) throws circularFreeFails
  // Allocates x.  Dies if not free.
  {
    int p,q;

    if (!testFree(x))
      throw new circularFreeFails("Already allocated");
    p=prev[x];
    q=next[x];
    next[p]=q;
    prev[q]=p;
    prev[x]=next[x]=(-1);
    numberFree--;
  }

  public void freeUp(int x) throws circularFreeFails
  // x is made free.  Dies if not allocated.
  {
    int q;

    if (testFree(x))
      throw new circularFreeFails("Already free");
    q=next[n];
    next[x]=q;
    prev[x]=n;
    next[n]=x;
    prev[q]=x;
    numberFree++;
  }

  public int allocateAny() throws circularFreeFails
  // Allocates some value that is available.
  // Dies if all values in 0 . . n-1 are allocated.
  {
    int p;

    p=next[n];
    allocate(p);
    return p;
  }

  public circularFree(int n)
  {
    int i;

    this.n=n;
    numberFree=n;
    prev=new int[n+1];
    next=new int[n+1];
    for (i=0;i<n;i++)
    {
      prev[i]=i-1;
      next[i]=i+1;
    }
    next[n]=0;
    prev[n]=n-1;
    prev[0]=n;
  }

}