Skip to content
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

Closed
p6rt opened this issue May 20, 2008 · 12 comments
Closed

Initial implementation of sort for rakudo's List. #90

p6rt opened this issue May 20, 2008 · 12 comments
Labels

Comments

@p6rt
Copy link

p6rt commented May 20, 2008

Migrated from rt.perl.org#54514 (status was 'resolved')

Searchable as RT54514$

@p6rt
Copy link
Author

p6rt commented May 20, 2008

From @bacek

Hello.

There is initial implementation of sort for Lists. Only
src/classes/List.pir affected.

Example output​:

bacek@​icebolt​:~/src/parrot/languages/perl6$ cat s2.t
my @​l = ('a', 'b', 'c', 'd', 1, 2, 3, 4);
my @​l1 = sort @​l;
say ~@​l1;

bacek@​icebolt​:~/src/parrot/languages/perl6$ ../../parrot perl6.pbc s2.t
1 2 3 4 a b c d

bacek@​icebolt​:~/src/parrot/languages/perl6$ cat s3.t
my @​l = ('a', 'b', 'c', 'd', 1, 2, 3, 4);
my @​l1 = sort { $^b <=> $^a } , @​l;
say ~@​l1;

bacek@​icebolt​:~/src/parrot/languages/perl6$ ../../parrot perl6.pbc s3.t
4 3 2 1 d c b a

--
Bacek

@p6rt
Copy link
Author

p6rt commented May 20, 2008

From @bacek

sort.diff
Index: 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

@p6rt
Copy link
Author

p6rt commented May 21, 2008

From @bacek

On Tue May 20 05​:53​:16 2008, bacek wrote​:

Hello.

There is initial implementation of sort for Lists. Only
src/classes/List.pir affected.

There is another implementation based on FixedPMCArray.

--
Bacek

@p6rt
Copy link
Author

p6rt commented May 21, 2008

From @bacek

sort.diff

@p6rt
Copy link
Author

p6rt commented May 21, 2008

From @bacek

On Tue May 20 05​:53​:16 2008, bacek wrote​:

Hello.

There is initial implementation of sort for Lists. Only
src/classes/List.pir affected.

There is another implementation based on FixedPMCArray.

--
Bacek

@p6rt
Copy link
Author

p6rt commented May 21, 2008

@bacek - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

p6rt commented May 21, 2008

From @bacek

On Tue May 20 23​:20​:41 2008, bacek wrote​:

There is another implementation based on FixedPMCArray.

Reworked version of patch after Jonathan review of old one.

--
Bacek

@p6rt
Copy link
Author

p6rt commented May 21, 2008

From @bacek

sort.diff
Index: 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.

@p6rt
Copy link
Author

p6rt commented May 21, 2008

From @bacek

And another one

:)

--
Bacek

@p6rt
Copy link
Author

p6rt commented May 21, 2008

From @bacek

sort2.diff
Index: 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.

@p6rt
Copy link
Author

p6rt commented May 24, 2008

From @bacek

Commited by jonathan in r27707

@p6rt
Copy link
Author

p6rt commented May 24, 2008

@bacek - Status changed from 'open' to 'resolved'

@p6rt p6rt closed this as completed May 24, 2008
@p6rt p6rt added the patch label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant