void TextView::highlight(std::vector<Range<int>> ranges, bool ensureVisible) {
    if (!ranges.empty()) {
        std::sort(ranges.begin(), ranges.end());

        if (ensureVisible) {
            std::vector<Range<int>> difference;

            set_difference(
                ranges.begin(), ranges.end(),
                highlighting_.begin(), highlighting_.end(),
                std::back_inserter(difference));

            if (difference.empty()) {
                set_difference(
                    highlighting_.begin(), highlighting_.end(),
                    ranges.begin(), ranges.end(),
                    std::back_inserter(difference));
            }

            if (!difference.empty()) {
                textEdit()->blockSignals(true);
                moveCursor(difference.front().end(), true);
                moveCursor(difference.front().start(), true);
                textEdit()->blockSignals(false);
            }
        }

        highlighting_.swap(ranges);
    } else {
        highlighting_.clear();
    }

    updateExtraSelections();
}

void LLAvatarList::computeDifference(
	const std::vector<LLUUID>& vnew_unsorted,
	std::vector<LLUUID>& vadded,
	std::vector<LLUUID>& vremoved)
{
	std::vector<LLUUID> vcur;
	std::vector<LLUUID> vnew = vnew_unsorted;

	// Convert LLSDs to LLUUIDs.
	{
		std::vector<LLSD> vcur_values;
		getValues(vcur_values);

		for (size_t i=0; i<vcur_values.size(); i++)
			vcur.push_back(vcur_values[i].asUUID());
	}

	std::sort(vcur.begin(), vcur.end());
	std::sort(vnew.begin(), vnew.end());

	std::vector<LLUUID>::iterator it;
	size_t maxsize = llmax(vcur.size(), vnew.size());
	vadded.resize(maxsize);
	vremoved.resize(maxsize);

	// what to remove
	it = set_difference(vcur.begin(), vcur.end(), vnew.begin(), vnew.end(), vremoved.begin());
	vremoved.erase(it, vremoved.end());

	// what to add
	it = set_difference(vnew.begin(), vnew.end(), vcur.begin(), vcur.end(), vadded.begin());
	vadded.erase(it, vadded.end());
}

void LLCommonUtils::computeDifference(
	const uuid_vec_t& vnew,
	const uuid_vec_t& vcur,
	uuid_vec_t& vadded,
	uuid_vec_t& vremoved)
{
	uuid_vec_t vnew_copy(vnew);
	uuid_vec_t vcur_copy(vcur);

	std::sort(vnew_copy.begin(), vnew_copy.end());
	std::sort(vcur_copy.begin(), vcur_copy.end());

	size_t maxsize = llmax(vnew_copy.size(), vcur_copy.size());
	vadded.resize(maxsize);
	vremoved.resize(maxsize);

	uuid_vec_t::iterator it;
	// what was removed
	it = set_difference(vcur_copy.begin(), vcur_copy.end(), vnew_copy.begin(), vnew_copy.end(), vremoved.begin());
	vremoved.erase(it, vremoved.end());

	// what was added
	it = set_difference(vnew_copy.begin(), vnew_copy.end(), vcur_copy.begin(), vcur_copy.end(), vadded.begin());
	vadded.erase(it, vadded.end());
}

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

void BaseGrid::SetSelectedSet(const Selection &new_selection) {
	Selection inserted, removed;
	set_difference(new_selection, selection, inserted);
	set_difference(selection, new_selection, removed);
	selection = new_selection;
	AnnounceSelectedSetChanged(inserted, removed);
	Refresh(false);
}

