Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
8236002:
Create StringOrdinal to allow placement of strings in sorted lists (Closed)
|
Created:
9 years, 2 months ago by csharp Modified:
9 years, 1 month ago CC:
chromium-reviews, Paweł Hajdan Jr., SteveT, tfarina Visibility:
Public. |
DescriptionCreate StringOrdinal to allow placement of strings in sorted lists
The StringOrdinal class is intended to allow sorted lists of strings to be treated as floating point numbers, and can be used to create a value to be sorted into any index location, allowing an element to change it's index without any other elements having to change their index value.
BUG=94662
TEST=Unit tests created in chrome/common/string_ordinal_unittest.cc
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=107566
Patch Set 1 #
Total comments: 19
Patch Set 2 : Adjusting code to comply with code review requests #
Total comments: 8
Patch Set 3 : Fixing issue with StringIndex overflow #Patch Set 4 : Adding unit test for overflow #Patch Set 5 : Changing StringIndex to a class #
Total comments: 30
Patch Set 6 : Cleanup of StringIndex #Patch Set 7 : Add comment about copy and assignment of StringIndex #
Total comments: 25
Patch Set 8 : Changing StringIndex to StringOrdinal and making code review changes. #
Total comments: 45
Patch Set 9 : Adjusting code to comply with code review comments #
Total comments: 19
Patch Set 10 : Modifying DropUnneededDigits logic and code review changes #
Total comments: 9
Patch Set 11 : Small cleanup #
Total comments: 10
Patch Set 12 : Reverting some lines #Patch Set 13 : Removing temporary string from DropUnneededDigits #
Total comments: 8
Patch Set 14 : Clarifying name of GetLengthWithTrailingZeros #
Total comments: 8
Patch Set 15 : Fixing out of bounds issue in GetLengthWithoutTrailingZeros #Patch Set 16 : Clearer comment for AddHalf failing and extra test for its loop #
Total comments: 4
Patch Set 17 : Fixing StringOrdinal comments #
Messages
Total messages: 44 (0 generated)
One thing I'm not sure about in this code is that the middle string will always be at least as long as max(before, after), because it tries to take the value closest to the middle. However in a case like before=BZZZZT and after=DAAAB, we could return C, which is still in the middle (just not the exact middle). I guess what I'm wondering is how important less characters is verse exact middle.
http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:7: StringIndex::StringIndex(): kMaxDigitValue(kMaxDigit - kZeroDigit), surely you don't need these to be initialized for every StringIndex object? http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:12: int end_position = value.length() - 1; assert that value is non-empty http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:25: ++value[position - 1]; what if this also overflows? consider (.99999 + .00001) / 2. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:29: int StringIndex::GetPositionValue(const std::string& value, size_t index) { this can be a static function, or a free function in an anon namespace http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:37: if (end.length() == 0) { end.empty() http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:38: return CreateStringBetween(start, this fails the precondition below http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:40: } assert that start < end || start.empty() assert that the strings match [a-z]*[b-z] if non-empty. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:59: middle_string += kMidDigit; pretty sure this is only needed because you don't perform the last half operation. I'd prefer removing this hack, implementing 'real' averaging above, and doing the truncation as a final step below. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:70: return middle_string; assert that start < middle < end http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.h File chrome/common/string_index.h (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.h#ne... chrome/common/string_index.h:23: std::string CreateStringBetween(const std::string& start, since kmaxDigitvalue and kMidDigitValue are constants, then this can be static, too. Since this is static, then there's no need for the class at all, at least how this CL stands.
On 2011/10/11 15:47:35, csharp1 wrote: > One thing I'm not sure about in this code is that the middle string will always > be at least as long as max(before, after), because it tries to take the value > closest to the middle. > > However in a case like before=BZZZZT and after=DAAAB, we could return C, which > is still in the middle (just not the exact middle). I guess what I'm wondering > is how important less characters is verse exact middle. probably not too important. simple is better.
I've made most of the changes you suggested but I've failure right now so I can't update the code right now. I'm unsure of what you mean in one of your comments right now. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:25: ++value[position - 1]; I'm fairly certain it can't overflow. It could only overflow if the value is kMaxDigit and this function is only called if their was a unused half when adding, so the value would have to be 2*kMaxDigit +1, which we can never get. I've added an assert here though to ensure this condition is true. On 2011/10/11 19:34:39, akalin wrote: > what if this also overflows? consider (.99999 + .00001) / 2. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:25: ++value[position - 1]; I'm fairly certain it can't overflow. It could only overflow if the value is kMaxDigit and this function is only called if their was a unused half when adding, so the value would have to be 2*kMaxDigit +1, which we can never get. I've added an assert here though to ensure this condition is true. On 2011/10/11 19:34:39, akalin wrote: > what if this also overflows? consider (.99999 + .00001) / 2. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:38: return CreateStringBetween(start, I'm not sure what you mean here. This does fail start < end, but this was the best way I could see to signify that the end is the max value. On 2011/10/11 19:34:39, akalin wrote: > this fails the precondition below
http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:25: ++value[position - 1]; On 2011/10/11 21:46:03, csharp1 wrote: > I'm fairly certain it can't overflow. > > It could only overflow if the value is kMaxDigit and this function is only > called if their was a unused half when adding, so the value would have to be > 2*kMaxDigit +1, which we can never get. > > I've added an assert here though to ensure this condition is true. > > On 2011/10/11 19:34:39, akalin wrote: > > what if this also overflows? consider (.99999 + .00001) / 2. Ah, it can't overflow because mid digit value is set to 12 (M) when it should be 13 (N) (if you're simulating base-26 arithmetic). When you fix that bug, then overflow can definitely happen, e.g. 'zzz', 'aab'. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:38: return CreateStringBetween(start, On 2011/10/11 21:46:03, csharp1 wrote: > I'm not sure what you mean here. This does fail start < end, but this was the > best way I could see to signify that the end is the max value. Seems better to go the extra step to make the precondition hold (i.e., if end is empty and start is all 'z's, make an end value that is greater than that. > > On 2011/10/11 19:34:39, akalin wrote: > > this fails the precondition below >
Ok, I've made the changes requested and have all the tests passing. I also ended up changing how CreateStringBetween works, instead of working directly on the inputs, it copies the inputs to internal strings that it then pads out correctly (to ensure same length and that empty start and end values are correctly created) and works off of those. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:25: ++value[position - 1]; I fixed the middle digit bug, but I still don't see how the overflow could occur. For the overflow to occur the last index would need to have a value kMaxDigit,and also set the add_half variable to true. To get a value of kMaxDigit the start and end string must both be kMaxDigit, but then add_half will be false, (2*kMaxDigit) % 2 == 0, so we enter AddHalf for the next position. Maybe I'm missing something, could you provide an example where the overflow will occur in value[position -1]? On 2011/10/11 22:00:24, akalin wrote: > On 2011/10/11 21:46:03, csharp1 wrote: > > I'm fairly certain it can't overflow. > > > > It could only overflow if the value is kMaxDigit and this function is only > > called if their was a unused half when adding, so the value would have to be > > 2*kMaxDigit +1, which we can never get. > > > > I've added an assert here though to ensure this condition is true. > > > > On 2011/10/11 19:34:39, akalin wrote: > > > what if this also overflows? consider (.99999 + .00001) / 2. > > Ah, it can't overflow because mid digit value is set to 12 (M) when it should be > 13 (N) (if you're simulating base-26 arithmetic). When you fix that bug, then > overflow can definitely happen, e.g. 'zzz', 'aab'. http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.h File chrome/common/string_index.h (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.h#ne... chrome/common/string_index.h:23: std::string CreateStringBetween(const std::string& start, Ok, I've changed it to just be a namespace. On 2011/10/11 19:34:39, akalin wrote: > since kmaxDigitvalue and kMidDigitValue are constants, then this can be static, > too. Since this is static, then there's no need for the class at all, at least > how this CL stands.
http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:25: ++value[position - 1]; On 2011/10/12 15:31:12, csharp1 wrote: > I fixed the middle digit bug, but I still don't see how the overflow could > occur. For the overflow to occur the last index would need to have a value > kMaxDigit,and also set the add_half variable to true. To get a value of > kMaxDigit the start and end string must both be kMaxDigit, but then add_half > will be false, (2*kMaxDigit) % 2 == 0, so we enter AddHalf for the next > position. > > Maybe I'm missing something, could you provide an example where the overflow > will occur in value[position -1]? I did, in my previous two comments about it. :P To repeat it, in base 10, consider .999 + .001. In base 26, consider 'zzz' and 'aab'.
http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.c... chrome/common/string_index.cc:27: DCHECK(value[position - 1] <= kMaxDigit); as I mentioned previously, this won't work. you'll have to propagate the carry backwards. http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.c... chrome/common/string_index.cc:36: DCHECK(value[0] >= kZeroDigit); use DCHECK_GE, DCHECK_LE, etc. http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.c... chrome/common/string_index.cc:68: CHECK(start_expanded < end_expanded); CHECK_LT http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.c... chrome/common/string_index.cc:81: } this should be decomped out into a helper function like ComputeMidpoint(). Then this function could be something like: std::string middle_string = ComputeMidpoint(start, end); RemoveTrailingZeros(&middle_string); if (middle_string.size() > max_size) { // Try truncating if it doesn't break the invariants. } return middle_string; http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.h File chrome/common/string_index.h (right): http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.h... chrome/common/string_index.h:13: namespace StringIndex { static functions in a namespace isn't a great interface. I feel like we're going in circles, so I'll just outline what I think would be a workable interface: class StringIndex { public: // Creates a valid StringIndex if str matches [A-Z]*[B-Z] StringIndex(const std::string& str); // Invalid StringIndex. StringIndex(); bool IsValid() const; bool LessThan(const StringIndex& other) const; // LessThan(other) must hold. Returns a StringIndex x s.t. LessThan(x) holds, and x.LessThan(other) holds. StringIndex CreateBetween(const StringIndex& other) const; // Returns a StringIndex x s.t. x.LessThan(*this) holds. StringIndex CreateBefore() const; // Returns a StringIndex x s.t. LessThan(x) holds. StringIndex CreateAfter() const; std::string ToString() const; }; http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.h... chrome/common/string_index.h:25: // middle value is x and a half, so we are inserting the half here. why is this public? http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.h... chrome/common/string_index.h:29: std::string RemoveTrailingZeros(const std::string& value); why is this public? http://codereview.chromium.org/8236002/diff/8001/chrome/common/string_index.h... chrome/common/string_index.h:35: static const char kZeroDigit = 'A'; why are these in the header?
http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/1/chrome/common/string_index.cc#n... chrome/common/string_index.cc:25: ++value[position - 1]; Ok, I made a unit test with the example you gave and had it fail on me :) When I was looking at the code I was forgetting the index value before could have had AddHalf applied to it, which made it possible to have the overflow issue. It should be fixed now. On 2011/10/12 18:13:07, akalin wrote: > On 2011/10/12 15:31:12, csharp1 wrote: > > I fixed the middle digit bug, but I still don't see how the overflow could > > occur. For the overflow to occur the last index would need to have a value > > kMaxDigit,and also set the add_half variable to true. To get a value of > > kMaxDigit the start and end string must both be kMaxDigit, but then add_half > > will be false, (2*kMaxDigit) % 2 == 0, so we enter AddHalf for the next > > position. > > > > Maybe I'm missing something, could you provide an example where the overflow > > will occur in value[position -1]? > > I did, in my previous two comments about it. :P To repeat it, in base 10, > consider .999 + .001. In base 26, consider 'zzz' and 'aab'.
http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:108: if (add_half && EqualValueIndexs(middle_string,start.ToString())) { Note that if middle_string.length() > max_size it means that without the extra digit our invariant would fail, which means if we have middle_string.length() > max_size we sadly can't reduce its size.
more comments http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:10: static const std::string kInvalidStringIndex = ""; static non-POD types are a no-no. use 'static const char[] kInvalidStringIndex = '''. Although honestly you don't really need a string for this http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:11: static const char kZeroDigit = 'A'; prefer anon namespace http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:28: if (string_index_ == kInvalidStringIndex) { simply check for empty http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:32: for (size_t i = 0; i < string_index_.length(); ++i) { better to do this computation in the constructor and store an is_valid_ flag, since we're going to be checking this all over the place. http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:38: return (string_index_[string_index_.length() - 1] > kZeroDigit); and it must also be <= maxdigit http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:42: return string_index_ < other.string_index_; CHECK that both strings are valid (this goes for all public functions) http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:73: return i < string_index_.length() ? string_index_[i] - kZeroDigit : 0; use parenthesis to the clauses of the ternary operator http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:88: std::string StringIndex::ComputeMidpoint(const StringIndex& start, so when i asked you to decomp this function out, I meant that the operation "take two strings representing base-26 numbers and return their midpoint" should be abstracted out. This function doesn't take strings, and doesn't return the midpoint (since it has that extra logic for the extra digit) http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:90: size_t max_size = std::max(start.ToString().length(), #include <algorithm> for max http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:90: size_t max_size = std::max(start.ToString().length(), CHECK that both start and end are valid http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:90: size_t max_size = std::max(start.ToString().length(), rather than calling ToString() multiple times, set it to a const string ref http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:108: if (add_half && EqualValueIndexs(middle_string,start.ToString())) { if start is valid (which it should be if you check above) then you don't need to trim the string. http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:125: DCHECK(i > 0); DCHECK_GT http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:125: DCHECK(i > 0); better to CHECK -- if this fails, you'll do an out-of-bounds write, which is bad. http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.h File chrome/common/string_index.h (right): http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:11: #include "base/basictypes.h" what is this for? if this is for size_t, #include <cstddef> instead http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:13: class StringIndex { add comment explaining what the class is for http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:15: // Create a valid StringIndex if the str matches [A-Z]*[B-Z], str -> string http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:16: // otherwise create an invalid StringIndex end with period http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:19: // Create an invalid StringIndex end with period http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:22: // Check to see if this matches [A-Z]*[B-Z] Returns true iff this was initialized with a string matching [A-Z]*[B-Z]. http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:25: bool LessThan(const StringIndex& other) const; probably should include an Equals() mem-fn for convenience http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:25: bool LessThan(const StringIndex& other) const; add comment http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:27: // LessThan(other) must hold. Returns a StringIndex x s.t. LessThan(x) clean up this comment (e.g., s.t. -> such that) http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:31: // Returns a StringIndex x s.t. x.LessThan(*this) holds. clean up http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:34: // Returns a StringIndex x s.t. LessThan(x) holds. clean up http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:37: std::string ToString() const; add a comment like copy constructor and default assignment welcome http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:46: static StringIndex CreateStringIndexBetween(const StringIndex& start, is there are a reason why these functions are exposed in the header? if not, put them in an anonymous namespace in the .cc file (I believe I've already mentioned this). A good reason would be that the static function accesses private fields of StringIndex. If it can be done using only the public interface, then it can be moved into the .cc file. http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.h:64: std::string string_index_; const
I didn't change string_index_ to constant because if I do, then the class is no longer assignable (since it has a constant member), which was something else you had expressed as desirable. We have two options and I'm unsure which would be the better fit: 1) Leave string_index_ as nonconst, it can only be change from inside the class and that shouldn't occur (but can cause big problems if it does). This will allow us to assign instances of this class. 2) Make string_index_ const. This means we can't assign StringIndex instances and would need to have the application data hold a pointer to the index value, instead of just containing the index value. I can see advantages to both methods, which one should we use? http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/14001/chrome/common/string_index.... chrome/common/string_index.cc:38: return (string_index_[string_index_.length() - 1] > kZeroDigit); This is already checked in the above for loop. We just check the zero digit here because it is a special case for just the last digit. On 2011/10/14 10:16:29, akalin wrote: > and it must also be <= maxdigit
On Fri, Oct 14, 2011 at 9:52 AM, <csharp@google.com> wrote: > I didn't change string_index_ to constant because if I do, then the class is > no > longer assignable (since it has a constant member), which was something else > you > had expressed as desirable. > > We have two options and I'm unsure which would be the better fit: > 1) Leave string_index_ as nonconst, it can only be change from inside the > class > and that shouldn't occur (but can cause big problems if it does). This will > allow us to assign instances of this class. > 2) Make string_index_ const. This means we can't assign StringIndex > instances > and would need to have the application data hold a pointer to the index > value, > instead of just containing the index value. > > I can see advantages to both methods, which one should we use? I always forget about that. Let's go with #1. > (string_index_[string_index_.length() - 1] > kZeroDigit); > This is already checked in the above for loop. We just check the zero > digit here because it is a special case for just the last digit. Ah, you're right.
More comments. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.cc File chrome/common/string_index.cc (right): http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:13: static const char kZeroDigit = 'A'; no need for static since we're in anon namespace http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:54: // Compute the midpoint string that is between start and end. This is what I want, basically: // Given strings a, b representing base-26 numbers in (0..1), returns a string representing (a + b) / 2. std::string ComputeMidpoint(const std::string& a, std::string& b) { const size_t midpoint_size = std::max(start.length(), end.length()) + 1; std::string mid(midpoint_size, kZeroDigit); ... } } That is, add an extra digit here if necessary, and truncate the string outside this function. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:89: // We only add an extra digit if it is required for uniqueness, otherwise Although you can decomp this logic (which will turn into 'drop last digit if possible') into a separate fn http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:106: is_valid_ = false; decomp this into a function. That is, have: bool IsValidStringIndex(const std::string& str); and have the initialization list just be: string_index_(str), is_valid_(IsValidStringIndex(string_index_)) http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:120: StringIndex::StringIndex() : string_index_(""), is_valid_(false) { omit string_index_ (it's already default-initialized to be empty) http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:128: CHECK(other.IsValid()); nit: prefer CHECK(IsValid()) before CHECK(other.IsValid()) http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:134: CHECK(other.IsValid()); here too http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:136: omit extra line http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:141: CHECK(other.IsValid()); here too http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:149: CHECK(IsValid()); I think the following would be clearer: const size_t length = string_index_.length(); std::string start_string = std::string(length, kZeroDigit); start_string[length - 1] = kMinDigit; if (...) { start_string[length - 1] = kZeroDigit; start_string += kMinDigit; } #include <cstddef> for size_t http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:159: return CreateStringIndexBetween(StringIndex(start_string), *this); return StringIndex(start_string).CreateBetween(*this); http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:159: return CreateStringIndexBetween(StringIndex(start_string), *this); Add comment saying that, even though start_string is already < *this, we want to leave some room. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:168: return CreateBetween(StringIndex(end)) http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.cc:169: return CreateStringIndexBetween(*this, StringIndex(end)); Add comment similar to CreateBefore http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.h File chrome/common/string_index.h (right): http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:1: // Copyright (c) 2011 The Chromium Authors. All rights reserved. Thinking about it, a better name for this class would be StringOrdinal, as "index" has multiple meanings. So rename these files to string_ordinal{.h,.cc,_unittest.cc}, and rename this class to StringOrdinal. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:11: // This class allows strings to be used as floating point numbers (in base 26) This class is actually closer to fixed-point than floating-point, but it is neither. Say something like: A StringOrdinal represents a specially-formatted string that can be used for ordering. The StringOrdinal class has an unbounded dense strict total order, which means for any StringOrdinals a, b, and c: - a < b and b < c imply a < c (transitivity); - exactly one of a < b, b < a, and a = b holds (trichotomy); - if a < b, there is a StringOrdinal x such that a < x < b (density); - there are StringOrdinals x and y such that x < a < y (unboundedness). http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:19: // Create a valid StringIndex if the string matches [A-Z]*[B-Z], how about using [a-z]*[b-z] instead? I find lowercase strings easier to read, and we'd be stuck with this format once we start using it. :) http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:19: // Create a valid StringIndex if the string matches [A-Z]*[B-Z], Say something like: Creates a (possibly invalid) StringOrdinal from the given string. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:26: // Returns true iff this was initialized with a string matching [A-Z]*[B-Z]. I think we can omit this comment (since it's just an implementation detail) http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:28: add a comment: // Ordering functions. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:29: // Returns true iff other is a lexicographically smaller StringIndex than The comment is incorrect (backwards). Something like: // Returns true iff |*this| < |other|. (no need to specify implementation details like lexicographic order) http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:33: // Return true iff other has the same value. // Returns true iff |*this| = |other| (i.e., |*this| is neither greater than nor less than |other|). http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:36: // this.LessThan(other) must hold. Returns a StringIndex x such that LessThan( Actually we should relax the precondition to just nonequality. Change comment to: // Given that |*this| != |other|, returns a StringOrdinal x such that min(|*this|, |other|) < x < max(|*this|, |other|). It is an error to call this function with |*this| = |other|. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:40: // Returns a StringIndex x such that x.LessThan(*this) holds. Returns a StringOrdinal x such that x < |*this|. http://codereview.chromium.org/8236002/diff/21001/chrome/common/string_index.... chrome/common/string_index.h:43: // Returns a StringIndex x such that LessThan(x) holds. // Returns a StringOrdinal x such that |*this| < x.
Changes made and I've made the switch to lower case, however as a side effect I had to modify AddHalf because the index values were overflowing and causing incorrect result to enter the system. AddHalf has been fixed but it is now a little more complex due to the potential overflowing issue.
On 2011/10/18 15:04:12, csharp1 wrote: > Changes made and I've made the switch to lower case, however as a side effect I > had to modify AddHalf because the index values were overflowing and causing > incorrect result to enter the system. AddHalf has been fixed but it is now a > little more complex due to the potential overflowing issue. drive-by comment: Could you update the CL description to reflect the actual changes before landing? I.e., it isn't more StringIndex but StringOrdinal, etc...
A meta question: what is the use case of this API? Should we check in code that isn't really used by anyone yet? http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... File chrome/common/string_ordinal_unittest.cc (right): http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:8: TEST(StringOrdinalTest, IsValid) { please, could you wrap this into an unnamed namespace? namespace { ... } // namespace http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:9: StringOrdinal index_ = StringOrdinal("b"); index_ -> index Also can't you create the index object by doing instead: StringOrdinal index("b") ?
On 2011/10/18 17:10:54, tfarina wrote: > A meta question: what is the use case of this API? Should we check in code that > isn't really used by anyone yet? See crbug.com/94662 . It will be used. (As an aside, this CL should have 94662 in BUG=)
More comments http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:19: const int kMidDigitValue = kMidDigit - kZeroDigit; put kMidDigitValue before kMaxDigitValue http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:20: const int kFullDigitValue = (kMaxDigit + 1) - kZeroDigit; #include base/basictypes.h and use COMPILE_ASSERT to check the values of kMaxDigitValue, etc. http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:20: const int kFullDigitValue = (kMaxDigit + 1) - kZeroDigit; a better name would be kRadix, and you can set it to kMaxDigitValue + 1 http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:48: // We can't preform this operation directly on the string because preform -> perform http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:50: int new_position_value = value[position] + kMidDigitValue; do static_cast<int>(value[position]) just to be clear http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:60: value[i] = value[i] - kFullDigitValue; -= http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:68: std::string DropUnneededDigits(std::string value, use const refs to strings instead of passing by value http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:70: CHECK(value > start); CHECK_GT http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:81: // Compute the midpoint string that is between start and end. start -> |start| end -> |end| http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:85: std::string middle_string(max_size, kZeroDigit); middle_string -> midpoint http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:102: // Create a StringOrdinal that is lexigraphically greater than start and start -> |start| end -> |end| http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:103: // lexigraphically less than end, ideally the StringOrdinal will be a "end, ideally" -> "end. The returned StringOrdinal will be roughly between |start| and |end|. http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:104: // middle value between the two StringIndexs. StringOrdinals http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:108: CHECK(end.IsValid()); CHECK(start.LessThan(end)) http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:109: std::string start_string = start.ToString(); use const refs http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:110: std::string end_string = end.ToString(); here, too http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:113: std::string middle_string = ComputeMidpoint(start_string, end_string); middle_string -> midpoint http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:166: CHECK(other.IsValid()); CHECK(!Equal(other)) http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:179: std::string start_string = std::string(length, kZeroDigit); start_string -> start (to be consistent with CreateAfter() http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:179: std::string start_string = std::string(length, kZeroDigit); don't do std::string foo = std::string(...), just do std::string foo(...); http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:186: // Even though start_string is already a valid StringOrdinal that is less |start_string| http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:187: // than *this, we don't return it because we wouldn't have much space in |*this| http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:189: return StringOrdinal(start_string).CreateBetween(*this); can actually just do: return CreateBetween(StringOrdinal(start)) http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:194: std::string end = std::string(string_index_.length(), kMaxDigit); std::string end(...) http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:199: // Even though end is already a valid StringOrdinal that is greater than |end| http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:200: // *this, we don't return it because we wouldn't have much space after |*this| http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:205: std::string StringOrdinal::ToString() const { CHECK(is_valid_) http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:14: // a < b and b < c implies a < c (transitivity); Please preserve bullets and newlines around them like I had in my comment http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:18: // This means that when StringOrdinal is used for sorting a list, if extra space after bullets and before this paragraph http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:20: // has to change to represent the new order, all the other older values can stay "order, all" -> "order, and all" http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:25: explicit StringOrdinal(const std::string& str); str -> string_ordinal http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:31: Add comment saying all other functions can only be called if IsValid() holds http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:34: // Returns true iff |*this| < |other| period at end http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:37: // Return true iff |*this| == |other| (ie this->LessThan(other) and ie -> i.e., http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:42: // min(|*this|, |other|).LessThan(x) holds, and use min(...) < ... < max(...) like in my suggested comment. (You already do so for LessThan and CreateBefore and CreateAfter, so we should be consistent.) http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:44: // this function with |*this| == |other| period at end. http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:53: std::string ToString() const; // It is guaranteed that a StringOrdinal constructed from the returned string will be valid. http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal.h:58: std::string string_index_; rename this variable to string_ordinal_ http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... File chrome/common/string_ordinal_unittest.cc (right): http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:10: EXPECT_TRUE(index_.IsValid()); you can just do EXPECT_TRUE(StringOrdinal(...).IsValid()) etc. http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:23: StringOrdinal small = StringOrdinal("b"); const StringOrdinal small(...); etc. http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:48: make sure to test the other direction, too http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:129: TEST(StringOrdinalTest, CrateBetweenLargeValueFirst) { Crate -> Create http://codereview.chromium.org/8236002/diff/25001/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:133: result = StringOrdinal("zzz").CreateBetween(StringOrdinal("aaz")); indent
Latest version upload with changes made in response to comment.
On 2011/10/18 19:05:53, csharp1 wrote: > Latest version upload with changes made in response to comment. Sorry, I didn't see your latest e-mail. :( I'll take a look ASAP.
Looking much better. Few more comments. http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:28: // Remove all trailing zeros from a value as they provide no value. zeros -> zero digits http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:29: std::string RemoveTrailingZeros(const std::string& value) { Make this a destructive operation, like: void RemoveTrailingZeros(std::string* value) { ... value->resize(end_position + 1); } http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:72: std::string DropUnneededDigits(const std::string& value, make this a destructive operation, also, so: void DropUnneededDigits(std::string* value, const std::string& start, const std::string& end) { ... } http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:76: std::string shorter_value = value.substr(0, value.length() - 1); it's possible that it may be enough to remove the trailing zeros first. Maybe something like: RemoveTrailingZeros(value); if ((start.length == end.length()) && (value->length() > (start.length() + 1)) || (value->compare(0, start.length(), start) > 0))) { // start and end are the same length, value adds an extra digit, but dropping the digit will still keep start < *value < end. value->resize(start.length()); RemoveTrailingZeros(value); } (clean up the code and comments above, it's just a rough sketch) http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:102: DCHECK(!add_half); here http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:125: return StringOrdinal(midpoint); Do; StringOrdinal midpoint_ordinal(midpoint); DCHECK(midpoint_ordinal.IsValid()); return midpoint_ordinal; http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:183: // Create the smallest, valid StringOrdinal to be the minimum boundary. no comma between 'smallest' and 'valid' StringOrdinal -> StringOrdinal of the appropriate length http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:200: std::string end(string_ordinal_.length(), kMaxDigit); Add a comment similar to CreateBefore(); // Create the largest valid StringOrdinal of the appropriate length to be the maximum boundary. http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:14: // - a < b and b < c implies a < c (transitivity); add extra line before, and indent each bullet 2 spaces. So: // ...a, b, and c: // // - a < b and .. // - ... // - there are ... // // This... http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:46: // min(|*this|, |other|) < x < max(|*this|,|other|). It is an error space after comma
http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.cc:72: std::string DropUnneededDigits(const std::string& value, On 2011/10/20 05:25:49, akalin wrote: > make this a destructive operation, also, so: > > void DropUnneededDigits(std::string* value, const std::string& start, const > std::string& end) { > ... > } Output parameters should be at the end of parameter list. http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Functi...
http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:29: StringOrdinal(); I think it would be less confusing to have an Invalid() static function that returns StringOrdinal for is_valid_ equal false. http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:60: // Use of copy constructor and default assignment for this class is allowed. Please, move this to the end of the private section, where we normally place DISALLOW_COPY_AND_ASSIGN macro. http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:63: std::string string_ordinal_; Can you document this two vars? http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:64: bool is_valid_; can you make this const? http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:66: #endif // CHROME_COMMON_STRING_ORDINAL_H_ please add a blank line above.
Changes made and code update. Only thing I'm not certain of is the change I made to DropUnneeded Digits, added an inline comment for it. http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:72: void DropUnneededDigits(const std::string& start, I ended up taking a different approach to how we drop digit here because the initial idea akalin@ suggested runs into some problems when the start and end string have different lengths. After playing around with a few different ideas I think that the best (and clearest) solution might just be to see if we can drop a single digit, regardless of the length of the various parts. While this won't always give the best answers (CreateAfter("YZ") returns Z) it gives good answers most of the time without being too complex. http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.h:67: bool is_valid_; As stated earlier in the review we can't make either variable const because then we would be unable to make assignments.
http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:14: // Constants I think you can remove this comment. if not, please add a blank line above. http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:39: remove extra line. http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:50: DCHECK_GT(position, static_cast<size_t>(0)); instead of static_cast<size_t>, 0U? http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:141: if (value.empty()) { no need of {} in single-line statements, here and elsewhere. http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:151: return (value[value.length() - 1] != kZeroDigit); no need of parentheses here. http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:153: } // namespace add a blank line above. http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:156: : string_ordinal_(string_ordinal), indent this 4 spaces.
Changes made and uploaded. On 2011/10/20 14:54:35, tfarina wrote: > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > File chrome/common/string_ordinal.cc (right): > > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:14: // Constants > I think you can remove this comment. if not, please add a blank line above. > > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:39: > remove extra line. > > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:50: DCHECK_GT(position, static_cast<size_t>(0)); > instead of static_cast<size_t>, 0U? > > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:141: if (value.empty()) { > no need of {} in single-line statements, here and elsewhere. > > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:151: return (value[value.length() - 1] != > kZeroDigit); > no need of parentheses here. > > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:153: } // namespace > add a blank line above. > > http://codereview.chromium.org/8236002/diff/38002/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:156: : string_ordinal_(string_ordinal), > indent this 4 spaces.
Thaigo, do you mind if I handle this review alone? Too many cooks and all. http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:29: StringOrdinal(); On 2011/10/20 13:02:36, tfarina wrote: > I think it would be less confusing to have an Invalid() static function that > returns StringOrdinal for is_valid_ equal false. I disagree. Negative tests are confusing. http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:60: // Use of copy constructor and default assignment for this class is allowed. On 2011/10/20 13:02:36, tfarina wrote: > Please, move this to the end of the private section, where we normally place > DISALLOW_COPY_AND_ASSIGN macro. I disagree. This is part of the public interface. http://codereview.chromium.org/8236002/diff/30003/chrome/common/string_ordina... chrome/common/string_ordinal.h:64: bool is_valid_; On 2011/10/20 13:02:36, tfarina wrote: > can you make this const? Can't, to keep it assignable.
http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:47: // the previous index values had an odd difference, so their correct difference -> midpoint their correct -> its correct http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.cc:80: std::string shorter_value = value->substr(0, value->length() - 1); hmm, i still don't like having to create this temp string What about change RemoveTrailingZeros() to: // Returns the last position before the given length that has a non-zero digit. size_t GetLastNonZeroPosition(const std::string& str, size_t length); and then DropUnneededDigits can be: size_t drop_length = GetLastNonZeroPosition(*value, value->length()); if (drop_length > 1) { // We must ... const size_t truncated_length = GetLastNonZeroPosition(*value, drop_length - 1); // If the truncated value is still greater than |start|, then use it. if (value->compare(0, truncated_length, start) < 0) { drop_length = truncated_length; } } value->resize(drop_length); http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:21: // any item changes its position in the list, only its StringOrinal value Orinal -> Ordinal http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:29: // Create an invalid StringOrdinal. please revert this back to the default constructor (it's worth noting that the default constructor is still around, but then it leaves the value of is_valid_ uninitialized :( ) http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:42: // Return true iff |*this| == |other| (i.e. this->LessThan(other) and say (i.e., |*this| < |other| and |*this| > |other| are both false) http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:48: // to call this function with |*this| == |other|. with -> when http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:51: // Returns a StringOrdinal x such that x < |*this|. x -> |x| http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:54: // Returns a StringOrdinal x such that |*this| < x. x -> |x| http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:62: // The value of the StringOrdinal. value -> string representation http://codereview.chromium.org/8236002/diff/40001/chrome/common/string_ordina... chrome/common/string_ordinal.h:65: // The validity of the StringOrdinal (is it of the format [a-z]*[b-z]), "is it" -> "i.e., is it"
LGTM after comments and green tryjobs http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:38: return end_position + 1; ah I was confused, this should be renamed to "GetNonZeroLength" (or something like that) and the comment changed to "Returns the length the given string would have with all trailing zeros removed." http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:72: std::string* value) { can't this fit on previous line? http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal.h:26: // Create a StringOrdinal from the given string. It may be valid or invalid. Create -> Creates http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal.h:29: // Create an invalid StringOrdinal. Creates http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal.h:37: // Ordering Functions What about "Order-related functions" http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal.h:42: // Return true iff |*this| == |other| (i.e. |*this| < |other| and Return -> Returns http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... File chrome/common/string_ordinal_unittest.cc (right): http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:11: // on the small_value with the large_value as the parameter and two spaces before 'parameter' -> one space http://codereview.chromium.org/8236002/diff/43002/chrome/common/string_ordina... chrome/common/string_ordinal_unittest.cc:13: void TestCreateBetween(StringOrdinal small_value, move this fn closer to where it's used
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/csharp@chromium.org/8236002/42007
The commit queue went berserk retrying too often for a seemingly flaky test. Builder is linux_rel, revision is 106909, job name was 8236002-42007 (previous was lost) (previous was lost) (previous was lost) (previous was lost).
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/csharp@chromium.org/8236002/42007
Some drive by comments, helping find why the win try bots were failing... BYE MAD http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.cc:35: while (value[end_position] == kZeroDigit) { Check for end_position > 0 http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.cc:50: DCHECK_GT(position, 0U); Also check that position is LT size... http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.cc:63: CHECK_GT(i, 0U); So we crash when all previous values have reached max??? http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.h:17: // - if a < b, there is a StringOrdinal x such that a < x < b (density); I don't think you can confirm infinite density...
Chris, can you fix these in a separate CL? http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.cc:35: while (value[end_position] == kZeroDigit) { On 2011/10/25 15:13:29, MAD wrote: > Check for end_position > 0 Ah, right. The implicit cast to int is gross, too. This should probably look like: while ((length > 0) && (value[length - 1] == kZeroDigit) { --length; } return length; http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.cc:63: CHECK_GT(i, 0U); On 2011/10/25 15:13:29, MAD wrote: > So we crash when all previous values have reached max??? Yeah, you're right. This should probably return a carry bit and the caller can check that instead (I don't think it's possible to actually hit this case with the caller) http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.h File chrome/common/string_ordinal.h (right): http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.h:17: // - if a < b, there is a StringOrdinal x such that a < x < b (density); On 2011/10/25 15:13:29, MAD wrote: > I don't think you can confirm infinite density... I don't know what you mean by 'infinite' density, but density is exactly the property listed here.
Oops, didn't realize this hasn't been checked in yet. I guess fix it in this one. On 2011/10/25 17:22:19, akalin wrote: > Chris, can you fix these in a separate CL? > > http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... > File chrome/common/string_ordinal.cc (right): > > http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:35: while (value[end_position] == kZeroDigit) { > On 2011/10/25 15:13:29, MAD wrote: > > Check for end_position > 0 > > Ah, right. The implicit cast to int is gross, too. This should probably look > like: > > while ((length > 0) && (value[length - 1] == kZeroDigit) { > --length; > } > > return length; > > http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... > chrome/common/string_ordinal.cc:63: CHECK_GT(i, 0U); > On 2011/10/25 15:13:29, MAD wrote: > > So we crash when all previous values have reached max??? > > Yeah, you're right. This should probably return a carry bit and the caller can > check that instead (I don't think it's possible to actually hit this case with > the caller) > > http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.h > File chrome/common/string_ordinal.h (right): > > http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... > chrome/common/string_ordinal.h:17: // - if a < b, there is a StringOrdinal x > such that a < x < b (density); > On 2011/10/25 15:13:29, MAD wrote: > > I don't think you can confirm infinite density... > > I don't know what you mean by 'infinite' density, but density is exactly the > property listed here.
Yeah, we were not able to commit it because of try bot errors, and so I looked at the code to find where the error was... While waiting for the unit test to build on my machine and run them... Sometimes a code review is faster than a build and run tests... :-) On Tue, Oct 25, 2011 at 1:22 PM, <akalin@chromium.org> wrote: > Oops, didn't realize this hasn't been checked in yet. I guess fix it in > this > one. > > > On 2011/10/25 17:22:19, akalin wrote: > >> Chris, can you fix these in a separate CL? >> > > > http://codereview.chromium.**org/8236002/diff/42007/chrome/** > common/string_ordinal.cc<http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.cc> > >> File chrome/common/string_ordinal.**cc (right): >> > > > http://codereview.chromium.**org/8236002/diff/42007/chrome/** > common/string_ordinal.cc#**newcode35<http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.cc#newcode35> > >> chrome/common/string_ordinal.**cc:35: while (value[end_position] == >> kZeroDigit) >> > { > >> On 2011/10/25 15:13:29, MAD wrote: >> > Check for end_position > 0 >> > > Ah, right. The implicit cast to int is gross, too. This should probably >> look >> like: >> > > while ((length > 0) && (value[length - 1] == kZeroDigit) { >> --length; >> } >> > > return length; >> > > > http://codereview.chromium.**org/8236002/diff/42007/chrome/** > common/string_ordinal.cc#**newcode63<http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.cc#newcode63> > >> chrome/common/string_ordinal.**cc:63: CHECK_GT(i, 0U); >> On 2011/10/25 15:13:29, MAD wrote: >> > So we crash when all previous values have reached max??? >> > > Yeah, you're right. This should probably return a carry bit and the >> caller >> > can > >> check that instead (I don't think it's possible to actually hit this case >> with >> the caller) >> > > > http://codereview.chromium.**org/8236002/diff/42007/chrome/** > common/string_ordinal.h<http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.h> > >> File chrome/common/string_ordinal.h (right): >> > > > http://codereview.chromium.**org/8236002/diff/42007/chrome/** > common/string_ordinal.h#**newcode17<http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordinal.h#newcode17> > >> chrome/common/string_ordinal.**h:17: // - if a < b, there is a >> StringOrdinal x >> such that a < x < b (density); >> On 2011/10/25 15:13:29, MAD wrote: >> > I don't think you can confirm infinite density... >> > > I don't know what you mean by 'infinite' density, but density is exactly >> the >> property listed here. >> > > > > http://codereview.chromium.**org/8236002/<http://codereview.chromium.org/8236... >
Ok, the bug has been fixed. I slightly changed the way the code removes the trailing zeros by using std::string::find_last_not_of instead of manual looping over the string. http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/42007/chrome/common/string_ordina... chrome/common/string_ordinal.cc:63: CHECK_GT(i, 0U); We would, but this case can't occur. For this to occur the digit infront would need to be kMaxDigit, but it also needed to require an extra digit to represent the difference between the two digits it used as input, so it's input can't be (kMaxDigit, kMaxDigit). This means the inorder for it to still have the value of kMaxDigit, add half needed to be called on it as well. The same argument applies and all digits would require addhalf to be called on them, however the first digit can never have addhalf called on it (because there is no digit before), so it can't make addhalf added to the next value and also have the value kMaxDigit, so we never have this case. Hopefully I did ok job of explaining it, took me a few rewrite to get it sounding better.
Ok, I add an extra test that uses the internal loop in AddHalf a few times and also added a comment explaining why the program should fail if we have i == 0.
Still LGTM. Are the trybots still failing? Can you give a link to the failing runs? This CL shouldn't affect anything but its own unittests. ??:( http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:34: size_t end_position = value.find_last_not_of(kZeroDigit, length - 1); if you want to consider the entire string, just omit the 2nd argument http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:113: // AddHalf only returns false if (midpoint[0] > kMaxDigit) and it Just say that AddHalf() returning false implies that the midpoint of two strings in [0, 1) is >= 1, which is a contradiction.
Yeah, it was just it's own unit test that was failing on Windows because of an STL assert that the index was valid and we were passing a negative index... Which is fixed now, so I'm guessing the try/commit bots should succeed this time... On Wed, Oct 26, 2011 at 2:36 PM, <akalin@chromium.org> wrote: > Still LGTM. > > Are the trybots still failing? Can you give a link to the failing runs? > This > CL shouldn't affect anything but its own unittests. ??:( > > > http://codereview.chromium.**org/8236002/diff/52002/chrome/** > common/string_ordinal.cc<http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordinal.cc> > File chrome/common/string_ordinal.**cc (right): > > http://codereview.chromium.**org/8236002/diff/52002/chrome/** > common/string_ordinal.cc#**newcode34<http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordinal.cc#newcode34> > chrome/common/string_ordinal.**cc:34: size_t end_position = > value.find_last_not_of(**kZeroDigit, length - 1); > if you want to consider the entire string, just omit the 2nd argument > > http://codereview.chromium.**org/8236002/diff/52002/chrome/** > common/string_ordinal.cc#**newcode113<http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordinal.cc#newcode113> > chrome/common/string_ordinal.**cc:113: // AddHalf only returns false if > (midpoint[0] > kMaxDigit) and it > Just say that AddHalf() returning false implies that the midpoint of two > strings in [0, 1) is >= 1, which is a contradiction. > > http://codereview.chromium.**org/8236002/<http://codereview.chromium.org/8236... >
Updated some comments and I'll try submitting this again tomorrow morning. Hopefully it'll go through this time :) http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordina... File chrome/common/string_ordinal.cc (right): http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:34: size_t end_position = value.find_last_not_of(kZeroDigit, length - 1); We don't want to always consider the entire string, because we might want to ignore the last section of the string. On 2011/10/26 18:36:42, akalin wrote: > if you want to consider the entire string, just omit the 2nd argument http://codereview.chromium.org/8236002/diff/52002/chrome/common/string_ordina... chrome/common/string_ordinal.cc:113: // AddHalf only returns false if (midpoint[0] > kMaxDigit) and it On 2011/10/26 18:36:42, akalin wrote: > Just say that AddHalf() returning false implies that the midpoint of two strings > in [0, 1) is >= 1, which is a contradiction. Done.
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/csharp@chromium.org/8236002/57001
Change committed as 107566 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
