Stop using LinkedList in TrieParser and most of our tests

[cpovirk]

I just noticed that we use it in TrieParser -- particularly egregious because IIRC that code exists largely to help on GWT, where I would assume LinkedList is even more terrible.

We might not be using it anywhere else (in public Guava, at least), except:

• in tests (which we might as well also fix)
• in GWT *TreeTraverser (and I forget what the situation is with GWT... we could probably roll our own ArrayDeque there, but probably we shouldn't bother)

For a time, Java 5 / Froyo compatibility kept us from using ArrayDeque. But now we can use it, and we should. (But we probably should never have used LinkedList, anyway. For example, TrieParser could probably use ArrayList if it were written to modify the end of the list instead of the beginning.)

[cpovirk]

Oh, obviously TrieParser has the same GWT problem with using ArrayDeque as *TreeTraverser does. And it does look like ArrayDeque is unavailable there.

We could still use ArrayList, but I note that TrieParser calls join(stack), so we'd need to use Lists.reverse to view it in the proper order. That's possibly still worth doing, but maybe we should just do the ArrayDeque emulation....

[cpovirk]

Alternatively, we could operate on the end of the list as I suggested above but then reverse the result when we're done. That might be better than what we do now, which is to operate on the beginning of the list and reverse every individual chunk in place.

[cpovirk]

I have a working CL, but I feel bad about it, partially because I can see a way to do even better and partially because I have no idea if I'm addressing a real bottleneck here. I'll abandon it for now.

[cpovirk]

We took a lot of these out, but we have some left.

[jrtom]

Note that it's probably not worth much effort to mess with TreeTraverser because that's hopefully going to be deprecated in the next release in favor of the new common.graph-based Traverser.

[cpovirk]

Looks like LineReader, too? Not sure why I would have skipped that.

[MykolaBova]

Hi Team! Is it still important to fix? Is it a good fix for beginner to work on?

[cpovirk]

It's not urgent or critical, just nice to fix someday. If you're lucky, you may be able to just replace LinkedList with ArrayDeque nowadays, as it looks like ArrayDeque is now available under all environments that we target, including GWT (since 2.8.0, which I believe is what we already require). I'd be happy to have a look at a PR.

[alvalov]

Hi! We are a group of five students (me, Olof, Joakim, Caroline, Robin) taking a course in which we are to solve issues, can we take on this one?

@MykolaBova Have you started work on this?