---

ToySegmentList.c

/***************************************************************************
                          ToySegmentList.c  -  Core code for creating,
    modifying, copying, sorting, and deleting linked lists of segments.
                             -------------------
    begin                : Sat Jan 25 2003
    copyright            : (C) 2003 by Tyler Montbriand
    student #            : 200200370
    class                : CS330
    email                : monttyle@heavyspace.ca
***************************************************************************/

#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include "ToySegment.h"
#include "ToySegmentList.h"

/*  Remove 'node' from list.  Does not deallocate.  */
void TMM_RemoveFromList(SegList *node)
{
  /*  Can't do anything with nonexistent nodes  */
  if(node==NULL)  return;

  /*  Set nodes before/after it to point around it  */
  if(node->prev!=NULL)  node->prev->next=node->next;
  if(node->next!=NULL)  node->next->prev=node->prev;

  /*  Have this node point to nothing, for safety's sake  */
  node->prev=node->next=NULL;
}

void TMM_InsertBefore(SegList *pos, SegList *node)
{
  node->next=pos;

  if(pos!=NULL)
  {
    node->prev=pos->prev;
    if(pos->prev!=NULL) pos->prev->next=node;
    pos->prev=node;
  }
}

void TMM_InsertAfter(SegList *pos, SegList *node)
{
  /*  First, set up the new node  */
  node->prev=pos;
  if(pos==NULL) node->next=NULL;
  else          node->next=pos->next;

  if(pos!=NULL)
  {
    if(pos->next!=NULL)
    {
      pos->next->prev=node;
    }
    pos->next=node;
  }
}

SegList *TMM_OrderedInsert(SegList *list, SegList *node)
{
  /*  If list doesn't exist, start a new list */
  if(list==NULL)
  {
    node->next=node->prev=NULL;
    return(node);
  }

  /*  Search until position is found  */
  while(list!=NULL)
  {
    if(list->seg.pos>node->seg.pos)
    {
      TMM_InsertBefore(list,node);
      return(TMM_SeekSegListHead(list));
    }
    else if(list->next==NULL)
    {
      TMM_InsertAfter(list,node);
      return(TMM_SeekSegListHead(list));
    }

    list=list->next;
  }

  /*  If this has happened something has gone REALLY wrong */
  return(NULL);
}

/*  Returns size of list in nodes  */
int TMM_SegListSize(SegList *list)
{
  int len=0;
  /*  Yes, we could optimize this algorithm by counting
      forwards and backwards.  but this works, so it's
      good enough for now.                              */
  list=TMM_SeekSegListHead(list);
  /*  A NULL list is actally valid - it means emtpy */
  if(list==NULL)  return(0);

  do  /*  Count every node in the list  */
  {
    len++;
    list=list->next;
  } while(list!=NULL);

  return(len);  /*  Return length */
}


/* Returns 1st memory space capable of holding n elements, or -1 if none
*/
int TMM_FindSegSpace(SegList *list, int n)
{
  list=TMM_SeekSegListHead(list);

  while(list!=NULL)
  {
    if(list->seg.len>=n)        return(list->seg.pos);
    list=list->next;
  }

  return(-1);
}

SegList *TMM_CopySegList(SegList *list)
{
  SegList *copy=NULL;
  list=TMM_SeekSegListHead(list);

  while(list!=NULL)
  {
    SegList *node=TMM_CreateSegList(list->seg.pos,list->seg.len,NULL,NULL);
    copy=TMM_AppendSegList(copy,node);
    list=list->next;
  }
  return(copy);
}

SegList *TMM_AddAreaToSegList(SegList *list, int pos, int len)
{
  /* ToySegment seg={pos,len};*/
  ToySegment seg;
  int intersect=0;
  SegList *head;

  seg.pos=pos;
  seg.len=len;

  if(list==NULL)        return(NULL);

  list=TMM_SeekSegListHead(list);
  head=list;

  while(list!=NULL)
  {
    intersect|=TMM_AreaIntersectsSeg(&seg,&(list->seg));
    list=list->next;
  }
  list=head;

  if(intersect)
  {
    return(list);
  }
  else
  {
    SegList *nlist=TMM_CreateSegList(seg.pos,seg.len,NULL,NULL);
    TMM_AppendSegList(head,nlist);
    list=TMM_SortSegList(list);
    list=TMM_MergeSegList(list);
    return(list);
  }
}

SegList *TMM_MergeSegList(SegList *list)
{
  SegList *head;

  if(list==NULL)        return(NULL);

  list=TMM_SeekSegListHead(list);
  head=list;

  while(list->next!=NULL)
  {
    /* If the two segments are end-to-end, merge 'em - add length to the
       first one, and delete the following. */
    if(list->seg.len+list->seg.pos == list->next->seg.pos)
    {
      SegList *temp=list->next;

      list->seg.len+=temp->seg.len;

      if(temp->prev!=NULL)      temp->prev->next=temp->next;
      if(temp->next!=NULL)      temp->next->prev=list;

      free(temp);

      continue;
    }

    list=list->next;
  }

  return(head);
}

int TMM_CompSegList(const SegList *l1, const SegList *l2)
{
  if(l1->seg.pos>l2->seg.pos)       return(1);
  else if(l1->seg.pos<l2->seg.pos)  return(-1);
  else                              return(0);
}

