Change name?

[igouy]

original-insertion-order-preserving removal would want to be implemented with tombstones, but I've decided this is going to be a separately named hash map. So: fork time.

Just an idle thought -- OrderMap was a good name for something that does guarantee insertion-order-preserved for all operations, so have a new name for this new thing which does not make that guarantee.

Is there a FastMap ? :-)

[bluss]

Maybe. The main feature is that it has a consistent (iteration) order that does not depend on the keys or the hash function.

[bluss]

Note that for clarity reasons it did already change name from OrderedMap to OrderMap

[igouy]

What would you call the "separately named hash map" if this one is still called OrderMap ?

[bluss]

Renaming the crate seems prudent; the name is the first impression we have, and there we need to deliver the correct expectations about what the data structure does.

NOTE: This is the name for the datastructure in this crate in its current implementation. current OrderMap will change name.

The datastructure is a hash table, stored in a compact indexable range, where it keeps insertion order as long as you don't call .remove().

Name Alternatives:

1. LinearMap
2. SequenceMap
3. IndexMap

I prefer LinearMap because its succinct, vaguely reminds one of the compactly indexable "Like a Vec" ordering semantics.

Thoughts and wo-hoos are welcome. Please leave well thought out alternative names too. Migration will use deprecation with clear message to point to the new crate name, and there will be a migratory crate version that is 100% API compatible with the other.

[bluss]

Thoughts on new name from @nox @cuviper @igouy @Techcable @pczarn @arthurprs @Binero @garro95 and everyone else!?

[clarfonthey]

LinearMap implies linear access time, so, no go for that. I'd personally prefer OrderedHashMap or something similar.

[clarfonthey]

IMO: the name of the type can be succinct but the crate's name should be very precise.

[bluss]

I'm not going for that meaning of "linear" here. We can describe a Vec as linear too, and it is constant time indexable; I think it can work.

[clarfonthey]

@bluss that would be fine, but linear-map is already a crate that does linear search. https://crates.io/crates/linear-map

[bluss]

Aw, that's too bad.

[cuviper]

The reason to rename is so an always-ordered crate can assume the name OrderMap?

My next preference is IndexMap, since indexing is such a powerful property here.

[bluss]

The reason is twofold. Most importantly now that ordermap seems to have delivered the wrong expectations. Secondly yes because I think a full insertion order map is important to Rust, to give the name to it.

[Binero]

For what it's worth, I think @bluss's IndexMap is a pretty descriptive name.

[cuviper]

(it wasn't my name, I just picked it from #14 (comment))

[garro95]

I like IndexMap too

[arthurprs]

IndexMap sounds reasonable to me 😄

[Techcable]

Although I am nostalgic for OrderMap, I think it's okay to rename it to either SequenceMap or IndexMap.

[bluss]

I appreciate the feedback!

Now 😄 I'm sorry to capture you like this (it's entirely voluntary), you who have already commented here or those that happen to read this: co-maintainers are also welcome since a good crate needs shared ownership. Maybe we don't have so much to do? The most important goal is just 1.0, and the name should be the only thing left blocking that..

[cuviper]

I'm willing to be a co-maintainer.

[bluss]

cc @vitiral too, thoughts about the name?

@cuviper Awesome!

Other volunteers are also welcome to help out, of course.

[vitiral]

Some other names:

