Class PriorityQueueBase


  • final class PriorityQueueBase
    extends java.lang.Object
    • Constructor Detail

      • PriorityQueueBase

        PriorityQueueBase()
    • Method Detail

      • deleteMin

        static <T> Tuple2<T,​Seq<PriorityQueueBase.Node<T>>> deleteMin​(java.util.Comparator<? super T> comparator,
                                                                            Seq<PriorityQueueBase.Node<T>> forest)
        fun deleteMin [] = raise EMPTY * | deleteMin ts = * val (Node (x,r,c), ts) = getMin ts * val (ts',xs') = split ([],[],c) * in fold insert xs' (meld (ts, ts')) end
      • insert

        static <T> Seq<PriorityQueueBase.Node<T>> insert​(java.util.Comparator<? super T> comparator,
                                                         T element,
                                                         Seq<PriorityQueueBase.Node<T>> forest)
        fun insert (x, ts as t1 :: t2 :: rest) = * if rank t1 = rank t2 then skewLink(Node(x,0,[]),t1,t2) :: rest * else Node (x,0,[]) :: ts * | insert (x, ts) = Node (x,0,[]) :: ts
      • findMin

        static <T> PriorityQueueBase.Node<T> findMin​(java.util.Comparator<? super T> comparator,
                                                     Seq<PriorityQueueBase.Node<T>> forest)
        Find the minimum root in the forest

        fun findMin [] = raise EMPTY * | findMin [t] = root t * | findMin (t :: ts) = * let val x = findMin ts * in if Elem.leq (root t, x) then root t else x end

      • rebuild

        private static <T> Seq<PriorityQueueBase.Node<T>> rebuild​(java.util.Comparator<? super T> comparator,
                                                                  Seq<PriorityQueueBase.Node<T>> forest)
        Separate the rank 0 trees from the rest, rebuild the 0 rank ones and merge them back

        fun split (ts,xs,[]) = (ts, xs) * | split (ts,xs,t :: c) = * if rank t = 0 then split (ts,root t :: xs,c) * else split (t :: ts,xs,c)

      • uniqify

        private static <T> Seq<PriorityQueueBase.Node<T>> uniqify​(java.util.Comparator<? super T> comparator,
                                                                  Seq<PriorityQueueBase.Node<T>> forest)
        fun uniqify [] = [] * | uniqify (t :: ts) = ins (t, ts) (∗ eliminate initial duplicate ∗)
      • meldUnique

        private static <T> Seq<PriorityQueueBase.Node<T>> meldUnique​(java.util.Comparator<? super T> comparator,
                                                                     Seq<PriorityQueueBase.Node<T>> forest1,
                                                                     Seq<PriorityQueueBase.Node<T>> forest2)
        fun meldUniq ([], ts) = ts * | meldUniq (ts, []) = ts * | meldUniq (t1 :: ts1, t2 :: ts2) = * if rank t1 < rank t2 then t1 :: meldUniq (ts1, t2 :: ts2) * else if rank t2 < rank t1 then t2 :: meldUniq (t1 :: ts1, ts2) * else ins (link (t1, t2), meldUniq (ts1, ts2))