Skip to main content

Make Integer and Long implement List

16 replies [Last post]
lucretius2
Offline
Joined: 2004-12-19

I've submitted this idea as an RFE (which hasn't appeared in the Java bug database yet), but some people here may have their comments. FWIW this would also provide an Collection-compatible replacement for BitSet (with all its problems), for up to 64 bits at least.

Here's the RFE:
Make Integer and Long implement List for improved bitfield support

Java 5 added various static methods to Integer and Long to help when they are being treated as arrays of bits, e.g. numberOfLeadingZeros(), the constant SIZE, etc.

This support can be extended and rationalized by simply making Integer and Long implement List. Thus Integer and Long objects are treated as immutable, fixed-sized arrays of 32 or 64 Boolean objects. See Justification for some implementation code. The benefits are:

* get(int index) to read the value of a bit. This is easier than using >> and bit masks; for instance, it checks the index's range, and would also be quite fast.

* iterator() to iterate through all the bits in turn. Again this is easier than using >> and bit masks, and allows use of the foreach construct.

* subList() allows you to create bit fields smaller than an Integer or Long, e.g. new Integer(n).subList (0,10) is a List of the lowest 10 bits of n.

* indexOf() and lastIndexOf() are more natural than numberOfTrailingZeros() and numberOfLeadingZeros(), especially lastIndexOf() since it returns the actual index of the bit. They also work for both 0 and 1 bits.

* This could also provide a replacement for the long-forgotten BitSet, which is not a Collection, for up to 64 bits. Use subList for sizes other than 32 or 64. .

Methods that would mutate the value, e.g. add(Boolean), throw UnsupportedOperationException. If desired, special methods could be added to set/clear/flip bits, returning new Integer and Long values; this would be important if this is to mostly replace BitSet.

JUSTIFICATION :
This would properly integrate Integer/Long, and thus also int/long, with both boolean and Collections. Any number of bits up to 64 could be efficiently treated as a Collection but stored as a single Integer or Long value.