bool Diff::compare(string exclude) {
    RegExp exc;
    if (!exclude.empty()) {
        exc.setExpr(exclude);
    }
    bool same = true;
    FileWalker fw;
    vector<string> files1;
    fw.walk(file1, [&] (const File& f) {
        if (f.getType() == File::FileType::DIRECTORY) {
            return;
        }
        if (!exclude.empty() && exc.matches(f.getName())) {
            return;
        }
        string relPart = f.getPath().substr(file1.getPath().size());
        files1.push_back(relPart);
    });
    sort(files1.begin(),files1.end());
    vector<string> files2;
    fw.walk(file2, [&] (const File& f) {
        if (f.getType() == File::FileType::DIRECTORY) {
            return;
        }
        if (!exclude.empty() && exc.matches(f.getName())) {
            return;
        }
        string relPart = f.getPath().substr(file2.getPath().size());
        files2.push_back(relPart);
    });
    sort(files2.begin(),files2.end());
    vector<string> intersected;
    set_intersection(files1.begin(),files1.end(),files2.begin(), files2.end(),back_inserter(intersected));
    for (auto f:intersected) {
        string f1 = file1.getPath() + f;
        string f2 = file2.getPath() + f;
        string cmd = "cmp -s '" + f1 + "' '" + f2 + "'";
        int exitCode = system(cmd.c_str());
        if (exitCode != 0) {
            cout << "meld " << f1 << " " << f2 << endl;
            same =false;
        }
    }
    vector<string> only1;
    set_difference(files1.begin(),files1.end(),files2.begin(), files2.end(),back_inserter(only1));
    for (auto f:only1) {
        cout << "only in " << file1.getPath() << ": " << f << endl;
        same = false;
    }
    vector<string> only2;
    set_difference(files2.begin(),files2.end(),files1.begin(), files1.end(),back_inserter(only2));
    for (auto f:only2) {
        cout << "only in " << file2.getPath() << ": " << f << endl;
        same = false;
    }

    return same;
}

static void
flow_uninit_scan_statements (flownode_t *node, set_t *defs, set_t *uninit)
{
	set_t      *stuse;
	set_t      *stdef;
	statement_t *st;
	set_iter_t *var_i;
	flowvar_t  *var;
	operand_t  *op;

	// defs holds only reaching definitions. make it hold only reaching
	// uninitialized definitions
	set_intersection (defs, uninit);
	stuse = set_new ();
	stdef = set_new ();
	for (st = node->sblock->statements; st; st = st->next) {
		flow_analyze_statement (st, stuse, stdef, 0, 0);
		for (var_i = set_first (stuse); var_i; var_i = set_next (var_i)) {
			var = node->graph->func->vars[var_i->element];
			if (set_is_intersecting (defs, var->define)) {
				def_t      *def = flowvar_get_def (var);
				if (def) {
					if (options.warnings.uninited_variable) {
						warning (st->expr, "%s may be used uninitialized",
								 def->name);
					}
				} else {
					bug (st->expr, "st %d, uninitialized temp %s",
						 st->number, operand_string (var->op));
				}
			}
			// avoid repeat warnings in this node
			set_difference (defs, var->define);
		}
		for (var_i = set_first (stdef); var_i; var_i = set_next (var_i)) {
			var = node->graph->func->vars[var_i->element];
			// kill any reaching uninitialized definitions for this variable
			set_difference (defs, var->define);
			if (var->op->op_type == op_temp) {
				op = var->op;
				if (op->o.tempop.alias) {
					var = op->o.tempop.alias->o.tempop.flowvar;
					if (var)
						set_difference (defs, var->define);
				}
				for (op = op->o.tempop.alias_ops; op; op = op->next) {
					var = op->o.tempop.flowvar;
					if (var)
						set_difference (defs, var->define);
				}
			}
		}
	}
	set_delete (stuse);
	set_delete (stdef);
}

int NotificationMessageLayer::UpdateMessages()
{
	std::set<int> visibleKeys;
	for (auto message : _userMessages)
	{
		int key = message.first;

		visibleKeys.insert(key);

		if (message.second->IsOutdated())
		{
			World::Instance().GetMessageManager().RemoveMessage(key);
		}
	}

	const std::map<int, UserMessage::Ptr> messages = World::Instance().GetMessageManager().GetMessages();
	std::set<int> realKeys;
	for (auto message : messages)
	{
		realKeys.insert(message.first);
	}

	int changed = 0;
	std::set<int> newKeys;
	set_difference(realKeys.begin(), realKeys.end(),
				   visibleKeys.begin(), visibleKeys.end(),
				   inserter(newKeys, newKeys.begin()));

	if (newKeys.size() > 0)
	{
		for (int key : newKeys)
		{
			AddNewMessage(key, messages);
			changed++;
		}
	}

	std::set<int> keysToRemove;
	set_difference(visibleKeys.begin(), visibleKeys.end(),
				   realKeys.begin(), realKeys.end(),
				   inserter(keysToRemove, keysToRemove.begin()));

	if (keysToRemove.size() > 0)
	{
		for (int key : keysToRemove)
		{
			removeChild(_userMessages.at(key));
			_userMessages.erase(key);

			changed++;
		}
	}

	return changed;
}

