Implementing `insert_before` method

[olebedev]

Hi there 👋

I've encountered a need to insert a key/value pair before a specific node in the underlying linked list. Currently, there's no available API to achieve this. I considered extending the functionality myself; however, the required attach_before and detach_node functions are private, making them inaccessible.

Is there an alternative method to accomplish this without altering the crate, if there is no an alternative, would you be open to accepting a PR that implements this method?

Best regards, Oleg

[kyren]

Hi! 👋

I don't think there's a way to do this without a PR, but yeah I think I'm willing to accept one.

Designing the right API for it is a little tricky, you could provide a simplistic LinkedHashMap::insert_before(&mut self, before: KB, key: K, value: V) method but that feels pretty ad hoc. We could provide insert_before methods on OccupiedEntry and RawOccupiedEntryMut instead, which is maybe a little better, but still feels pretty ad hoc. There might be a better and more general API than that that allows the user to safely change the linked list order in a more general way, but I don't know what such a thing would look like yet.

[olebedev]

Great, thank you for your swift response!

We could provide insert_before methods on OccupiedEntry and RawOccupiedEntryMut instead, which is maybe a little better, but still feels pretty ad hoc.

I agree, this solution seems pretty ad hoc, particularly for a project of this scope. While I can't propose a superior API right now, but I'm interested in further researching to identify a more efficient approach.

Given the rarity of my use case, it might not be widely applicable. Thus, integrating it with LinkedHashMap may not be necessary currently. Perhaps, as we gain more insight into a high-level API, OccupiedEntry::insert_before could be beneficial and time-saving, considering further adoption of the approach.

I'll focus on OccupiedEntry::insert_before for now and see how it progresses.

[olebedev]

G'Day @kyren 👋

I've been experimenting with OccupiedEntry::insert_before this weekend (I'll push my changeset soon) and noticed its similarity to CursorMut::insert_before from the RFC.

The difference for the LinkedHashMap's Cursor and CursorMut API would be as little as:

-     /// Returns the cursor position index within the `LinkedList`.
-    pub fn index(&self) -> Option<usize>;
+     /// Returns the cursor position key within the `LinkedHashMap`.
+    pub fn key(&self) -> Option<K>;

Would the implementations for Cursor and CursorMut in LinkedHashMap align with your general API requirements?

Considering the complexity of this implementation, it's currently beyond my capacity. I'm also unsure if it's necessary, as I haven't noticed a consistent demand for this feature. Can you confirm if my understanding is correct?

I'm ready to create a plan, divide it into achievable tasks, and focus on the core components. Once I reach my initial goal, I'll hand it over to anyone interested in continuing the work. I'd appreciate your thoughts on this.

[olebedev]

Closed by #25