/*
 * Mark ring package
 *
 * Copyright (c) 1993, 1995
 *      ONO Kouichi             onono@fuka.info.waseda.ac.jp
 * All rights reserved.
 */

#include "xdvi-config.h"	/* added by Masahito Yamaga */
#include "markring.h"
#include <stdio.h>
/* #include <malloc.h> */
/* removed by Masahito Yamaga for BSD/OS (suggested by Mr. S.Hagihira) */

void
  MakeRingNull(ring)
MARKRING        *ring;
{
  ring->front = INITIAL_FRONT;
  ring->rear = INITIAL_REAR;
}

MARKRING
  *CreateNewRing()
{
  MARKRING      *ring = NULL;

  /* calloc() ---> xcalloc() by Masahito Yamaga */
  ring = (MARKRING *) xcalloc(1, sizeof(MARKRING));
  MakeRingNull(ring);
  return ring;
}

BOOL
  EmptyRing(ring)
MARKRING        *ring;
{
  return Is_Empty_Location(ring->front, ring->rear);
}

BOOL
  ElementExistsHereInRing(index, ring)
RING_LOCATION   index;
MARKRING        *ring;
{
  if(EmptyRing(ring)) {
    return FALSE;
  } else {
    return BetweenOnRing(ring->front, ring->rear, index);
  }
}

BOOL
  BetweenOnRing(pre, post, index)
RING_LOCATION   pre, post, index;
{
  if(pre<=post) {
    return ((pre<=index)&&(index<=post));
  } else {
    /* pre>post */
    return (   (INITIAL_FRONT<=index) && (index<=        post)
            || (pre          <=index) && (index<=INITIAL_REAR));
  }
}

BOOL
  MemberOfRing(elem, ring)
RING_ELEMENT    elem;
MARKRING        *ring;
{
  register RING_LOCATION index = ring->front;
  
  while(! Is_Empty_Location(index, ring->rear)) {
    if(ring->element[index]==elem) {
      return TRUE;
    } else {
      index = Ring_Next_Location(index);
    }
  }
  return FALSE;
}

RING_LOCATION
  LocationOfMemberInRing(elem, ring)
RING_ELEMENT    elem;
MARKRING        *ring;
{
  register RING_LOCATION index = ring->front;
  
  while(! Is_Empty_Location(index, ring->rear)) {
    if(ring->element[index]==elem) {
      return index;
    } else {
      index = Ring_Next_Location(index);
    }
  }
  return ILLEGAL_LOCAT;
}

RING_ELEMENT
  RingTopElement(ring)
MARKRING        *ring;
{
  if(EmptyRing(ring)) {
    fprintf(stderr, "Mark ring has no elements.\n");
  } else {
    return ring->element[ring->front];
  }
}

RING_ELEMENT
  RingLastElement(ring)
MARKRING        *ring;
{
  if(EmptyRing(ring)) {
    fprintf(stderr, "Mark ring has no elements.\n");
  } else {
    return ring->element[ring->rear];
  }
}

NUMBER
  NumberOfElementsInRing(ring)
MARKRING        *ring;
{
  register NUMBER num = 0;
  
  if(EmptyRing(ring)) {
    return num;
  } else {
    register RING_LOCATION index = ring->front;
    
    while(! Is_Empty_Location(index, ring->rear)) {
      num++;
      index = Ring_Next_Location(index);
    }
    return num;
  }
}

void
  PurgeOldElementFromRing(ring)
MARKRING        *ring;
{
  if(EmptyRing(ring)) {
    fprintf(stderr, "Mark ring has no elements.\n");
  } else {
    ring->front = Ring_Next_Location(ring->front);
    /* forget the oldest (first-in) element to free space */
  }
}

void
  PurgeLastElementFromRing(ring)
MARKRING        *ring;
{
  if(EmptyRing(ring)) {
    fprintf(stderr, "Mark ring has no elements.\n");
  } else {
    ring->rear = Ring_Prev_Location(ring->rear);
    /* forget the last (last-in) element to free space */
  }
}

void
  PurgeElementHereFromRing(index, ring)
