---

LinkedLists.c

Go to the documentation of this file.

/* Single and indirect linked lists.*/

#include <stdlib.h>
#include <math.h>
#include "LinkedLists.h"


UInt32 DestroyLinkedList(NodePtr linkedList, UInt8 (*DestructorFunction)(NodePtr theNode))
{
  
  NodePtr curNode, copyPtr;
  UInt32 nbrDestroyed = 0;
  if (!DestructorFunction)
    return 0;
  for (curNode = linkedList; curNode;)
  {
    copyPtr = curNode->next;
    if (DestructorFunction(curNode))
      return nbrDestroyed;
    nbrDestroyed++;
    curNode = copyPtr;
  }
  return nbrDestroyed;
}

UInt8 DestroyIndirectNode(NodePtr theNode)
{
  free((IndirectNodePtr)(theNode));
  return (!theNode);
}


UInt32 FindLast(NodePtr linkedList, NodePtr* last)
{
  
  NodePtr curNode;
  UInt32 nbrNodes = 0;
  for (curNode = linkedList; curNode->next; curNode = curNode->next)
    nbrNodes++;
  if (last)
    *last = curNode;
  return (nbrNodes + 1);
}


NodePtr GetNthNode(NodePtr linkedList, UInt32 n)
{
  NodePtr curNode = linkedList;
  while ( (n--) && (curNode) )
    curNode = curNode->next;
  return curNode;
}


NodePtr SplitAtNth(NodePtr linkedList, UInt32 n)
{
  UInt32 curPos = 0;
  NodePtr curNode, copyPtr;
  for (curNode = linkedList; (++curPos) != n; curNode = curNode->next)
  {
    if (!curPos)
      return NULL;
  }
  copyPtr = curNode->next;
  curNode->next = NULL;
  return copyPtr;
}


IndirectNodePtr FindAndList(NodePtr linkedList, UInt8 (*IsWhatIWant)(NodePtr theNode))
{
  NodePtr curNode;
  IndirectNodePtr foundList = NULL, lastInFoundList = NULL;
  if (!IsWhatIWant)
    return NULL;
  for(curNode = linkedList; curNode; curNode = curNode->next)
  {
    if (IsWhatIWant(curNode))
    {
      IndirectNodePtr newNode = malloc(sizeof(IndirectNode));
      newNode->nodePtr = curNode;
      if (!foundList)
      {
  foundList = newNode;
  lastInFoundList = newNode;
      }
      else
      {
  lastInFoundList->nodeHeader.next = (Node*)(newNode);
  lastInFoundList = newNode;
      }
      lastInFoundList->nodeHeader.next = NULL;
    }
  }
  return foundList;
}


NodePtr FindAndMoveOut(NodePtr *linkedListPtr, UInt8 (*IsWhatIWant)(NodePtr theNode))
{
  NodePtr *curNodePtrPtr, newList;
  IndirectNodePtr foundList = FindAndList(*linkedListPtr, IsWhatIWant), curIndirect;
  if (!foundList)
    return NULL;
  curIndirect = foundList;
  for(curNodePtrPtr = linkedListPtr; *curNodePtrPtr;)
  {
    if (*curNodePtrPtr == curIndirect->nodePtr)
    {
      *curNodePtrPtr = (*curNodePtrPtr)->next;
      /* Searching for next one */
      curIndirect = (IndirectNodePtr)(curIndirect->nodeHeader.next);
      if (!curIndirect)
  break;
    }
    else
    {
      curNodePtrPtr = &((*curNodePtrPtr)->next);
    }
  }
  ApplyIndirectOnSimple(foundList);
  newList = foundList->nodePtr;
  /* Destroying temporary indirect linked list... */
  DestroyLinkedList((Node*)(foundList), DestroyIndirectNode);
  return newList;
}


void ApplyIndirectOnSimple(IndirectNodePtr indirectList)
{
  IndirectNodePtr curIndirect;
  for (curIndirect = indirectList; curIndirect->nodeHeader.next;
       curIndirect = (IndirectNodePtr)(curIndirect->nodeHeader.next))
  {
    curIndirect->nodePtr->next =
    ((IndirectNodePtr)(curIndirect->nodeHeader.next))->nodePtr;
  }
  /* Do the last one. Otherwise ((IndirectNodePtr)(curIndirect->nodeHeader.next))->nodePtr */
  /* is just junk from *NULL... */
  curIndirect->nodePtr->next = NULL;
}


void InvertList(NodePtr *linkedListPtr)
{
  NodePtr newList, lastNode;
  UInt32 nbrNodes = NbrNodes(*linkedListPtr), curNth;
  if (nbrNodes < 2)
    return;
  lastNode = newList = GetNthNode(*linkedListPtr, nbrNodes-1);
  for (curNth = (nbrNodes - 2); curNth; curNth--)
  {
    lastNode->next = GetNthNode(*linkedListPtr, curNth);
    lastNode = lastNode->next;
  }
  /* Add the last one. */
  lastNode->next = *linkedListPtr;
  (*linkedListPtr)->next = NULL;
  *linkedListPtr = newList;
}


void SplitAndMergeSort(NodePtr *linkedList, SInt8 (*CompareFunction)(NodePtr a, NodePtr b))
{
  Node empty;
  NodePtr listA, listB, curNode = &empty, newList = &empty;
  UInt32 nbrNodesFullList = NbrNodes(*linkedList);
  
  /* Split... */
  listA = *linkedList;
  listB = SplitAtNth(listA, nbrNodesFullList/2);
  
  /* ...(sorting)... */
  if (floor((double)(nbrNodesFullList)/2) > 1) /* Size of listA */
    SplitAndMergeSort(&listA, CompareFunction);
  if (ceil((double)(nbrNodesFullList)/2) > 1) /* Size of listB */
    SplitAndMergeSort(&listB, CompareFunction);
  
  /* ... and Merge */
  while (listA && listB)
  {
    if (CompareFunction(listA, listB) < 0)
    {
      /* listA is smaller than listB */
      curNode->next = listA;
      curNode = curNode->next;
      listA = listA->next;
    }
    else
    {
      /* listB is smaller or equal to listA */
      curNode->next = listB;
      curNode = curNode->next;
      listB = listB->next;
    }
  }
  while (listA)
  {
    curNode->next = listA;
    curNode = curNode->next;
    listA = listA->next;
  }
  while (listB)
  {
    curNode->next = listB;
    curNode = curNode->next;
    listB = listB->next;
  }
  newList = newList->next;
  *linkedList = newList;
}

---