• IterMap: to show it's performance when iterating
• DetMap with crate name deterministic_map to show that iterating is deterministic (very important for tests).
• IndexMap: already mentioned, I really like it. I think it gets to the root of what the crate does (... also note... I didn't actually realize indexing was supported in the public API -- cool!).

I think my vote is IndexMap but I thought I would spitball the others in case someone else has a real idea.

Also, I will be adding this to the ergo_std crate (not yet announced) in the ergo crate ecosystem as I think it should be considered a core type of ergonomic programming. So you chose a good time to rename!

[bluss]

DeterministicMap is a good point, DetMap is not a very understandable shortening, but deterministic is right in the realm of names we have been shooting for (even SteadyMap).

Note that the current plan is a common release of version 0.4 of ordermap and indexmap that are API-identical (apart from deprecation in ordermap, and the addition of the renamed types in indexmap). Then shortly after that indexmap can be 1.0.

It sounds a bit convoluted but it each step along the plan is simple and actionable. Ideally there should be an indexmap 0.4 that is ready to be rubber stamped as 1.0 soon.

[vitiral]

Just so I understand:

• The types currently in ordermap are moving to indexmap (or some other name) and being renamed accordingly.
• There will be new types in ordermap that have some different functionality, i.e. always ordered or something.

Is that right?

[bluss]

(It's basically right) The second point is a later concern, since no implementation exists, it will of course be a breaking version upgrade.

[nox]

I think DetMap is pretty good; even if reader is confused at the Det part for a few seconds, they'll see use deterministic_map::DetMap; somewhere.

[vitiral]

DetMap has the issue where it is not very deterministic when you do a remove, so I'm not sure it is actually the best name.

IndexMap kind of has this issue as well -- but then again if you remove a value from a Vec then the indexes of the other values move around, so that is probably fine. They don't move randomly like they do here, but that's probably okay as well...

[clarfonthey]

@vitrial this can easily be solved by renaming remove to swap_remove. It'd be clear what's happening then.

[Binero]

@clarcharr remove is just a thin wrapper around swap_remove. I think if we're going with IndexMap, it's important to make remove behave like it would on a Vec. This would of course be terribly slow, but if performance is an issue, people can always switch over to swap_remove.

We could of course also remove it completely.

[bluss]

I don't quite follow why remove() should change behaviour just because the data structure changes name. Maybe a different name is better then.

.remove() is a tricky knot in this case, there is an inconvenient half way solution — no remove method, but an extension trait that adds a .remove() method that wraps .swap_remove(). That makes dropping in ordermap in as a replacement of the standard HashMap one step more complicated.

[Binero]

When I think of an IndexMap I think of a hybrid between a Vec and a HashMap. The functions have the same effect to the indices as a Vec would have, and the same effect to the keys as a HashMap would have.

In a HashMap, the remove function removes the key and the value from the collection. In a Vec it removes the element and shifts all following elements one position forwards.

So, in a IndexMap, it would be intuitive if a remove function would remove the key and value pair, and shift all following elements one position forwards.

The current remove function works like the remove function of a HashMap, but is nothing like the remove function of a Vec. Rather, it acts like the swap_remove function of a Vec.

[vitiral]

@Binero while I agree with you that is slightly more expected, it has significant performance penalties. In most cases the fact that removing an element can affect the index of other elements is enough.

I would go the opposite -- add a shift_remove which does what @Binero is suggesting and just make sure docs state the behavior of remove.

In the majority of cases I would expect the performance of remove to be equivalent to HashMap. The specific behavior is normally not important.

[Binero]

In case we want to just focus on the fact the collection works like a HashMap which allows for fast iterating, where the indexing features are merely a side-effect of the way it is implemented (and thus not really part of the core-features), I think @vitiral's IterMap is more fitting.

I'm just not sure if we want such a narrow use-case for the collection while it could easily handle more.

[bluss]

From discussion in #rust, came the idea that clear docs would be even better than the perfect name.

No name can be so specific that it has the full picture in just the name. I might propose SteadyMap instead. With a unique name we can make the meaning clear in docs.

[arthurprs]

While I get the motivation, IndexMap still feels way better than SteadyMap (which is essentially arbitrary).

[vitiral]

@Binero

In case we want to just focus on the fact the collection works like a HashMap which allows for fast iterating, where the indexing features are merely a side-effect

Something that is fast indexing is pretty much by definition fast at iterating, which is why I think IndexMap is probably the better name.

IterMap also has the problem that it sounds like the struct you get when you call IndexMap::iter() 😆

[bluss]

Thanks a lot for being part of the process, IndexMap it is! And thanks @cuviper that you want to help out!