/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-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_types.h"
#include "igraph_memory.h"
#include "igraph_error.h"
#include "igraph_types_internal.h"
#include "config.h"

#include <assert.h>
#include <string.h>     /* memmove */

#define SET(s) ((s).stor_begin)

/**
 * \ingroup set
 * \function igraph_set_init
 * \brief Initializes a set.
 *
 * \param set pointer to the set to be initialized
 * \param size the expected number of elements in the set
 *
 * \return error code:
 *       \c IGRAPH_ENOMEM if there is not enough memory.
 *
 * Time complexity: operating system dependent, should be around
 * O(n), n is the expected size of the set.
 */
int igraph_set_init(igraph_set_t *set, int long size) {
  long int alloc_size = size > 0 ? size : 1;
  if (size < 0) { size = 0; }
  set->stor_begin=igraph_Calloc(alloc_size, igraph_integer_t);
  set->stor_end=set->stor_begin + alloc_size;
  set->end=set->stor_begin;

  return 0;
}

/**
 * \ingroup set
 * \function igraph_set_destroy
 * \brief Destroys a set object.
 *
 * \param set pointer to the set to be destroyed
 *
 * Time complexity: operating system dependent.
 */
void igraph_set_destroy(igraph_set_t* set) {
  assert(set != 0);
  if (set->stor_begin != 0) {
    igraph_Free(set->stor_begin);
    set->stor_begin = NULL;
  }
}

/**
 * \ingroup set
 * \function igraph_set_inited
 * \brief Determines whether a set is initialized or not.
 *
 * This function checks whether the internal storage for the members of the
 * set has been allocated or not, and it assumes that the pointer for the
 * internal storage area contains \c NULL if the area is not initialized yet.
 * This only applies if you have allocated an array of sets with \c igraph_Calloc or
 * if you used the \c IGRAPH_SET_NULL constant to initialize the set.
 *
 * \param set The set object.
 *
 * Time complexity: O(1)
 */
igraph_bool_t igraph_set_inited(igraph_set_t* set) {
  return (set->stor_begin != 0);
}

/**
 * \ingroup set
 * \function igraph_set_reserve
 * \brief Reserve memory for a set.
 *
 * \param set The set object.
 * \param size the new \em allocated size of the set.
 *
 * Time complexity: operating system dependent, should be around
 * O(n), n is the new allocated size of the set.
 */
int igraph_set_reserve(igraph_set_t* set, long int size) {
  long int actual_size = igraph_set_size(set);
  igraph_integer_t *tmp;
  assert(set != NULL);
  assert(set->stor_begin != NULL);
  if (size <= actual_size) return 0;

  tmp=igraph_Realloc(set->stor_begin, (size_t) size, igraph_integer_t);
  if (tmp==0) {
    IGRAPH_ERROR("cannot reserve space for set", IGRAPH_ENOMEM);
  }
  set->stor_begin=tmp;
  set->stor_end=set->stor_begin+size;
  set->end=set->stor_begin+actual_size;

  return 0;
}

/**
 * \ingroup set
 * \function igraph_set_empty
 * \brief Decides whether the size of the set is zero.
 *
 * \param set The set object.
 * \return Non-zero number if the size of the set is not zero and
 *         zero otherwise.
 *
 * Time complexity: O(1).
 */
igraph_bool_t igraph_set_empty(const igraph_set_t* set) {
  assert(set != NULL);
  assert(set->stor_begin != NULL);
  return set->stor_begin == set->end;
}

/**
 * \ingroup set
 * \function igraph_set_clear
 * \brief Removes all elements from a set.
 * 
 * </para><para>
 * This function simply sets the size of the set to zero, it does
 * not free any allocated memory. For that you have to call
 * \ref igraph_set_destroy().
 * \param v The set object.
 * 
 * Time complexity: O(1).
 */
void igraph_set_clear(igraph_set_t* set) {
  assert(set != NULL);
  assert(set->stor_begin != NULL);
  set->end = set->stor_begin;
}


