#include <stdio.h>                                                                /* CharList.c */
#include <stdlib.h>
#include <stdbool.h>
#include "CharList.h"

void printCharList(CharList p) {
  while( p != NULL ) {
    printf("%c", p->data);
    p = p->nextPtr;
  }
}
CharList newCharListNode(char c, CharList rest) {
  CharList r = malloc( sizeof (CharListNode) );
  if ( r == NULL )  fprintf(stderr, "newCharListNode: out of memory!\n");
  else                     { r->data = c; r->nextPtr = rest; }
  return r;
}
/*@{}@XPC{Insertion changes the argument list --- pass by reference necessary!} */
void insert(CharList * p, char val) {
  if( *p == NULL  ||  val <= (*p)->data) { *p = newCharListNode(val, *p); }
  else                                                    { insert( &((*p)->nextPtr), val); }
}
void insertIter(CharList * p, char val) {
  CharList tmp;
  while (*p != NULL && val > (*p)->data) /* search insertion point */
    { p = &((*p)->nextPtr); }
  if ((tmp = newCharListNode(val, *p)) == NULL)
    fprintf(stderr, "insertIter: out of memory - not inserted.\n");
  else
    *p = tmp;  /*@{}@XPC{redirect @CP style {symbol} {*p} to inserted node}*/
}
/*@{}@XPC{free a node, returning its successor list --- assumes non-NULL argument!} */
CharList freeCharListNode(CharListNode * q) {
  CharList next = q->nextPtr;
  free(q);
  return next;
}

/*@{}@XPC{Deletion changes the argument list --- pass by reference necessary!} */
void delete(CharList * p, char val) {
  if ( *p == NULL  ||  val < (*p)->data ) { return; }
  else if ( val == (*p)->data )                { *p = freeCharListNode(*p); }
  else                                                   { delete( &((*p)->nextPtr), val); }
}
void append(CharList * p, CharList q) {
    if( *p == NULL )   { *p = q; }
    else                        { append( &((*p)->nextPtr), q); }
}

void appendIter(CharList * p, CharList q) {
    while ( *p != NULL )
        { p = &((*p)->nextPtr); }
    *p = q;
}
/*@{}@XPC{Deletion changes the argument list --- pass by reference necessary!} */
void deleteIter(CharList * p, char val) {
  while (*p != NULL && val > (*p)->data ) /* search deletion point */
    { p = &((*p)->nextPtr); }
  if ( *p == NULL || val < (*p)->data ) { return; }
  else { *p = freeCharListNode(*p); }
}
void deleteList( CharList *p ) {
    if( *p == NULL ) return;
    else {
        deleteList( &((*p)->nextPtr) );
        free(*p);
        *p = NULL;
    }
}
CharList copyList_unsafe( CharList p ) {
  if( p == NULL ) return NULL;
  else return newCharListNode(p->data, copyList_unsafe(p->nextPtr));
}
bool copyList( CharList * dest, CharList p ) {
    if( p == NULL) { *dest = NULL; return true; }
    *dest = newCharListNode(p->data, NULL);
    if( *dest == NULL ) return false;
    else {
        if ( copyList( &((*dest)->nextPtr), p->nextPtr ) )
            return true;
        else {
            free( *dest );
            *dest = NULL;
            return false;
}   }   }
void reverseIter( CharList * p ) {           /* linear complexity */
  CharList prev = NULL, current = *p, next;
  if (current == NULL) return;
  next = current->nextPtr;
  current->nextPtr = prev;
  while( next != NULL ) { *p = next;
                                       prev = current;
                                       current = next;
                                       next = current->nextPtr;
                                       current->nextPtr = prev;    }
}
CharList rev(CharList q) {
  CharList next = q->nextPtr;
  if (next == NULL) return q;
  else {
      CharList result = rev(next);
      next->nextPtr = q;
      q -> nextPtr = NULL;
      return result;
  }}
void reverse( CharList * p ) {  if (*p != NULL) *p = rev(*p); }