Provide DiscreteDomain.advance(T, long)

[gissuebot]

Original issue created by Lethargish on 2012-05-29 at 03:23 PM

---

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.

[gissuebot]

Original comment posted by Lethargish on 2012-05-29 at 03:24 PM

---

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

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 03:26 PM

---

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();

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 03:29 PM

---

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

[gissuebot]

Original comment posted by kevinb@google.com on 2012-05-29 at 03:52 PM

---

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.

---

Status: Invalid

[gissuebot]

Original comment posted by Lethargish on 2012-05-29 at 06:22 PM

---

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.

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

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 06:43 PM

---

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

[gissuebot]

Original comment posted by Lethargish on 2012-05-29 at 06:50 PM

---

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.

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 06:55 PM

---

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.

[gissuebot]

Original comment posted by Lethargish on 2012-05-29 at 07:10 PM

---

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.

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 07:12 PM

---

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

[gissuebot]

Original comment posted by Lethargish on 2012-05-29 at 08:29 PM

---

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.

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-30 at 07:36 AM

---

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.

---

Status: New

[gissuebot]

Original comment posted by Lethargish on 2012-05-30 at 07:54 AM

---

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!

[gissuebot]

Original comment posted by kevinb@google.com on 2012-06-19 at 05:37 PM

---

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

---

Status: Acknowledged Labels: Package-Collect, Type-Addition

[gissuebot]

Original comment posted by wasserman.louis on 2012-06-22 at 12:50 PM

---

(No comment entered for this change.)

[gissuebot]

Original comment posted by kevinb@google.com on 2012-06-22 at 06:16 PM

---

(No comment entered for this change.)

---

Status: Research

[gissuebot]

Original comment posted by kevinb@google.com on 2012-06-22 at 06:49 PM

---

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

[gissuebot]

Original comment posted by wasserman.louis on 2012-06-22 at 06:53 PM

---

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.