haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
316 stars 178 forks source link

Add left and right link variants #307

Open treeowl opened 8 years ago

treeowl commented 8 years ago

We have

link :: a -> Set a -> Set a -> Set a
link x Tip r  = insertMin x r
link x l Tip  = insertMax x l
link x l@(Bin sizeL y ly ry) r@(Bin sizeR z lz rz)
  | delta*sizeL < sizeR  = balanceL z (link x l lz) rz
  | delta*sizeR < sizeL  = balanceR y ly (link x ry r)
  | otherwise            = bin x l r

Several places we call this, we know that only one subtree could possibly be heavy. So we should add

linkL :: a -> Set a -> Set a -> Set a
linkL x l Tip  = insertMax x l
linkL x (Bin sizeL y ly ry) r@(Bin sizeR z lz rz)
  | delta*sizeR < sizeL  = balanceR y ly (link x ry r)
linkL x l r = bin x l r

and linkR similarly.

So I don't forget: these should be useful for implementing insert2 and insert2R for two-element union special cases. If both elements go left/right, we only need to check balance one way; if one goes left and the other right, we don't need to check balance at all.

treeowl commented 8 years ago

Never mind the two-element insertion for union. It turns out that balance variants are sufficient to implement insert2, but union using that is slow. I'm guessing this could be a branch prediction issue, but I'm not really sure.