klib_list.c File Reference

Implementation of the klib_List class. More...

#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include "klib_log.h"
#include "klib_object.h"
#include "klib_list.h"
#include "klib_string.h"

Functions
int	klib_list_length (const klib_List *self)
	Get the number of items in the list.
klib_Object *	klib_list_get (const klib_List *self, int i)
	Get the i'th item in the list.
klib_String *	klib_list_tostring (const klib_List *self)
	Get a string representation of the the whole list.
void	klib_list_construct (klib_List *self)
klib_List *	klib_list_new (void)
	Create a new empty list.
void	klib_list_dispose (klib_List *self)
klib_ListItem *	klib_list_get_last_item (const klib_List *self)
	Get a pointer to the last item in the list.
void	klib_list_append (klib_List *self, klib_Object *o)
	Append an item to the list.
int	klib_list_sort_string_ascending (klib_Object *o1, klib_Object *o2)
	Sort the list using a default (ASCII order) comparison.
void	klib_list_clear (klib_List *self)
	Clear the list, disposing all the objects in it.
void	klib_list_sort (klib_List *self, klib_List_CompareFunc compare_func)
	Sort the list using a specified comparison function.
klib_List *	klib_list_new_sorted (klib_List *self, klib_List_CompareFunc compare_func)
	Sort the list into a new list, using the specified comparison function.
klib_List *	klib_list_new_shuffled (klib_List *self)
	Create a new list containing the elements of this one in random order.
void	klib_list_filter (klib_List *self, klib_List_FilterFunc filter_func, void *data)
	Filter the list, removing all items that do not pass the filter.
void	klib_list_shuffle (klib_List *self)
	Radnomize this list.
klib_List *	klib_list_new_filter (klib_List *self, klib_List_FilterFunc filter_func, void *data)
	Filter the list into a new list.
klib_List *	klib_list_new_sublist (const klib_List *self, int first, int limit)
	Filter the list, removing all items that do not pass the filter.
void	klib_list_append_to (klib_List *self, const klib_List *other)
	Add all items in another list to this one.

---

Detailed Description

Implementation of the klib_List class.

---

Function Documentation

void klib_list_append	(	klib_List *	self,
		klib_Object *	o
	)

Append an item to the list.

  {
  klib_ListItem *li = (klib_ListItem *) malloc (sizeof (klib_ListItem));
  if (!li)
    {
    klib_log (KLIB_LOG_ERROR, "Out of memory in klib_list_append()");
    return;
    }

  li->next = NULL;
  li->data = o;
  klib_object_add_ref (li->data);  

  klib_ListItem *last = klib_list_get_last_item (self);
  if (last)
    {
    last->next = li;
    }
  else
    {
    self->head = li;
    }
  }

void klib_list_append_to	(	klib_List *	self,
		const klib_List *	other
	)

Add all items in another list to this one.

  {
  int i, l = klib_list_length (other);
  for (i = 0; i < l; i++)
    klib_list_append (self, klib_list_get (other, i));
  } 

void klib_list_clear

(

klib_List *

self

)

Clear the list, disposing all the objects in it.

  {
  klib_ListItem *li = self->head;
  while (li)
    {
    klib_object_unref (li->data);
    klib_ListItem *temp = li->next;
    free (li);
    li = temp;
    }
  self->head = NULL;
  }

void klib_list_construct

(

klib_List *

self

)

  {
  if (klib_object_trace_flags & KLIB_OBJECT_TRACE_CONSTRUCTION)
    klib_log (KLIB_LOG_TRACE, "Called constructor for List\n");

  klib_object_construct ((klib_Object *)self, "List");
  ((klib_Object *)self)->dispose_func = (klib_Object_DisposeFunc) 
     klib_list_dispose;
  ((klib_Object *)self)->tostring_func = (klib_Object_TostringFunc) 
     klib_list_tostring;
  }

void klib_list_dispose

