dqueue.pmt

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2003-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA

   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 Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include "igraph_memory.h"
#include "igraph_error.h"
#include "config.h"

#include <assert.h>
#include <string.h>         /* memcpy & co. */
#include <stdlib.h>

/**
 * \section igraph_dqueue
 * <para>
 * This is the classic data type of the double ended queue. Most of
 * the time it is used if a First-In-First-Out (FIFO) behavior is
 * needed. See the operations below.
 * </para>
 *
 * <para>
 * \example examples/simple/dqueue.c
 * </para>
 */

/**
 * \ingroup dqueue
 * \function igraph_dqueue_init
 * \brief Initialize a double ended queue (deque).
 *
 * The queue will be always empty.
 * \param q Pointer to an uninitialized deque.
 * \param size How many elements to allocate memory for.
 * \return Error code.
 *
 * Time complexity: O(\p size).
 */

int FUNCTION(igraph_dqueue, init) (TYPE(igraph_dqueue)* q, long int size) {
    assert(q != 0);
    if (size <= 0 ) {
        size = 1;
    }
    q->stor_begin = igraph_Calloc(size, BASE);
    if (q->stor_begin == 0) {
        IGRAPH_ERROR("dqueue init failed", IGRAPH_ENOMEM);
    }
    q->stor_end = q->stor_begin + size;
    q->begin = q->stor_begin;
    q->end = NULL;

    return 0;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_destroy
 * \brief Destroy a double ended queue.
 *
 * \param q The queue to destroy
 *
 * Time complexity: O(1).
 */

void FUNCTION(igraph_dqueue, destroy) (TYPE(igraph_dqueue)* q) {
    assert(q != 0);
    if (q->stor_begin != 0) {
        igraph_Free(q->stor_begin);
        q->stor_begin = 0;
    }
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_empty
 * \brief Decide whether the queue is empty.
 *
 * \param q The queue.
 * \return Boolean, \c TRUE if \p q contains at least one element, \c
 * FALSE otherwise.
 *
 * Time complexity: O(1).
 */

igraph_bool_t FUNCTION(igraph_dqueue, empty) (const TYPE(igraph_dqueue)* q) {
    assert(q != 0);
    assert(q->stor_begin != 0);
    return q->end == NULL;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_clear
 * \brief Remove all elements from the queue.
 *
 * \param q The queue
 *
 * Time complexity: O(1).
 */

void FUNCTION(igraph_dqueue, clear)   (TYPE(igraph_dqueue)* q) {
    assert(q != 0);
    assert(q->stor_begin != 0);
    q->begin = q->stor_begin;
    q->end = NULL;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_full
 * \brief Check whether the queue is full.
 *
 * If a queue is full the next igraph_dqueue_push() operation will allocate
 * more memory.
 * \param q The queue.
 * \return \c TRUE if \p q is full, \c FALSE otherwise.
 *
 * Time complecity: O(1).
 */

igraph_bool_t FUNCTION(igraph_dqueue, full) (TYPE(igraph_dqueue)* q) {
    assert(q != 0);
    assert(q->stor_begin != 0);
    return q->begin == q->end;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_size
 * \brief Number of elements in the queue.
 *
 * \param q The queue.
 * \return Integer, the number of elements currently in the queue.
 *
 * Time complexity: O(1).
 */

long int FUNCTION(igraph_dqueue, size) (const TYPE(igraph_dqueue)* q) {
    assert(q != 0);
    assert(q->stor_begin != 0);
    if (q->end == NULL) {
        return 0;
    } else if (q->begin < q->end) {
        return q->end - q->begin;
    } else {
        return q->stor_end - q->begin + q->end - q->stor_begin;
    }
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_head
 * \brief Head of the queue.
 *
 * The queue must contain at least one element.
 * \param q The queue.
 * \return The first element in the queue.
 *
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue, head) (const TYPE(igraph_dqueue)* q) {
    assert(q != 0);
    assert(q->stor_begin != 0);
    return *(q->begin);
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_back
 * \brief Tail of the queue.
 *
 * The queue must contain at least one element.
 * \param q The queue.
 * \return The last element in the queue.
 *
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue, back) (const TYPE(igraph_dqueue)* q) {
    assert(q != 0);
    assert(q->stor_begin != 0);
    if (q->end == q->stor_begin) {
        return *(q->stor_end - 1);
    }
    return *(q->end - 1);
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_pop
 * \brief Remove the head.
 *
 * Removes and returns the first element in the queue. The queue must
 * be non-empty.
 * \param q The input queue.
 * \return The first element in the queue.
 *
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue, pop) (TYPE(igraph_dqueue)* q) {
    BASE tmp = *(q->begin);
    assert(q != 0);
    assert(q->stor_begin != 0);
    (q->begin)++;
    if (q->begin == q->stor_end) {
        q->begin = q->stor_begin;
    }
    if (q->begin == q->end) {
        q->end = NULL;
    }

    return tmp;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_pop_back
 * \brief Remove the tail
 *
 * Removes and returns the last element in the queue. The queue must
 * be non-empty.
 * \param q The queue.
 * \return The last element in the queue.
 *
 * Time complexity: O(1).
 */

BASE FUNCTION(igraph_dqueue, pop_back) (TYPE(igraph_dqueue)* q) {
    BASE tmp;
    assert(q != 0);
    assert(q->stor_begin != 0);
    if (q->end != q->stor_begin) {
        tmp = *((q->end) - 1);
        q->end = (q->end) - 1;
    } else {
        tmp = *((q->stor_end) - 1);
        q->end = (q->stor_end) - 1;
    }
    if (q->begin == q->end) {
        q->end = NULL;
    }

    return tmp;
}

/**
 * \ingroup dqueue
 * \function igraph_dqueue_push
 * \brief Appends an element.
 *
 * Append an element to the end of the queue.
 * \param q The queue.
 * \param elem The element to append.
 * \return Error code.
 *
 * Time complexity: O(1) if no memory allocation is needed, O(n), the
 * number of elements in the queue otherwise. But not that by
 * allocating always twice as much memory as the current size of the
 * queue we ensure that n push operations can always be done in at
 * most O(n) time. (Assuming memory allocation is at most linear.)
 */

int FUNCTION(igraph_dqueue, push) (TYPE(igraph_dqueue)* q, BASE elem) {
    assert(q != 0);
    assert(q->stor_begin != 0);
    if (q->begin != q->end) {
        /* not full */
        if (q->end == NULL) {
            q->end = q->begin;
        }
        *(q->end) = elem;
        (q->end)++;
        if (q->end == q->stor_end) {
            q->end = q->stor_begin;
        }
    } else {
        /* full, allocate more storage */

        BASE *bigger = NULL, *old = q->stor_begin;

        bigger = igraph_Calloc( 2 * (q->stor_end - q->stor_begin) + 1, BASE );
        if (bigger == 0) {
            IGRAPH_ERROR("dqueue push failed", IGRAPH_ENOMEM);
        }

        if (q->stor_end - q->begin) {
            memcpy(bigger, q->begin,
                   (size_t)(q->stor_end - q->begin) * sizeof(BASE));
        }
        if (q->end - q->stor_begin > 0) {
            memcpy(bigger + (q->stor_end - q->begin), q->stor_begin,
                   (size_t)(q->end - q->stor_begin) * sizeof(BASE));
        }

        q->end       = bigger + (q->stor_end - q->stor_begin);
        q->stor_end  = bigger + 2 * (q->stor_end - q->stor_begin) + 1;
        q->stor_begin = bigger;
        q->begin     = bigger;

        *(q->end) = elem;
        (q->end)++;
        if (q->end == q->stor_end) {
            q->end = q->stor_begin;
        }

        igraph_Free(old);
    }

    return 0;
}

#if defined (OUT_FORMAT)

#ifndef USING_R
int FUNCTION(igraph_dqueue, print)(const TYPE(igraph_dqueue)* q) {
    return FUNCTION(igraph_dqueue, fprint)(q, stdout);
}
#endif

int FUNCTION(igraph_dqueue, fprint)(const TYPE(igraph_dqueue)* q, FILE *file) {
    if (q->end != NULL) {
        /* There is one element at least */
        BASE *p = q->begin;
        fprintf(file, OUT_FORMAT, *p);
        p++;
        if (q->end > q->begin) {
            /* Q is in one piece */
            while (p != q->end) {
                fprintf(file, " " OUT_FORMAT, *p);
                p++;
            }
        } else {
            /* Q is in two pieces */
            while (p != q->stor_end) {
                fprintf(file, " " OUT_FORMAT, *p);
                p++;
            }
            p = q->stor_begin;
            while (p != q->end) {
                fprintf(file, " " OUT_FORMAT, *p);
                p++;
            }
        }
    }

    fprintf(file, "\n");

    return 0;
}

#endif

BASE FUNCTION(igraph_dqueue, e)(const TYPE(igraph_dqueue) *q, long int idx) {
    if ((q->begin + idx < q->end) ||
        (q->begin >= q->end && q->begin + idx < q->stor_end)) {
        return q->begin[idx];
    } else if (q->begin >= q->end && q->stor_begin + idx < q->end) {
        idx = idx - (q->stor_end - q->begin);
        return q->stor_begin[idx];
    } else {
        return 0;           /* Error */
    }
}