ISet and negative integers

[pveber]

ISet does not seem to support negative integers:

# ISet.(add_range (-4) 5 empty);;
Exception: Invalid_argument "ISet.add_range - -4 > 5".

However this is not stated in the module documentation, nor is it clear from the source code actually. The module starts with definition suited to unsigned ints:

let compare_uint n1 n2 =
  let sgn1 = (n1 lsr 24) - (n2 lsr 24) in
  if sgn1 = 0 then (n1 land 0xffffff) - (n2 land 0xffffff) else sgn1

let (>) n1 n2 = compare_uint n1 n2 > 0
let (>=) n1 n2 = compare_uint n1 n2 >= 0
let (<) n1 n2 = compare_uint n1 n2 < 0
let (<=) n1 n2 = compare_uint n1 n2 <= 0
let compare = compare_uint

let max n1 n2 = if n1 >= n2 then n1 else n2
let min n1 n2 = if n1 <= n2 then n1 else n2

let max_int = ~-1
let min_int = 0

This suggests that negative integers are not supported, but this is not checked in constructors:

# ISet.(add (-4) empty);;
- : Batteries.ISet.t = 

So there should be some correction here. If nobody's in charge of this module already, I'm ok to have a look at it.

[agarwal]

Which change do you propose? Allow negative integers, or fix the documentation to state that negative integers are not supported? I prefer the former; it seems there is no reason to disallow negative integers.

On Tue, Aug 16, 2011 at 9:54 AM, pveber < reply@reply.github.com>wrote:

ISet does not seem to support negative integers:

# ISet.(add_range (-4) 5 empty);;
Exception: Invalid_argument "ISet.add_range - -4 > 5".

However this is not stated in the module documentation, nor is it clear from the source code actually. The module starts with definition suited to unsigned ints:

let compare_uint n1 n2 = let sgn1 = (n1 lsr 24) - (n2 lsr 24) in if sgn1 = 0 then (n1 land 0xffffff) - (n2 land 0xffffff) else sgn1

let (>) n1 n2 = compare_uint n1 n2 > 0 let (>=) n1 n2 = compare_uint n1 n2 >= 0 let (<) n1 n2 = compare_uint n1 n2 < 0 let (<=) n1 n2 = compare_uint n1 n2 <= 0 let compare = compare_uint

let max n1 n2 = if n1 >= n2 then n1 else n2 let min n1 n2 = if n1 <= n2 then n1 else n2

let max_int = ~-1 let min_int = 0

This suggests that negative integers are not supported, but this is not checked in constructors:

# ISet.(add (-4) empty);;
- : Batteries.ISet.t = 

So there should be some correction here. If nobody's in charge of this module already, I'm ok to have a look at it.

Reply to this email directly or view it on GitHub: https://github.com/ocaml-batteries-team/batteries-included/issues/167

[pveber]

At first glance, I cannot see why the implementation would not be correct for negative integers. It would be nice to have the author's opinion on this :o)

[yoriyuki]

Assuming that Batteries team do not alter the code, ISet treat integers as unsigned integer. Therefore, -4 is treated as a large positive integer. This explains the behaviors 1)"ISet.add_range (-4) 5 empty" raises the exception, since -4 is larger then 5, and 2)"ISet.add -4 empty" successes without errors.

This design of ISet was to handle code of ISO-UCS characters, which are used to be 31-bits integer. Now, ISO-UCS and Unicode standard are synchronized and to represent Unicode character we need only 21-bits integer. Therefore, I would remove this feature from Camomile.

Since Batteries are general purpose library, I guess that you want to treat integers as singed (built-in semantics of int) and support negative integers.

[yoriyuki]

By the way, there is an improved version of Diet http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8247388

Does anyone try it?

[pveber]

Thanks a lot for your speedy answer ! Your explanations seem to indicate than one would just need to remove the definitions at the top of the module (on comparisons) to handle negative numbers properly. Is that correct ?

BTW, thanks for the reference, I think Ashish will be interested too.

[yoriyuki]

Yes, I think your are right (concerning removing top re-definitions of comparison).

[agarwal]

Thanks for the reference to the new paper! I had not seen this yet.

[pveber]

Actually, thelema had already commented out the analogous stuff in IMap, so this is another reason to be confident on this change. I've done the modification on my fork. I plan to add tests for ISet and then submit a patch.

[thelema]

Thanks for creating this patch. Apparently I forgot to remove the unsigned code for iset as I did for imap. Commit merged.