static void
flow_kill_aliases (set_t *kill, flowvar_t *var, const set_t *uninit)
{
	operand_t  *op;
	set_t      *tmp;

	set_union (kill, var->define);
	op = var->op;
	tmp = set_new ();
	if (op->op_type == op_temp) {
		if (op->o.tempop.alias) {
			op = op->o.tempop.alias;
			var = op->o.tempop.flowvar;
			if (var)
				set_union (tmp, var->define);
		}
		for (op = op->o.tempop.alias_ops; op; op = op->next) {
			var = op->o.tempop.flowvar;
			if (var)
				set_union (tmp, var->define);
		}
	} else if (op->op_type == op_def) {
		def_visit_all (op->o.def, 1, flow_kill_aliases_visit, tmp);
		// don't allow aliases to kill definitions in the entry dummy block
		set_difference (tmp, uninit);
	}
	// merge the alias kills with the current def's kills
	set_union (kill, tmp);
}

/**********************************************************************
 *
 *	firstpos
 *
 * Fills firstpos-field in syntax tree. Here we suppose, that all
 * nodes below current node are already visited (depth-first traversal).
 * Firstpos is a set of positions that can match the first symbol of a 
 * string generated by the subexpression rooted by node.
 */
static void firstpos(REG1 int node, REG2 node_t* tnode)
{
	switch (tnode->type) {
		case EMPTY_ID:
		    set_clear(tnode->firstpos, rbuf.setsize);
		    break;
		case CLASS_ID:
		case ID:
		    add_set(tnode->firstpos, node);
		    break;
		case OR:
		    set_union(tnode->firstpos,
		        rbuf.tree[tnode->val.next.left].firstpos,
			rbuf.tree[tnode->val.next.right].firstpos,
			rbuf.setsize);
		    break;
		case CAT:
		    if (rbuf.tree[tnode->val.next.left].nullable)
			set_union(tnode->firstpos,
			    rbuf.tree[tnode->val.next.left].firstpos,
			    rbuf.tree[tnode->val.next.right].firstpos,
			    rbuf.setsize);
		    else
			set_copy(tnode->firstpos,
			    rbuf.tree[tnode->val.next.left].firstpos,
			    rbuf.setsize);
		    break;
		case CLOSURE:
		    set_copy(tnode->firstpos,
		         rbuf.tree[tnode->val.next.left].firstpos,
		         rbuf.setsize);
		    break;
	}
}

static void
live_set_def (set_t *stdef, set_t *use, set_t *def)
{
	// the variable is defined before it is used
	set_difference (stdef, use);
	set_union (def, stdef);
}

Compatible::Compatible(Query* s1, Query* s2)
	: Query2(s1, s2),
	  allcols(set_union(source->columns(), source2->columns())) {
	Lisp<Fixed> fixed1 = source->fixed();
	Lisp<Fixed> fixed2 = source2->fixed();
	Lisp<Fixed> f1;
	Lisp<Fixed> f2;
	for (f1 = fixed1; !nil(f1); ++f1)
		for (f2 = fixed2; !nil(f2); ++f2)
			if (f1->field == f2->field &&
				nil(intersect(f1->values, f2->values))) {
				disjoint = f1->field;
				return;
			}
	Fields cols2 = source2->columns();
	for (f1 = fixed1; !nil(f1); ++f1)
		if (!member(cols2, f1->field) && !member(f1->values, SuEmptyString)) {
			disjoint = f1->field;
			return;
		}
	Fields cols1 = source->columns();
	for (f2 = fixed2; !nil(f2); ++f2)
		if (!member(cols1, f2->field) && !member(f2->values, SuEmptyString)) {
			disjoint = f2->field;
			return;
		}
}

int main(int argc, char *argv[])
{
    int i, size = 100, *x;
    struct set *s, *t, *u;
    
    if (argc > 1)
	size = atoi(argv[1]);
    
    srand(time(NULL));

    s = set_create(size, sizeof(int), cmpint);
    t = set_create(size, sizeof(int), cmpint);
    if (s == NULL || t == NULL){
	printf("Unable to create the test set\n");
	return 1;
    }

    printf("Inserting into first set...\n");
    for (i = 0; i < size; i++){
	int y = rand() % size;

	printf("%d ", y);
	set_insert(s, &y);
    }
    printf("\n\n");

    printf("The set contains:\n");
    for (set_reset(s), x = set_next(s); x != NULL; x = set_next(s)) 
	printf("%d ", *x);
    printf("\n\n");

    printf("Inserting into second set...\n");
    for (i = 0; i < size; i++){
	int y = rand() % size;

	printf("%d ", y);
	set_insert(t, &y);
    }
    printf("\n\n");

    printf("The set contains:\n");
    for (set_reset(t), x = set_next(t); x != NULL; x = set_next(t)) 
	printf("%d ", *x);
    printf("\n\n");

    u = set_union(s, t);
    printf("The union of the two sets is:\n");
    for (set_reset(u), x = set_next(u); x != NULL; x = set_next(u)) 
	printf("%d ", *x);
    printf("\n\n");
    set_destroy(u);

    u = set_diff(s, t);
    printf("The difference of the two sets is:\n");
    for (set_reset(u), x = set_next(u); x != NULL; x = set_next(u)) 
	printf("%d ", *x);
    printf("\n\n");
    
    return 0;
}

