/* Copyright (c) 2009
 * Vincenzo Liberatore, Case Western Reserve University
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * - Redistributions of source code must retain the above copyright notice, this
 *   list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * - Neither the name of Case Western Reserve University nor the names of
 *   its contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 */

/* Examples 4: a generic bag */

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>


typedef struct {
  void **bag;
  size_t n;                     /* Maximum size of the bag */
  size_t cnt;                   /* Number of elements in the bag */
  int (*equal)(void *, void *); /* Equality among bag elements */
} bag_t;


bag_t *bag_init(size_t n, int (*equal)(void *, void *)) {
  bag_t *bag;

  /* Allocate the bag */
  bag = (bag_t *) malloc(sizeof(bag_t));
  if (bag == NULL) {
    fprintf(stderr, "Cannot allocate bag\n");
    exit(EXIT_FAILURE);
  }

  /* Allocate the bag array */
  bag->bag = (void **) calloc(n, sizeof(void *));
  if (bag->bag == NULL) {
    fprintf(stderr, "Cannot allocate bag array\n");
    exit(EXIT_FAILURE);
  }

  /* Initialize bag values */
  bag->n     = n;
  bag->cnt   = 0;
  bag->equal = equal;

  return bag;
}


int bag_insert(bag_t *bag, void *value) {
  assert(bag != NULL);

  /* Check that there is enough room in the bag */
  if (bag->cnt >= bag->n)
    return 0;

  bag->bag[bag->cnt++] = value;
  return 1;
}



int bag_search(bag_t *bag, void *value) {
  size_t i;                  /* Cursor */
  size_t cnt;                /* Alias for bag->cnt */
  void   **bag_array;        /* Alias for bag->bag */

  assert(bag != NULL);

  /* Assign local aliases */
  cnt       = bag->cnt;
  bag_array = bag->bag;

  /* Search the array */
  for (i = 0; i < cnt && !bag->equal(bag_array[i],value); i++);

  /* If i<cnt, the loop terminated earlier --> the element was found.
     Otherwise, it ran to the end --> it was not found */
  return i < cnt;
}


void bag_delete(bag_t *bag) {
  assert(bag != NULL);

  free(bag->bag);
  free(bag);
}


/* Functions for a bag of doubles */
int double_equal(void *a, void *b) {
  double *k, *m;

  assert(a != NULL);
  assert(b != NULL);

  k = (double *) a;
  m = (double *) b;

  return *k == *m;
}


/* Structure and functions for a bag of plane points */

typedef struct {
  double x;
  double y;
} plane_point_t;

int point_equal(void *a, void *b) {
  plane_point_t *k, *m;

  assert(a != NULL);
  assert(b != NULL);

  k = (plane_point_t *) a;
  m = (plane_point_t *) b;
  return k->x == m->x && k->y == m->y;
}


int main() {
  double number[4];
  plane_point_t point[4];
  bag_t *double_bag, *point_bag;

  /* Point bags */
  point_bag = bag_init(10, point_equal);

  point[0].x = 4.;
  point[0].y = 5.;
  printf("Insert (4,5): %u (1=ok, 0=failure)\n", 
         bag_insert(point_bag, (void *) point));

  point[1].x = 8.;
  point[1].y = 9.;
  printf("Insert (8,9): %u (1=ok, 0=failure)\n", 
         bag_insert(point_bag, (void *) (point+1)));

  printf("Insert (4,5): %u (1=ok, 0=failure)\n", 
         bag_insert(point_bag, (void *) point));

  point[2].x = 7.;
  point[2].y = 6.;
  printf("Is (7,6) in the bag? %u\n", 
         bag_search(point_bag, (void *) (point+2)));

  printf("Insert (7,6): %u (1=ok, 0=failure)\n", 
         bag_insert(point_bag, (void *) (point+2)));

  printf("Is (7,6) in the bag? %u\n", 
         bag_search(point_bag, (void *) (point+2)));

  bag_delete(point_bag);


  /* Double bags */
  double_bag = bag_init(10, double_equal);

  number[0] = 4.;
  printf("Insert 4: %u (1=ok, 0=failure)\n", 
         bag_insert(double_bag, (void *) number));

  number[1] = 9.;
  printf("Insert 9: %u (1=ok, 0=failure)\n", 
         bag_insert(double_bag, (void *) (number+1)));

  printf("Insert 4: %u (1=ok, 0=failure)\n", 
         bag_insert(double_bag, (void *) number));

  number[2] = 7.;
  printf("Is 7 in the bag? %u\n", bag_search(double_bag, (void *) (number+2)));

  printf("Insert 7: %u (1=ok, 0=failure)\n", 
         bag_insert(double_bag, (void *) (number+2)));

  printf("Is 7 in the bag? %u\n", bag_search(double_bag, (void *) (number+2)));

  bag_delete(double_bag);

  return 0;
}