use v6;
use Algorithm::Treap::Node;

unit role Algorithm::Treap[::KeyT];

my enum TOrder is export <DESC ASC>;

has $.root;
has TOrder $!order-by;
has Code $.gt;
has Code $.lt;
has Code $.eq;

submethod BUILD(TOrder :$!order-by) {
    if (not $!order-by.defined) {
	    $!order-by = TOrder::ASC;
    }
    if (none KeyT ~~ Str|Int) {
	    die "Error: key is Str or Int"
    }
    if (KeyT ~~ Str) {
	    $!gt = sub (Str $lhs, Str $rhs) {
	        return $lhs gt $rhs;
	    }
	    $!lt = sub (Str $lhs, Str $rhs) {
	        return $lhs lt $rhs;
	    }
	    $!eq = sub (Str $lhs, Str $rhs) {
	        return $lhs eq $rhs;
	    }
	    if ($!order-by == TOrder::DESC) {
	        $!gt = sub (Str $lhs, Str $rhs) {
		        return $lhs lt $rhs;
	        }
	        $!lt = sub (Str $lhs, Str $rhs) {
		        return $lhs gt $rhs;
	        }
	    }
    }
    elsif (KeyT ~~ Int) {
	    $!gt = sub (Int $lhs, Int $rhs) {
	        return $lhs > $rhs;
	    }
	    $!lt = sub (Int $lhs, Int $rhs) {
	        return $lhs < $rhs;
	    }
	    $!eq = sub (Int $lhs, Int $rhs) {
	        return $lhs == $rhs;
	    }
	    if ($!order-by == TOrder::DESC) {
	        $!gt = sub (Int $lhs, Int $rhs) {
		        return $lhs < $rhs;
	        }
	        $!lt = sub (Int $lhs, Int $rhs) {
		        return $lhs > $rhs;
	        }
	    }
    }
}

method !insert($current is rw, $k, $v, Num $priority) {
    if (not $current.defined) {
	    $current = Algorithm::Treap::Node.new(key => $k, value => $v, priority => $priority);
	    return $current;
    }

    if ($.eq.($k,$current.key)) {
	    die "Error: keys are duplicated";
    }
    elsif ($.lt.($k,$current.key)) {
	    $current.left-child = self!insert($current.left-child, $k, $v, $priority);

	    if ($current.left-child.priority > $current.priority) {
	        $current = self!right-rotate($current);
	    }
    }
    else {
	    $current.right-child = self!insert($current.right-child, $k, $v, $priority);

	    if ($current.right-child.priority > $current.priority) {
	        $current = self!left-rotate($current);
	    }
    }
    return $current;
}

method !delete($current is rw, $k) {
    if (not $current.defined) {
	    return $current;
    }
    
    if ($.lt.($k,$current.key)) {
	    $current.left-child = self!delete($current.left-child, $k);
	    return $current;
    }
    elsif ($.gt.($k,$current.key)) {
	    $current.right-child = self!delete($current.right-child, $k);
	    return $current;
    }

    else {
	    if (not $current.left-child.defined) {
	        return $current.right-child;
	    }
	    
	    elsif (not $current.right-child.defined) {
	        return $current.left-child;
	    }
	    
	    else {
	        if ($current.left-child.priority > $current.right-child.priority) {
		        $current = self!right-rotate($current);
		        $current.right-child = self!delete($current.right-child, $k);
		        return $current;
	        }
	        else {
		        $current = self!left-rotate($current);
		        $current.left-child = self!delete($current.left-child, $k);
		        return $current;
	        }
	    }
    }
}

method !right-rotate($y is rw) {
    my $x = $y.left-child;
    my $B = $x.right-child;
    $x.right-child = $y;
    $y.left-child = $B;
    return $x;
}

method !left-rotate($x is rw) {
    my $y = $x.right-child;
    my $B = $y.left-child;
    $y.left-child = $x;
    $x.right-child = $B;
    return $y;
}

method !find($current, $k) {
    return Any if (not $current.defined);

    if ($.lt.($k,$current.key)) {
	    return self!find($current.left-child, $k);
    }
    elsif ($.eq.($k,$current.key)) {
	    return $current;
    }
    else {
	    return self!find($current.right-child, $k);
    }
}

method !find-first-key($root) {
    return Any if (not $root.defined);
    my $current = $root;
    while ($current.left-child.defined) {
	    $current = $current.left-child;
    }
    return $current.key;
}

method !find-last-key($root) {
    return Any if (not $root.defined);
    my $current = $root;
    while ($current.right-child.defined) {
	    $current = $current.right-child;
    }
    return $current.key;
}

method find-first-key() {
    return self!find-first-key($!root);
}

method find-last-key() {
    return self!find-last-key($!root);
}

multi method insert(KeyT $k, $v) {
    if (self!find($!root, $k).defined) {
	    $!root = self!delete($!root, $k);
    }

    $!root = self!insert($!root, $k, $v, rand);
}

multi method insert(KeyT $k, $v, $priority) {
    if (self!find($!root, $k).defined) {
	    $!root = self!delete($!root, $k);
    }

    $!root = self!insert($!root, $k, $v, $priority);
}

