Insert after `==` items

[ivan-m]

Is it possible to insert a value into a MinQueue after values that are equal to it? (i.e. insert it just before values which are larger)

As an example:

λ> import qualified Data.PQueue.Min as P
λ> data Foo = F Int Char deriving (Eq, Show)
λ> instance Ord Foo where compare (F x _) (F y _) = compare x y
λ> P.fromList $ zipWith F [1..4] ['a'..'e']
fromAscList [F 1 'a',F 2 'b',F 3 'c',F 4 'd']
λ> P.insert (F 2 'z') it
fromAscList [F 1 'a',F 2 'z',F 2 'b',F 3 'c',F 4 'd']

I want a way to have the F 2 'z' after the F 2 'b'.

[lspitzner]

I don't think there currently exists a function for that. Seems possible to add though. Any ideas for a name? insertBack sounds like pushing to the end of a container.. perhaps insertBehind ?

@lowasser comments? The invariant for the "cached" element (as in MinQueue len cached heap) becomes a bit more complex, i.e.

The cached element is the smallest according to firstly (key) comparison and secondly insertion order, where insertion order is defined by: An element X is smaller than any element currently in the container if inserted using insert and greater than any element currently in the container if inserted using insertBehind.

Which is implemented by simply replacing (<=) with (<) for insertBehind. Seems unproblematic to me.

[lspitzner]

@ivan-m is there any interest in this, still?

the implementation is in branch insertbehind. Could make a new release for this, if desired.

[ivan-m]

I don't actually recall where I was using/wanting this; I suspect it was a project at work, so I'll check when I'm in tomorrow.

[ivan-m]

OK, I've checked and remember now: it's a library whose need was no longer needed and thus I stopped working on, but would probably be worth cleaning up, finishing and releasing. So having this functionality would be appreciated, but I think one reason I stopped work on it was because I was waiting for @zadarnowski to finish off another library it was depending upon.

(i.e. no real rush :p)

[lspitzner]

1.3.2 has insertBehind