Package io.vavr.collection
Class PriorityQueueBase
java.lang.Object
io.vavr.collection.PriorityQueueBase
-
Nested Class Summary
Nested Classes -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static <T> Tuple2
<T, Seq<PriorityQueueBase.Node<T>>> deleteMin
(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(package private) static <T> PriorityQueueBase.Node
<T> findMin
(Comparator<? super T> comparator, Seq<PriorityQueueBase.Node<T>> forest) Find the minimum root in the forestprivate static <T> Seq
<PriorityQueueBase.Node<T>> ins
(Comparator<? super T> comparator, PriorityQueueBase.Node<T> tree, Seq<PriorityQueueBase.Node<T>> forest) fun ins (t, []) = [t] * | ins (t, t' :: ts) = (∗ rank t ≤ rank t' ∗) * if rank t invalid input: '<' rank t' then t :: t' :: ts * else ins (link (t, t'), ts)(package private) static <T> Seq
<PriorityQueueBase.Node<T>> insert
(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(package private) static <T> Seq
<PriorityQueueBase.Node<T>> meld
(Comparator<? super T> comparator, Seq<PriorityQueueBase.Node<T>> source, Seq<PriorityQueueBase.Node<T>> target) fun meld (ts, ts') = meldUniq (uniqify ts, uniqify ts')private static <T> Seq
<PriorityQueueBase.Node<T>> meldUnique
(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 invalid input: '<' rank t2 then t1 :: meldUniq (ts1, t2 :: ts2) * else if rank t2 invalid input: '<' rank t1 then t2 :: meldUniq (t1 :: ts1, ts2) * else ins (link (t1, t2), meldUniq (ts1, ts2))private static <T> Seq
<PriorityQueueBase.Node<T>> rebuild
(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 backprivate static <T> Seq
<PriorityQueueBase.Node<T>> uniqify
(Comparator<? super T> comparator, Seq<PriorityQueueBase.Node<T>> forest) fun uniqify [] = [] * | uniqify (t :: ts) = ins (t, ts) (∗ eliminate initial duplicate ∗)
-
Constructor Details
-
PriorityQueueBase
PriorityQueueBase()
-
-
Method Details
-
deleteMin
static <T> Tuple2<T,Seq<PriorityQueueBase.Node<T>>> deleteMin(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(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 -
meld
static <T> Seq<PriorityQueueBase.Node<T>> meld(Comparator<? super T> comparator, Seq<PriorityQueueBase.Node<T>> source, Seq<PriorityQueueBase.Node<T>> target) fun meld (ts, ts') = meldUniq (uniqify ts, uniqify ts') -
findMin
static <T> PriorityQueueBase.Node<T> findMin(Comparator<? super T> comparator, Seq<PriorityQueueBase.Node<T>> forest) Find the minimum root in the forestfun 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(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 backfun 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(Comparator<? super T> comparator, Seq<PriorityQueueBase.Node<T>> forest) fun uniqify [] = [] * | uniqify (t :: ts) = ins (t, ts) (∗ eliminate initial duplicate ∗) -
ins
private static <T> Seq<PriorityQueueBase.Node<T>> ins(Comparator<? super T> comparator, PriorityQueueBase.Node<T> tree, Seq<PriorityQueueBase.Node<T>> forest) fun ins (t, []) = [t] * | ins (t, t' :: ts) = (∗ rank t ≤ rank t' ∗) * if rank t invalid input: '<' rank t' then t :: t' :: ts * else ins (link (t, t'), ts) -
meldUnique
private static <T> Seq<PriorityQueueBase.Node<T>> meldUnique(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 invalid input: '<' rank t2 then t1 :: meldUniq (ts1, t2 :: ts2) * else if rank t2 invalid input: '<' rank t1 then t2 :: meldUniq (t1 :: ts1, ts2) * else ins (link (t1, t2), meldUniq (ts1, ts2))
-