/**
 * \ingroup set
 * \function igraph_vector_set
 * \brief Gives the size (=length) of the set.
 * 
 * \param v The set object
 * \return The size of the set.
 *
 * Time complexity: O(1). 
 */

long int igraph_set_size(const igraph_set_t* set) {
  assert(set != NULL);
  assert(set->stor_begin != NULL);
  return set->end-set->stor_begin;
}


/**
 * \ingroup set
 * \function igraph_set_add
 * \brief Adds an element to the set.
 *
 * \param set The set object.
 * \param e The element to be added.
 * \return Error code:
 *         \c IGRAPH_ENOMEM: not enough memory.
 *
 * Time complexity: O(log(n)), n is the number of elements in \p set.
 */
int igraph_set_add(igraph_set_t* set, igraph_integer_t e) {
  long int left, right, middle;
  long int size;
  assert(set != NULL);
  assert(set->stor_begin != NULL);

  size = igraph_set_size(set);

  /* search where to insert the new element */
  left = 0;
  right = size-1;
  while (left < right-1) {
    middle = (left+right)/2;
    if (SET(*set)[middle] > e) {
      right = middle;
    } else if (SET(*set)[middle] < e) {
      left = middle;
    } else {
      left = middle;
      break;
    }
  }

  if (right >= 0 && SET(*set)[left] != e && SET(*set)[right] == e) {
    left = right;
  }

  while (left < size && set->stor_begin[left] < e) left++;
  if (left >= size || set->stor_begin[left] != e) {
    /* full, allocate more storage */
    if (set->stor_end == set->end) {
      long int new_size = size * 2;
      if (new_size == 0) new_size = 1;
      IGRAPH_CHECK(igraph_set_reserve(set, new_size));
    }

    /* Element should be inserted at position 'left' */
    if (left < size)
      memmove(set->stor_begin+left+1, set->stor_begin+left, 
	      (size_t) (size-left)*sizeof(set->stor_begin[0]));

    set->stor_begin[left] = e;
    set->end += 1;
  }

  return 0;
}

/**
 * \ingroup set
 * \function igraph_set_contains
 * \brief Checks whether a given element is in the set or not.
 *
 * \param set The set object.
 * \param e The element being sought.
 * \return Positive integer (true) if \p e is found, zero (false) otherwise.
 *
 * Time complexity: O(log(n)), n is the number of elements in \p set.
 */
int igraph_set_contains(igraph_set_t* set, igraph_integer_t e) {
  long int left, right, middle;

  assert(set != NULL);
  assert(set->stor_begin != NULL);

  left = 0;
  right = igraph_set_size(set)-1;

  /* search for the new element */
  while (left < right-1) {
    middle = (left+right)/2;
    if (SET(*set)[middle] > e) {
      right = middle;
    } else if (SET(*set)[middle] < e) {
      left = middle;
    } else {
      left = middle;
      return 1;
    }
  }

  if (SET(*set)[left] != e && SET(*set)[right] == e) return 1;
  return (SET(*set)[left] == e);
}

/**
 * \ingroup set
 * \function igraph_set_iterate
 * \brief Iterates through the element to the set.
 *
 * Elements are returned in an arbitrary order.
 *
 * \param set The set object.
 * \param state Internal state of the iteration.
 *   This should be a pointer to a \c long variable
 *   which must be zero for the first invocation.
 *   The object should not be adjusted and its value should
 *   not be used for anything during the iteration.
 * \param element The next element or \c NULL (if the iteration
 *   has ended) is returned here.
 * 
 * \return Nonzero if there are more elements, zero otherwise.
 */
igraph_bool_t igraph_set_iterate(igraph_set_t* set, long int* state,
				 igraph_integer_t* element) {
  assert(set != 0);
  assert(set->stor_begin != 0);
  assert(state != 0);
  assert(element != 0);

  if (*state < igraph_set_size(set)) {
    *element = set->stor_begin[*state];
    *state = *state+1;
    return 1;
  } else {
    *element = 0;
    return 0;
  }
}