//-------------------------------------------------------------------------------------
void EntityCoordinateNode::entitiesInRange(std::vector<Entity*>& foundEntities, CoordinateNode* rootNode,
									  const Position3D& originPos, float radius, int entityUType)
{
	std::set<Entity*> entities_X;
	std::set<Entity*> entities_Z;

	entitiesInAxisRange<CoordinateNodeWrapX>(entities_X, rootNode, originPos, radius, entityUType);
	entitiesInAxisRange<CoordinateNodeWrapZ>(entities_Z, rootNode, originPos, radius, entityUType);

	// 查找Y
	if (CoordinateSystem::hasY)
	{
		std::set<Entity*> entities_Y;
		entitiesInAxisRange<CoordinateNodeWrapY>(entities_Y, rootNode, originPos, radius, entityUType);


		std::set<Entity*> res_set;
		set_intersection(entities_X.begin(), entities_X.end(), entities_Z.begin(), entities_Z.end(), std::inserter(res_set, res_set.end()));
		set_intersection(res_set.begin(), res_set.end(), entities_Y.begin(), entities_Y.end(), std::back_inserter(foundEntities));
	}
	else
	{
		set_intersection(entities_X.begin(), entities_X.end(), entities_Z.begin(), entities_Z.end(), std::back_inserter(foundEntities));
	}
}

/** Procédure récursive pour trouver les cliques du graphe (Algorithme de Bron-Kerbosch).*/
void OperateurEnsemble::bk_recursive(setNoeud combination, setNoeud intersection, setNoeud possible, vector<setNoeud>* res)
{
    /*cout<<"Current :";
    for(setNoeud::iterator it = combination.begin();it!=combination.end();it++)
    	cout<<(*it)->nom_parser<<" ";
    cout<<endl;
    cout<<"Possible :";
    for(setNoeud::iterator it = possible.begin();it!=possible.end();it++)
    	cout<<(*it)->nom_parser<<" ";
    cout<<endl;
    cout<<"Intersection :";
    for(setNoeud::iterator it = intersection.begin();it!=intersection.end();it++)
    	cout<<(*it)->nom_parser<<" ";
    cout<<endl<<endl;*/
    if(intersection.empty()) //plus rien à ajouter, on a trouvé une clique
    {
        res->push_back(combination);
        return;
    }
    setNoeud S = possible;
    for(setNoeud::iterator it = S.begin(); it!=S.end(); it++) //pour chaque noeud à traiter
    {
        possible.erase(*it); //on supprime l'élément sélectionné des candidats
        setNoeud new_inter;
        set_intersection(intersection.begin(),intersection.end(),succ[*it].begin(),succ[*it].end(),inserter(new_inter,new_inter.begin())); //intersection avec les voisins du noeud sélectionné

        setNoeud new_possible;
        set_intersection(possible.begin(),possible.end(),succ[*it].begin(),succ[*it].end(),inserter(new_possible,new_possible.begin())); //intersection avec les voisins du noeud sélectionné

        setNoeud new_comb = combination;
        new_comb.insert(*it);
        bk_recursive(new_comb,new_inter,new_possible,res);
    }
}

void bron_kerbosch(set <int> R, set <int> P, set <int> X) { // where R is probable clique, P - possible vertices in clique, X - exluded vertices
    if (P.size() == 0 && X.size() == 0) { // R is maximal clique
        cliques.push_back(vector<int>(0));
        for (set<int>::iterator i = R.begin(); i != R.end(); i++) {
            cliques.back().push_back(*i);
        }
    }
    else {
        set <int> foriterate = P;
        for (set<int>::iterator i = foriterate.begin(); i != foriterate.end(); i++) {
            set <int> newR;
            set <int> newP;
            set <int> newX;

            newR = R;
            newR.insert(*i);

            set_intersection(P.begin(), P.end(), edge[*i].begin(), edge[*i].end(), inserter(newP, newP.begin()));

            set_intersection(X.begin(), X.end(), edge[*i].begin(), edge[*i].end(), inserter(newX, newX.begin()));

            bron_kerbosch(newR, newP, newX);

            P.erase(*i);
            X.insert(*i);
        }
    }
}

 void castGWAS::interSect(castSNP &SNPs)
 {
     set<string> tmp;
     
     set_intersection(initial_keys.begin(), initial_keys.end(), SNPs.onChip.begin(), SNPs.onChip.end(), inserter(tmp, tmp.end()));
     semifinishedKeys.clear();
     set_intersection(tmp.begin(), tmp.end(), SNPs.onHapMap.begin(), SNPs.onHapMap.end(), inserter(semifinishedKeys, semifinishedKeys.end()));
 }