SegList *TMM_SortSegList(SegList *list)
{
  if(list==NULL)        return(NULL);

  list=TMM_SeekSegListHead(list);

  while(list->next!=NULL)
  {
    /* bubble-sort */
    if(TMM_CompSegList(list,list->next)>0)
    {
      /* Easier to swap data than move nodes */
      ToySegment seg=list->next->seg;
      list->next->seg=list->seg;
      list->seg=seg;
      if(list->prev!=NULL)      list=list->prev;
      continue;
    }

    list=list->next;
  }

  list=TMM_SeekSegListHead(list);
  return(list);
}

SegList *TMM_RemoveAreaFromSegList(SegList *list, int pos, int len)
{
/*  ToySegment seg={pos,len}; */
  ToySegment seg;
  SegList *tail=TMM_SeekSegListEnd(list);
  list=TMM_SeekSegListHead(list);

  seg.pos=pos;
  seg.len=len;

  while(list!=NULL)
  {
    int v;

    ToySegment segs[2];

    v=TMM_SubtractSegs(&(list->seg),&seg,segs);

    switch(v)
    {
    case -1:    /*Nothing*/
      break;

    case 0:
    {
      /*Remove seg from list*/
      SegList *tmp=list->next;

      if((list->prev==NULL)&&(list->next==NULL))


      {
        free(list);
        return(NULL);
      }

      if(list->prev!=NULL)
      {
        list->prev->next = list->next;
      }
      if(list->next!=NULL)
      {
        list->next->prev=list->prev;
      }


      free(list);
      list=tmp;
      continue;
    }

    case 1:
      list->seg.len=segs[0].len;
      list->seg.pos=segs[0].pos;
      /*Modify seg*/
      break;

    case 2:
    {
      SegList *nseg=TMM_CreateSegList(segs[1].pos,segs[1].len,NULL,NULL);

      list->seg.len=segs[0].len;
      list->seg.pos=segs[0].pos;

      TMM_AppendSegList(tail,nseg);
      TMM_SeekSegListEnd(tail);
      break;
    }
    }


    list=list->next;
  }

  list=TMM_SeekSegListHead(tail);
  list=TMM_SortSegList(list);

  return(list);

}

void TMM_PrintSegList(SegList *list)
{
  int n=0;
  list=TMM_SeekSegListHead(list);
  printf("Seg   Pos     Length\n");
  printf("----------------------\n");
  while(list!=NULL)
  {
    printf("%03d        %03d    %03d\n",n,list->seg.pos,list->seg.len);
    list=list->next;
    n++;
  }
}


SegList *TMM_AppendSegList(SegList *list,SegList *node)
{
  list=TMM_SeekSegListEnd(list);

  if(node==NULL)        return(list);
  if(list==NULL)
  {
    node->prev=NULL;
    return node;
  }
  else
  {
    node->prev=list;
    list->next=node;
    return(TMM_SeekSegListHead(list));
  }
}

SegList *TMM_CreateSegList(int pos, int len, SegList *prev, SegList *next)
{
  SegList *list=(SegList *)malloc(sizeof(SegList));

  if(list==NULL)
  {
    /* Out of memory */
    return(NULL);
  }
  else
  {
    list->next=next;
    list->prev=prev;
    list->seg.len=len;
    list->seg.pos=pos;
    return(list);
  }
}

SegList *TMM_SeekSegListHead(SegList *list)
{
  SegList *l=list;

  if(l==NULL)   return NULL;

  while(l->prev!=NULL)  l=l->prev;
  return(l);
}


SegList *TMM_SeekSegListEnd(SegList *list)
{
  SegList *l=list;

  if(l==NULL)   return NULL;

  while(l->next!=NULL)  l=l->next;
  return(l);
}


int TMM_FreeSegList(SegList *list)
{
  SegList *l;
  if(list==NULL)        return(-1);

  l=TMM_SeekSegListHead(list);

  while(l->next!=NULL)
  {
    SegList *temp=l->next;
    free(l);
    l=temp;
  }
  free(l);
  return(0);
}

int TMM_AreaIntersectsSeg(ToySegment *seg1, ToySegment *seg2)
{
  int dp=seg2->pos-seg1->pos;

  if(dp>0)
  {
    if(dp>=seg1->len)   return(0);  /*  No intersect  */
    else                return(1);  /*  Overlap       */
  }
  else
  {
    dp=-dp;
    if(seg2->len<=dp) return(0);    /*  no overlap  */
    else              return(1);    /*  Overlap     */
  }
}


int TMM_SubtractSegs(ToySegment *seg1, ToySegment *seg2, ToySegment segOut[2])
{
  int dp=seg2->pos-seg1->pos;

  if(!TMM_AreaIntersectsSeg(seg1,seg2)) return(-1);

  if(dp>0)
  {
    if(SegEnd(seg2) >= SegEnd(seg1))
    {/*clip off end*/
      int olSize=seg1->len-dp;
      segOut[0].pos=seg1->pos;
      segOut[0].len=seg1->len-olSize;
      return(1);
    }
    else
    {/*Remove chunk from middle*/
      segOut[0].pos=seg1->pos;
      segOut[0].len=dp;
      segOut[1].pos=SegEnd(seg2);
      segOut[1].len=seg1->len-(seg2->len+dp);
      return(2);
    }
  }
  else  /*dp<0*/
  {     /*Make dp non-negative for more intuitive calculations*/
    dp=-dp;

    if(SegEnd(seg2)>=SegEnd(seg1))      return(0);      /*Totally remove*/
    else        /*Clip off front*/
    {
      int olSize=seg2->len-dp;
      segOut[0].pos=seg1->pos+olSize;
      segOut[0].len=seg1->len-olSize;
      return(1);
    }
  }
}

---