(A more radical implementation of this idea is the elegant Java variant Kava: http://www.research.ibm.com/people/d/dfb/papers.html .)

It would allow fiddly code like this:

int bitfield = 99;
for (int i = 0; i < Integer.SIZE; i++) {
int bit = (bitfield >>> i) & 1;
System.out.println(bit);
}

...to be replaced by this:

int bitfield = 99;
for (Boolean bit : bitfield) {
System.out.println(bit.booleanValue() ? 1 : 0);
}

Using subList(), bitfields of any size between 0 and 64 bits can be used in the same way.

The methods to be added to Integer would be something like this (untested and some methods need filling in):

public final class Integer extends Number implements Comparable, List, RandomAccess {

/** index is the number of the bit (0 to 31) to return.
* @return Boolean.TRUE if the specified bit is 1, Boolean.FALSE if it is 0.
* @throw IndexOutOfBoundsException if index is < 0 or > 31.
*/
public Boolean get(int index) {
if (index < 0 || index >= SIZE) {
throw new IndexOutOfBoundsException();
}
return Boolean.valueOf((value & (1< c) {
return false;
}

/** @todo Write this. */
public Boolean[] toArray() {
return null;
}

/** @todo Write this. */
public Boolean[] toArray(Boolean[] a) {
return null;
}

/** @todo Write this. */
public Iterator iterator() {
return null;
}

/** @todo Write this. */
public ListIterator listIterator() {
return null;
}

/** @todo Write this. */
public ListIterator listIterator(int index) {
return null;
}

/** This is useful for creating bit fields smaller than 32 bits, e.g. new Integer(n).subList(0,10) is a bitfield of 10 bits.
@todo Write this. */
public List subList(int fromIndex, int toIndex) {
return null;
}

public boolean add(Boolean o) {
throw new UnsupportedOperationException();
}

public boolean remove(Object o) {
throw new UnsupportedOperationException();
}

public boolean addAll(Collection<? extends Boolean> c) {
throw new UnsupportedOperationException();
}

public boolean removeAll(Collection<?> c) {
throw new UnsupportedOperationException();
}

public boolean retainAll(Collection<?> c) {
throw new UnsupportedOperationException();
}

public void clear() {
throw new UnsupportedOperationException();
}

public boolean addAll(int index, Collection<? extends Boolean> c) {
throw new UnsupportedOperationException();
}

public Boolean set(int index, Boolean element) {
throw new UnsupportedOperationException();
}

public void add(int index, Boolean element) {
throw new UnsupportedOperationException();
}

public Boolean remove(int index) {
throw new UnsupportedOperationException();
}

/// ...the remaining methods of Integer are unchanged }
}

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
viper_wolf
Offline
Joined: 2004-06-03

> you still don't understand?

A bit is either 0 (false) or 1 (true).
A boolean is either false (0) or true 1.

They possably couldn't represent each other at all. Even the java.util.BitSet class doesnt use a boolean for its [b]public boolean get( int bitIndex )[/b] and [b]public void set( int bitIndex, boolean value )[/b] methods.

fabiocastilhomartins
Offline
Joined: 2005-03-21

A boolean is either true or false only. We're talking Java here, not C. In Java there is no relation between numbers and booleans.

tackline
Offline
Joined: 2003-06-19

> Why create a new object, when an Integer can just
> [b]be[/b] a List? If nothing else, the
> foreach construct becomes very direct and powerful:

You will typically be creting a new object to convert an int into an Integer. A wrapping method would just swap one class for another. The "enhanced" for loop will also create another object.

> What would it mean to 'iterate through the set bits'?
> the iterator would always return Boolean.TRUE?

No, Integer would implement List. A class cannot implement both List and List.

> Integer would be simply a List, a list of 32
> Boolean values. [...]

Thinking about BigInteger and BitSet, isn't it peculiar that iterating through an Integer doesn't stop at the most significant set bit?

lucretius2
Offline
Joined: 2004-12-19

> You will typically be creting a new object to convert
> an int into an Integer. A wrapping method would just
> swap one class for another. The "enhanced" for loop
> will also create another object.

OK, but sometimes you will already have an Integer object, not an int, so no need to create another object. Furthermore, why add another class (to access bits) when Integer can already do the job?

> Thinking about BigInteger and BitSet, isn't it
> peculiar that iterating through an Integer doesn't
> stop at the most significant set bit?

BitSet isn't a Collection, nor (I think) could it be, since it has behaviour at odds with the design of Collections. It is little-used and might as well be deprecated.

Why on earth should an iterator stop at the highest set bit? For BigInteger, this is a way of indicating the number of bits 'used', but then BigInteger isn't a Collection. Since Integer would be a Collection, you'd find this out by calling size(), and you'd get back the answer 32. All 32 bits in an Integer exist, even if some of them are 0.

viper_wolf
Offline
Joined: 2004-06-03

This looks nicer. Adding a method seems to work better then redefining the implementation.

[b]public java.util.List listBits( )[/b]

or preferrably

[b]public java.util.BitSet toBitSet( )[/b]

mgrev
Offline
Joined: 2003-08-12

> in case you weren't aware yet a List is not an array and a Boolean is not a bit.

Hehe, with that kind of logic:

X coordinate can't be expressed with an int, because int is not an x coordinate...

jwenting
Offline
Joined: 2003-12-02

you still don't understand?
A Boolean is a datatype, so is a bit.
And they're quite different...

An int is a datatype, an x coordinate is not a datatype...

mgrev
Offline
Joined: 2003-08-12

Yeah, sure...

dbr
Offline
Joined: 2005-03-03

You can do something similar in the Nice extension of Java. Nice supports (among many other things) get and set syntax on native ints and longs to access individual bits:
[b]
int bitfield = 99;
for (int n = 0; n < 32; n++)
System.out.println(bitfield[n] ? 1 : 0);

// set the highest bit
bitfield[31] = true;
System.out.println(bitfield);
[/b]
This is implemented in bytecode with bitshifts, and so should be as efficient as the manual implementation, just much more readable.

Nice is presented at http://nice.sf.net

lucretius2
Offline
Joined: 2004-12-19

If you want to vote/comment on the RFE for this, here it is:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6210755

tackline
Offline
Joined: 2003-06-19

Why not just write a method to convert an int/long to List?

I'd expect Long.iterator to iterate through the set bits. So we have a problem of interpretation.

lucretius2
Offline
Joined: 2004-12-19

> Why not just write a method to convert an int/long to
> List?

Why create a new object, when an Integer can just [b]be[/b] a List? If nothing else, the foreach construct becomes very direct and powerful:

[b]int myInt = 0xCAFEBABE;
for (Boolean bit : myInt) {
// process bit
}
[/b]
> I'd expect Long.iterator to iterate through the set
> bits. So we have a problem of interpretation.

What would it mean to 'iterate through the set bits'? the iterator would always return Boolean.TRUE?

Integer would be simply a List, a list of 32 Boolean values. Iterating through it returns the 32 values in turn, starting with index 0 (i.e. bit 0). I don't think interpretation comes into it: this is specified in the contract for List.iterator().

dgreenbean
Offline
Joined: 2003-12-08

> Why create a new object, when an Integer can just
> [b]be[/b] a List?

This may seem like a good idea at first, but it is unintuitive. An Integer (or int) is meant to represent a number. The fact that it is represented on the back end by 32 binary bits is just an implementation detail. If I wanted to, I could implement the Integer class using an array of base 10 numbers, and it should work identically to the java.lang.Integer class.

The shift operators may seem to counter this argument, but in all reality, the shift operators are just specialized functions meant to operate on numbers in order to retrieve information about how the numbers are stored. The ability to manipulate bits of an int is an added bonus of these operators, but should not have a bearing on the design of Integers.

> If nothing else, the
> foreach construct becomes very direct and powerful:
>
> [b]int myInt = 0xCAFEBABE;
> for (Boolean bit : myInt) {
> // process bit
> }
> [/b]

I agree this is a nice syntax, but there is little benefit to this over:
[b]List myInt = generateBools(0xCAFEBABE);
for (Boolean bit : myInt) {
// process bit
}
[/b]
where generateBools is statically imported.

> Integer would be simply a List, a list of 32
> Boolean values. Iterating through it returns the 32
> values in turn, starting with index 0 (i.e. bit 0). I
> don't think interpretation comes into it: this is
> specified in the contract for List.iterator().

Again, it seems like it can make sense at first, but then you run into a number of problems both abstractly and semantically:
-An Integer may be a list of 32 Boolean values, but that is not its primary purpose. It is, rather, a welcomed side-effect of the implementation.
-If an Integer [i]is[/i] a List, what happens when you call [code]i.set(2,true)[/code]? Does that change the Integer? That would violate the immutability of Integers. You would need to implement a special type of list to disallow this type of mutation. One way around this would be to simply implement the Iterable interface, but then there's the remove() method of Iterator.

At most the closest compromise would be to add a member method to Integer that returns an array of 32 booleans (primitive type). This would simply be a way of easily extracting the underlying implementation data, without exposing the Integer to mutation or calling an Integer something that it isn't. This is similar to having a toString() method in Integer.

The best way to get a List from an Integer would be a library method. Such a method implies that you are transforming the Integer into another data type, which is exactly what you are doing.

lucretius2
Offline
Joined: 2004-12-19

> Again, it seems like it can make sense at first, but
> then you run into a number of problems both
> abstractly and semantically:
> -An Integer may be a list of 32 Boolean values, but
> that is not its primary purpose. It is, rather, a
> welcomed side-effect of the implementation.
> -If an Integer [i]is[/i] a List, what
> happens when you call [code]i.set(2,true)[/code]?
> Does that change the Integer? That would violate
> e the immutability of Integers. You would need to
> implement a special type of list to disallow this
> type of mutation. One way around this would be to
> simply implement the Iterable interface, but then
> there's the remove() method of Iterator.

If you look at my source code above, you'll see that set() throws UnsupportedOperationException. Iterator.remove() and any other mutators would do the same. All these methods are marked as 'optional operations' in the List contract, so it's perfectly valid to have immutable Lists.

Yes, if you really want quasi-mutability, you could add methods like set() to Integer which return a new Integer. At least this would allow Integer to largely replace the long-forgotten BitSet (which is not a Collection, and I think can't be, due to its various design anomalies).

> At most the closest compromise would be to add a
> member method to Integer that returns an array of 32
> booleans (primitive type). This would simply be a
> way of easily extracting the underlying
> implementation data, without exposing the Integer to
> mutation or calling an Integer something that it
> isn't. This is similar to having a toString() method
> in Integer.
>
> The best way to get a List from an Integer
> would be a library method. Such a method implies
> that you are transforming the Integer into another
> data type, which is exactly what you are doing.

One problem with these approaches is that they're slower. The idea behind my proposal was not to have to wrap or convert an Integer; this means that methods like get() are almost as fast as doing bit manipulation by hand.

jwenting
Offline
Joined: 2003-12-02

in case you weren't aware yet a List is not an array and a Boolean is not a bit.

lucretius2
Offline
Joined: 2004-12-19

A fixed-size list with constant access time, which is what this List is, is an array.

A Boolean isn't a bit, but it's the best object we have which can represent a bit. If you prefer, we could use an Integer taking values 0 and 1, i.e. make Integer/Long implement List. This is a somewhat trivial objection.