//  supporting functions - for paging heaps

#include "array.h"
#include <math.h>
extern MArray a;
extern int p;

int first (int);
int pow (int,int);

void adjust (int & n)
//  Adjust the array to allow for a "hole" at the end of each page 
//  adjustment is needed only for paging heaps.
{int k,shift,an;
  
  an = n;			// ??
  shift = n / (p-1);
  n = an + shift;
  for (k=an-1; k>=p-1; k--)
    {  a[k+shift] = a[k];
       if ((k+shift) % p == 0) shift--;
    }
  a.setSize (n);
}

void unadjust (int & n)
//  Undo the adjustment made to the array for paging heaps.
//  "Remove" the hole at the end of each page, compressing the array.
{  int k, shift = 1;

   k = p-1; 
   while (k<n-shift)
     {  if ((k+shift)%p == p-1) shift++;
	a[k] = a[k+shift];
	k++;
     }
   n = k;
   a.setSize (n);
}

void incr (int & i)
//  increment the reference parameter
//  paging heaps need to be aware of the "holes" in the array.
{  i++;
   if ((i+1)%p == 0) i++;   
}

void decr (int & i)
//  decrement the reference parameter
//  paging heaps need to be aware of the "holes" in the array.
{  i--;
   if ((i+1)%p == 0) i--;
}
 
void child (int node, int & lc, int & rc)
//  find the two children of node
//  return their positions in the two reference parameters
{  if (node%p < p/2-1)		// internal node in page
     {  lc = 2*(node%p) + p*(node/p)+1;
	rc = lc + 1;
     }
   else 				// leaf node in page
     {  lc = p*(2*node - p*(node/p) - p + 3);
	rc = lc + p;			// right child
     }
}

int parent (int node)
//  return the position of the parent of node
{  int page = node / p;
   if (node%p == 0)				// root on a page
      return p * ((page-1)/p) + ((page-1)%p)/2 + p/2 - 1;
   else 
      return (node%p-1)/2 + page*p;  	// non root on a page
}