Deques?

On Sunday March 22 2009, Randall R Schulz wrote:
> Hi,
>
> ...
>
> Am I overlooking a way to get a deque with uniform access methods?

Indeed I was: scala.collection.mutable.DoubleLinkedList

Randall Schulz

On Sunday March 22 2009, Randall R Schulz wrote:
> On Sunday March 22 2009, Randall R Schulz wrote:
> > Hi,
> >
> > ...
> >
> > Am I overlooking a way to get a deque with uniform access methods?
>
> Indeed I was: scala.collection.mutable.DoubleLinkedList

Except that's an abstract type.

Since my need at the moment is to implement a tree-traversal method can
can be invoked for either depth-first or breadth-first traversal, I'll
just split it up into two separate implementations, one using a stack
and the other using a queue.

Randall Schulz

Hi,

There are two mutable Deque implementations in Java 1.6. The array
backed one is fast.

-Henry

On Sun, Mar 22, 2009 at 1:01 PM, Randall R Schulz wrote:
> On Sunday March 22 2009, Randall R Schulz wrote:
>> On Sunday March 22 2009, Randall R Schulz wrote:
>> > Hi,
>> >
>> > ...
>> >
>> > Am I overlooking a way to get a deque with uniform access methods?
>>
>> Indeed I was: scala.collection.mutable.DoubleLinkedList
>
> Except that's an abstract type.
>
> Since my need at the moment is to implement a tree-traversal method can
> can be invoked for either depth-first or breadth-first traversal, I'll
> just split it up into two separate implementations, one using a stack
> and the other using a queue.
>
>
> Randall Schulz
>

Randall R Schulz schrieb:
> As far as I can tell, there's no deque data structure / collection in
> the Scala library.

This was discussed last month, I mentioned
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451
(everybody would be grateful if you contributed a deque based on that)
and there was:
http://www.nabble.com/Why-is-List%3A%2B-deprecated--tt22228254.html#a223...

- Florian.

On Monday March 23 2009, Florian Hars wrote:
> Randall R Schulz schrieb:
> > As far as I can tell, there's no deque data structure / collection
> > in the Scala library.
>
> This was discussed last month, I mentioned
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451
> (everybody would be grateful if you contributed a deque based on
> that) and there was:
>

Thanks for the reference. I'm too much the rank amateur to try to
produce a proper implementation of a class for the Scala collections
library. And when I venture in, it will probably be to do a multiset
and a multimap, since I use those quite a lot (I wrote Java versions
once upon a time)

> - Florian.

Randall Schulz

On Monday March 23 2009, Florian Hars wrote:
> Randall R Schulz schrieb:
> > As far as I can tell, there's no deque data structure / collection
> > in the Scala library.
>
> This was discussed last month, I mentioned
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451
> ...

It looks like this is the official / final publication of that paper:

- "Purely functional, real-time deques with catenation"

> - Florian.

Randall Schulz

Randall R Schulz schrieb:
> It looks like this is the official / final publication of that paper:

ACM paywall junk :-(

- Florian.

On Monday March 23 2009, Florian Hars wrote:
> Randall R Schulz schrieb:
> > It looks like this is the official / final publication of that
> > paper:
>
> ACM paywall junk :-(

Excuse me?

> - Florian.

Randall Schulz

You have to have an ACM subscription to access the full paper...

People at universities or workplaces with corporate subscriptions probably won't notice, but people at home will...

On Mon, Mar 23, 2009 at 12:57 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Monday March 23 2009, Florian Hars wrote:
> Randall R Schulz schrieb:
> > It looks like this is the official / final publication of that
> > paper:
>
> ACM paywall junk :-(

Excuse me?


> - Florian.


Randall Schulz

--
http://erikengbrecht.blogspot.com/

On Monday March 23 2009, Erik Engbrecht wrote:
> You have to have an ACM subscription to access the full paper...

And that makes it "junk?"

The LNCS and LNAI series as well as several other journals are beyond
both my personal subscriptions and my university library's online
subscriptions, but I don't consider them junk. More like forbidden
fruit...

Randall Schulz

As always, scholar.google.com is your friend:

http://www.math.tau.ac.il/~haimk/adv-ds-2000/jacm-final.pdf

On Monday March 23 2009, Dave Griffith wrote:
> As always, scholar.google.com is your friend:

I agree. During certain phases of my work, I spend hour after hour—even
day after day—with Google Scholar. And when there's a prepublication
draft of a paper that is not accessible to me in its final / official
form, I'll certainly make do with that.

I only pointed out the official publication 'cause it was exactly that.

> http://www.math.tau.ac.il/~haimk/adv-ds-2000/jacm-final.pdf

Here you can see all the versions of that paper that Google Scholar has
indexed:

Often there is a PostScript version as well as (or instead of) the PDF.
I've found that the open-source PostScript to PDF conversion software
frequently produces files that render properly (on-screen and on a
printer) but cannot be searched and / or copied from due to some kind
of encoding anomaly. In those cases, I convert the PostScript to PDF
using Adobe Acrobat. Most of the time, this yields a PDF for which
searching and copying works.

Randall Schulz

Scala includes an implementation of MultiMap.

  import scala.collection.mutable.{Set, MultiMap, HashMap}

  case class Person(name: String)
  case class Fruit(name: String)

  val favorites = new HashMap[Person, Set[Fruit]] with MultiMap[Person, Fruit]

  favorites.add(Person("Jorge"), Fruit("Strawberries"))
  favorites.add(Person("Jorge"), Fruit("Mangos"))
  favorites.add(Person("Jorge"), Fruit("Apples"))

  favorites(Person("Jorge"))
    == Set(Fruit(Apples), Fruit(Mangos), Fruit(Strawberries))

--j

On Mon, Mar 23, 2009 at 6:40 AM, Randall R Schulz <rschulz@sonic.net> wrote:

On Monday March 23 2009, Florian Hars wrote:
> Randall R Schulz schrieb:
> > As far as I can tell, there's no deque data structure / collection
> > in the Scala library.
>
> This was discussed last month, I mentioned
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451
> (everybody would be grateful if you contributed a deque based on
> that) and there was:
><http://www.nabble.com/Why-is-List%3A%2B-deprecated--tt22228254.html#a22388476>

Thanks for the reference. I'm too much the rank amateur to try to
produce a proper implementation of a class for the Scala collections
library. And when I venture in, it will probably be to do a multiset
and a multimap, since I use those quite a lot (I wrote Java versions
once upon a time)


> - Florian.


Randall Schulz

On Monday March 23 2009, Jorge Ortiz wrote:
> Scala includes an implementation of MultiMap.

So it does.

Some time soon I need to spend some time just perusing the ScalaDocs for
the standard library.

Randall Schulz