double H_x_given_y(deque<deque<int>> &en, deque<deque<int>> &ten, int dim) {
    // you know y and you want to find x according to a certain index labelling.
    // so, for each x you look for the best y.
    double H_x_y = 0;
    double H2 = 0;
    for (int j = 0; j < en.size(); j++) {
        deque<double> p;
        double I2 = double(en[j].size());
        double O2 = (dim - I2);
        p.push_back(I2 / dim);
        p.push_back(O2 / dim);
        double H2_ = H(p);
        p.clear();
        H2 += H2_;
        double diff = H2_;
        for (int i = 0; i < ten.size(); i++) {
            double I1 = double(ten[i].size());
            double O1 = (dim - I1);
            p.push_back(I1 / dim);
            p.push_back(O1 / dim);
            double H1_ = H(p);
            p.clear();
            deque<int> s(dim);
            double I1_I2 = set_intersection(ten[i].begin(), ten[i].end(), en[j].begin(), en[j].end(), s.begin()) -
                           s.begin();    // common
            double I1_02 =
                    set_difference(ten[i].begin(), ten[i].end(), en[j].begin(), en[j].end(), s.begin()) - s.begin();
            double O1_I2 =
                    set_difference(en[j].begin(), en[j].end(), ten[i].begin(), ten[i].end(), s.begin()) - s.begin();
            double O1_02 = dim - I1_I2 - I1_02 - O1_I2;
            p.push_back(I1_I2 / dim);
            p.push_back(O1_02 / dim);
            double H12_positive = H(p);
            p.clear();
            p.push_back(I1_02 / dim);
            p.push_back(O1_I2 / dim);
            double H12_negative = H(p);
            double H12_ = H12_negative + H12_positive;
            p.clear();
            if (H12_negative > H12_positive) {
                H12_ = H1_ + H2_;
            }
            if ((H12_ - H1_) < diff) {
                diff = (H12_ - H1_);
            }
        }
        if (H2_ == 0)
            H_x_y += 1;
        else
            H_x_y += (diff / H2_);
    }
    return (H_x_y / (en.size()));
}

set<int> neighbour3D::GetP2P_Neigh( int p_index, int n)
{

        set <int> previous; previous.insert(p_index);
        set <int> new_ring = P2P[p_index];

        if ( n == 0) return previous;
        if ( n == 1) return new_ring;

        set < int > myset;

        for(int i = 1; i<n; i++)
        {
            // compute the 1 neighbourhood of the previously computed ring

            myset.clear();

            for ( set <int> :: iterator it(new_ring.begin()); it != new_ring.end(); it++)
            {
                for (set<int> :: iterator it2(P2P[*it].begin()); it2 != P2P[*it].end(); it2++)
                {
                myset.insert(*it2);
                }
            }

            set <int> dum; //seems uneasy to remove elements while updating the set at the same time ==> dum set for performing the boolean difference

            //extract previous from my set
            set_difference( myset.begin(), myset.end(),
                            previous.begin(), previous.end(),
                            insert_iterator< set<int> >(dum,dum.begin())
                            );
            myset = dum; // copy dum result into myset... I whish I could have avoided this

            //previous = myset INTERSECTED with new ring
            previous.clear();
            set_intersection( myset.begin(), myset.end(),
                            new_ring.begin(), new_ring.end(),
                            insert_iterator< set<int> >(previous,previous.begin())
                    );

            //new_ring = myset MINUS previous
            new_ring.clear();
            set_difference( myset.begin(), myset.end(),
                            previous.begin(), previous.end(),
                            insert_iterator< set<int> >(new_ring,new_ring.begin())
                            );

        }

        return new_ring;
}