RING_LOCATION   index;
MARKRING        *ring;
{
  if(ElementExistsHereInRing(index, ring)) {
    RING_LOCATION prev, next;
    
    ring->rear = Ring_Prev_Location(ring->rear);
    next = index;
    prev = next;
    while(! Is_Empty_Location(prev, ring->rear)) {
      next = Ring_Next_Location(prev);
      ring->element[prev] = ring->element[next];
      prev = next;
    }
  } else {
    fprintf(stderr, "There is no elements in the Mark ring.\n");
  }
}

void
  PurgeTheValueAllFromRing(elem, ring)
RING_ELEMENT    elem;
MARKRING        *ring;
{
  register RING_LOCATION index;
  
  while((index = LocationOfMemberInRing(elem, ring))!=ILLEGAL_LOCAT) {
    PurgeElementHereFromRing(index, ring);
  }
}

void
  AddElementToRing(elem, ring)
RING_ELEMENT    elem;
MARKRING        *ring;
{
  if(Is_Empty_Location(ring->front, Ring_Next_Location(ring->rear))) {
    PurgeOldElementFromRing(ring);
  }
  ring->rear = Ring_Next_Location(ring->rear);
  ring->element[ring->rear] = elem;
}

void
  InsertElementToRing(elem, ring)
RING_ELEMENT    elem;
MARKRING        *ring;
{
  if(Is_Empty_Location(Ring_Prev_Location(ring->front), ring->rear)) {
    PurgeLastElementFromRing(ring);
  }
  ring->front = Ring_Prev_Location(ring->front);
  ring->element[ring->front] = elem;
}

void
  RotateRing(ring)
MARKRING        *ring;
{
  RING_ELEMENT    elem;
  
  if(EmptyRing(ring)) {
    fprintf(stderr, "Mark ring has no elements.\n");
  } else {
    elem = RingLastElement(ring);
    PurgeLastElementFromRing(ring);
    InsertElementToRing(elem, ring);
  }
}

void
  ReverseRotateRing(ring)
MARKRING        *ring;
{
  RING_ELEMENT    elem;
  
  if(EmptyRing(ring)) {
    fprintf(stderr, "Mark ring has no elements.\n");
  } else {
    elem = RingTopElement(ring);
    PurgeOldElementFromRing(ring);
    AddElementToRing(elem, ring);
  }
}

MARKRING
  *CopyRing(ring)
MARKRING        *ring;
{
  register RING_LOCATION index = ring->front;
  MARKRING            *newring = NULL;
  
  newring = CreateNewRing();
  while(! Is_Empty_Location(index, ring->rear)) {
    AddElementToRing(ring->element[index], newring);
    index = Ring_Next_Location(index);
  }
  return newring;
}

MARKRING
  *MakeRingUnique(ring)
MARKRING        *ring;
{
  register RING_LOCATION index = ring->front;
  MARKRING            *newring = NULL;
  
  newring = CreateNewRing();
  while(! Is_Empty_Location(index, ring->rear)) {
    if(! MemberOfRing(ring->element[index], newring)) {
      AddElementToRing(ring->element[index], newring);
    }
    index = Ring_Next_Location(index);
  }
  return newring;
}

int
  RingElemCompare(elem1, elem2)
RING_ELEMENT *elem1, *elem2;
{
  return *elem1-*elem2;
}

MARKRING
  *MakeRingSort(ring)
MARKRING        *ring;
{
  MARKRING      *newring = NULL;
  
  newring = CopyRing(ring);
  qsort(newring->element, newring->rear+1,
        sizeof(RING_ELEMENT), RingElemCompare);
  return newring;
}

LIST_LOCATION
  MakeListFromRing(ring, list)
MARKRING        *ring;
LIST_ELEMENT    list[LISTSIZE];
{
  register RING_LOCATION index;
  register LIST_LOCATION loc = INITIAL_LIST;
  
  index = ring->front;
  
  while(! Is_Empty_Location(index, ring->rear)) {
    list[loc] = ring->element[index];
    loc++;
    index = Ring_Next_Location(index);
  }
  return loc-1;
}