void test_set_intersection (void) {
  int numbers1[] = {1, 2, 3, 4, 5, 6, 7};
  int numbers2[] = {5, 6, 7, 8, 9, 10, 11};
  int result[] = {5, 6, 7};
  int i;
  Set* set1;
  Set* set2;
  Set* result_set;
  size_t allocated;

  /* Create the first set */

  set1 = set_new (int_hash, int_equal);

  for (i = 0; i < 7; ++i) {
    set_insert (set1, &numbers1[i]);
    }

  /* Create the second set */

  set2 = set_new (int_hash, int_equal);

  for (i = 0; i < 7; ++i) {
    set_insert (set2, &numbers2[i]);
    }

  /* Perform the intersection */

  result_set = set_intersection (set1, set2);

  assert (set_num_entries (result_set) == 3);

  for (i = 0; i < 3; ++i) {
    assert (set_query (result_set, &result[i]) != 0);
    }

  /* Test out of memory scenario */

  alloc_test_set_limit (0);
  assert (set_intersection (set1, set2) == NULL);

  /* Can allocate set, can't copy all values */

  alloc_test_set_limit (2 + 2);
  allocated = alloc_test_get_allocated();
  assert (set_intersection (set1, set2) == NULL);
  assert (alloc_test_get_allocated() == allocated);

  set_free (set1);
  set_free (set2);
  set_free (result_set);
  }