/* Add exactly b to the set guarded by meta. */
int meta_alloc(void* meta, size_t size, ubb_p up, size_t index, db_t db, struct xn_m_vec *mv, int n) {
	/* ensure that {old_set U b} == new_set */
	static inline int add(Set old, Set new, db_t db) {
		return set_eq(set_union(old, set_single((T){db})), new);
	}
	return meta_transaction(add, meta, size, up, index, db, mv, n);
}

void test_set_operations(){
	set_t *even1 = new_set(10);
	set_t *even2 = new_set(10);
	set_t *odd  = new_set(10);
	
	int i;
	for (i=0; i < 10; i++){
		set_put(even1, 2*i);
		set_put(even2, 2*i);
		set_put(odd, 2*i+1);
	}
	
	set_union(even1, odd);
	assert(set_size(even1) == 20);
	
	set_difference(even2, odd);
	assert(set_size(even2) == 10);
	
	set_intersection(even2, odd);
	assert(set_size(even2) == 0);
	
	set_print(even1); printf("\n");
	set_optimize(even1);
	set_print(even1); printf("\n");
	
	set_print(even2); printf("\n");
	set_print(odd); printf("\n");
	
	delete_set(even1);
	delete_set(even2);
	delete_set(odd);
}

int main(void) 
{
  set s1, s2;
  int m = 10;

  s1 = set_init(m);
  set_add(s1, 1);
  set_add(s1, 3);
  set_add(s1, 5);
  s2 = set_init(m + 2);
  set_add(s2, 0);
  set_add(s2, 2);
  set_add(s2, 3);
  set_add(s2, 4);
  set_add(s2, 5);
  set_add(s2, 11);
  set_print(s1);
  printf("\n");
  set_print(s2);
  printf("\nIntersection: ");
  set_print(set_intersection(s1, s2));
  printf("\nUnion: ");
  set_print(set_union(s1, s2));
  printf("\nComplement for s2: ");
  set_print(set_complement(s2));
  printf("\n");  
  return 0;
}

int main(int argc, string argv[])
{
    stream istr, ostr;
    string itags[MaxBodyFields];

    initparam(argv, defv);
    new_field(&LinkField, IntType, LinkTag);	/* use int's worth of space */
    new_field(&LinkField + 1, NULL, NULL);
    layout_body(bodytags, Precision, NDIM);
    istr = stropen(getparam("in"), "r");
    get_history(istr);
    if (! get_snap(istr, &btab, &nbody, &tnow, itags, TRUE))
        error("%s: snapshot input failed\n", getargv0());
    if (! set_member(itags, PosTag))
        error("%s: %s data missing\n", getargv0(), PosTag);
    if (getbparam("subkey") && ! set_member(itags, KeyTag))
        error("%s: %s data missing\n", getargv0(), KeyTag);
    findobj(getdparam("bcrit"),	getiparam("nmin"), getbparam("subkey"));
    ostr = stropen(getparam("out"), "w");
    put_history(ostr);
    put_snap(ostr, &btab, &nbody, &tnow,
             set_union(itags, set_cons(KeyTag, NULL)));
    strclose(ostr);
    return (0);
}

static void
flow_find_loops (flowgraph_t *graph)
{
	flownode_t *node;
	set_iter_t *succ;
	flowloop_t *loop, *l;
	flowloop_t *loop_list = 0;
	int         i;

	for (i = 0; i < graph->num_nodes; i++) {
		node = graph->nodes[i];
		for (succ = set_first (node->successors); succ;
			 succ = set_next (succ)) {
			if (set_is_member (node->dom, succ->element)) {
				loop = make_loop (graph, node->id, succ->element);
				for (l = loop_list; l; l = l->next) {
					if (l->head == loop->head
						&& !set_is_subset (l->nodes, loop->nodes)
						&& !set_is_subset (loop->nodes, l->nodes)) {
						set_union (l->nodes, loop->nodes);
						delete_loop (loop);
						loop = 0;
						break;
					}
				}
				if (loop) {
					loop->next = loop_list;
					loop_list = loop;
				}
			}
		}
	}
	graph->loops = loop_list;
}

