/* $Id: cxdeque.c,v 1.6 2008/02/26 10:29:23 yjung Exp $
 *
 * This file is part of the ESO C Extension Library
 * Copyright (C) 2001-2006 European Southern Observatory
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

/*
 * $Author: yjung $
 * $Date: 2008/02/26 10:29:23 $
 * $Revision: 1.6 $
 * $Name:  $
 */

#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif

#include <stdlib.h>
#include <stdio.h>
#include "cxmemory.h"
#include "cxmessages.h"

#include "cxdeque.h"


static cx_deque_compare current_compare;

struct stable
{
   cxint indx;
   void *member;
};

static int compare_stable(const void *a, const void *b)
{
   cxint comp = current_compare(((struct stable *)a)->member,
			    ((struct stable *)b)->member);

   /* If members compare equal, compare their indices */
   if (comp != 0) return comp;
   else return ((struct stable *)a)->indx - ((struct stable *)b)->indx;

}

/**
 * @defgroup cxdeque Double-ended queue.
 *
 * The module implements a double-ended queue. This is a linear list
 * for which all insertions and deletions are made at the ends of the
 * list.
 *
 * @par Synopsis:
 * @code
 *   #include <cxdeque.h>
 * @endcode
 */

/**@{*/

/*
 * Double-ended queue structure and data types
 */
struct _cx_deque_
{
    void **members;
    unsigned long front;
    unsigned long size;
    unsigned long back;

};

/**
 * @brief
 *   Create a new deque without any elements.
 *
 * @return Handle to the newly allocated deque.
 *
 * The function allocates memory for the deque object and initializes
 * it to an empty deque.
 */

cx_deque *
cx_deque_new(void)
{

    cx_deque *d = cx_calloc(1, sizeof(*d));
 

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

    d->members = NULL;
 

    d->front = 0;
    d->size = 0;
    d->back = 0;


    return d;
}


/**
 * @brief
 *   Append data at the end of a deque.
 *
 * @param d     The deque to update.
 * @param data  Data to append.
 *
 * @return Nothing.
 *
 * The data @em data is inserted into the deque @em d after the last
 * element, so that it becomes the new deque tail.
 *
 * It is equivalent to the statement
 * @code
 *   cx_deque_insert(d, cx_deque_end(d), data);
 * @endcode
 */

void
cx_deque_push_back(cx_deque *d, cxptr data)
{
    cx_assert( d != NULL );

    /* 
    * If back is 0, the maximum allocated memory has been
    * reached. This means, it's necessary to allocate new
    * memory for inserting new members. 
    */
    if (d->back == 0)
        {

            void **new_members;
            unsigned long i;
            d->back = d->size + 1;
            new_members = cx_calloc(d->front + d->size + d->back, sizeof(void *));
  
            for (i = 0; i < d->size; i++)
                {
                   /* transfer the old members to their positions in the new
                      container, which is now bigger*/
                    new_members[d->front + i] = d->members[d->front + i];
                }

            cx_free(d->members);
            d->members = new_members;


        }

    d->members[d->front + d->size] = (cxptr)data;
    d->size++;
    d->back--;  

    return;
}

/**
 * @brief
 *   Insert data at the beginning of a deque.
 *
 * @param d     The deque to update.
 * @param data  Data to add to the deque.
 *
 * @return Nothing.
 *
 * The data @em data is inserted into the deque @em d before the first
 * element of the deque, so that it becomes the new deque head.
 *
 * It is equivalent to the statement
 * @code
 *   cx_deque_insert(d, cx_deque_begin(d), data);
 * @endcode
 */

void
cx_deque_push_front(cx_deque *d, cxptr data)
{
    cx_assert( d != NULL );

    if (d->front == 0)
        {

            void **new_members;
            unsigned long i;

            d->front = d->size + 1;
            new_members = cx_calloc(d->front + d->size + d->back, sizeof(void *));

            for (i = 0; i < d->size; i++)
                {
                    new_members[d->front + i] = d->members[0 + i];
                }

            cx_free(d->members);
            d->members = new_members;


        }

    d->front--;
    d->size++;
    d->members[d->front] = data;

    return;
}

/**
 * @brief
 *   Retrive an element from the deque.
 *
 * @param d  The deque to query.
 * @param indx  The position of the element to get.
 *
 * @return A handle to the data object.
 *
 * The function returns a reference to the data item stored in the deque
 * @em d at the iterator position @em indx.
 *
 */

cxptr
cx_deque_get(const cx_deque *d, cx_deque_const_iterator indx)
{
    cx_assert( d != NULL );
    cx_assert( indx < d->size );

    return d->members[d->front + indx];  
}

/**
 * @brief
 *   Erase a deque element.
 *
 * @param d           The deque to update.
 * @param indx        Deque iterator position.
 * @param deallocate  Data deallocator.
 *
 * @return The iterator for the deque position after @em indx.
 *
 * The function removes the data object stored at position @em indx
 * from the deque @em d. The data object itself is deallocated by calling
 * the data deallocator @em deallocate.
 */

cx_deque_iterator
cx_deque_erase(cx_deque *d, cx_deque_iterator indx, cx_free_func deallocate)
{
    unsigned long i;


    cx_assert( d != NULL );
    cx_assert( indx < d->size );

    deallocate(d->members[d->front + indx]);

    for (i = indx; i < d->size - 1; i++)
    {
        d->members[d->front + i] = d->members[d->front + i + 1];
            
    }

    d->size--;
    d->back++;

    return indx;
}

