From: "Hal E. Fulton" Date: 2003-05-28T06:35:11+09:00 Subject: Re: Binary Tree vs. Hash ----- Original Message ----- From: "Robert Klemme" Newsgroups: comp.lang.ruby To: "ruby-talk ML" Sent: Tuesday, May 27, 2003 11:49 AM Subject: Re: Binary Tree vs. Hash [snip discussion of "sorted" flag for arrays] I can see both sides of this. I think the original idea has some merit. As I see it, the @sorted flag would be set only when a sort was done, and it would be unset when any operation was done NOT guaranteeing preservation of sorting. This would make me want an "insert" operation that would add an element and preserve the sorting. (slice already preserves the state, since it operates only on contiguous items.) One problem I see is the potential ambiguity of "sorted" -- we can apply any sorting technique we like to an array, right? And not all of these are conducive to a speedup unless we do an internal Schwartzian transform. An overall better approach might be a SortedArray inheriting from Array -- it could even have its own definitions of << and so on that would preserve sorting. And the method of sorting would (could/ should/might?) be fixed on an instance basis. Just my $0.02, Hal