# include <stdio.h>
# include <stdlib.h>

# include "ppc_ll.h"
# include "ppc_xmalloc.h"

/******************************************************************************/

conscell *ll_filter ( conscell *list,
          int (*filter) (const void *a), conscell **removed )

/******************************************************************************/
/*
  Purpose:

    ll_filter() filters a linked list.

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    29 April 2024

  Author:

    John Burkardt

  Reference:

    Rouben Rostamian,
    Programming Projects in C 
    for Students of Engineering, Science, and Mathematics,
    SIAM, 2014,
    ISBN: 978-1-611973-49-5

  Input:

    conscell *list: a linked list to be filtered.

    int (*filter)(const void *a): the filter function;

  Output:

    conscell *list: the filtered list.

    conscell **removed: a linked list of removed items.
*/
{
  if ( list == NULL )
  {
    return list;
  }
  else if ( filter ( list->data ) )
  {
    conscell *p = list->next;
    list->next = *removed;
    *removed = list;
    return ll_filter ( p, filter, removed );
  }
  else
  {
    list->next = ll_filter ( list->next, filter, removed );
    return list;
  }
}
/******************************************************************************/

void ll_free ( conscell *list )

/******************************************************************************/
/*
  Purpose:

    ll_free() frees the conscells memory of a linked list.

  Discussion:

    If memory was allocated for associated data, it must be freed before
    calling ll_free().

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    24 April 2024

  Author:

    John Burkardt

  Reference:

    Rouben Rostamian,
    Programming Projects in C 
    for Students of Engineering, Science, and Mathematics,
    SIAM, 2014,
    ISBN: 978-1-611973-49-5

  Input:

    conscell *list: a linked list whose conscells memory is to be freed.
*/
{
  while ( list != NULL )
  {
    conscell *p = list->next;
    free ( list );
    list = p;
  }
  return;
}
/******************************************************************************/

int ll_length ( conscell *list )

/******************************************************************************/
/*
  Purpose:

    ll_length() returns the length of a linked list.

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    29 April 2024

  Author:

    John Burkardt

  Reference:

    Rouben Rostamian,
    Programming Projects in C 
    for Students of Engineering, Science, and Mathematics,
    SIAM, 2014,
    ISBN: 978-1-611973-49-5

  Input:

    conscell *list: a linked list.

  Output:

    int ll_length: the length of the list.
*/
{
  int l;
 
  l = 0;
  for ( conscell *p = list; p != NULL; p = p->next )
  {
    l = l + 1;
  }

  return l;
}
/******************************************************************************/

conscell *ll_pop ( conscell *list )

/******************************************************************************/
/*
  Purpose:

    ll_pop() removes the first node of a linked list.

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    24 April 2024

  Author:

    John Burkardt

  Reference:

    Rouben Rostamian,
    Programming Projects in C 
    for Students of Engineering, Science, and Mathematics,
    SIAM, 2014,
    ISBN: 978-1-611973-49-5

  Input:

    conscell *list: a linked list.

  Output:

    conscell *ll_pop: the updated linked list.
*/
{
  if ( list == NULL )
  {
    return NULL;
  }
  conscell *p = list->next;
/*
  Now is the time to free list->data if it was allocated.
*/
  free ( list );

  return p;
}
/******************************************************************************/

conscell *ll_push ( conscell *list, void *data )

/******************************************************************************/
/*
  Purpose:

    ll_push() prepends a node to a linked list.

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    23 April 2024

  Author:

    John Burkardt

  Reference:

    Rouben Rostamian,
    Programming Projects in C 
    for Students of Engineering, Science, and Mathematics,
    SIAM, 2014,
    ISBN: 978-1-611973-49-5

  Input:

    conscell *list: a linked list.

    void *data: the data for the new node.

  Output:

    conscell *ll_push: the linked list, updated with a prepended node.
*/
{
  conscell *new = xmalloc ( sizeof ( *new ) );

  new->data = data;
  new->next = list;

  return new;
}
/******************************************************************************/

conscell *ll_reverse ( conscell *list )

/******************************************************************************/
/*
  Purpose:

    ll_reverse() reverses the nodes of a linked list.

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    25 April 2024

  Author:

    John Burkardt

  Reference:

    Rouben Rostamian,
    Programming Projects in C 
    for Students of Engineering, Science, and Mathematics,
    SIAM, 2014,
    ISBN: 978-1-611973-49-5

  Input:

    conscell *list: a linked list.

  Output:

    conscell *ll_reverse: the reversed linked list.
*/
{
  conscell *new = NULL;
 
  while ( list )
  {
    new = ll_push ( new, list->data );
    list = ll_pop ( list );
  }

  return new;
}
/******************************************************************************/

conscell *ll_sort ( conscell *list,
          int (*cmp) (const void *a, const void *b, void *params ),
          void *params )

/******************************************************************************/
/*
  Purpose:

    ll_sort() sorts the nodes of a linked list.

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    27 April 2024

  Author:

    John Burkardt

  Reference:

    Rouben Rostamian,
    Programming Projects in C 
    for Students of Engineering, Science, and Mathematics,
    SIAM, 2014,
    ISBN: 978-1-611973-49-5

  Input:

    conscell *list: a linked list.

    int (*cmp) (const void *a, const void *b, void *params ):
    the comparison function.

    void *params: God knows.

  Output:

    conscell *ll_sort: the sorted linked list.
*/
{
  conscell *list1 = NULL;
  conscell *list2 = NULL;
  conscell *p;
  conscell *q;
  conscell *head;

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

  head = list;
  p = list->next;

  while ( p != NULL )
  {
    q = p->next;
    if ( cmp ( p->data, head->data, params ) < 0 )
    {
      p->next = list1;
      list1 = p;
    }
    else
    {
      p->next = list2;
      list2 = p;
    }
    p = q;
  }
  
  list1 = ll_sort ( list1, cmp, params );
  list2 = ll_sort ( list2, cmp, params );
  head->next = list2;

  if ( list1 == NULL )
  {
    return head;
  }
/*
  Find tail node of list #1.
*/
  for ( p = list1; p->next != NULL; p = p->next )
  {
    continue;
  }
  p->next = head;

  return list1;
}