/*
 * Fsanity.c
 *
 * The author of this software is Alain K\"{a}gi.
 *
 * Copyright (c) 1993 by Alain K\"{a}gi and the University of Wisconsin
 * Board of Trustees.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR NOR THE UNIVERSITY OF
 * WISCONSIN MAKE ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING
 * THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
 * PURPOSE.
 *
 * ------------------------------------------------------------------------
 *
 * This a collection of functions which check certain invariants.
 *   
 * ------------------------------------------------------------------------
 *
 * $Id$
 *
 */

#include <stdio.h>
#include "Fheap.h"
#include "Fstruct.h"

int
SanityCheck1(HeapP * h, Item * i)
{
  HeapP * h1;

  if(h == NULL_HEAP)
  {
     return(TRUE);
  }

  h1 = h;
  do
  {
    if(LessThan(ITEM(h1), i))
    {
      return(FALSE);
    }
    if(!SanityCheck1(CHILD(h1), ITEM(h1)))
    {
      return(FALSE);
    }

    h1 = FORWARD(h1);
  }
  while(h1 != h);

  return(TRUE);
}

int
SanityCheck2(HeapP * h)
{
  int   sum;
  HeapP * h1;
  HeapP * h2;

  if(h == NULL_HEAP)
  {
     return(TRUE);
  }

  h1 = h;
  do
  {
    if(CHILD(h1) != NULL_HEAP)
    {
      sum = 0;
      h2 = CHILD(h1);
      do
      {
         sum += RANK(h2) + 1;

         h2 = FORWARD(h2);
      }
      while(h2 != CHILD(h1));
      if(sum != RANK(h1))
      {
        return(FALSE);
      }

      if(!SanityCheck2(CHILD(h1)))
      {
        return(FALSE);
      }
    }

    h1 = FORWARD(h1);
  }
  while(h1 != h);

  return(TRUE);
}

int
SanityCheck3(HeapP * h, int rank)
{
  int   sum;
  HeapP * h1;
  HeapP * h2;

  if((h == NULL_HEAP) && (rank == 0))
  {
     return(TRUE);
  }

  sum = 0;
  h1 = h;
  do
  {
    sum += RANK(h1) + 1;

    if(!SanityCheck3(CHILD(h1), RANK(h1)))
    {
      return(FALSE);
    }

    h1 = FORWARD(h1);
  }
  while(h1 != h);

  if(sum == rank)
  {
    return(TRUE);
  }
  else
  {
    return(FALSE);
  }
}

void
PrettyPrint(HeapP * h)
{
  HeapP * h1;

  if(h == NULL_HEAP)
  {
    printf(" nil ");
    return;
  }

  printf("(");

  h1 = h;
  do
  {
    //PrintItem(ITEM(h1));
    printf("[%u] ", RANK(h1));
    PrettyPrint(CHILD(h1));
    h1 = FORWARD(h1);
  }
  while(h1 != h);

  printf(")");
}