module lisplist;

import tango.stdc.stdlib;  	// malloc and free
import StringZ = tango.stdc.stringz;	
import tango.stdc.string;
import tango.io.Console;
import Text = tango.text.Util;

alias void*   POINTER;      

/**
 A CONS is a data structure that can construct lists. 
 It consists of two cells, called the "car" cell and the "cdr" cell.
 A CONS is to symbolic processing what a binary digit is to numerical processing.

 By combining CONS we can form lists, binary trees, hierarchies, 
 and an infinite number of other useful data structures.
*/

struct CONS                 // A CONS consists of two void pointers  
{
   POINTER  car;
   POINTER  cdr;
} 

alias CONS    *LIST;        // A LIST is a pointer to a CONS cell

// ------------------------------- Helper functions

alias bool function(char*, char*) CompFunc;

bool string_compare(char* a, char* b)
{
	return ( a[0 .. strlen(a)] == b[0 .. strlen(b)] );
	//return (fromUtf8z(a) == fromUtf8z(b));
}
	
LIST outputlist(LIST lst)
{
	CONS *acons;
	LIST  list = lst;
	char* c;
	char[] o;
	while ( (acons = cpop(&list)) !is null ) //!is cast(LIST)null )
		c = cast(char*)acons.car;
		o = c[0 .. strlen(c)];
		Cout(o).newline;
		//Cout( StringZ.fromStringz(cast(char*)acons.car) ).newline;		
	return lst;
}

// ------------------------    general-purpose list processing

/** cons (create a CONS) 
 Uses malloc to allocate a CONS and set its         
 car cell to a and its cdr cell to b.  
*/
CONS* cons(POINTER a, POINTER b)
{
   CONS  *z;
   z = cast(LIST) malloc(CONS.sizeof);
   if (z is null) exit(1);

   z.car = a;
   z.cdr = b;

   return z;
}  
/** pop (pop an item off a list)
 Uses cpop to pop a CONS off lst.       
 if lst is empty.  free the CONS and return the car cell of the CONS.
*/
POINTER pop(LIST *lst)
{
	POINTER  item;
	CONS     *z;

	z = cpop(lst);

	if (z is null) return null;		// list is empty

	item = z.car;             		// get what cons pointed to
	free(z);                   		// release the cons

	return item;
}

/** cpop (pop a CONS off a list)                 
 if *lst is empty return NULL, 
 else set *lst to the the car cell of the first CONS on *lst 
 and return a pointer to the first CONS on *lst.
*/
LIST cpop(LIST *lst)
{
	LIST  rvalue;
	rvalue = *lst;

	if (rvalue !is null)
		*lst = cast(LIST)rvalue.cdr;

	return rvalue;
}

/** push (push an item onto a list)
 Uses cons to create a CONS and sets its car cell  to item.
 Its cdr is set to *lst.
 *lst is set to point to the CONS created.  
 A pointer to the CONS  is also returned.
*/
LIST push(POINTER item, LIST *lst)
{
   return *lst = cons(item, *lst);
} 

/** cpush  (cons push)
Adds a CONS to the head of a list                  
modify the cdr cell of *z to point to *lst.  
Set lst to point to the CONS z and return a pointer to the CONS.
*/
LIST cpush(CONS *z, LIST *lst)
{
	z.cdr = *lst;
	
	return (*lst = z);
}

/** reverse (reverse a list)
 distructively modify the cdr cells of the CONS     
 which make up lst so that a new list is created    
 which is the reverse of the original list.         
 return the new list.
*/
LIST reverse(LIST  lst)
{
	LIST  rlst = null;

	while (lst !is null)
		cpush(cpop(&lst), &rlst);

	return rlst;
}

/**split (split a list in half)
 Find the mid CONS in lst.  set its cdr cell to  null.
 return the remainder of lst, i.e. a pointer to the next CONS after the mid CONS.
*/
LIST split(LIST lst)
{
	LIST tail = cast(LIST)lst.cdr;
	
	if ( (lst is null) || (tail is null) )
		return lst;
		
	while( (tail !is null) && ( (tail = cast(LIST)tail.cdr) !is null) )
	{
		lst = cast(LIST)lst.cdr;
		tail = cast(LIST)tail.cdr;
	}
	
   tail = cast(LIST)lst.cdr;
   lst.cdr = null;
   
   return tail;
}

/** sort (sort a list)
 If cmp is a two argument ordering procedure,
 sort the items in lst based on cmp and return the results
*/
LIST sort( LIST lst, CompFunc cmp)
{
	LIST lst2;

	if ( (lst is null) || (lst.cdr is null) ) return lst;

	lst2 = split(lst);

	return merge( sort(lst,cmp), sort(lst2,cmp), cmp);
}

/** merge (merge two lists)
 If cmp is a two argument ordering procedure,      
 merge the items in lst1 and lst2 based on cmp and return the results
*/
LIST merge(LIST lst1, LIST lst2, CompFunc cmp)
{
	LIST  rlst = null;

	while ( (lst1 !is null) && (lst2 !is null) )
		cpush((cmp(cast(char*)lst2.car, cast(char*)lst1.car) ? cpop(&lst1) : cpop(&lst2)), &rlst);
		
	while ( lst1 !is null )
		cpush( cpop(&lst1),&rlst );

	while ( lst2 !is null )
		cpush( cpop(&lst2), &rlst );
		
	return reverse(rlst);
}



// ------------------------------  Test
int main()
{
	LIST mylist = null;

    char[] source = "one,two,three,Four";

    // split into an array
	char[][] lines = Text.delimit(source, ",");
	
	foreach (line; lines)
	{
		Cout(line).newline;
		push(StringZ.toStringz(line), &mylist);  // push to mylist
	}	
	Cout("Sorted output ...").newline; 
	// show results
	outputlist( sort(mylist, &string_compare) );
	
	return 0;
}