Provide DiscreteDomain.advance(T, long)

[GoogleCodeExporter]

I'm building a class to represent an IP address in a subnet.
An IP subnet is both an immutable list and a discrete bounded domain.

Since java doesn't allow multiple inheritance there's no nice way for me to use 
both of these base classes.
It'd nice if DiscreteDomain were an interface rather than an abstract base 
class. 

Original issue reported on code.google.com by Letharg...@gmail.com on 29 May 2012 at 3:23

[GoogleCodeExporter]

Another use case is that this collection inherently supports random access as 
well as iteration.

Original comment by Letharg...@gmail.com on 29 May 2012 at 3:24

[GoogleCodeExporter]

This doesn't sound like a DiscreteDomain.  "A discrete domain always represents 
the entire set of values of its type," but this doesn't represent the entire 
set of IP addresses.

That said, this kind of sounds like

    DiscreteDomain<Address> addressDomain = ...
    return Ranges.closed(subnetLowerBound, subnetUpperBound).asSet(addressDomain).asList();

Original comment by wasserman.louis on 29 May 2012 at 3:26

[GoogleCodeExporter]

(FYI, this returns an ImmutableList, but it has the efficient e.g. contains() 
implementation of a Range.)

That said, Lethargish, Guava quite deliberately makes it impossible to subclass 
ImmutableList at all.  You would probably implement the List interface instead.

Original comment by wasserman.louis on 29 May 2012 at 3:29

[GoogleCodeExporter]

I agree that this request is based on a misunderstanding of what DiscreteDomain 
is.  Each type only ever needs a *single* instance of DiscreteDomain<ThatType> 
to exist; there's never two different ways it could be implemented for the same 
type. And there's never a reason for that instance to have to also implement 
some other type. And finally, Immutable collections are not user-implementable 
by design, to maintain the immutability guarantee.

Original comment by kevinb@google.com on 29 May 2012 at 3:52

• Changed state: Invalid

[GoogleCodeExporter]

Sorry I thought replying by email would end up here.

You're right about the conceptual problem in my model, sorry I misunderstood.

I have some other questions/suggestions, but I don't think I have them clear 
enough to file issues for.

1. "relative random access" to a DiscreteDomain 

In a discrete domain, currently if you want an instance 5 steps away from 
another you'd have to call next/prev 5 times.
I'd imagine most domains would be able to make this jump in a more efficient 
manner, and those that couldn't could just loop.
I can't think of a snappy name for this, perhaps just add a variant of next and 
prev with a 'long' as a parameter.

2. List-like access to bounded discrete ranges

Ranges are good because you don't have to hold the whole thing in memory.
In cases where you know how big a range is, it'd be nice to have a list-like 
way to do random access on a range.

Do you guys think this sounds reasonable?

Thanks,
Marcus

Original comment by Letharg...@gmail.com on 29 May 2012 at 6:22

[GoogleCodeExporter]

"most domains would be able to make this jump in a more efficient manner"

Not all of them -- and I'm inclined to think that we should leave 
DiscreteDomain open to those use cases.  I vaguely recall some discussion of 
some DiscreteDomain variant along these lines, though -- Kevin?

Original comment by wasserman.louis on 29 May 2012 at 6:43

[GoogleCodeExporter]

Would looping not be acceptable in those cases?
You'd need to decide on a return value if it went beyond the domain limits, but 
null might be enough.

Original comment by Letharg...@gmail.com on 29 May 2012 at 6:50

[GoogleCodeExporter]

Hmmm.  If I understand correctly, you're suggesting a _default_ implementation 
of -- let's call it

   C advance(C start, int index) {
     C result = start;
     if (index >= 0) {
       for (int i = 0; i < index; i++) {
         result = next(result);
       }
     } else { 
       for (int i = 0; i > index; i--) {
         result = previous(result);
       }
     }
     return result;
   }

...and allow DiscreteDomain implementors to override it?

That...could be a doable thing, but I guess I'm concerned that 
range.asSet(domain).asList() returns an ImmutableList which people expect to 
_always_ have O(1) get(int) performance, even if the backing DiscreteDomain 
doesn't necessarily support efficiently advancing by an arbitrary amount.

