Re: [boost] Re: new component, extent_set<>

From: Nathan Myers (ncm-yahoospam_at_[hidden])
Date: 2001-12-28 16:25:17

On Thu, 27 Dec 2001 13:53:27 -0500, "Beman Dawes" <bdawes_at_[hidden]> wrote:

> At 03:55 AM 12/27/2001, Nathan wrote:
> 
>  >On Wed, 26 Dec 2001 20:05:14 -0500, "Beman Dawes" <bdawes_at_[hidden]> wrote:
>  >> Did you consider asserting or throwing on b < e precondition 
>  >> violations?
>  >
>  >As a precondition, it is a logical error to insert into the set elements
>  >that are already present.  The type std::set<> doesn't throw if you try
>  >to insert the same element again.
> 
> But std::set<> doesn't have a precondition that the element can't already 
> be present, and has very well defined (ignore the insert) behavior if it is 
> already present.
> 
> I understand the reluctance to throw, but what about asserting on any of 
> the preconditions where the complexity of testing the precondition is 
> minimal?  Sure it is just a QOI issue, but it does help users.

In practice the way you use these things is to insert a big range, and then
carve off pieces, returning them when you're finished.  You know that a range
isn't included because you know what you have and where you got it.

Testing for b > e, or b >= e, is easy and cheap, but is a very unlikely
error.  Checking has_all or !has_any is more likely to catch errors, but
is quite expensive.

>  >  Passing a range to std::set<> with the
>  >iterators reversed does not result in an exception.
> 
> No, but an implementation is free to assert on that, if detectable.

Do any?

>  >I cannot imagine how client code could respond meaningfully to such an
>  >exception.
> 
> For precondition violations, asserts are often better that exceptions.  But 
> there has been past discussion where people pointed out cases where assert 
> was desirable in debug builds, but they would like an exception in release 
> mode.

Mm, they won't get that from the regular STL components.
What exception would you suggest?  I am inclined to std::logic_error.
I have included some code to do the cheaper but less useful checks.

>  >> What is the rationale for the insert precondition !has_any(b, e),
>  >> and the erase precondition has_all(b, e)?  (I'm just curious and
>  >> not suggesting that looser preconditions would be better.)
>  >
>  >The preconditions radically simplify the logic of the insert and erase
>  >members.  They correspond, logically, to the requirement the same memory
>  >not be passed to free() twice.  More general functions that don't impose
>  >such preconditions must contain a loop.  They would be easy to add (along 
> 
>  >with general set union, intersection, and complement-intersection), and I
>  >expect that will happen eventually, but they would not be a substitute 
>  >for the more basic operations.
> 
> Understood.  You might want to add the above to Rationale or FAQ docs.

I will.

>  >> The portion of the license which reads "Permission is granted for
>  >> any use free of charge provided..." can be read two ways:
>  >> ...
>  >
>  >I have edited the license to eliminate any ambiguity:
>  >
>  >// Copyright 2001 by Nathan C. Myers <ncm-nospam_at_[hidden]>.
>  >// Permission is granted free of charge for any use provided that (1)
>  >// this copyright notice is retained unchanged in its entirety, and
>  >// (2) the author is indemnified, held harmless, and released from all
>  >// responsibility for any  consequences of such use.
>  >
>  >As I understand it this is the minimal license that allows unrestricted
>  >use without exposing me to liability.
> 
> Thanks for clarifying the wording.
> 
> When first looking at extent_set yesterday, I thought I'd once had a need 
> for something similar, but couldn't remember the details.  It has now come 
> back to me, but the half-open ranges would be a problem.
> 
> The problem was a QA audit program for a map database to determine if there 
> was overlap in house number ranges for various records representing 
> segments of a street.
> 
> Thus Bound would be a class named HouseNumber.  About 99% of the streets in 
> the US have unsigned numeric house numbers.  But the other 1% have 
> different numbering schemes, with very approximately 200 in common 
> use.  Thus HouseNumber isn't an integer, but rather a complex class capable 
> of dealing with the numbering schemes.
> 
> HouseNumber is "assignable, copyable, and equality-comparable, and 
> comparable using the Compare operation" but it doesn't have any increment() 
> or successor() operations because for some addressing schemes there is no 
> valid result possible from such an operation.  That means there isn't any 
> way to form a half-open range, at least not without changing HouseNumber.
> 
> A specific example would be single-character alphabetic house numbers 
> running from A to Z.  What is the half-open range?  Z doesn't have a 
> successor.
> 
> One solution would be to modify the HouseNumber class to add a successor, 
> with a special off-the-end value.  That's uncomfortable; why should a type 
> which meets the requirements still need modification?  There are also some 
> schemes with discontinuous (although orderable) schemes; they would be an 
> additional headache.
> 
> I guess the question this raises is whether or not a half-open range is the 
> best way to specify ranges for arbitrary types?  It's really natural for 
> iterators, but seems unnatural at least for the HouseNumber application.
> 
> Are there killer arguments in favor of half-open ranges for extent_set?

It bothered me too that the submitted version cannot represent membership of
MAXINT.  I have an implementation of extent_set using closed ranges, but it
requires both successor and predecessor functions (n + 1 and n - 1), which
had seemed to me to limit extent_set<>'s application more than the half-open
ranges.  (Either would work fine for my purposes.)  Of course, instead of
literally "n + 1", it says "this->succ(n)", invoking an instantiation of 
a template argument.  That makes the interface a little more complicated.

I have posted the closed-range implementation in the files section, under 
the names "extent_set-0.2.tgz" and "extent_set-0_2.zip". See
  http://groups.yahoo.com/group/boost/files/extent_set/

It includes tests to ensure that the predecessor and successor functions
never try to generate a value that exceeds the range of the argument type.

Please let me know if you like it better.

Nathan Myers
ncm at cantrip dot org