Use push! and pop! for PriorityQueue etc

[dpsanders]

We should use push! and pop! instead of enqueue! and dequeue!,
so that different data structures are interchangeable without changing code.

cf. #289

[kmsquire]

Consistency is good, and enqueue and dequeue don't exist in mainline Julia. However, regular arrays have unshift! and shift!, so one question is whether the pair of unshift! and pop! should be used instead of push! and pop!.

[dpsanders]

Coming back to this since it recently annoyed me again when using a PriorityQueue.

I think we should rename

• enqueue! -> push!
• dequeue_pair! -> pop!

[kmsquire]

For consistency with Base, this should probably be pushfront! pushfirst! andpop!

[dpsanders]

I think you mean pushfirst!, in which case it should be popfirst!.
I see where the suggestion comes from, but since a priority queue has "nowhere else" to push and pop from, I don't see that the first adds anything.

The situation with Base.Vector is strange, since it's effectively a deque, without really declaring itself to be one. Thus the docstring of push!:

help?> push!
  Insert one or more items at the end of collection.

But, in my opinion, push! should generically just mean "add an element to the data structure".

[dpsanders]

E.g. push! is already used in this way for SortedDicts.

[goretkin]

"push" and "pop" are often the name of the operations defined on a stack, i.e. something following first-in-last-out , so it's a bit of clash of terminology, but I agree Base.push! should apply to queues (it's less of clash with priority queues).

Base.push! already doesn't mean the same thing as "push" in the context of stacks, since it's defined on Set, which has no insertion/extraction order. [EDIT, missed negation]

[kmsquire]

Base.push! already doesn't mean the same thing as "push" in the context of stacks, since it's defined on Set, which has insertion/extraction order.

I think you meant that it has no insertion/extraction order, right? I do agree that the meaning of push! has been extended beyond the traditional meaning of "push". It would probably be worth it to revisit that choice for Julia 2.0.

[dpsanders]

Revisit meaning what?

Personally I like thinking of push! as "add an element to the container", whenever that makes sense in an unambiguous way.

[goretkin]

I think you meant that it has no insertion/extraction order, right?

that's right, thanks for noticing I meant the opposite of what I wrote!

Personally I like thinking of push! as "add an element to the container", whenever that makes sense in an unambiguous way.

That's how I feel. I didn't mean to suggest that push! shouldn't extend beyond "stack.push", but that DataStructures.jl should follow the same tradition, and use push! for queues and any other collection.

[kmsquire]

It would probably be worth it to revisit that choice for Julia 2.0.

Revisit meaning what

Revisit whether "add an element to the container" (when unambiguous) is the best meaning for push!, and therefore whether push! and pop! should be used on unordered collections.

Currently, we have the following:

Data structure	push!	pop!	pushfirst!	popfirst!	enqueue!	dequeue!
Base.Vector	✔️	✔️	✔️	✔️
Base.Set	✔️	✔️
Base.Dict	✔️	✔️
─────	─────	─────	─────	─────	─────	─────
Stack	✔️	✔️
Deque	✔️	✔️	✔️	✔️
CircularQueue	✔️	✔️	✔️	✔️
OrderedDict, OrderedSet	✔️	✔️	◯	◯
SortedDict, SortedSet	✔️	✔️		◯
─────	─────	─────	─────	─────	─────	─────
Queue, PriorityQueue (current)					✔️	✔️
Queue, PriorityQueue (proposal 1)	✔️	✔️
Queue, PriorityQueue (proposal 2)		✔️	✔️

✔️= implemented
◯ = not implemented, but could/should be
────────────────────────────────────────

From this, we can see that push! and pop! have two different meanings.

1. For unordered and sorted collections, they simply mean to add or remove elements from the collection.
2. For every other collection listed, they (necessarily) mean to add or remove elements from the end of the collection, and they carry their traditional meaning.

Queue is the only outlier.

"Proposal 1" (which @dpsanders prefers) above suggests that Queue should be treated like Set, Dict, and SortedDict/SortedSet, (and perhaps Stack), since there's only one way to add things to the collection.

"Proposal 2" above suggests that Queue should be treated like a Vector, Deque, CircularDeque, (and perhaps OrderedDict, OrderedSet, and Stack), since there's a distinction as to whether things are added to the front or back of the collection.

The fact that there really are two meanings for push! and pop! are what I think should be revisited for Julia 2.0.

For example, if there were add! and remove! functions, then those could be defined for Set, Dict, SortedDict/SortedSet, and if desired, Stack and Queue, and they would mean "add" or "remove" elements from a collection. Then push!, pop!, pushfirst!, and popfirst! would always refer to the back and front of collections, which would clarify everything.

Cc: @StefanKarpinski

[dpsanders]

That's a great analysis, thanks!

[kmsquire]

I'm going to post this on Discourse for more visibility.

[StephenVavasis]

Just a quick addendum to Kevin's very useful chart: for SortedSet and SortedDict, pushfirst! does not make sense but popfirst! does.

Also, if we are looking forward to Julia 2.0, could someone start a list of semantic anomalies and other rough edges of DataStructures that deserve attention? I have a couple more of these.

[oxinabox]

Also, if we are looking forward to Julia 2.0, could someone start a list of semantic anomalies and other rough edges of DataStructures that deserve attention? I have a couple more of these.

Please make them as seperate issues each, and apply a common tag to them.
Rather than 1 big list

[kmsquire]

Just a quick addendum to Kevin's very useful chart: for SortedSet and SortedDict, pushfirst! does not make sense but popfirst! does.

Thanks, updated!

[kmsquire]

Hilariously (to me), the source of this pain is "past me":

• RFC: Split delete!(h::Dict,key) into pop!(), delete!() (#3405) JuliaLang/julia#3439
• the two meanings of delete! JuliaLang/julia#3405

🙈
Darn you, past me! 😠

[kmsquire]

Discourse link: https://discourse.julialang.org/t/taking-push-and-pop-seriously-in-julia-2-0/34326

(Tables look better in github)

[tkf]

I think this PR may be relevant JuliaLang/julia#34274 (Define push! and popfirst! for AbstractChannel)

[oxinabox]

We should do this.

we should do:

• enqueue -> push!
• dequeue -> popfirst

to match Channels in JuliaLang/julia#34274 (

[jonas-schulze]

In the light of #743, can this issue as well as #677 be closed?

[oxinabox]

Queue is done but PriorityQueue remains