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

#include <iostream>
#include <stdlib.h>
#include "circularFree.h"

using namespace std;

bool circularFree::testFree(int x)
// Returns TRUE iff x is free
{
if (x<0 || x>=n)
{
  cout << "Range error " << __LINE__ << " \n";
  exit(0);
}
return next[x]!=(-1);
}

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

void circularFree::allocate(int x)
// Allocates x.  Dies if not free.
{
int p,q;

if (!testFree(x))
{
  cout << "Already allocated " << __LINE__ << " \n";
  exit(0);
}
p=prev[x];
q=next[x];
next[p]=q;
prev[q]=p;
prev[x]=next[x]=(-1);
numberFree--;
}

void circularFree::freeUp(int x)
// x is made free.  Dies if not allocated.
{
int q;

if (testFree(x))
{
  cout << "Already free " << __LINE__ << " \n";
  exit(0);
}
q=next[n];
next[x]=q;
prev[x]=n;
next[n]=x;
prev[q]=x;
numberFree++;
}

int circularFree::allocateAny()
// 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;
}

circularFree::circularFree(int n)
{
int i;

this->n=n;
numberFree=n;
prev=new int[n+1];
next=new int[n+1];
if (!prev || !next)
{
  cout << "new failed! "<< __LINE__ << "\n";
  exit(0);
}
for (i=0;i<n;i++)
{
  prev[i]=i-1;
  next[i]=i+1;
}
next[n]=0;
prev[n]=n-1;
prev[0]=n;
}

circularFree::~circularFree()
{
delete [] prev;
delete [] next;
}