(

klib_List *

self

)

  {
  if (klib_object_trace_flags & KLIB_OBJECT_TRACE_CONSTRUCTION)
    klib_log (KLIB_LOG_TRACE, "Called destructor for List\n");

  klib_ListItem *li = self->head;
  while (li)
    {
    klib_object_unref (li->data);
    klib_ListItem *temp = li->next;
    free (li);
    li = temp;
    }

  klib_object_dispose ((klib_Object *)self);
  }

void klib_list_filter	(	klib_List *	list,
		klib_List_FilterFunc	filter_func,
		void *	data
	)

Filter the list, removing all items that do not pass the filter.

  {
  klib_List *new = klib_list_new_filter (self, filter_func, data);
  klib_list_clear (self);

  int i = 0, l = klib_list_length (new);
  for (i = 0; i < l; i++)
    {
    klib_Object *o = klib_list_get (new, i);
    //klib_object_add_ref (o);
    klib_list_append (self, o);
    }
  klib_object_unref ((klib_Object *)new);
  }

klib_Object* klib_list_get	(	const klib_List *	self,
		int	i
	)

Get the i'th item in the list.

  {
  if (!self) return NULL;
  if (!self->head) return NULL;
  int count = 0;
  klib_ListItem *li = self->head;
  while (count < i)
    {
    li = li->next;
    count++;
    }
  return li->data;
  }

klib_ListItem* klib_list_get_last_item

(

const klib_List *

self

)

Get a pointer to the last item in the list.

  {
  if (self->head == NULL) return NULL;
  klib_ListItem *li = self->head;
  while (li->next)
    {
    li = li->next;
    }
  return li;
  }

int klib_list_length

(

const klib_List *

self

)

Get the number of items in the list.

  {
  if (!self) return 0;
  if (!self->head) return 0;
  int count = 1;
  klib_ListItem *li = self->head;
  while (li->next)
    {
    li = li->next;
    count++;
    }
  return count;
  }

klib_List* klib_list_new

(

void

)

Create a new empty list.

  {
  if (klib_object_trace_flags & KLIB_OBJECT_TRACE_CONSTRUCTION)
    klib_log (KLIB_LOG_TRACE, "Called new for List\n");

  klib_List *self = (klib_List *) malloc (sizeof (klib_List));
  memset (self, 0, sizeof (klib_List));
  klib_list_construct (self); 

  return self;
  }

klib_List* klib_list_new_filter	(	klib_List *	list,
		klib_List_FilterFunc	filter_func,
		void *	data
	)

Filter the list into a new list.

See klib_list_sort for caveats

  {
  klib_List *list = klib_list_new ();

  int i, l = klib_list_length (self);
  for (i = 0; i < l; i++)
    {
    klib_Object *o = klib_list_get (self, i);
    if (filter_func (o, data))
      klib_list_append (list, o);
    }

  return list;
  }

klib_List* klib_list_new_shuffled

(

klib_List *

list

)

Create a new list containing the elements of this one in random order.

  {
  if (!self) return NULL;
  
  int i = 0, l = klib_list_length (self);

  int *indexes = (int *) malloc (l * sizeof (int));
  if (!indexes)
    {
    klib_log (KLIB_LOG_ERROR, "Out of memory in klib_list_sort ()\n");
    return NULL;
    }

  for (i = 0; i < l; i++)
    indexes[i] = i;

  // Shuffle the indexes 

  for (i = 0; i < l - 1; i++)
    {
    int j = rand() / (RAND_MAX / (l - 1) + 1);
    int t = indexes[j];
    indexes[j] = indexes[i];
    indexes[i] = t;
    }


  klib_List *out = klib_list_new();
  for (i = 0; i < l; i++)
    {
    klib_Object *o = klib_list_get (self, indexes[i]);
    klib_list_append (out, o);
    }

  free (indexes);
  return out;
  }

klib_List* klib_list_new_sorted	(	klib_List *	self,
		klib_List_CompareFunc	compare_func
	)

Sort the list into a new list, using the specified comparison function.