static void test_ops(void)
{
    Set *s1 = set_create();
    Set *s2 = set_create();
    Set *s3 = set_create();

    if (s1 == 0 || s2 == 0 || s3  == 0)
        err_syserr("Out of memory\n");

    load_set(s1, 1, 3, 4, 6);
    dump_set("S1", s1);

    load_set(s2, 2, 5, 7, 9);
    dump_set("S2", s2);

    set_union(s1, s2, s3);
    dump_set("S1 union S2", s3);

    set_empty(s3);
    set_intersect(s1, s2, s3);
    dump_set("S1 intersect S2", s3);

    set_empty(s3);
    set_difference(s1, s2, s3);
    dump_set("S1 minus S2", s3);

    set_empty(s3);
    set_difference(s2, s1, s3);
    dump_set("S2 minus S1", s3);

    set_destroy(s1);
    set_destroy(s2);
    set_destroy(s3);
}

// Merge a given rank sink (new_sink) (ie. a set of Nodes) with one of exsisting
// rank sink(s).
// Returns ture if it merges, otherwise insert it to sink(s) group as a new rank sink
// merge condition : if new_sink n sinks_i => merged( new_sink u sinks_i) for all 'i' in sinks
// where
//    n, u - set intersect and union operators
//    sink_i - 'i'th sink set in sinks
bool PageRank::merge_rank_sinks(vector<vector<Node> >& sinks, vector<Node>& new_sink) const {

  // check whether the created rank_sink can be  merged with an already created rank sink
  for (unsigned int rs=0; rs< sinks.size(); ++rs) { // check all rank sink created so far
    bool shared_nodes= has_intersection(sinks[rs].begin(), sinks[rs].end(), 
					new_sink.begin(), new_sink.end());
    if (shared_nodes) { // merge new rank_sink with sinks[rs] set
      vector<Node> merged_sink;
      merged_sink.resize( new_sink.size() + sinks[rs].size()); // size() on the safe side
      vector<Node>::iterator nsize;
      nsize = set_union(new_sink.begin(), new_sink.end(),
			sinks[rs].begin(), sinks[rs].end(), merged_sink.begin());
      merged_sink.resize(nsize - merged_sink.begin()); // resize
      sinks[rs] = merged_sink;
      PRINT(LOG_LVL_3, "Rank sink is merged with a previously found sink" << endl);
      return true;
    }
  }
  
  // couldn't merge create a new sink group
  sinks.push_back( new_sink);
  PRINT(LOG_LVL_3, "New rank sink created" << endl);
  return false;
  
}

void Board::setFrontier()
{
    setFrontierFor(sideFlag);
    setFrontierFor(!sideFlag);
    allFrontier.clear();
    set_union(sideFrontier[sideFlag].begin(), sideFrontier[sideFlag].end(), sideFrontier[!sideFlag].begin(), sideFrontier[!sideFlag].end(), inserter(allFrontier, allFrontier.begin()));
}

	void distinct_keys(std::vector<std::unordered_set<key_type> >& key_assignments,
                       std::unordered_set<key_type>& result) {
		std::unordered_set<key_type> I, U;
		set_intersection(key_assignments, I);
		set_union(key_assignments, U);
		set_difference(U, I, result);
	}

bool xRedisClient::sunion(const DBIArray& vdbi,     const KEYS& vkey, VALUES& sValue) {
    int size = vkey.size();
    VALUES *setData = new VALUES[size];
    VALUES::iterator endpos;

    DBIArray::const_iterator iter_dbi = vdbi.begin();
    KEYS::const_iterator     iter_key = vkey.begin();
    int i=0;
    for (; iter_key!=vkey.end(); ++iter_key, ++iter_dbi, ++i) {
        const string &key = *iter_key;
        const RedisDBIdx &dbi = *iter_dbi;
        if (!smember(dbi, key, setData[i])) {
            delete [] setData;
            return false;
        }
    }

    int n=0;
    while(n++<size-1) {
        endpos = set_union( setData[n].begin(), setData[n].end(), setData[n+1].begin(), setData[n+1].end() , sValue.begin());
        sValue.resize( endpos - sValue.begin());
    }
    delete [] setData;
    return true;
}

int main()
{
  int p, q, i, id[N], p_id, q_id, size_arr[N];
  // initialize ids and size
  for (i = 0; i < N; i++)
  {
	  id[i] = i;
	  size_arr[i] = 1;
  }

  // read pairs and keep/update connected components information
  printf("Enter pairs p q: \n");
  while (scanf("%d %d", &p, &q) == 2)
  {
    p_id = find(p, id);
    q_id = find(q, id);
    

    if (p_id == q_id)
    {
      printf(" %d and %d were on the same set\n", p, q);
	  print_array_int(id, N);
      continue;
    }

    set_union(p_id, q_id, id, N, size_arr,p,q);   // sending two extra values.. 
    printf(" %d %d link led to set union\n", p, q);
    
    print_array_int(id, N);
    print_array_int(size_arr, N);
  }
  return 0;
}

