Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
9455051:
Add getMinimum, getMaximum, getPreceding and getSucceeding to SplayTree. (Closed)
|
Created:
8 years, 10 months ago by Anders Johnsen Modified:
8 years, 9 months ago CC:
reviews_dartlang.org, jjb Visibility:
Public. |
DescriptionAdd getMinimum, getMaximum, getPreceding and getSucceeding to SplayTree.
Committed: https://code.google.com/p/dart/source/detail?r=4689
Patch Set 1 #
Total comments: 6
Patch Set 2 : #
Total comments: 22
Patch Set 3 : #Patch Set 4 : #Patch Set 5 : #
Total comments: 3
Patch Set 6 : #
Total comments: 7
Patch Set 7 : #Patch Set 8 : #
Messages
Total messages: 16 (0 generated)
Hi Kasper, Any idea who I should get to review this? I'll add tests/rename if the methods gets approved. Thank you! - Anders
LGTM with a few simple tests, that would visually show the outcome of these methods.
DBC. I think there should be an interface for these operations, e.g OrderedMap or SortedMap. https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:242: V getMinimum() { Can we avoid the use of 'get' in the name of methods? I know we have getKeys above but I think that is a mistake. I expect the 'minimum' of an ordered collection to be the minimum key. That way the minimum would also work when the tree is thought of as a set of keys. Since your expectation of what the constitutes a minumum is different to mine, perhaps it should be made explicit. minValue() would make it clear that the returned value is a map value and not a key. minKey() might also be a useful operation. K minKey() => root == null ? null : _minNode().key; V minValue() => root == null ? null : _minNode().value; Java's SortedMap uses firstKey / lastKey. Using firstKey might avoid the potential confusion that minKey might also mean the lowest legal key. I don't know if optional arguments would be useful in your application: K firstKey([ifEmpty]) => root == null ? ifEmpty : _minNode().key; V firstValue([ifEmpty]) => root == null ? ifEmpty : _minNode().value; var v1 = tree.firstValue(); var v2 = tree.firstValue(ifEmpty: 0); Please add DartDoc comments since these operations are not described elsewhere. (It might be nice to add an interface for these operations, since all ordered Maps could potentially implement them.) https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:244: SplayTreeNode<K, V> node = _root; Should min and max splay the tree? I.e. do you consider them as being in the set of operations with guarantee on amortized time, or are you OK with worst-case O(N) for repeated min and/or max? https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:260: V getPreceding(K key) { It feels slightly wrong that preceding and succeeding return a different type than the argument - I think of 'preceding' as comparing two things of the same type as in 'the preceding element'. Again, it might be useful to have these operations for keys too. Adding 'value' and 'key' to the name would help with that slightly wrong feeling. ('following' might be better than 'succeeding' since succeeding could be confused with success.) On balance, I would prefer shorter names if they are of equal clarity: K keyBefore(K key) => ... V valueAfter(K key) => ... Compare: var x = tree.getSucceeding('100'); var x = tree.valueSucceeding('100'); var x = tree.valueFollowing('100'); var x = tree.valueAfter('100');
Thank you all for your comments. I've updated the code, and I agree that working only on keys is much better. I would love to see a SortedMap interface in the future, that I can navigate and iterate through. https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:242: V getMinimum() { On 2012/02/24 22:21:14, sra1 wrote: > Can we avoid the use of 'get' in the name of methods? > I know we have getKeys above but I think that is a mistake. > > I expect the 'minimum' of an ordered collection to be the minimum key. > That way the minimum would also work when the tree is thought of as a set of > keys. > > Since your expectation of what the constitutes a minumum is different to mine, > perhaps it should be made explicit. > minValue() would make it clear that the returned value is a map value and not a > key. > minKey() might also be a useful operation. > > K minKey() => root == null ? null : _minNode().key; > V minValue() => root == null ? null : _minNode().value; > > Java's SortedMap uses firstKey / lastKey. > > Using firstKey might avoid the potential confusion that minKey might also mean > the lowest legal key. > > I don't know if optional arguments would be useful in your application: > > K firstKey([ifEmpty]) => root == null ? ifEmpty : _minNode().key; > V firstValue([ifEmpty]) => root == null ? ifEmpty : _minNode().value; > > var v1 = tree.firstValue(); > var v2 = tree.firstValue(ifEmpty: 0); > > > Please add DartDoc comments since these operations are not described elsewhere. > (It might be nice to add an interface for these operations, since all ordered > Maps could potentially implement them.) I agree, firstKey/lastKey is way better. The user can then always perform a lookup then, to extract the value. https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:244: SplayTreeNode<K, V> node = _root; On 2012/02/24 22:21:14, sra1 wrote: > Should min and max splay the tree? > > I.e. do you consider them as being in the set of operations with guarantee on > amortized time, or are you OK with worst-case O(N) for repeated min and/or max? I'm fine with splaying the tree, makes sense! Added. https://chromiumcodereview.appspot.com/9455051/diff/1/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:260: V getPreceding(K key) { On 2012/02/24 22:21:14, sra1 wrote: > It feels slightly wrong that preceding and succeeding return a different type > than the argument - I think of 'preceding' as comparing two things of the same > type as in 'the preceding element'. > Again, it might be useful to have these operations for keys too. > Adding 'value' and 'key' to the name would help with that slightly wrong > feeling. > ('following' might be better than 'succeeding' since succeeding could be > confused with success.) > On balance, I would prefer shorter names if they are of equal clarity: > > K keyBefore(K key) => ... > V valueAfter(K key) => ... > > Compare: > var x = tree.getSucceeding('100'); > var x = tree.valueSucceeding('100'); > var x = tree.valueFollowing('100'); > var x = tree.valueAfter('100'); Again, yes, this should be keys. I was using the values directly in my use-case, but this is a lot more useful. Changed!
LGTM. Not sure about the ifEmpty/ifInvalid. https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:10: SplayTreeNode(K k, V v) { Use this.key and this.value? https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:30: class SplayTree<K extends Comparable, V> implements Map<K, V> { Long term, it would be great with both a map and a set variant of this. It seems fairly easy to abstract out the creation of the internal nodes. Maybe we should rename this to SplayTreeMap right away? https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:222: forEach((Object k, Object v) { if (value == v) found = true; }); I guess there's no need to do containsValue in order so a much simpler implementation than the one in forEach should work fine. https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:245: K firstKey([K ifEmpty]) { Have you considered making ifEmpty a closure instead (like putIfAbsent)? At least it is something we should consider in general. https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:269: * Get the last key in the map that is strictly smaller then [key]. Returns then -> than https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:272: K keyBefore(K key, [K ifInvalid]) { lastKeyBefore? https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:285: * Get the first key in the map that is strictly larger then [key]. Returns then -> than https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:288: K keyAfter(K key, [K ifInvalid]) { firstKeyAfter?
https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:245: K firstKey([K ifEmpty]) { Why not just return null if the splay tree is empty? As far as I can see null is not a valid key anyway. The this function can also become a getter. Same for the other methods with ifEmpty and ifInvalid arguments.
https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:245: K firstKey([K ifEmpty]) { On 2012/02/27 07:53:16, Søren Gjesse wrote: > Why not just return null if the splay tree is empty? As far as I can see null is > not a valid key anyway. The this function can also become a getter. Same for the > other methods with ifEmpty and ifInvalid arguments. I think we should go with Søren's proposal for now (just returning null). It fits better with the other methods in map (like []).
Updated, with a few pending questions. Thank you! https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:10: SplayTreeNode(K k, V v) { On 2012/02/27 06:50:03, kasperl wrote: > Use this.key and this.value? Done. https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:30: class SplayTree<K extends Comparable, V> implements Map<K, V> { On 2012/02/27 06:50:03, kasperl wrote: > Long term, it would be great with both a map and a set variant of this. It seems > fairly easy to abstract out the creation of the internal nodes. Maybe we should > rename this to SplayTreeMap right away? Yep, renamed! https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:222: forEach((Object k, Object v) { if (value == v) found = true; }); On 2012/02/27 06:50:03, kasperl wrote: > I guess there's no need to do containsValue in order so a much simpler > implementation than the one in forEach should work fine. Done. https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:245: K firstKey([K ifEmpty]) { On 2012/02/27 07:53:16, Søren Gjesse wrote: > Why not just return null if the splay tree is empty? As far as I can see null is > not a valid key anyway. The this function can also become a getter. Same for the > other methods with ifEmpty and ifInvalid arguments. If we return null, then map[] should support null index as well. Otherwise we will not be able to do var firstValue = map[map.firstKey()]; I have the option of doing var firstValue = map[map.firstKey(-1)]; with the current implementation. Is that okay with you guys? https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:269: * Get the last key in the map that is strictly smaller then [key]. Returns On 2012/02/27 06:50:03, kasperl wrote: > then -> than Done. https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:272: K keyBefore(K key, [K ifInvalid]) { On 2012/02/27 06:50:03, kasperl wrote: > lastKeyBefore? Hmm, to me this sort of implies I could give any key, even one that is not in the map. That is not true. So, 1) rename and change implementation 2) keep name and implementation. What you think? https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:285: * Get the first key in the map that is strictly larger then [key]. Returns On 2012/02/27 06:50:03, kasperl wrote: > then -> than Done. https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:288: K keyAfter(K key, [K ifInvalid]) { On 2012/02/27 06:50:03, kasperl wrote: > firstKeyAfter? Same as above.
https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:245: K firstKey([K ifEmpty]) { On 2012/02/27 09:06:51, ajohnsen wrote: > On 2012/02/27 07:53:16, Søren Gjesse wrote: > > Why not just return null if the splay tree is empty? As far as I can see null > is > > not a valid key anyway. The this function can also become a getter. Same for > the > > other methods with ifEmpty and ifInvalid arguments. > > If we return null, then map[] should support null index as well. Otherwise we > will not be able to do > > var firstValue = map[map.firstKey()]; > > I have the option of doing > > var firstValue = map[map.firstKey(-1)]; > > with the current implementation. > > Is that okay with you guys? I actually find it hard to read the line: var firstValue = map[map.firstKey(-1)]; I guess it returns null if the key doesn't exist and there is no mapping for -1? Seems pretty brittle to me. I'd prefer something like: var firstValue = map.isEmpty() : null ? map[map.firstKey()]; https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:272: K keyBefore(K key, [K ifInvalid]) { On 2012/02/27 09:06:51, ajohnsen wrote: > On 2012/02/27 06:50:03, kasperl wrote: > > lastKeyBefore? > > Hmm, to me this sort of implies I could give any key, even one that is not in > the map. That is not true. So, > > 1) rename and change implementation > 2) keep name and implementation. > > What you think? To me the term 'keyBefore' is almost the same as 'anyKeyBefore' which is definitely not what you want, but I could be the only one who reads it that way. In terms of the requirement that the key has to be present in the map, I don't think there is any different between keyBefore and lastKeyBefore (at least not in how I interpret them).
Updated based on comments. Does this look okay for commit? https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:245: K firstKey([K ifEmpty]) { On 2012/02/27 09:18:45, kasperl wrote: > On 2012/02/27 09:06:51, ajohnsen wrote: > > On 2012/02/27 07:53:16, Søren Gjesse wrote: > > > Why not just return null if the splay tree is empty? As far as I can see > null > > is > > > not a valid key anyway. The this function can also become a getter. Same for > > the > > > other methods with ifEmpty and ifInvalid arguments. > > > > If we return null, then map[] should support null index as well. Otherwise we > > will not be able to do > > > > var firstValue = map[map.firstKey()]; > > > > I have the option of doing > > > > var firstValue = map[map.firstKey(-1)]; > > > > with the current implementation. > > > > Is that okay with you guys? > > I actually find it hard to read the line: > > var firstValue = map[map.firstKey(-1)]; > > I guess it returns null if the key doesn't exist and there is no mapping for -1? > Seems pretty brittle to me. I'd prefer something like: > > var firstValue = map.isEmpty() > : null > ? map[map.firstKey()]; Yeah, I've turned them into a getter. Thank you! https://chromiumcodereview.appspot.com/9455051/diff/3002/corelib/src/implemen... corelib/src/implementation/splay_tree.dart:272: K keyBefore(K key, [K ifInvalid]) { On 2012/02/27 09:18:45, kasperl wrote: > On 2012/02/27 09:06:51, ajohnsen wrote: > > On 2012/02/27 06:50:03, kasperl wrote: > > > lastKeyBefore? > > > > Hmm, to me this sort of implies I could give any key, even one that is not in > > the map. That is not true. So, > > > > 1) rename and change implementation > > 2) keep name and implementation. > > > > What you think? > > To me the term 'keyBefore' is almost the same as 'anyKeyBefore' which is > definitely not what you want, but I could be the only one who reads it that way. > In terms of the requirement that the key has to be present in the map, I don't > think there is any different between keyBefore and lastKeyBefore (at least not > in how I interpret them). I agree, and it makes a lot more sense the more I think about it. I've updated my implementation.
https://chromiumcodereview.appspot.com/9455051/diff/7/corelib/src/implementat... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/7/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:243: K get firstKey() { I don't think these should be getters. Last/first on List are methods -- so these should be methods too.
https://chromiumcodereview.appspot.com/9455051/diff/7/corelib/src/implementat... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/7/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:243: K get firstKey() { On 2012/02/27 11:52:34, kasperl wrote: > I don't think these should be getters. Last/first on List are methods -- so > these should be methods too. I would raise the question if last/first on List maybe should be getters then? Bob's description of a getter fits this description very well. However, we can always discuss this at a later point in time, so if there are no further comments, I'll remove 'get' and commit.
https://chromiumcodereview.appspot.com/9455051/diff/7/corelib/src/implementat... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/7/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:243: K get firstKey() { On 2012/02/27 11:58:50, ajohnsen wrote: > On 2012/02/27 11:52:34, kasperl wrote: > > I don't think these should be getters. Last/first on List are methods -- so > > these should be methods too. > > I would raise the question if last/first on List maybe should be getters then? > Bob's description of a getter fits this description very well. However, we can > always discuss this at a later point in time, so if there are no further > comments, I'll remove 'get' and commit. Yeah, it's a long discussion. I'm definitely in the camp that only want to use getters/setters for emulating fields.
lgtm https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:78: } else if (key.compareTo(current.key) > 0) { You could improve this by caching the value returned by key.compareTo(current.key) in a local. https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:241: * Get the first key in the map. Returns [ifEmpty] if the map is empty. There is no ifEmpty parameter. Since it is a key and null is not comparable, just fix the doc. https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:249: splay_(node.key); One does wonder if there is a concise specialization of splay that can do the splaying with no comparisons since they key is the minimum. Add a comment? https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:254: * Get the last key in the map. Returns [ifEmpty] if the map is empty. Ditto.
lgtm
Fixed. Will commit this if there are no further comments. :) Thank you all! https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... File corelib/src/implementation/splay_tree.dart (right): https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:78: } else if (key.compareTo(current.key) > 0) { On 2012/02/27 23:46:04, sra1 wrote: > You could improve this by caching the value returned by > key.compareTo(current.key) in a local. I don't expect this to be a huge improvement, but done. https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:241: * Get the first key in the map. Returns [ifEmpty] if the map is empty. On 2012/02/27 23:46:04, sra1 wrote: > There is no ifEmpty parameter. Since it is a key and null is not comparable, > just fix the doc. Ah yes, ty! https://chromiumcodereview.appspot.com/9455051/diff/8/corelib/src/implementat... corelib/src/implementation/splay_tree.dart:254: * Get the last key in the map. Returns [ifEmpty] if the map is empty. On 2012/02/27 23:46:04, sra1 wrote: > Ditto. Done. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