/**
 * @brief
 *   Insert data into a deque at a given iterator position.
 *
 * @param d      The deque to update.
 * @param indx   List iterator position.
 * @param data   Data item to insert.
 *
 * @return Nothing.
 *
 * The function inserts the data object reference @em data into the deque
 * @em d at the position given by the deque iterator @em indx.
 */

void
cx_deque_insert(cx_deque *d, cx_deque_iterator indx, cxptr data)
{
    /* printf("indx = %d size = %d\n", indx, d->size); */
    cx_assert( d != NULL );
    cx_assert( indx <= d->size );

    if ( indx == d->size )
        {
            cx_deque_push_back(d, data);
        }
    else
        {
            unsigned long i;

            cx_assert( indx < d->size );
            cx_assert( d->size > 1 );
      
            cx_deque_push_back(d, d->members[d->front + d->size - 1]);
      
            for (i = d->size-1; i > indx; i--)
                {
                    d->members[d->front + i] = d->members[d->front + i - 1];
                }
      
            d->members[d->front + indx] = data;
        }

    return;
}

/**
 * @brief
 *   Get the actual number of deque elements.
 *
 * @param d  A deque.
 *
 * @return The current number of elements the deque contains, or 0 if the
 *   deque is empty.
 *
 * Retrieves the number of elements currently stored in the deque @em d.
 */

cxsize
cx_deque_size(const cx_deque *d)
{
    cx_assert( d != NULL );
  
    return d->size;
}

/**
 * @brief
 *   Destroy a deque and all its elements.
 *
 * @param d           Deque container to destroy.
 * @param deallocate  Data deallocator.
 *
 * @return Nothing.
 *
 * The function deallocates all data objects referenced by the deque using
 * the data deallocation function @em deallocate and finally deallocates
 * the deque itself.
 */

void
cx_deque_destroy(cx_deque *d, cx_free_func deallocate)
{
    if (d != NULL)
        {
            if (deallocate != NULL)
                {
                    unsigned long i;
          
                    for (i = 0; i < d->size; i++)
                        {
                            deallocate(d->members[d->front + i]);
                        }
                }
            cx_free(d->members);
            cx_free(d);
        }
}

/**
 * @brief
 *   Check whether a deque is empty.
 *
 * @param d  A deque.
 *
 * @return The function returns @c TRUE if the deque is empty, and @c FALSE
 *   otherwise.
 *
 * The function tests if the deque @em d contains data. 
 *
 */

cxbool 
cx_deque_empty(const cx_deque *d)
{
    cx_assert(d != NULL);

    return (d->size == 0);
}

/**
 * @brief
 *   Get an iterator for the first deque element.
 *
 * @param d  A deque.
 *
 * @return Iterator for the first element in the deque or @b cx_deque_end()
 *   if the deque is empty.
 *
 * The function returns a handle to the first element of @em d. The
 * handle cannot be used directly to access the element data, but only
 * through the appropriate functions.
 */

cx_deque_iterator 
cx_deque_begin(const cx_deque *d)
{
    cx_assert(d != NULL);
    return 0;
}

/**
 * @brief
 *   Get an iterator for the position after the last deque element.
 *
 * @param d  A deque.
 *
 * @return Iterator for the end of the deque.
 *
 * The function returns an iterator for the position one past the last
 * element of the deque @em deque. The handle cannot be used to directly
 * access the element data, but only through the appropriate functions.
 */

cx_deque_iterator
cx_deque_end(const cx_deque *d)
{
    cx_assert(d != NULL);
    return d->size;
}

/**
 * @brief
 *   Get an iterator for the next deque element.
 *
 * @param d         A deque.
 * @param i         Current iterator position.
 *
 * @return Iterator for the next deque element.
 *
 * The function returns an iterator for the next element in the deque
 * @em d with respect to the current iterator position @em i.
 * If the deque @em d is empty or @em i points to the deque end
 * the function returns @b cx_deque_end().
 */

cx_deque_iterator
cx_deque_next(const cx_deque *d, cx_deque_const_iterator i)
{
    cx_assert(d != NULL);

    return i+1;
}

/**
 * @brief
 *   Sort all elements of a deque using the given comparison function.
 *
 * @param d        The deque to sort.
 * @param compare  Function comparing the list elements.
 *
 * @return Nothing.
 *
 * The input deque @em d is sorted using the comparison function
 * @em compare to determine the order of two deque elements. The comparison
 * function @em compare must return an integer less than, equal
 * or greater than zero if the first argument passed to it is found,
 * respectively, to be less than, match, or be greater than the second
 * argument. This function uses the stdlib function qsort().
 */


void cx_deque_sort(cx_deque *d, cx_deque_compare compare)
{
    struct stable *ss;
    unsigned long i;

    cx_assert(d != NULL);
    cx_assert(compare != NULL);

    current_compare = compare;

    /*
    * create temporary copy of array, including the
    * indices. note that the execution time is dominated
    * by the actual sorting
    */
    ss = cx_malloc(d->size * sizeof(struct stable));
    for (i = 0; i < d->size; i++) {
        ss[i].indx = i;
        ss[i].member = d->members[d->front + i];
    }

    qsort(ss, d->size, sizeof(struct stable), compare_stable);

    for (i = 0; i < d->size; i++) {
        d->members[d->front + i] = ss[i].member;
    }

    cx_free(ss);

    return;
}

/**@}*/