/*
    This program *attempts* to build the same kind of abstraction
    for linked lists in C as is available in Scheme and other modern
    Languages.
*/

#include<stdio.h>

/* A struct in C is like a class but there is no "public", "private"
   distinction.  And there are no "methods".  All functions in C are
   global and static.
*/


typedef struct cellstruct* cell;  // cell is same as struct cellstruct*

struct cellstruct
{
  int head;   // can use void* for generic type instead of int
  cell tail;
};

// constructor (cons):

cell cons(int h, cell t)
{
  cell newcell = (cell)malloc(8); // 8=number of bytes in struct
  newcell->head = h;              // -> in C is like . in Java
  newcell->tail = t;
  return newcell;
}

// accessors (car and cdr)

int car(cell L)
{ return L->head; }

cell cdr(cell L)
{ return L->tail; }


// destructor for deallocating memory with free()
void freecells(cell L)
{
  if (L != 0)    // null is just 0 in pure C
    {
      freecells(L->tail);  // recursively delete tail;
      free(L);             // delete current cell;
    }
}


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

// length of a list:
int length(cell L)
{ if (L==NULL) return 0; else return 1+length(cdr(L)); }

// list membership  (booleans are just ints in C)
int member(int x, cell L)
{ return (L != NULL) && (x==car(L) || member(x,cdr(L))); }

// returns nth cell, 0th is first.
cell nth(int n, cell L)
{
  if (n<1) return L; else return nth(n-1,cdr(L));
}

// print list - ok, ok, I'll use a loop this time!
void printlist(cell L)
{
  cell i;  // loop counter 
  for(i=L; i!=NULL; i=cdr(i)) printf("%d ", car(i));
  printf("\n");
}

// doubleup: from 1 2 3 to 1 1 2 2 3 3
cell doubleup(cell L)
{ if (L==NULL) return NULL; else
  return cons(car(L), cons(car(L), doubleup(cdr(L))));
}

// Even some higher-order functions are possible in C:
cell mapfun(int (*f)(int), cell L)
{
  if (L==NULL) return NULL;
  else return cons(f(car(L)),mapfun(f,cdr(L)));
}
int sqr(int x) { return x*x; } // for testing mapfun


// reversing a list - constructive and tail recursive:
cell reverse(cell L, cell ax)  // ax should be initially NULL
{
  if (L==NULL) return ax;
  else return reverse(cdr(L), cons(car(L),ax));
  // tail recursion in C is now just GOTO with some changes to 
  // the parameter variables.
}


// Now for deleteall, suddenly C breaks down:

cell deleteall(int x, cell L) // delete all x's from L
{
  if (L==NULL) return NULL;
  else if (x==car(L)) return deleteall(x,cdr(L));
  else return cons(car(L), deleteall(x,cdr(L)));
}


/*
 Now, to change a list to the new form, we WOULD LIKE TO DO

     A = deleteall(x,A);  // or  A = reverse(A,NULL);

 However, doing this will create a memory leak.  We might be
 able to do the following:

   cell temp = A;
   A = deleteall(x,A);
   freecells(temp);

 However, This would not work if parts of the A list is being shared
 with other elements of the program.  For example, if earlier
 we had executed:

   cell B = cons(1,cdr(cdr(A)));

 If we had automatic memory management, then there's nothing wrong
 with the above line. But here, deallocating the A list will also end
 up deallocating the tail of B!  In C it is your responsibility as
 programmer to make sure that this doesn't happen. YOU must carefully
 keep track of how all the memory cells that are being used by your
 program.  What does this mean?  Well, it means that you are stuck
 thinking about lists as consisting of memory cells and pointers
 instead of as an ABSTRACT DATA TYPE. You cannot just concentrate on
 the logic and algorithm of your program but must instead worry
 about the underlining memory structure.

 Ironically, one way to avoid the problem above in C is to adopt the
 the policy of never sharing common components between data structures.
 But this will end up making C LESS memory-efficient that Java/Scheme/Perl!

 Thus in C we cannot support the high-level abstract style of
 programming of Scheme (and Java, Perl for that matter) because of the
 lack of memory management. C is perfect for certain systems
 programming tasks where the whole point is to manipulate binary data
 at a very low level.  But as a language for applications programming,
 higher levels of abstraction can be desirable.  The String class in Java
 and C++ STL is another example.  Why would an applications programmer want
 to worry about allocating bytes for a string, as one would have to do
 in pure C?

 Memory management does bring an overhead like all "layers of
 abstraction."  30 years ago it would have been just a theoretical
 pipedream, as computers were always starving for speed and memory.
 But improved technology can also, albeit slowly, change the way we
 approach programming.  We now have the resources to afford this
 important layer of abstraction.  It's not just a "convenience for
 lazy programmers" but rather something that frees us to adopt a
 different style of programming altogether.

*/

int main()
{ 
  cell temp; // for deallocation.
  cell A = cons(1,cons(3,cons(5,cons(7,NULL))));
  cell B = cons(1,cdr(cdr(A)));  // B and A have something in common
  if (member(3,A)) printlist(A);
  printf("the length of B is %d\n", length(B));
  printlist(mapfun(sqr,A));  // applying higher-order function

  temp = deleteall(3,A);
  freecells(A);  // deallocate original list
  A = temp;
  printlist(A);  // OK
  printlist(B);  // oops!  you wrote it, you deserve it.
  exit(0);
}