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

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-12-27 13:53:27

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.

 >  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.

 >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.

 >> 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.

 >> 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?

--Beman