
Boost : 
Subject: Re: [boost] [LibrariesUnderConstruction] new LibrariesUnderConstruction wiki page
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 20081209 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk