Re: [boost] [LibrariesUnderConstruction] new LibrariesUnderConstruction wiki page

Subject: Re: [boost] [LibrariesUnderConstruction] new LibrariesUnderConstruction wiki page
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2008-12-09 12:47:52

2008/12/7 vicente.botet <vicente.botet_at_[hidden]>:
> Hi,
>
> I have created a new wiki page containing some of the libraries under construction for Boost.
> You can access this page from the Boost Trac wiki https://svn.boost.org/trac/boost/wiki > Projects > Libraries Under Construction or directly https://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction
>
>
> HTH,
> Vicente
>

Thank you, Vicente, for creating this list and putting
my lib Boost.ITL (Interval Template Library) on the list.

Browsing through the list I spotted *DenseSet* on the
Libraries Wish List.
"Implementation of dense set of integers using intervals"

I think that such a dense set is already contained in
itl::interval_set. Intervals themselves are dense sets
but they are incomplete for most of the fundamental
set operations.

While intersection

interval& operator *= (interval& i1, const interval& i2)

always yields a (dense) interval, set union (+=) or set
difference (-=)  do in general not yield an interval.
They result in a set of intervals, the union
of which is again a set (of elements).

The itl's interval_set implements exactly this completion
of incomplete operations on intervals.

{[1,3]} + [2,4] -> {[1,4]} //dense
{[1,3]} + [5,5] -> {[1,3],[5,5]} //not dense
{[1,3],[5,5]} + [4,4] -> {[1,5]} // dense again

itl::interval_set is *implemented* as a set of intervals
but it's semantics is the union of those intervals, which
is a set of elements.

An itl::interval_set is in a minimal representation.
So the criterion of density can always be tested by:

interval_set<int> iset;
iset += interval<int>::closed(1,3);
... // more operations
bool is_dense = iset.size()<=1;
   // a nonempty  interval_set is dense, iff it's size is 1.

I wonder whether you have more properties of DenseSet in mind
that might go beyond the functionality of itl's interval_sets.
May be those features could be integrated into the itl.

Cheers
Joachim