/*
 *  Utilities for handling sets.
 *
 *  Copyright (c) 1992, 1993
 *        Regents of the University of California
 *  All rights reserved.
 *
 *  Use and copying of this software and preparation of derivative works
 *  based upon this software are permitted.  However, any distribution of
 *  this software or derivative works must include the above copyright 
 *  notice.
 *
 *  This software is made available AS IS, and neither the Electronics
 *  Research Laboratory or the Universify of California make any
 *  warranty about the software, its performance or its conformity to
 *  any specification.
 *
 *  $Header: /projects/development/hsv/CVSRepository/vl2mv/src/set/set.c,v 1.1.1.1 2001/07/09 23:22:43 fabio Exp $
 *
 * Author: STCheng, stcheng@ic.berkeley.edu
 */

#include <stdio.h>
#include "util.h"
#include "st.h"
#include "set.h"

/*
 * strdup 
 *
 *     duplicate a string
 */
static char *SetStrdup(str)
char *str;
{
    char *retval;

    retval = ALLOC(char, strlen(str)+1);
    strcpy(retval, str);
    return retval;
}


/*
 * set_empty
 *
 *     initialize a new empty set
 *
 * argument:
 *
 * returns: {}
 *
 * bugs:
 * 
 * comments:
 */
set_t *set_empty()
{
    set_t *retval;

    retval = st_init_table(strcmp, st_strhash);
    return retval;
}

/*
 * set_destroy
 *
 *     destroy a set data structure
 *
 * argument: s
 *
 * returns:
 *
 * bugs:
 *
 * comments:
 */
void set_destroy(s)
set_t *s;
{
    st_generator *gen;
    char *key, *data;

    gen = st_init_gen(s);
    while (st_gen(gen, &key, &data)) {
	if (key != data)
	    FREE(key);
	FREE(data);
    }
    st_free_gen(gen);

    st_free_table(s);
}

/*
 * set_add
 *
 *     add am element to a set
 *
 * argument: a, s
 *
 * returns: s'
 *
 * side effects: s will be modified
 *
 * bugs:
 * 
 * comment:
 */
set_t *set_add(a, s)
char *a;
set_t *s;
{
    char *dummy;

    if (!st_lookup(s, a, &dummy)) {
	st_insert(s, SetStrdup(a), SetStrdup(a));
    }
    return s;
}

/*
 * set_eliminate
 *
 *     remove am element from a set
 *
 * argument: a, s
 *
 * returns: s'
 *
 * side effects: s will be modified
 *
 * bugs:
 * 
 * comment:
 */
set_t *set_eliminate(a, s)
char *a;
set_t *s;
{
    char *dummy;
    char *key;

    if (st_lookup(s, a, &dummy)) {
	key = a;
	st_delete(s, &key, &dummy);
	FREE(dummy);
	FREE(dummy);
    }
    return s;
}

/*
 * set_find
 * 
 *     determine if an element a is in s
 *
 * arguments: a, s
 *
 * returns: 1/0
 *
 * side effects:
 *
 * bugs:
 * 
 * comments:
 */
int set_find(a, s)
char *a;
set_t *s;
{
    char *dummy;

    return (st_lookup(s, a, &dummy));
}

/*
 * set_union
 * 
 *     given two sets (s1, s2) find their union
 *
 * argument: s1, s2
 *
 * returns: s1 + s2
 *
 * bugs:
 *
 * comments:
 */
set_t *set_union(s1, s2)
set_t *s1;
set_t *s2;
{
    st_generator *gen;
    set_t *retval;
    char *key, *data, *dummy;

    retval = st_init_table(strcmp, st_strhash);
    gen = st_init_gen(s1);
    while (st_gen(gen, &key, &data)) {
	st_insert(retval, SetStrdup(key), SetStrdup(data));
    }
    st_free_gen(gen);
    gen = st_init_gen(s2);
    while (st_gen(gen, &key, &data)) {
	if (!st_lookup(s1, key, &dummy)) {
	    st_insert(retval, SetStrdup(key), SetStrdup(data));
	}
    }
    st_free_gen(gen);

    return retval;
}

/*
 * set_intersect
 * 
 *     given two sets (s1, s2) find their intersection
 *
 * argument: s1, s2
 *
 * returns: s1 * s2
 *
 * bugs:
 *
 * comments:
 */
set_t *set_intersect(s1, s2)
set_t *s1;
set_t *s2;
{
    st_generator *gen;
    set_t *retval;
    char *key, *data, *dummy;

    retval = st_init_table(strcmp, st_strhash);
    gen = st_init_gen(s1);
    while (st_gen(gen, &key, &data)) {
	if (st_lookup(s2, key, &dummy)) {
	    st_insert(retval, SetStrdup(key), SetStrdup(key));
	}
    }
    st_free_gen(gen);

    return retval;
}

/*
 * set_dup
 * 
 *     duplicate a set and all its elements
 *
 * arguments: s
 *
 * returns: s' ( = s )
 *
 * side effects:
 *
 * bugs:
 * 
 * comments:
 */
set_t *set_dup(s)
set_t *s;
{
    st_generator *gen;
    set_t *retval;
    char *key, *data;

    retval = st_init_table(strcmp, st_strhash);
    gen = st_init_gen(s);
    while (st_gen(gen, &key, &data)) {
	st_insert(retval, SetStrdup(key), SetStrdup(data));
    }
    st_free_gen(gen);

    return retval;
}