void CityFinder::findNearbyCities(double radius) {

    set<string> citySetRes, citySetInters, citySet1, citySet2;

    double latLowBound   = centerCity.second.lat - radius;
    double latUpperBound = centerCity.second.lat + radius;
    for (auto it  = latLookup.lower_bound(latLowBound);
              it != latLookup.upper_bound(latUpperBound); ++it) {
        citySet1.insert(latLookup[it->first]);
    }

    double lonLowBound   = centerCity.second.lon - radius;
    double lonUpperBound = centerCity.second.lon + radius;
    for (auto it  = lonLookup.lower_bound(lonLowBound);
         it != lonLookup.upper_bound(lonUpperBound); ++it) {
        citySet2.insert(lonLookup[it->first]);
    }

    set_intersection(citySet1.begin(), citySet1.end(),
    citySet2.begin(), citySet2.end(), inserter(citySetInters, citySetInters.end()));

    for (string cityName : citySetInters) {
        City city = make_pair(cityName, cityLookup.find(cityName)->second);
        if (distance(city) <= radius) {
            citySetRes.insert(cityName);
        }
    }

    for (string cityName : citySetRes) {
        cout << cityName << endl;
    }
}

	std::pair<CombSet::iterator,bool> ReqS_LACP::operator() (
				std::list<CombSet::iterator> &local_state_cache,
				std::set<int> &dealed_factors,
				const Requirement &req)
	{
		float min_num=m_max_number;
		std::list<CombSet::iterator>::iterator selected_it1=local_state_cache.begin();
		std::list<CombSet::iterator>::iterator selected_it2=local_state_cache.end();
		for(std::list<CombSet::iterator>::iterator it=local_state_cache.begin();
			it!=local_state_cache.end();++it)
		{
			const std::set<int> &inter=(*it)->getParaSet();
			std::vector<int> temp(dealed_factors.size()+inter.size(),-1);
			std::vector<int>::iterator the_end=set_intersection(
					dealed_factors.begin(),dealed_factors.end(),
					inter.begin(),inter.end(),temp.begin());

			int num=1;
			for(std::vector<int>::const_iterator itp=temp.begin();itp!=the_end;++itp)
				num*=req.getParaValue(*itp);
			float number=((float)(num))/((float)((*it)->Size()));

			if(number<min_num && num>1)
			{
				min_num=number;
				selected_it2=it;
			}
		}

		CombSet::iterator selected_one;
		bool flag=ModifyLocalStateCache(selected_it1,selected_it2,
			local_state_cache,dealed_factors,selected_one);
		return std::pair<CombSet::iterator,bool>(selected_one,flag);
	}

  double mirkin_distance(const cluster_list& c1, const cluster_list& c2) {
    size_t c1_sum2 = 0;
    size_t n = 0;
    for (size_t i=0; i < c1.size(); i++) {
      c1_sum2 += c1[i].size() * c1[i].size();
      n += c1[i].size();
    }

    size_t c2_sum2 = 0;
    for (size_t i=0; i < c2.size(); i++) {
      c2_sum2 += c2[i].size() * c2[i].size();    
    }
  

    size_t c1c2_sum2 = 0;
    for (size_t i=0; i < c1.size(); i++) {
      for (size_t j=0; j < c2.size(); j++) {
        size_t size;
        set_intersection(c1[i].begin(), c1[i].end(), 
                         c2[j].begin(), c2[j].end(),
                         counter(size));
        c1c2_sum2 += size * size;
      }
    }

    return (c1_sum2 + c2_sum2 - (2 * c1c2_sum2)) / (double)(n*n);
  }

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;
}

	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);
	}

	/*
	This api takes the user input - and looks up the word[s] in the inverted index.
	The candidate documents are then ranked based on tf-idf BOW (bag of words) model
	*/
	std::vector<std::pair<int,double> > ServeIndex(const std::string& word,int topK)
	{
		//tokenize and normalize the user text
		std::vector<std::string>& word_tokens = _wordBreaker->BreakEnglishText(word.c_str());

		std::vector<std::pair<int,double> > results;

		//generate the candidate document set
		std::set<int> candSet;
		bool foundAny = false;
		for(size_t i=0;i<word_tokens.size();++i)
		{
			boost::unordered_map<std::string,IndexEntry>::iterator itor = _indexPtr->_wordIndex.find(word_tokens[i]);

			if( itor == _indexPtr->_wordIndex.end() )
				continue;

			else{
				//first entry which was found
				if(!foundAny){
					candSet = itor->second._docSet;
					foundAny = true;
				} else{
					std::set<int> temp;
					set_intersection(candSet.begin(),candSet.end(),(itor->second)._docSet.begin(),(itor->second)._docSet.end(),inserter(temp,temp.begin()));
					candSet.clear();
					candSet = temp;
				}
			}

		}

		return Rank(word_tokens,candSet,topK);
	}

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);
}

QueryResult AndQuery::eval(const TextQuery& text) const
{
	auto left=lhs.eval(text), right=rhs.eval(text);
	auto ret_lines=std::make_shared<std::set<line_no>>();
	set_intersection(left.begin(),left.end(),right.begin(),right.end(),inserter(*ret_lines,ret_lines->begin()));
	return QueryResult(rep(),ret_lines,left.get_file());
}

 vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
     vector<int> v;
     sort(nums1.begin(),nums1.end());
     sort(nums2.begin(),nums2.end());
     set_intersection(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),inserter(v,v.end()));
     return v;
 }

void
date_intersection(const CONT<TSeries<TDATE,TDATA,TSDIM,TSDATABACKEND,DatePolicy> >& cont,
                  II output_dates)
{
    std::vector<TDATE> inBuff;
    std::vector<TDATE> outBuff;

    typename CONT<TSeries<TDATE,TDATA,TSDIM,TSDATABACKEND,DatePolicy> >::const_iterator it = cont.begin();

    // pre-load dates for first series
    std::copy(it->getDates(),it->getDates() + it->nrow(),
              std::inserter(inBuff,inBuff.begin()));

    for(it = cont.begin() + 1; it != cont.end(); it++) {
        outBuff.clear();
        set_intersection(inBuff.begin(),inBuff.end(),
                         it->getDates(),it->getDates() + it->nrow(),
                         std::inserter(outBuff,outBuff.begin()));
        // swap buffs
        inBuff.clear();
        std::copy(outBuff.begin(),outBuff.end(),
                  std::inserter(inBuff,inBuff.begin()));
    }
    std::copy(outBuff.begin(),outBuff.end(),output_dates);
}

