add insert_before and insert_after methods

[loewis]

In http://bugs.python.org/issue22097, Antoine Pitrou suggested that an ordered set should provide insert_before and insert_after methods, allowing insertion into the middle, rather than at the end. So I suggest this as a feature for this library here. Names are up for bike shedding; ISTM that add_before and add_after might work as well.

One issue is how to deal with insert_after is how to deal with the addition of keys that are already in the set. I see three alternatives:

1. No action (as in add), or
2. Move the key from where it is now to the position where it was requested, or
3. Produce a ValueError exception.

[mkurnikov]

@simonpercivall Is any progress planned on this issue?

[simonpercivall]

Not before your question right now (though I kept this issue open for just that purpose).

I didn't want to add more methods without anyone saying they actually wanted them (i.e. more than "It would be nice" to "not in the stdlib" to "perhaps in this module").

Are you saying that you have a use-case where it would be useful?

[mkurnikov]

I'm implementing a parser for the configuration file, which will preserve ordering after circle read-write. I need a datastructure to store nodes in order in which they have been parsed.

I'm currently using simple list to store them, and implementing my own (very slow) insert_before/insert_after on top of list. Lookup is slow too. And I was going to move to OrderedDict with stub values later, if I'd have any problems with performance.