Maturing out the package (Path to DataStructures.jl v1.0)

[oxinabox]

What do we need to do before we would be happy to tag DataStructures.jl v1.0?
I mean, we are one of the most common dependencies in the package ecosystem,
and julia 1.0 is out.

My thoughts;

• Search the code base for anything written in outmoded styles (e.g. Update heap constructors #472)
• Get rid of anything deprecated Clean out deprecations that we declared #477 (but that will need to be done again after)
• Maybe split up the package Split up the package? #310, but noting that all the packages sliced out that way will want to hit 1.0 before (or at the same time as) DataStructures.jl does.

It hurts people when we break things, and while we are good at deprecating,
getting on the the "strict" side of semver is something we need to do for the sake of the ecosystem

[oxinabox]

People keep asking when will DataStructures 1.0 come out.
The answer is as soon as we completely audit the package to make sure there is nothing that needs to be removed/corrected to follow modern julia conventions.
And have actioned those corrections.
A lot of the code in the package is pretty old, and follows e.g. conventions from julia 0.3.
We need to identify and correct these.

I will post a list of files at the bottom of this post.
Then people can go through this and use the checklist to make sure everything is good, one file at a time.

How to audit a file to check if 1.0 ready

• Answer the question of should we even keep this in the package. E.g. no data structure that somone just kind of made up (like the now removed `Classifier Collection). If ours is is a worse version of something in another package it should also go.
• Type Names Correct/Sensible: for example make sure we don't have a type called MagicVectors that is a subtype of vector. That should be called MagicVector (singular).
• No constructors taking types as positional arguments. For example there should not be MagicVector(::Type{T}) where T, instead there should just be MagicVector{T}().
• No functions that duplicate constructors. For example there should not be a function magic_vector(xs), only MagicVector(xs).
• No functions that are improperly cased and pretend to be constructors.
  • E.g. no MagicVector(xs) = Vector(xs) .* "Magic", that should just be a normal function magic_vector(xs) = Vector(xs) .* "Magic"
  • E.g. no MagicVector(xs)=Vector{Magic}(xs), that should be a const type alias const MagicVector=Vector{Magic}
• No exported functions that could be just done with overloads of Base. E.g. don't need top, peak, head all of which act the same as first but on a particular data structure.
•  No internal helpers exported. If something isn't useful to the end user it should not be exported. In general The vast majority of the public API should be constructor or overloads of Base functions. Thus any export should be looked at closely.
• Correct return types push! and empty! and delete! should return the collection. (this is relatively minor as it would be a bug if they didn't so it isn't breaking for use to fix it later.)
• No defining methods in ways that disagree with Base: for example because Base has insert!(xs, index, value) we should not have no instert!(xs, val) (push! is for that). Conversely we should not have push!(xs, key, value) ( we dio both of these right now in various trees, and in accumulators respectively)

All these things are things that have changed during the life-time of this package.

List of files that need to be checked

(Checking each will also require checking the top-level file for relevant exports)

• accumulator.jl
• default_dict.jl
• robin_dict.jl
• dict_support.jl

• trie.jl
• balanced_tree.jl
• circ_deque.jl
• circular_buffer.jl
• dibit_vector.jl

• disjoint_set.jl
• fenwick.jl
• int_set.jl
• sparse_int_set.jl

• list.jl
• multi_dict.jl
• mutable_list.jl

• deque.jl
• queue.jl
• stack.jl

• sorted_dict.jl
• sorted_multi_dict.jl
• sorted_set.jl
• tokens.jl
• tokens2.jl

• priorityqueue.jl
• heaps.jl
• heaps/arrays_as_heaps.jl
• heaps/binary_heap.jl
• heaps/minmax_heap.jl
• heaps/mutable_binary_heap.jl

• container_loops.jl
• delegate.jl

Many of these should be easy, because they have kind of already been done.
E.g. Heaps were done for 0.18; robindict was created after julia 1.0 and so should follow conventions.
But lets get them all and check them off using the list criteria listed above.

Higher level process:

0.19 will be the last release before 1.0.
0.19 will be the same as 1.0 but with deprecations.
1.0 will come out the same day as 0.19

We will stick to making patch releases on 0.18 with deprecations while we can.
But once we can't we will swap master to 0.19-DEV, and say on that until we can release it and 1.0.
That might take a 6 or more months; depends how many (if any) people are about to spend time helping with the audit.
If necessary we will have a backport branch for 0.18 bug-fixes

Once @eulerkochy's GSOC work is complete we will not accept any new data structures until after 1.0 released.

If anyone want to help out, please feel strongly encouraged to do so.

[nickrobinson251]

No exported functions that could be just done with overloads of Base

How about reverse_iter? Can this just be Iterators.reverse? The only issue i see is that reverse_iter(s::Stack) returns a DequeIterator, not a Iterators.Reverse, but idk if Iterator's API is really supposed to guarantee Iterators.reverse(::T) -> Iterators.Reverse{T} or not. (edit: no it's not, that's why we have reverse, rather than just Reverse, so we don't have to guarantee returning a Reverse)

[nickrobinson251]

• No exported functions that could be just done with overloads of Base.

• No defining methods in ways that disagree with Base

I think this suggests we should make a call on which side this falls: #296