New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Initial implementation of sort for rakudo's List. #90
Comments
From @bacekHello. There is initial implementation of sort for Lists. Only Example output: bacek@icebolt:~/src/parrot/languages/perl6$ cat s2.t bacek@icebolt:~/src/parrot/languages/perl6$ ../../parrot perl6.pbc s2.t bacek@icebolt:~/src/parrot/languages/perl6$ cat s3.t bacek@icebolt:~/src/parrot/languages/perl6$ ../../parrot perl6.pbc s3.t -- |
From @baceksort.diffIndex: src/classes/List.pir
===================================================================
--- src/classes/List.pir (revision 27652)
+++ src/classes/List.pir (working copy)
@@ -1018,6 +1036,148 @@
.return list.'uniq'()
.end
+=item $!merge
+
+Subsubroutine for merge-sort
+
+=cut
+
+.sub '$!merge'
+ .param pmc comparer
+ .param pmc left
+ .param pmc right
+ .local pmc result, l, r
+ .local int have_left, have_right
+ .local pmc closure
+
+ result = new 'List'
+ $I0 = elements left
+ $I1 = elements right
+
+ have_left = 0
+ have_right = 0
+
+ loop_start:
+
+ shift_left:
+ if have_left goto shift_right
+ unless left goto finish_right
+ l = shift left
+ have_left = 1
+
+ shift_right:
+ if have_right goto loop_body
+ unless right goto finish_left
+
+ r = shift right
+ have_right = 1
+
+ loop_body:
+ closure = newclosure comparer
+ $I0 = closure(l, r)
+ if $I0 < 0 goto push_left
+
+ push_right:
+ push result, r
+ have_right = 0
+ goto loop_start
+
+ push_left:
+ push result, l
+ have_left = 0
+ goto loop_start
+
+
+ finish_left:
+ unless have_left goto finish_left_tail
+ push result, l
+ finish_left_tail:
+ unless left goto finish_right
+ l = shift left
+ push result, l
+ goto finish_left_tail
+
+ finish_right:
+ unless have_right goto finish_right_tail
+ push result, r
+ finish_right_tail:
+ unless right goto finish
+ r = shift right
+ push result, r
+ goto finish_right_tail
+
+ finish:
+ .return (result)
+
+.end
+
+=item $!merge_sort
+
+Implementation of merge-sort algorithm
+
+=cut
+
+.sub '$!merge_sort'
+ .param pmc comparer
+ .param pmc list
+ .local pmc left, right, result, elem
+ .local int len, half
+
+ len = elements list
+
+ unless len <= 1 goto lets_sort
+ .return (list)
+
+ lets_sort:
+ left = new 'List'
+ right = new 'List'
+ half = len / 2
+
+ create_left:
+ if half < 1 goto create_right
+ elem = shift list
+ push left, elem
+ dec half
+ goto create_left
+
+ create_right:
+ len = elements list
+ if len < 1 goto do_it
+
+ elem = shift list
+ push right, elem
+ goto create_right
+
+ do_it:
+ left = '$!merge_sort'(comparer, left)
+ right = '$!merge_sort'(comparer, right)
+ result = '$!merge'(left, right)
+ .return (result)
+.end
+
+
+.sub sort :multi(_, 'List')
+ .param pmc sorter
+ .param pmc list :slurpy
+ .local pmc sorted
+
+ sorted = '$!merge_sort'(sorter, list :flat)
+
+ .return (sorted)
+.end
+
+.sub sort :multi('List')
+ .param pmc list :slurpy
+ .local pmc sorted
+
+ get_global $P0, "infix:cmp"
+ sorted = '$!merge_sort'($P0, list :flat)
+
+ $P0 = 'list'(sorted)
+ .return ($P0)
+.end
+
+
## TODO: join map reduce sort zip
=back
|
From @bacekOn Tue May 20 05:53:16 2008, bacek wrote:
There is another implementation based on FixedPMCArray. -- |
From @bacekOn Tue May 20 05:53:16 2008, bacek wrote:
There is another implementation based on FixedPMCArray. -- |
@bacek - Status changed from 'new' to 'open' |
From @bacekOn Tue May 20 23:20:41 2008, bacek wrote:
Reworked version of patch after Jonathan review of old one. -- |
From @baceksort.diffIndex: src/classes/List.pir
===================================================================
--- src/classes/List.pir (revision 27698)
+++ src/classes/List.pir (working copy)
@@ -633,6 +633,58 @@
=back
+=item !sort()
+
+Sort list by copying into FPA, sorting and creating new List.
+
+=cut
+
+.sub '!sort' :method
+ .param pmc comparer
+ .local pmc elem, arr, comparer
+ .local int len, i
+
+ # Creating FPA
+ arr = new 'FixedPMCArray'
+ len = elements self
+ arr = len
+
+ # Copy all elements into it
+ i = 0
+ copy_to:
+ if i == len goto done_to
+ elem = self[i]
+ arr[i] = elem
+ inc i
+ goto copy_to
+
+ done_to:
+
+ # Sort in-place
+ arr.'sort'(comparer)
+
+ # and return new List.
+ .return 'list'(arr)
+.end
+
+=head2 sort()
+
+Sort list in-place
+
+=cut
+
+.sub 'sort' :method
+ .local pmc comparer
+ .local pmc res
+
+ get_hll_global comparer, 'infix:leg'
+ res = self.'!sort'(comparer)
+
+ .return (res)
+.end
+
+
+
=head1 Functions
=over 4
@@ -668,6 +720,36 @@
.end
+=item C<sort>
+
+Sort arguments.
+
+=cut
+
+.sub 'sort' :multi(_)
+ .param pmc args :slurpy
+ .local pmc l
+
+ l = 'list'(args :flat)
+ .return l.'sort'()
+.end
+
+=item C<sort>
+
+Sort arguments using comparition sub.
+
+=cut
+
+.sub 'sort' :multi(_,_)
+ .param pmc comparer
+ .param pmc args :slurpy
+ .local pmc l
+
+ l = 'list'(args :flat)
+ .return l.'!sort'(comparer)
+.end
+
+
=item C<infix:,(...)>
Operator form for building a list from its arguments.
|
From @bacekAnd another one :) -- |
From @baceksort2.diffIndex: src/classes/List.pir
===================================================================
--- src/classes/List.pir (revision 27698)
+++ src/classes/List.pir (working copy)
@@ -633,6 +633,48 @@
=back
+=item sort()
+
+Sort list by copying into FPA, sorting and creating new List.
+
+=cut
+
+.sub 'sort' :method
+ .param pmc comparer :optional
+ .param int have_comparer :opt_flag
+ .local pmc elem, arr, comparer
+ .local int len, i
+
+ # Creating FPA
+ arr = new 'FixedPMCArray'
+ len = elements self
+ arr = len
+
+ # Copy all elements into it
+ i = 0
+ copy_to:
+ if i == len goto done_to
+ elem = self[i]
+ arr[i] = elem
+ inc i
+ goto copy_to
+
+ done_to:
+
+ # Check comparer
+ if have_comparer goto do_sort
+ get_hll_global comparer, 'infix:cmp'
+
+ do_sort:
+
+ # Sort in-place
+ arr.'sort'(comparer)
+
+ # and return new List.
+ .return 'list'(arr)
+.end
+
+
=head1 Functions
=over 4
@@ -668,6 +710,22 @@
.end
+=item C<sort>
+
+Sort arguments using (optional) comparition sub.
+
+=cut
+
+.sub 'sort'
+ .param pmc comparer :optional
+ .param pmc args :slurpy
+ .local pmc l
+
+ l = 'list'(args :flat)
+ .return l.'sort'(comparer)
+.end
+
+
=item C<infix:,(...)>
Operator form for building a list from its arguments.
|
From @bacekCommited by jonathan in r27707 |
@bacek - Status changed from 'open' to 'resolved' |
Migrated from rt.perl.org#54514 (status was 'resolved')
Searchable as RT54514$
The text was updated successfully, but these errors were encountered: