--
-- Copyright (c) 2009 - 2010 Brendan Hickey - http://bhickey.net
-- New BSD License (see http://www.opensource.org/licenses/bsd-license.php)
--

module Data.Tree.Splay 
(SplayTree, head, tail, singleton, empty, null, fromList, fromAscList, toList, toAscList, insert, lookup, (!!), splay, size, delete) 
where

import Prelude hiding (head, tail, lookup, null, (!!))

data (Ord k) => SplayTree k v = 
    Leaf
  | SplayTree k v Int (SplayTree k v) (SplayTree k v) deriving (Eq (SplayTree k v)
Eq (SplayTree k v) =>
(SplayTree k v -> SplayTree k v -> Ordering)
-> (SplayTree k v -> SplayTree k v -> Bool)
-> (SplayTree k v -> SplayTree k v -> Bool)
-> (SplayTree k v -> SplayTree k v -> Bool)
-> (SplayTree k v -> SplayTree k v -> Bool)
-> (SplayTree k v -> SplayTree k v -> SplayTree k v)
-> (SplayTree k v -> SplayTree k v -> SplayTree k v)
-> Ord (SplayTree k v)
SplayTree k v -> SplayTree k v -> Bool
SplayTree k v -> SplayTree k v -> Ordering
SplayTree k v -> SplayTree k v -> SplayTree k v
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k v. (Ord k, Ord v) => Eq (SplayTree k v)
forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> Bool
forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> Ordering
forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> SplayTree k v
$ccompare :: forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> Ordering
compare :: SplayTree k v -> SplayTree k v -> Ordering
$c< :: forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> Bool
< :: SplayTree k v -> SplayTree k v -> Bool
$c<= :: forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> Bool
<= :: SplayTree k v -> SplayTree k v -> Bool
$c> :: forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> Bool
> :: SplayTree k v -> SplayTree k v -> Bool
$c>= :: forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> Bool
>= :: SplayTree k v -> SplayTree k v -> Bool
$cmax :: forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> SplayTree k v
max :: SplayTree k v -> SplayTree k v -> SplayTree k v
$cmin :: forall k v.
(Ord k, Ord v) =>
SplayTree k v -> SplayTree k v -> SplayTree k v
min :: SplayTree k v -> SplayTree k v -> SplayTree k v
Ord, SplayTree k v -> SplayTree k v -> Bool
(SplayTree k v -> SplayTree k v -> Bool)
-> (SplayTree k v -> SplayTree k v -> Bool) -> Eq (SplayTree k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Ord k, Eq v) => SplayTree k v -> SplayTree k v -> Bool
$c== :: forall k v. (Ord k, Eq v) => SplayTree k v -> SplayTree k v -> Bool
== :: SplayTree k v -> SplayTree k v -> Bool
$c/= :: forall k v. (Ord k, Eq v) => SplayTree k v -> SplayTree k v -> Bool
/= :: SplayTree k v -> SplayTree k v -> Bool
Eq)

-- | /O(1)/. 'singleton' constructs a splay tree containing one element.
singleton :: (Ord k) => (k,v) -> SplayTree k v
singleton :: forall k v. Ord k => (k, v) -> SplayTree k v
singleton (k
k,v
v) = k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k v
v Int
0 SplayTree k v
forall k v. SplayTree k v
Leaf SplayTree k v
forall k v. SplayTree k v
Leaf

-- | /O(1)/. 'empty' constructs an empty splay tree.
empty :: (Ord k) => SplayTree k v
empty :: forall k v. Ord k => SplayTree k v
empty = SplayTree k v
forall k v. SplayTree k v
Leaf

-- | /O(1)/. 'null' returns true if a splay tree is empty.
null :: (Ord k) => SplayTree k v -> Bool
null :: forall k v. Ord k => SplayTree k v -> Bool
null SplayTree k v
Leaf = Bool
True
null SplayTree k v
_ = Bool
False

size :: (Ord k) => SplayTree k v -> Int
size :: forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
Leaf = Int
0
size (SplayTree k
_ v
_ Int
d SplayTree k v
_ SplayTree k v
_) = Int
d

-- | /Amortized O(lg n)/. Given a splay tree and a key, 'lookup' attempts to find a node with the specified key and splays this node to the root. If the key is not found, the nearest node is brought to the root of the tree.
lookup :: (Ord k) => k -> SplayTree k v -> SplayTree k v
lookup :: forall k v. Ord k => k -> SplayTree k v -> SplayTree k v
lookup k
_ SplayTree k v
Leaf = SplayTree k v
forall k v. SplayTree k v
Leaf
lookup k
k' t :: SplayTree k v
t@(SplayTree k
k v
_ Int
_ SplayTree k v
l SplayTree k v
r)
  | k
k' k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k = SplayTree k v
t
  | k
k k -> k -> Bool
forall a. Ord a => a -> a -> Bool
> k
k' =
    case k -> SplayTree k v -> SplayTree k v
forall k v. Ord k => k -> SplayTree k v -> SplayTree k v
lookup k
k' SplayTree k v
l of
      SplayTree k v
Leaf -> SplayTree k v
t
      SplayTree k v
lt -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
SplayTree k v -> SplayTree k v -> SplayTree k v
zig SplayTree k v
lt SplayTree k v
t
  | Bool
otherwise = 
    case k -> SplayTree k v -> SplayTree k v
forall k v. Ord k => k -> SplayTree k v -> SplayTree k v
lookup k
k' SplayTree k v
r of
      SplayTree k v
Leaf -> SplayTree k v
t
      SplayTree k v
rt -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
SplayTree k v -> SplayTree k v -> SplayTree k v
zag SplayTree k v
t SplayTree k v
rt

-- | Locates the i^{th} element in BST order without splaying it.
(!!) :: (Ord k) => SplayTree k v -> Int -> (k,v)
!! :: forall k v. Ord k => SplayTree k v -> Int -> (k, v)
(!!) SplayTree k v
Leaf Int
_ = [Char] -> (k, v)
forall a. HasCallStack => [Char] -> a
error [Char]
"index out of bounds"
(!!) (SplayTree k
k v
v Int
d SplayTree k v
l SplayTree k v
r) Int
n =
  if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
d
  then [Char] -> (k, v)
forall a. HasCallStack => [Char] -> a
error [Char]
"index out of bounds"
  else 
    let l' :: Int
l' = SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
l in
      if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l'
      then (k
k,v
v)
      else if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l'
           then SplayTree k v
l SplayTree k v -> Int -> (k, v)
forall k v. Ord k => SplayTree k v -> Int -> (k, v)
!! Int
n
           else SplayTree k v
r SplayTree k v -> Int -> (k, v)
forall k v. Ord k => SplayTree k v -> Int -> (k, v)
!! (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l')

-- | Splays the i^{th} element in BST order
splay :: (Ord k) => SplayTree k v -> Int -> SplayTree k v
splay :: forall k v. Ord k => SplayTree k v -> Int -> SplayTree k v
splay SplayTree k v
Leaf Int
_ = [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"index out of bounds"
splay t :: SplayTree k v
t@(SplayTree k
_ v
_ Int
d SplayTree k v
l SplayTree k v
r) Int
n =
  if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
d
  then [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"index out of bounds"
  else 
    let l' :: Int
l' = SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
l in
      if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l'
      then SplayTree k v
t
      else if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l'
           then case SplayTree k v -> Int -> SplayTree k v
forall k v. Ord k => SplayTree k v -> Int -> SplayTree k v
splay SplayTree k v
l Int
n of
                  SplayTree k v
Leaf -> [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"index out of bounds"
                  SplayTree k v
lt -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
SplayTree k v -> SplayTree k v -> SplayTree k v
zig SplayTree k v
lt SplayTree k v
t
           else case SplayTree k v -> Int -> SplayTree k v
forall k v. Ord k => SplayTree k v -> Int -> SplayTree k v
splay SplayTree k v
r (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l') of
                  SplayTree k v
Leaf -> [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"index out of bounds"
                  SplayTree k v
rt -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
SplayTree k v -> SplayTree k v -> SplayTree k v
zag SplayTree k v
t SplayTree k v
rt

-- | /O(1)/. zig rotates its first argument up
zig :: (Ord k) => SplayTree k v -> SplayTree k v -> SplayTree k v
zig :: forall k v.
Ord k =>
SplayTree k v -> SplayTree k v -> SplayTree k v
zig SplayTree k v
Leaf SplayTree k v
_ = [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"tree corruption"
zig SplayTree k v
_ SplayTree k v
Leaf = [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"tree corruption"
zig (SplayTree k
k1 v
v1 Int
_ SplayTree k v
l1 SplayTree k v
r1) (SplayTree k
k v
v Int
d SplayTree k v
_ SplayTree k v
r) =
  k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k1 v
v1 Int
d SplayTree k v
l1 (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k v
v (Int
d Int -> Int -> Int
forall a. Num a => a -> a -> a
- SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
l1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) SplayTree k v
r1 SplayTree k v
r)

-- | /O(1)/. zig rotates its second argument up
zag :: (Ord k) => SplayTree k v -> SplayTree k v -> SplayTree k v
zag :: forall k v.
Ord k =>
SplayTree k v -> SplayTree k v -> SplayTree k v
zag SplayTree k v
Leaf SplayTree k v
_ = [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"tree corruption"
zag SplayTree k v
_ SplayTree k v
Leaf = [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"tree corruption"
zag (SplayTree k
k v
v Int
d SplayTree k v
l SplayTree k v
_) (SplayTree k
k1 v
v1 Int
_ SplayTree k v
l1 SplayTree k v
r1) =
  k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k1 v
v1 Int
d (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k v
v (Int
d Int -> Int -> Int
forall a. Num a => a -> a -> a
- SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
r1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) SplayTree k v
l SplayTree k v
l1) SplayTree k v
r1

-- | /Amortized O(lg n)/. Given a splay tree and a key-value pair, 'insert' places the the pair into the tree in BST order. This function is unsatisfying.
insert :: (Ord k) => k -> v -> SplayTree k v -> SplayTree k v
insert :: forall k v. Ord k => k -> v -> SplayTree k v -> SplayTree k v
insert k
k v
v SplayTree k v
t =
  case k -> SplayTree k v -> SplayTree k v
forall k v. Ord k => k -> SplayTree k v -> SplayTree k v
lookup k
k SplayTree k v
t of
    SplayTree k v
Leaf -> (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k v
v Int
0 SplayTree k v
forall k v. SplayTree k v
Leaf SplayTree k v
forall k v. SplayTree k v
Leaf)
    (SplayTree k
k1 v
v1 Int
d SplayTree k v
l SplayTree k v
r) ->
        if k
k1 k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k
        then k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k v
v (Int
d Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k1 v
v1 (Int
d Int -> Int -> Int
forall a. Num a => a -> a -> a
- SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) SplayTree k v
l SplayTree k v
forall k v. SplayTree k v
Leaf) SplayTree k v
r
        else k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k v
v (Int
d Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) SplayTree k v
l (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k1 v
v1 (Int
d Int -> Int -> Int
forall a. Num a => a -> a -> a
- SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) SplayTree k v
forall k v. SplayTree k v
Leaf SplayTree k v
r)

-- | /O(1)/. 'head' returns the key-value pair of the root.
head :: (Ord k) => SplayTree k v -> (k,v)
head :: forall k v. Ord k => SplayTree k v -> (k, v)
head SplayTree k v
Leaf = [Char] -> (k, v)
forall a. HasCallStack => [Char] -> a
error [Char]
"head of empty tree"
head (SplayTree k
k v
v Int
_ SplayTree k v
_ SplayTree k v
_) = (k
k,v
v)

-- | /Amortized O(lg n)/. 'tail' removes the root of the tree and merges its subtrees
tail :: (Ord k) => SplayTree k v -> SplayTree k v
tail :: forall k v. Ord k => SplayTree k v -> SplayTree k v
tail SplayTree k v
Leaf = [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"tail of empty tree"
tail (SplayTree k
_ v
_ Int
_ SplayTree k v
Leaf SplayTree k v
r) = SplayTree k v
r
tail (SplayTree k
_ v
_ Int
_ SplayTree k v
l SplayTree k v
Leaf) = SplayTree k v
l
tail (SplayTree k
_ v
_ Int
_ SplayTree k v
l SplayTree k v
r)    = 
  case SplayTree k v -> SplayTree k v
forall k v. Ord k => SplayTree k v -> SplayTree k v
splayRight SplayTree k v
l of
    (SplayTree k
k v
v Int
d SplayTree k v
l1 SplayTree k v
Leaf) -> (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k v
v (Int
d Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
r) SplayTree k v
l1 SplayTree k v
r)
    SplayTree k v
_ -> [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"splay tree corruption"

delete :: (Ord k) => k -> SplayTree k v -> SplayTree k v
delete :: forall k v. Ord k => k -> SplayTree k v -> SplayTree k v
delete k
_ SplayTree k v
Leaf = SplayTree k v
forall k v. SplayTree k v
Leaf
delete k
k SplayTree k v
t = 
  case k -> SplayTree k v -> SplayTree k v
forall k v. Ord k => k -> SplayTree k v -> SplayTree k v
lookup k
k SplayTree k v
t of
    t' :: SplayTree k v
t'@(SplayTree k
k1 v
_ Int
_ SplayTree k v
_ SplayTree k v
_) -> 
      if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k1
      then SplayTree k v -> SplayTree k v
forall k v. Ord k => SplayTree k v -> SplayTree k v
tail SplayTree k v
t'
      else SplayTree k v
t'
    SplayTree k v
Leaf -> [Char] -> SplayTree k v
forall a. HasCallStack => [Char] -> a
error [Char]
"splay tree corruption"


splayRight :: (Ord k) => SplayTree k v -> SplayTree k v
splayRight :: forall k v. Ord k => SplayTree k v -> SplayTree k v
splayRight SplayTree k v
Leaf = SplayTree k v
forall k v. SplayTree k v
Leaf
splayRight h :: SplayTree k v
h@(SplayTree k
_ v
_ Int
_ SplayTree k v
_ SplayTree k v
Leaf) = SplayTree k v
h
splayRight (SplayTree k
k1 v
v1 Int
d1 SplayTree k v
l1 (SplayTree k
k2 v
v2 Int
_ SplayTree k v
l2 SplayTree k v
r2)) = 
  SplayTree k v -> SplayTree k v
forall k v. Ord k => SplayTree k v -> SplayTree k v
splayRight (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k2 v
v2 Int
d1 (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k1 v
v1 (Int
d1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
r2) SplayTree k v
l1 SplayTree k v
l2) SplayTree k v
r2)

splayLeft :: (Ord k) => SplayTree k v -> SplayTree k v
splayLeft :: forall k v. Ord k => SplayTree k v -> SplayTree k v
splayLeft SplayTree k v
Leaf = SplayTree k v
forall k v. SplayTree k v
Leaf
splayLeft h :: SplayTree k v
h@(SplayTree k
_ v
_ Int
_ SplayTree k v
Leaf SplayTree k v
_) = SplayTree k v
h
splayLeft (SplayTree k
k1 v
v1 Int
d1 (SplayTree k
k2 v
v2 Int
_ SplayTree k v
l2 SplayTree k v
r2) SplayTree k v
r1) = 
  SplayTree k v -> SplayTree k v
forall k v. Ord k => SplayTree k v -> SplayTree k v
splayLeft (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k2 v
v2 Int
d1 SplayTree k v
l2 (k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
forall k v.
Ord k =>
k -> v -> Int -> SplayTree k v -> SplayTree k v -> SplayTree k v
SplayTree k
k1 v
v1 (Int
d1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- SplayTree k v -> Int
forall k v. Ord k => SplayTree k v -> Int
size SplayTree k v
l2) SplayTree k v
r2 SplayTree k v
r1))

-- | /O(n lg n)/. Constructs a splay tree from an unsorted list of key-value pairs.
fromList :: (Ord k) => [(k,v)] -> SplayTree k v
fromList :: forall k v. Ord k => [(k, v)] -> SplayTree k v
fromList [] = SplayTree k v
forall k v. SplayTree k v
Leaf
fromList [(k, v)]
l = (SplayTree k v -> (k, v) -> SplayTree k v)
-> SplayTree k v -> [(k, v)] -> SplayTree k v
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (\ SplayTree k v
acc (k
k,v
v) -> k -> v -> SplayTree k v -> SplayTree k v
forall k v. Ord k => k -> v -> SplayTree k v -> SplayTree k v
insert k
k v
v SplayTree k v
acc) SplayTree k v
forall k v. SplayTree k v
Leaf [(k, v)]
l

-- | /O(n lg n)/. Constructs a splay tree from a list of key-value pairs sorted in ascending order.
fromAscList :: (Ord k) => [(k,v)] -> SplayTree k v
fromAscList :: forall k v. Ord k => [(k, v)] -> SplayTree k v
fromAscList = [(k, v)] -> SplayTree k v
forall k v. Ord k => [(k, v)] -> SplayTree k v
fromList

-- | /O(n lg n)/. Converts a splay tree into a list of key-value pairs with no constraint on ordering.
toList :: (Ord k) => SplayTree k v -> [(k,v)]
toList :: forall k v. Ord k => SplayTree k v -> [(k, v)]
toList = SplayTree k v -> [(k, v)]
forall k v. Ord k => SplayTree k v -> [(k, v)]
toAscList

-- | /O(n lg n)/. 'toAscList' converts a splay tree to a list of key-value pairs sorted in ascending order.
toAscList :: (Ord k) => SplayTree k v -> [(k,v)]
toAscList :: forall k v. Ord k => SplayTree k v -> [(k, v)]
toAscList h :: SplayTree k v
h@(SplayTree k
_ v
_ Int
_ SplayTree k v
Leaf SplayTree k v
_) = SplayTree k v -> (k, v)
forall k v. Ord k => SplayTree k v -> (k, v)
head SplayTree k v
h (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
: SplayTree k v -> [(k, v)]
forall k v. Ord k => SplayTree k v -> [(k, v)]
toAscList (SplayTree k v -> SplayTree k v
forall k v. Ord k => SplayTree k v -> SplayTree k v
tail SplayTree k v
h)
toAscList SplayTree k v
Leaf = []
toAscList SplayTree k v
h = SplayTree k v -> [(k, v)]
forall k v. Ord k => SplayTree k v -> [(k, v)]
toAscList (SplayTree k v -> [(k, v)]) -> SplayTree k v -> [(k, v)]
forall a b. (a -> b) -> a -> b
$ SplayTree k v -> SplayTree k v
forall k v. Ord k => SplayTree k v -> SplayTree k v
splayLeft SplayTree k v
h