Can a dynamic 2D array implement the Java.Collection.size() method?

Question

Okay, so I'm making a dynamic 2D array in Java that implements the java.util.Collection interface. I made my array implement it because I wanted it to have the same functionality as a normal Collection. However, I cannot implement the size() method because in the interface it returns an integer and a 2D matrix could potentially overflow an integer type.

Here's a snippet of my class I'm trying to make:

public abstract class AbstractMatrix<E> implements Collection<E>{
     @Override
     public long size() {
         return columns * rows;
     }
}

Now, this won't work because "The return type is incompatible with Collection<E>.size()", and if I change the type to int, columns * rows could overflow.

I know I can't override the size method like this, but is there any way I can make sure the method returns the correct size while still implementing the Collection interface?

Yes, I know this is impractical and will likely never be an issue, but I was interested to know if there was a good solution for it.

An overflow as in a matrix larger than 45k rows x 45k columns (assuming it is square)? — assylias, Jun 18 '12 at 16:55
What could you *do* with a `size` that is `columns*rows`? What would it let you do with the matrix? — ewan.chalmers, Jun 18 '12 at 16:55
I think the question you should be asking is "do my use cases actually require size to be defined like this"? "Does my definition of size make sense in general"? — Tudor, Jun 18 '12 at 16:56
Related: http://stackoverflow.com/questions/7632126/maximum-size-of-hashset-vector-linkedlist — assylias, Jun 18 '12 at 16:58
Yes, I realize that this probably won't ever be used, but I was asking for the learning potential I guess — Wires77, Jun 18 '12 at 17:26

assylias · Accepted Answer · 2012-06-18T17:11:18.420

Although your implementation of size is questionable, the contract for Collection#size is defined in the javadoc:

Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

So you could calculate the size as a long, and return Integer.MAX_VALUE if it is larger than Integer.MAX_VALUE.

Alternatively, you could mimic the way it is implemented in LinkedList#add for example, where size is simply incremented and is allowed to overflow.

score 2 · Answer 2 · answered Jun 18 '12 at 16:59

2

Assuming you were willing to have an 8GB array -- the minimum size of a two-dimensional array that would overflow an int with its total size -- and assuming you were willing to do anything interesting with that collection, like iterate over it (costing several minutes at least just for the iteration)...

I believe the typical approach is either to back down to implementing Iterable and not Collection, or to just return Integer.MAX_VALUE, as specified by the Javadoc:

Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

answered Jun 18 '12 at 16:59

Louis Wasserman

191,574
25
345
413

1

Interestingly, LinkedList#add lets size overflow with no check. – assylias Jun 18 '12 at 17:11
It's not that surprising; your memory will usually run out long before you'll start hitting these kinds of issues. (Also, it is difficult to imagine a use for `LinkedList`s that would scale up to that many elements in the first place.) – Louis Wasserman Jun 18 '12 at 20:27

score 0 · Answer 3 · answered Jun 18 '12 at 16:59

If you are really concerned with large enough matrices that could overflow, you could ensure that does not happen by checking whether the resulting size (initialization or resize) would still be within the range of integer, and throw a (runtime) exception if that would be the case

score -1 · Answer 4 · answered Jun 18 '12 at 16:59

-1

I don't think so, you will need to use a workaround of some sort. You could maybe extend your size to return negative numbers and interpret them as unsigned 32 bit integers, which would give you a maximum of 4 billion and change.

Ask yourself though, do you really need to be able to support that many objects? Keep in mind that 4 billion and change 32 bit integers will take up 16GB of RAM. Using 64 bit java, a 4 billion long array of Object set to all null will take up 32GB because references on 64 bit java are 64 bits. That doesn't even take into account the memory used to actually instantiate that many classes, which will in all likelihood be much higher.

answered Jun 18 '12 at 16:59

Wug

12,956
4
34
54

Yes, I realize that it's impractical to have a 2D array that would overflow like this, but I was asking just to see if there is a solution. – Wires77 Jun 18 '12 at 17:29
Have you considered looking at the code for ArrayList. Why does your return type need to be long anyway? – branchgabriel Jun 18 '12 at 20:53
mugafuga: ArrayLists are Collections, and have only `int size()`, no `long size()`. – Wug Jun 18 '12 at 21:32

Can a dynamic 2D array implement the Java.Collection.size() method?

4 Answers4