- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
linked lists in collection libraries
Thu, 2009-09-10, 10:51
Linked lists as they are implemented now and collection libraries
simply do not fit. We can't have a test of isEmpty and at the same
time implement empty linked lists with null. In my mind, using null
for an empty linked list has to go. Right now, we have compromised
method sameElements in LinearSequenceTample to deal with null for
empty lists, so that test t2212 passes. This is definitely not the way
to do it (for once there remain many other operations that crash at an
empty linked list). I removed the hack in sameElements and will
disable test t2212 for the time being.
What's needed rather urgently is:
Put in new linked lists which do not rely on null for an empty
element. An elegant way to do this is to use
a circular list with a header field. So the list xs is empty if
xs.next eq xs. If, furthermore, if you let the list reference always
point to the last node of the ring, then insertions at the beginning
and end are both very fast. So it's an ideal structure for queues.
Anybody wants to redesign this part of collections?
Classes affected would be:
LinkedList
DoubleLinkedlist
MutableList
Queue
LinkedListTemplate
Cheers
Thu, 2009-09-10, 13:27
#2
Re: linked lists in collection libraries
Paul, If you wouldn't mind holding off a few days I'd like to take a crack at it. It seems like it would be beneficial to spread the collections knowledge around a bit and this doesn't sound like too hard of a task (famous last words). I'll be on IRC over the weekend to pester you with questions.
-Erik
On Thu, Sep 10, 2009 at 8:08 AM, Paul Phillips <paulp@improving.org> wrote:
--
http://erikengbrecht.blogspot.com/
-Erik
On Thu, Sep 10, 2009 at 8:08 AM, Paul Phillips <paulp@improving.org> wrote:
On Thu, Sep 10, 2009 at 11:51:19AM +0200, martin odersky wrote:
> Anybody wants to redesign this part of collections?
Not that I'm running out of stuff to do, but I know the collections (and
these classes in particular) well enough now to do it reasonably
quickly, so I'll do it unless someone calls me off in the near future.
--
Paul Phillips | All men are frauds. The only difference between
Future Perfect | them is that some admit it. I myself deny it.
Empiricist | -- H. L. Mencken
pp: i haul pills |----------* http://www.improving.org/paulp/ *----------
--
http://erikengbrecht.blogspot.com/
Thu, 2009-09-10, 13:47
#3
Re: linked lists in collection libraries
On Thu, Sep 10, 2009 at 08:20:33AM -0400, Erik Engbrecht wrote:
> Paul, If you wouldn't mind holding off a few days I'd like to take a
> crack at it. It seems like it would be beneficial to spread the
> collections knowledge around a bit and this doesn't sound like too
> hard of a task (famous last words). I'll be on IRC over the weekend
> to pester you with questions.
You are the proud new father of several baby collections. Have a cigar.
Thu, 2009-09-10, 16:47
#4
Re: linked lists in collection libraries
On Thu, Sep 10, 2009 at 5:39 AM, Paul Phillips <paulp@improving.org> wrote:
On Thu, Sep 10, 2009 at 08:20:33AM -0400, Erik Engbrecht wrote:
> Paul, If you wouldn't mind holding off a few days I'd like to take a
> crack at it. It seems like it would be beneficial to spread the
> collections knowledge around a bit and this doesn't sound like too
> hard of a task (famous last words). I'll be on IRC over the weekend
> to pester you with questions.
You are the proud new father of several baby collections. Have a cigar.
Is this one of those Bugs Bunny exploding cigars?
--
Paul Phillips | Eschew mastication.
Stickler |
Empiricist |
pal, i pill push |----------* http://www.improving.org/paulp/ *----------
--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Git some: http://github.com/dpp
Thu, 2009-09-10, 19:27
#5
Re: linked lists in collection libraries
On Thursday September 10 2009, David Pollak wrote:
> On Thu, Sep 10, 2009 at 5:39 AM, Paul Phillips wrote:
> > ...
> >
> > You are the proud new father of several baby collections.
> > Have a cigar.
>
> Is this one of those Bugs Bunny exploding cigars?
Or maybe one of the CIA's Castro-killing exploding cigars?
RRS
On Thu, Sep 10, 2009 at 11:51:19AM +0200, martin odersky wrote:
> Anybody wants to redesign this part of collections?
Not that I'm running out of stuff to do, but I know the collections (and
these classes in particular) well enough now to do it reasonably
quickly, so I'll do it unless someone calls me off in the near future.