The first workaround for *that* that comes to mind is that we start using the 
RandomAccess marker interface on DiscreteDomains too...blegh, confusing.

Original comment by wasserman.louis on 29 May 2012 at 6:55

[GoogleCodeExporter]

Pretty much, yes. Here's a slight adaption:

  C advance(C start, long index) {
    C result = start;
    if (index >= 0) {
      for (long i = 0; result != null, i < index; i++) {
        result = result.next();
      }
    } else { 
      for (long i = 0; result != null, i > index; i--) {
        result = result.prev();
      }
    }
    return result;
  }

The longs are there to be consistent with the distance function and the null 
checks will ensure it returns null if next/prev do.

Yeah, the List implementation sounds a whole lot more complex, and would need 
more thought.

Original comment by Letharg...@gmail.com on 29 May 2012 at 7:10

[GoogleCodeExporter]

Counterpoint: if the whole point of this is to provide a List implementation, 
then advancing by a long distance is pointless, since List.get takes an int.

(Also, if you ever run a nonempty for loop with more than Integer.MAX_VALUE 
iterations, your program's already a little broken.)

Original comment by wasserman.louis on 29 May 2012 at 7:12

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Agreed, but I'd say an 'advance' function has use beyond a list implementation.
Binary search over a bounded discrete domain would be another potential usage.

I've realised that I'll be exceeding both int and long when representing the 
IPv6 address pool :(

"(Also, if you ever run a nonempty for loop with more than Integer.MAX_VALUE 
iterations, your program's already a little broken.)"

You're program's probably broken long time before it reaches Integer.MAX_VALUE 
;)
That's my point i guess, without the extra function there's just no sane way of 
doing it.

I'd argue that the long is important, because otherwise people will have to 
write wrapper code for the advance function just to support the distance value 
being returned.
A list interface on top of this would have to have glue code anyway, so I don't 
see why it couldn't do a type conversion too.

Original comment by Letharg...@gmail.com on 29 May 2012 at 8:29

[GoogleCodeExporter]

Hmmmmmkay.  And I can certainly imagine that the ability to binary-search in a 
Range with a DiscreteDomain can be nice.  I withdraw my objection to the use of 
long.

That said, I believe we've set the precedent that distance() results are capped 
at Long.MAX_VALUE.

But all that said, what would you _do_ with a Collection with size more than 
Integer.MAX_VALUE, except do contains() checks and the like?  I'm not sure that 
any subclass of Collection is really appropriate for your use case.

That said, I'm reopening the issue, because I think we're playing with some 
useful ideas now.

Original comment by wasserman.louis on 30 May 2012 at 7:36

• Changed title: Augment DiscreteDomain for "random access operations"
• Changed state: New

[GoogleCodeExporter]

Yeah my use-case isn't so clear now, but I'm glad there's some mileage in these 
ideas.

Also I realised that I incorrectly changed these lines:

        result = result.next();
        result = result.prev();

What you originally posted was correct.

Thanks for the discussion!

Original comment by Letharg...@gmail.com on 30 May 2012 at 7:54

[GoogleCodeExporter]

Louis, can you update the summary to describe what you think this issue is 
really about now?

Original comment by kevinb@google.com on 19 Jun 2012 at 5:37

• Changed state: Acknowledged
• Added labels: Package-Collect, Type-Addition

[GoogleCodeExporter]

Original comment by wasserman.louis on 22 Jun 2012 at 12:50

• Changed title: Provide DiscreteDomain.advance(T, long)

[GoogleCodeExporter]

Original comment by kevinb@google.com on 22 Jun 2012 at 6:16

• Changed state: Research

[GoogleCodeExporter]

The goal is just to add that method for certain users to call directly, or is 
it so that any particular Range features could make use of it (e.g. 
asSet().asList()?)

Original comment by kevinb@google.com on 22 Jun 2012 at 6:49

[GoogleCodeExporter]

I think it's for potential future features, but it could be useful in its own 
right.  I'd vaguely prefer to wait to add it until we have some of those 
features figured out, though.

Original comment by wasserman.louis on 22 Jun 2012 at 6:53

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:14

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:18

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:08

• Added labels: Restrict-AddIssueComment-Commit