method delete($k) {
    $!root = self!delete($!root, $k);
}

method find-value($k) {
    my $node = self!find($!root,$k);
    if ($node.defined) {
	    return $node.value;
    }
    return Any;
}

method find($k) {
    return self!find($!root,$k);
}



head

Algorithm::Treap - randomized search tree


# store Int key
my $treap = Algorithm::Treap[Int].new;
$treap.insert(0, 0);
$treap.insert(1, 10);
$treap.insert(2, 20);
$treap.insert(3, 30);
$treap.insert(4, 40);
my $value = $treap.find-value(3); # 30
my $first-key = $treap.find-first-key(); # 0
my $last-key = $treap.find-last-key(); # 4


# store Str key
my $treap = Algorithm::Treap[Str].new;
$treap.insert('a', 0);
$treap.insert('b', 10);
$treap.insert('c', 20);
$treap.insert('d', 30);
$treap.insert('e', 40);
my $value = $treap.find-value('a'); # 0
my $first-key = $treap.find-first-key(); # 'a'
my $last-key = $treap.find-last-key(); # 'e'


Algorithm::Treap is a implementation of the Treap algorithm. Treap is the one of the self-balancing binary search tree. It employs a randomized strategy for maintaining balance.


my $treap = Algorithm::Treap[::KeyT].new(%options);


Sets either one of the type objects(Int or Str) for C<::KeyT> and some C<%options>, where C<::KeyT> is a type of insertion items to the treap.


item

Sets key order C<TOrder::ASC> or C<TOrder::DESC> in the treap.
Default is C<TOrder::ASC>.


Inserts the key-value pair to the treap.
If the treap already has the same key, it overwrites existing one.


Deletes the node associated with the key from the treap.


Returns the value associated with the key in the treap.
When it doesn't hit any keys, it returns type object Any.


Returns the instance of the Algorithm::Treap::Node associated with the key in the treap.
When it doesn't hit any keys, it returns type object Any.


my $first-key = $treap.find-first-key();


This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.


The algorithm is from Seidel, Raimund, and Cecilia R. Aragon. "Randomized search trees." Algorithmica 16.4-5 (1996): 464-497.


root

README

React

=begin React :component<HeaderCol> :id<menu> 
=para L<Documentation|/doc/introduction>
=para L<Modules| /mods>
=para L<Examples| file:../examples/index.podlite>
=para L<Download |file:../download/index.podlite>
=para L<About|file:../about/index.podlite>
=para 🔍 K<⌘K>/K<ctrl-K>
=end React


=begin React :component<HeaderCol> :id<footer>  
=begin nested :!nested
=item1 B<Language>
    =item2 L<Get started|file:../getting-started/getting-started.podlite>
    =item2 L<Why Raku?|/doc/language/faq#Why-should-I-learn-Raku-What's-so-great-about-it>
    =item2 L<Try Raku|https://glot.io/new/raku>
    =item2 L<Raku cheat sheet|https://github.com/Raku/mu/blob/master/docs/Perl6/Cheatsheet/cheatsheet.txt>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<Raku on Exercism|https://exercism.org/tracks/raku>
    =item2 L<Wikipedia|https://en.wikipedia.org/wiki/Raku_(programming_language)>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=begin nested :!nested

=item1 B<L<Documentation|/doc>>
    =item2 L<Getting started, Migration guides from other languages, & Tutorials | file:../doc/introduction.podlite>
    =item2 L<Language References|file:../doc/reference.podlite>
    =item2 L<Type Reference| file:../doc/types.podlite>
    =item2 L<Miscellaneous| file:../doc/miscellaneous.podlite>
    =item2 L<FAQs (Frequently Asked Questions)|/doc/language/faq>
    =item2 L<Community|/doc/language/community>
    =item2 L<The list of all documents|file:../doc/index.podlite>

=item1 B<Resources>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>

=end nested
=begin nested :!nested

=item1 B<Resoures>
    =item2 L<Download | file:../download/index.podlite>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=item1 B<Learning>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Wikibook |https://en.wikibooks.org/wiki/Raku_Programming>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>
    =item2 L<Learn Raku in Y minutes|https://learnxinyminutes.com/docs/raku/>
    =item2 L<Golfing |https://github.com/AlexDaniel/raku-golf-cheatsheet>
=end nested
=begin nested :!nested

=item1 B<Explore>
    =item2 L<Raku Blog Aggregator|https://planet.raku.org/>
    =item2 L<Rakudo Weekly|https://rakudoweekly.blog/>
    =item2 L<The Weekly Challenge |https://perlweeklychallenge.org/>
    =item2 L<Raku Advent Calendar|https://raku-advent.blog/>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=end React


=begin React :component<CookieConsent> :id<CookieConsent> :buttonCaption("Got it!")
=para
This website uses cookies for analytics.
=end React


Treap

NAME

SYNOPSIS

DESCRIPTION

CONSTRUCTOR

new

OPTIONS

METHODS

insert

delete

find-value

find

find-first-key

find-last-key

METHODS NOT YET IMPLEMENTED

AUTHOR

COPYRIGHT AND LICENSE

Algorithm::Treap v0.10.1

Authors

License

Dependencies

Test Dependencies

Provides

Documentation