map<string, vector<span>> program_eval::eval(program& prog) {
  map<string, vector<span>> answer;
  auto sorted_rules = sort_rules(prog.rules);

  for (auto rule : sorted_rules) {
    rule_eval evaluator(answer, document_);
    auto result = evaluator.eval(*rule);

    auto it = answer.find(rule->pred.name);

    if (it == answer.end()) {
      // Move
      answer.insert(make_pair(rule->pred.name, move(result)));
    } else {
      // Union
      auto& spans = it->second;
      vector<span> span_union;
      span_union.reserve(spans.size() + result.size());
      set_union(spans.begin(), spans.end(), result.begin(), result.end(),
          back_inserter(span_union));
      span_union.shrink_to_fit();
      spans.swap(span_union);
    }
  }

  return answer;
}

/**********************************************************************
 *
 *	followpos
 *
 * Creates followpos array using depth-first traversal.
 * Followpos(i) is the set of positions j such that there is some input 
 * string ...cd... such that i corresponds to this occurence of c and 
 * j to this occurence of d. So for example for a subexpression cd each 
 * lastpos of c is followed by firstpos of d, or for c* each lastpos of
 * c is followed by firstpos in c.
 */
static bool followpos(void)
{
	REG1 int	i; 
	REG2 int	j;
	REG3 node_t*	inode;
	REG4 node_t*	jnode;
	REG5 set_t**	followptr;
	
	if ((followptr = calloc((rbuf.root+1) * sizeof(set_t *), 1)) == NULL)
		return FALSE;
	rbuf.follow_array = followptr;
	inode = rbuf.tree;
	for (i = 0; i <= rbuf.root; i++, inode++, followptr++) {
		if (inode->type != ID && inode->type != CLASS_ID ) {
			*followptr = NULL;
			continue;
		}
		if ((*followptr = calloc(rbuf.setsize, 1)) == NULL)
			return FALSE;
		jnode = &rbuf.tree[i+1];
		for (j = i+1; j <= rbuf.root; j++, jnode++) {
			switch (jnode->type) {
			    case CAT:
				if (in_set(rbuf.tree[jnode->val.next.left].
				    lastpos, i))
				    set_union(
				      *followptr,
				      *followptr,
				      rbuf.tree[jnode->val.next.right].firstpos,
				      rbuf.setsize);
				break;
			    case CLOSURE:
				if (in_set(jnode->lastpos, i))
				    set_union(
				      *followptr,
				      *followptr,
				      jnode->firstpos,
				      rbuf.setsize);
				break;
			    default:
				break;
			}
		}
	}
	return TRUE;
}

vector<T> merge_vectors(vector<T> &v1, vector<T> &v2) {
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    vector<T> result;
    set_union(v1.begin(), v1.end(), v2.begin(), v2.end(),
              back_inserter(result));
    return result;
}

/**
 * Traduit une formule en sa forme conjonctive.
 * @param form La formule simplifiée à transformer.
 * @param correspondance La liste des correspondances nom<->numéro des variables de la formule.
 * @return La forme conjonctive équivalente à la formule form.
 * @see formule
 * @see forme_conjonctive
 * @see simplifie_formule(const formule*, const bool)
 */
forme_conjonctive trad_forme_conjonctive(const formule *form, map<string, unsigned int> &correspondance) {
	forme_conjonctive fc_out, fc1, fc2;
	if(is_binary(form->op)) {
		fc1 = trad_forme_conjonctive(form->arg1, correspondance);
		fc2 = trad_forme_conjonctive(form->arg2, correspondance);
	}
	switch(form->op) {
		case o_variable:
		{
			clause cl;
			cl.push_back(correspondance[*(form->nom)]);
			fc_out.push_back(cl);
			break;
		}

		case o_non:
		{
			clause cl;
			cl.push_back(-correspondance[*(form->arg->nom)]);
			fc_out.push_back(cl);
			break;
		}

		case o_ou:
		{
			forme_conjonctive::const_iterator it1, it2;
			clause cl;

			for(it1=fc1.begin(); it1!=fc1.end(); it1++) {
				for(it2=fc2.begin(); it2!=fc2.end(); it2++) {
					cl.clear();
					set_union(it1->begin(), it1->end(), it2->begin(), it2->end(), insert_iterator<clause>(cl, cl.begin()));
					fc_out.push_back(cl);
				}
			}
			break;
		}

		case o_et:
		{
			set_union(fc1.begin(), fc1.end(), fc2.begin(), fc2.end(), insert_iterator<forme_conjonctive>(fc_out, fc_out.begin()));
			break;
		}
	}
	return fc_out;
}