CODEWITHSUNDEEP
clojure
Cubic
Cubic

Reputation: 15683

Is there such a thing as an associative queue?

I want a clojure data structure that:

Is there something like that in Clojure (unfortunately PersistentQueue doesn't fulfill Nr.3), or should I built it on top of vector?

Upvotes: 6

Views: 381

Answers (4)

wowest
wowest

Reputation: 1994

Sounds like you want a deque like python's deque except you might prefer the indexed access performance characteristics of the c++ std::deque<T> whose documentation is somewhat more obtuse.

Java ships with java.util.Deque implementations which you could just use, much like @tnoda's suggestion of java.util.LinkedList.

If you were rolling your own, the implementation is pretty straightforward for a non-persistent collection, and seems reasonably intuitive to me at least to implement against the "hashed array trees" underlying clojure's hashmap and vector, or directly against vector initially if the details annoy you.

Upvotes: 0

tnoda
tnoda

Reputation: 1524

If you do not require persistency of the data structure, you could use java.util.LinkedList in your Clojure programs.

Example:

;;; Creation
user> (import 'java.util.LinkedList)
java.util.LinkedList
user> (def linked-list (LinkedList. [:a :b :c :d :e]))
#'user/linked-list

;;; Pop from the front
user> (.pop ^LinkedList linked-list)
:a
user> linked-list
#<LinkedList [:b, :c, :d, :e]>

;;; Push to the rear, but costly
user> (.addLast ^LinkedList linked-list :x)
nil
user> linked-list
#<LinkedList [:b, :c, :d, :e, :x]>

;;; Assoc (cf. (assoc linked-list 0 :y)
user> (.add ^LinkedList linked-list 0 :y)
nil
user> linked-list
#<LinkedList [:y, :b, :c, :d, :x]>

Upvotes: 1

Jordan Lewis
Jordan Lewis

Reputation: 17948

You could use a sorted-map, but you'd have to implement the index part yourself.

For example, to push a value v, you could assoc it with the key produced by incrementing the last key in the map. To pop, you could dissoc the first key in the map.

Upvotes: 0

mikera
mikera

Reputation: 106371

There isn't a data structure in standard Clojure that will meet these requirements efficiently.

There was some talk on the Clojure-Dev mailing list about using RRB trees for vectors, which would be a great data structure for this:

Not sure how far that has developed - but if you are interested in this kind of data structure then it is definitely worth taking a look at this.

Upvotes: 1

Related Questions