bool xRedisClient::sinter(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_intersection( 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;
}

	/**
	 * Find all maximal cliques in an induced subgraph of some chain component
	 *
	 * NOTE: the function does not check whether the provided range of vertices
	 * really is a subset of some chain component!
	 */
	template <typename InputIterator> std::vector<std::set<uint> > getMaxCliques(InputIterator first, InputIterator last)
	{
		std::vector<std::set<uint> > maxCliques;

		// Trivial case: range of vertices contains at most one vertex
		if (std::distance(first, last) <= 1) {
			maxCliques.push_back(std::set<uint>(first, last));
			return maxCliques;
		}

		// For less trivial cases, first generate a LexBFS-ordering on the provided range of vertices
		std::vector<uint> ordering = lexBFS(first, last);

		// Find maximal cliques using the LexBFS-ordering
		std::set<uint> nbhdSubset(first, last);
		std::set<uint> vertices, C;
		std::vector<std::set<uint> >::iterator cliqueIter;
		bool included;
		for (int i = ordering.size() - 1; i >= 0; --i) {
			nbhdSubset.erase(ordering[i]);
			vertices = getNeighbors(ordering[i]);
			C = set_intersection(vertices, nbhdSubset);
			C.insert(ordering[i]);
			included = false;
			for (cliqueIter = maxCliques.begin(); !included && cliqueIter != maxCliques.end(); ++cliqueIter)
				included = std::includes(cliqueIter->begin(), cliqueIter->end(), C.begin(), C.end());
			if (!included)
				maxCliques.push_back(C);
		}

		return maxCliques;
	}

mixed *set_difference(mixed *a, mixed *b, varargs int r) {
   mixed *c;

   c = set_intersection(a, set_symmetric_difference(a, b));

   return r ? set_remove_repeats(c) : c;
}

int
RACScore::GetMultiLevelCommNeighbors( const BglVertex& u, const BglVertex& v, 
    vector<int>& vecCommNeighbors, const int level)
{
  vector<int> vecUNeighbor;
  vector<int> vecVNeighbor;
  int initial = 0;
  BFS(u, vecUNeighbor, initial, level);
  BFS(v, vecVNeighbor, initial, level);
  sort(vecUNeighbor.begin(), vecUNeighbor.end());
  sort(vecVNeighbor.begin(), vecVNeighbor.end());
  int maxSize = vecUNeighbor.size() > vecVNeighbor.size()? vecUNeighbor.size():vecVNeighbor.size();
  vector<int> myVecCommNeighbors(maxSize);
  myVecCommNeighbors.resize(maxSize);
  vector<int>::iterator it_end;
  it_end = set_intersection(vecUNeighbor.begin(), vecUNeighbor.end(), 
      vecVNeighbor.begin(), vecVNeighbor.end(), myVecCommNeighbors.begin());
  //cout << vecUNeighbor.size() << ' ' << vecVNeighbor.size() <<' ' << maxSize <<' ' << distance(myVecCommNeighbors.begin(),it_end) <<endl;
  
  vecCommNeighbors.resize(distance(myVecCommNeighbors.begin(), it_end));
  copy(myVecCommNeighbors.begin(), it_end ,vecCommNeighbors.begin());


  return distance(myVecCommNeighbors.begin(),it_end) ;
}

void Server::handleInvolvedByMinIds()
{
    // read input data
    size_t tp_hash_count = recvLong();
    std::vector<GitOid> tp_hashes;
    for (size_t i = 0; i < tp_hash_count; ++i) {
        tp_hashes.push_back(recvOid());
    }

    std::vector<int> min_ids = getMinIds(recvLongVector());

    // process request
    sort(min_ids.begin(), min_ids.end());

    // TODO: sort tp_hashes by first_id (to optimize reads from mapped file), remember indices before sorting!

    std::vector<int> res;
    for (size_t i = 0; i < tp_hashes.size(); ++i)
    {
        std::vector<int> c_ids = getTphashMinIds(tp_hashes[i]);
        sort(c_ids.begin(), c_ids.end());

        std::vector<int> intersection(min_ids.size());
        if (set_intersection(
            min_ids.begin(), min_ids.end(),
            c_ids.begin(), c_ids.end(),
            intersection.begin()) != intersection.begin())
        {
            res.push_back(i);
        }
    }

    // write output data
    sendLongVector(res);
}