On a related point: what would have happened had Bloch not been able to come up with a rangeCheck function quickly?
Would Google have stopped Android from shipping until it was complete? It's more likely they would have just left it as a bug to be fixed later.
Bashing it out cowboy style would have been faster and in no way harmed Android. It's Oracle's codebase he was spending time and energy improving with good engineering practice.
My point is specifically related to Oracle's claim that Android couldn't have shipped without a rangeCheck() function, which is patently nonsense.
That this is the only direct copyright infringement they could find is highly ironic, but I guess either the lawyers didn't understand the subtleties here, or thought the jury wouldn't as this argument wasn't made (except obliquely in Bloch's statements).
There might be a nine line function that takes a day or two to get right, but for even a bad programmer, rangeCheck would take a few minutes. With thorough tests, maybe ten minutes. I've barely touched Java code in over a decade, but I could write that function -- with tests -- in less than two minutes.
RangeCheck is the kind of function you'd get on a quiz in your first week of your first CS class in college.
I really thought Oracle couldn't surprise me, but they keep getting to new lows.
The ubiquitous "gotchas" in binary search are well documented; Jon Bentley did a talk on it. At Google, if memory serves.
A set of tests took me about 6 minutes.
Programming takes time... which is why it's so powerful if you can reuse code (as Bloch did), and even better if you can find a way to reduce the code needed, or best, to avoid needing any code.
sub rangeCheck {
my ($len, $from, $to) = @_;
if (($from > $to) || ($from < 0) || ($to > $len)) {
die "Illegal index $len ($from / $to)";
}
}
As it happens I've recently written somewhat similar code in Perl where I want to explicitly deal with out-of-range accesses (in a way other than silently receiving undefs) in a particular case, so this isn't even that odd.
private static void rangeCheck(int length, int fromIndex, int toIndex) {
if (fromIndex > toIndex || fromIndex < 0 || toIndex > length)
throw new Exception("Illegal index");
}All this reminds me of people saying that could code stackoverflow or facebook in a weekend. The difference is that rangeCheck actually is trivial - it's just that it's easy to underestimate the work involved in coding something. Even something trivial.
I know. I reduced it to one generic exception because that is what the person I was replying to did. Bloch's version is better of course.
I think in defining a range, the toIndex means up-to-but-not-including the element at that index. Thus, to include the full array, you'd use the range fromIndex=0, toIndex=length (one past the last one, since the index of the last element is length-1). With this notation, you can then make ranges of any width, from 0 up to length. If instead you included the element at that index, you couldn't have 0-width ranges (unless you allowed toIndex to equal one less than fromIndex).
I don't know whether 0-width ranges are directly useful for the Timsort algorithm; or whether it's just a convenient notation that happens to have that ability as an unused side-effect.
Thus, if we do suppose that Android was accelerated two days, the benefit wasn't $6 million - it was having that money in hand a little earlier. The interest on $3 million for a day at 7% pa is $575/day - or $1725 total. Or less money than it costs Oracle's counsel to sneeze.
From that, it's not remotely clear whether saving 2 days to beta would have even resulted in 2 days of savings in the creation of any device.
To say nothing of whether Google/TMobile/HTC pre-selected a launch date in advance for the Dream, in which case they easily may have squandered a handful of days waiting for their desired PR timing.
All it means is you'd have had to allocate two more days worth of some programmer's time away from some less important task. For something like this, the programmer wouldn't even need to know thing one about the Android project - just that "we need our own implementation of this standard Java function".
I don't like the idea of court video that much...bad memories of the OJ trial.
Parallelization is limited similarly to http://en.wikipedia.org/wiki/Amdahl%27s_law (usually called critical path when applied to development). I don't know the dependencies for this code, though it is part of a sort (Timsort) which was likely used by a few things, being a utility. As for test code, although TDD advocates doing it first, it's not a functional dependency. But, given the crucial importance of compatibility in this situation (reverse-engineering standard libraries), you might well want it first, to catch problems ASAP when they are cheaper to fix.
> Q. Why did you copy the rangecheck function for Timsort?
> A. It's good engineering to reuse the same function if possible
BTW: Some other people are responding without reading fully - please take the time to do so. It elevates the discussion, making it interesting and engaging. I am really delighted to be shown wrong and to learn something, but it's hard for a response to a comment to be persuasive if it doesn't address that comment.
I'm sure there are more than 200 developers, so that lost person day would mean much less than $150,000 in lost profits.
Actually, that's not entirely true. If you swapped the "hi" and "lo" parameters, the function would return an unmodified array if rangeCheck were taken out, rather than throwing an exception. But that's the only functional change.
So the idea that rangeChange is in any way significant is disingenuous at best, I think.
To answer Groklaw's final question as to why Alsup couldn't decide on API copyrightability yet, he clearly said he needed to do a lot of reading. He not only has to decide according to law, he is in effect creating law, since this specific issue hasn't been decided earlier. His ruling has wider significance than just this particular case. Future potential litigants will read his ruling, and will avoid court if it's clear who would win. Although he is only one judge and so his precedent won't be binding on a full bench/higher court, those judges would also carefully read his judgment. He'd better get it right, not only in the result, but in the reasoning, and integrating it with related cases.
It's great that Groklaw is making these transcripts - because the court is a public institution, I think the official transcripts should be available (and why not video too? The emphasis in oral argument sometimes isn't captured in a transcript.)