template <typename PointT> void
pcl::ExtractIndices<PointT>::applyFilterIndices (std::vector<int> &indices)
{
  if (indices_->size () > input_->points.size ())
  {
    PCL_ERROR ("[pcl::%s::applyFilter] The indices size exceeds the size of the input.\n", getClassName ().c_str ());
    indices.clear ();
    removed_indices_->clear ();
    return;
  }

  if (!negative_)  // Normal functionality
  {
    indices = *indices_;

    if (extract_removed_indices_)
    {
      // Set up the full indices set
      std::vector<int> full_indices (input_->points.size ());
      for (int fii = 0; fii < static_cast<int> (full_indices.size ()); ++fii)  // fii = full indices iterator
        full_indices[fii] = fii;

      // Set up the sorted input indices
      std::vector<int> sorted_input_indices = *indices_;
      std::sort (sorted_input_indices.begin (), sorted_input_indices.end ());

      // Store the difference in removed_indices
      removed_indices_->clear ();
      set_difference (full_indices.begin (), full_indices.end (), sorted_input_indices.begin (), sorted_input_indices.end (), inserter (*removed_indices_, removed_indices_->begin ()));
    }
  }
  else  // Inverted functionality
  {
    // Set up the full indices set
    std::vector<int> full_indices (input_->points.size ());
    for (int fii = 0; fii < static_cast<int> (full_indices.size ()); ++fii)  // fii = full indices iterator
      full_indices[fii] = fii;

    // Set up the sorted input indices
    std::vector<int> sorted_input_indices = *indices_;
    std::sort (sorted_input_indices.begin (), sorted_input_indices.end ());

    // Store the difference in indices
    indices.clear ();
    set_difference (full_indices.begin (), full_indices.end (), sorted_input_indices.begin (), sorted_input_indices.end (), inserter (indices, indices.begin ()));

    if (extract_removed_indices_)
      removed_indices_ = indices_;
  }
}

 std::pair<std::set<T>,std::set<T> > 
 set_partition(const std::set<T>& s, const std::set<T>& partition) {
   std::set<T> a, b;
   a = set_intersect(s, partition);
   b = set_difference(s, partition);
   return std::make_pair(a, b);
 }

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

bool xRedisClient::sdiff(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_difference( 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;
}

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

// delete multiple vertices
bool t_dir_graph::delete_vertices(const set<t_vertex>& V){
	// 1. update the P3-set & the diamond-set
	set<t_3path> bad_p3, new_bad_p3;
	for(set<t_vertex>::const_iterator i = V.begin(); i != V.end(); i++){
		new_bad_p3 = get_p3_involving(*i);
		bad_p3.insert(new_bad_p3.begin(), new_bad_p3.end());
	}
	for(set<t_3path>::const_iterator i = bad_p3.begin(); i != bad_p3.end(); i++)
		decrease_diamond(t_diamond(i->first.first, i->second.second));

	set<t_3path> temp_p3;
	set_difference(p3_set.begin(), p3_set.end(), bad_p3.begin(), bad_p3.end(), inserter(temp_p3,temp_p3.begin()));
	p3_set = temp_p3;
	// 2. delete all arcs that involve V
	for(t_adjtable::iterator i = successors.begin(); i != successors.end(); i++)
		i->second = set_substract(i->second, V);
	for(t_adjtable::iterator i = predecessors.begin(); i != predecessors.end(); i++)
		i->second = set_substract(i->second, V);
	// 3. delete V itself
	bool result = true;
	for(set<t_vertex>::iterator i = V.begin(); i != V.end(); i++){
		result &= (successors.erase(*i)>0);
		result &= (predecessors.erase(*i)>0);
	}
	return result;
}

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

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

bool TimeTableSet::UpdateByIndex(TimeTableSet & ttSet, size_t const index)
{
  auto const & updated = ttSet.m_table[index];

  if (index >= ttSet.Size() || !updated.IsValid())
    return false;

  for (auto i = 0; i < ttSet.Size(); ++i)
  {
    if (i == index)
      continue;

    auto && tt = ttSet.m_table[i];
    // Remove all days of updated timetable from all other timetables.
    TOpeningDays days;
    set_difference(std::begin(tt.GetOpeningDays()), std::end(tt.GetOpeningDays()),
                   std::begin(updated.GetOpeningDays()), std::end(updated.GetOpeningDays()),
                   inserter(days, std::end(days)));

    if (!tt.SetOpeningDays(days))
      return false;
  }

  return true;
}

id_set PhenomatrixBase::copy_construct_row_ids(const PhenomatrixBase& rhs, const id_set& remove_rows) {
    id_set lhs_row_ids;
    // Remove rows from row_ids list
    set_difference(rhs.row_ids_.begin(), rhs.row_ids_.end(),
                   remove_rows.begin(), remove_rows.end(),
                   std::insert_iterator<id_set>(lhs_row_ids, lhs_row_ids.begin()));
    return lhs_row_ids;
}