Velocity Reviews > C++ > Intersection of Multiple Sets

# Intersection of Multiple Sets

Ryan R. Rosario
Guest
Posts: n/a

 09-06-2003
Hello -

I am working on a scheduling application that has many "rules" for
scheduling people. I throw each person into the set that corresponds
to 2 teams. Then I split this large group (of everybody) into 3 groups
(indicating which day they will work a particular shift).

So I have two disjoint sets: teamA and teamB.
and I have three sets: day1, day2, day3 (not divided by team).
and so on...

This continues for several more steps as I have other rules I must
apply. What I would like to do is find the intersection of these
multiple sets. For example, I want to know who is in Team A *and* is
working on day2 and is working in location1,
TeamA & (day1 & locationA).

I know that there is the set_intersection function that I suppose I
could nest (?), but I could see this making a mess of iterators that
will crash or do something bizarre.

Any suggestions how I can do this?

TIA,
Ryan

Rob Williscroft
Guest
Posts: n/a

 09-06-2003
Ryan R. Rosario wrote in news:(E-Mail Removed):

> Hello -
>
> I am working on a scheduling application that has many "rules" for
> scheduling people. I throw each person into the set that corresponds
> to 2 teams. Then I split this large group (of everybody) into 3 groups
> (indicating which day they will work a particular shift).
>
> So I have two disjoint sets: teamA and teamB.
> and I have three sets: day1, day2, day3 (not divided by team).
> and so on...
>
> This continues for several more steps as I have other rules I must
> apply. What I would like to do is find the intersection of these
> multiple sets. For example, I want to know who is in Team A *and* is
> working on day2 and is working in location1,
> TeamA & (day1 & locationA).

I'll assume all 3 of the above are std::set< Person >

std::vector< Person > eg( )
{
std::vector< Person > temp, output;

std::set_intersection(
TeamA.begin(), TeamA.end(),
day1.begin(), day1.end(),
std::back_inserter( temp )
);

std::set_intersection(
temp.begin(), temp.end(),
locationA.begin(), locationA.end(),
std::back_inserter( output )
);

return output;
}

You can make this more generic if it helps:

template < typename I1, typename I2, typename I3, typename Out >
Out set_intersect3(
I1 f1, I1 l1, I2 f2, I2 l2, I3 f3, I3 l3, Out out
)
{
typedef typename std::iterator_traits< I1 >::value_type vt;
std::vector< vt > temp;

std::set_intersection(
f1, l1, f2, l2,
std::back_inserter( temp )
);

return std::set_intersection(
temp.begin(), temp.end(), f3, l3, out
);
}

>
> I know that there is the set_intersection function that I suppose I
> could nest (?), but I could see this making a mess of iterators that
> will crash or do something bizarre.
>

Don't know how you would "nest" std::set_intersect, But ...

template <typename C1, typename C2>
std::vector< typename C1::value_type >
nest_intersect( C1 const &c1, C2 const &c2 )
{
std::vector< typename C1::value_type > nrv;
std::set_intersect(
c1.begin(), c1.end(), c2.begin(), c2.end(),
std::back)inserter( nrv )
);
return nrv;
}

Now you can do:

std::vector< Person > r =
nest_intersect( TeamA, nest_intersect( day1, locationA ) )
;

> Any suggestions how I can do this?

Use a database, its what they're designed for .

Rob.
--
http://www.victim-prime.dsl.pipex.com/