Note that items are not cloned -- both lists will end up with pointers to the same data. klib objects don't normally mind being free'd more than once, so this should not be a hazard.

  {
  if (!self) return NULL;
  
  int i = 0, l = klib_list_length (self);

  int *indexes = (int *) malloc (l * sizeof (int));
  if (!indexes)
    {
    klib_log (KLIB_LOG_ERROR, "Out of memory in klib_list_sort ()\n");
    return NULL;
    }

  for (i = 0; i < l; i++)
    indexes[i] = i;

  // Sort the indexes 

  for (i = 0; i < l - 1; i++)
    {
    int j;
    for (j = 0; j < l - 1; j++)
      {
      klib_Object *o1 = klib_list_get (self, indexes[j]);
      klib_Object *o2 = klib_list_get (self, indexes[j + 1]);
      int r = compare_func (o1, o2);
      if (r > 0)
        {
        int t = indexes[j];
        indexes[j] = indexes[j + 1];
        indexes[j+1] = t;
        }
      }
    }

  //for (i = 0; i < l; i++)
  // printf ("i=%d value=%d\n", i, indexes[i]);

  klib_List *out = klib_list_new();
  for (i = 0; i < l; i++)
    {
    klib_Object *o = klib_list_get (self, indexes[i]);
    //klib_object_add_ref (o);
    klib_list_append (out, o);
    }

  free (indexes);
  return out;
  }

klib_List* klib_list_new_sublist	(	const klib_List *	self,
		int	first,
		int	limit
	)

Filter the list, removing all items that do not pass the filter.

  {
  klib_List *list = klib_list_new ();
  if (first < 0) first = 0;
  if (limit < 0) limit = 0;
  
  int i, l = klib_list_length (self);
  for (i = first; i < l && i < first + limit; i++)
    klib_list_append (list, klib_list_get (self, i));
  return list;
  }

void klib_list_shuffle

(

klib_List *

list

)

Radnomize this list.

  {
  klib_List *new = klib_list_new_shuffled (self);
  klib_list_clear (self);

  int i = 0, l = klib_list_length (new);
  for (i = 0; i < l; i++)
    {
    klib_Object *o = klib_list_get (new, i);
    //klib_object_add_ref (o);
    klib_list_append (self, o);
    }
  klib_object_unref ((klib_Object *)new);
  }

void klib_list_sort	(	klib_List *	self,
		klib_List_CompareFunc	compare_func
	)

Sort the list using a specified comparison function.

  {
  klib_List *new = klib_list_new_sorted (self, compare_func);
  klib_list_clear (self);

  int i = 0, l = klib_list_length (new);
  for (i = 0; i < l; i++)
    {
    klib_Object *o = klib_list_get (new, i);
    //klib_object_add_ref (o);
    klib_list_append (self, o);
    }
  klib_object_unref ((klib_Object *)new);
  }

int klib_list_sort_string_ascending	(	klib_Object *	o1,
		klib_Object *	o2
	)

Sort the list using a default (ASCII order) comparison.

Do not use unless the list contains klib_String objects

  {
  if (o1 == NULL) return 0;
  if (o2 == NULL) return 0;
  klib_String *s1 = (klib_String *)o1;
  klib_String *s2 = (klib_String *)o2;
  if (s1->str == NULL) return 0;
  if (s2->str == NULL) return 0;

  // TODO -- unicode sort
  return (strcmp (s1->str, s2->str));
  }

klib_String* klib_list_tostring

(

const klib_List *

self

)

Get a string representation of the the whole list.

  {
  klib_String *s = _klib_object_tostring ((klib_Object *)self);
  klib_string_append (s, "\n");
  int i, l = klib_list_length (self);
  for (i = 0; i < l; i++)
    {
    klib_Object *o = klib_list_get (self, i);
    klib_String *ss = klib_object_tostring (o);
    klib_string_append (s, ss->str);
    klib_object_unref ((klib_Object *)ss);
    klib_string_append (s, "\n");
    }
  return s;
  }