-- Demonstrates the use of a Priority Queue data structure so sort.
-- by Scot Drysdale on 10/17/07

-- The qualified is to avoid name clashes.
import qualified ListPriorityQueue as PQ

-- Sorts by inserting items into a priority queue and removing them.
-- The first thing in each pair is the priority.
pqSort    :: Ord a => [(a,b)] -> [(a,b)]
pqSort lst = iter initPQ 
  where
  initPQ = foldr PQ.insert PQ.empty lst 
  
  iter   :: Ord a => PQ.PriorityQueue a b -> [(a,b)]
  iter pq = if PQ.isEmpty pq
            then []
            else PQ.getMin pq : iter (PQ.deleteMin pq)
            
-- Demonstrates pqSort

lst1    = [(10, "cow"), (5, "bear"), (20, "eagle"), (5, "ant"), (5, "bee"),
           (25, "llama"), (3, "sheep")]
sorted1 = pqSort  lst1

lst2    = zip (reverse [1..10000] ++ [1..10000]) [3.0, 6.0..]
sorted2 = pqSort lst2
len2    = length sorted2