// See notes 9. Maintains free/allocated elements 0 . . n-1 in O(1) // time, but can also find a free element. #include #include #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