Back to dada's perl lab
|
|
List Operations |
Back to the Win32 Shootout Back to dada's perl lab |
| All Source For List Operations |
|---|
| lists.bcc |
/* -*- mode: c -*-
* $Id: lists.gcc,v 1.3 2001/04/29 04:39:50 doug Exp $
* http://www.bagley.org/~doug/shootout/
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10000
// a simple Double Linked List
// the head node is special, it's val is length of list
typedef struct DLL {
int val;
struct DLL *next;
struct DLL *prev;
} DLL;
int list_length(DLL *head) { return(head->val); }
int list_empty(DLL *head) { return(list_length(head) == 0); }
DLL *list_first(DLL *head) { return(head->next); }
DLL *list_last(DLL *head) { return(head->prev); }
void list_push_tail(DLL *head, DLL *item) {
DLL *tail = head->prev;
tail->next = item;
item->next = head;
head->prev = item;
item->prev = tail;
head->val++;
}
DLL *list_pop_tail(DLL *head) {
DLL *prev, *tail;
if (list_empty(head)) return(NULL);
tail = head->prev;
prev = tail->prev;
prev->next = head;
head->prev = prev;
head->val--;
return(tail);
}
void list_push_head(DLL *head, DLL *item) {
DLL *next = head->next;
head->next = item;
next->prev = item;
item->next = next;
item->prev = head;
head->val++;
}
DLL *list_pop_head(DLL *head) {
DLL *next;
if (list_empty(head)) return(NULL);
next = head->next;
head->next = next->next;
next->next->prev = head;
head->val--;
return(next);
}
int list_equal(DLL *x, DLL *y) {
DLL *xp, *yp;
// first val's checked will be list lengths
for (xp=x, yp=y; xp->next != x; xp=xp->next, yp=yp->next) {
if (xp->val != yp->val) return(0);
}
if (xp->val != yp->val) return(0);
return(yp->next == y);
}
void list_print(char *msg, DLL *x) {
DLL *xp, *first = x->next;
int i = 0;
printf(msg);
printf("length: %d\n", list_length(x));
for (xp=x->next; xp->next != first; xp=xp->next) {
printf("i:%3d v:%3d n:%3d p:%3d\n", ++i,
xp->val, xp->next->val, xp->prev->val);
}
printf("[last entry points to list head]\n");
printf("[val of next of tail is: %d]\n", xp->next->val);
}
DLL *list_new() {
DLL *l = (DLL *)malloc(sizeof(DLL));
l->next = l;
l->prev = l;
l->val = 0;
return(l);
}
DLL *list_sequence(int from, int to) {
int size, tmp, i, j;
DLL *l;
if (from > to) {
tmp = from; from = to; to = tmp;
}
size = to - from + 1;
l = (DLL *)malloc((size+1) * sizeof(DLL));
from--;
for (i=0, j=1; i<size; ++i, ++j) {
l[i].next = &l[i+1];
l[j].prev = &l[j-1];
l[i].val = from++;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].prev = &l[size-1];
l[size].val = from;
l[0].val = size;
return(l);
}
DLL *list_copy(DLL *x) {
int i, j, size = list_length(x);
DLL *xp, *l = (DLL *)malloc((size+1) * sizeof(DLL));
for (i=0, j=1, xp=x; i<size; i++, j++, xp=xp->next) {
l[i].next = &l[j];
l[j].prev = &l[i];
l[i].val = xp->val;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].val = list_last(x)->val;
return(l);
}
void list_reverse (DLL *head) {
DLL *tmp, *p = head;
do {
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = tmp;
} while (p != head);
}
int test_lists() {
int len = 0;
// create a list of integers (li1) from 1 to SIZE
DLL *li1 = list_sequence(1, SIZE);
// copy the list to li2
DLL *li2 = list_copy(li1);
// remove each individual item from left side of li2 and
// append to right side of li3 (preserving order)
DLL *li3 = list_new();
// compare li2 and li1 for equality
if (!list_equal(li2, li1)) {
fprintf(stderr, "li2 and li1 are not equal\n");
exit(1);
}
while (!list_empty(li2)) {
list_push_tail(li3, list_pop_head(li2));
}
// li2 must now be empty
if (!list_empty(li2)) {
fprintf(stderr, "li2 should be empty now\n");
exit(1);
}
// remove each individual item from right side of li3 and
// append to right side of li2 (reversing list)
while (!list_empty(li3)) {
list_push_tail(li2, list_pop_tail(li3));
}
// li3 must now be empty
if (!list_empty(li3)) {
fprintf(stderr, "li3 should be empty now\n");
exit(1);
}
// reverse li1 in place
list_reverse(li1);
// check that li1's first item is now SIZE
if (list_first(li1)->val != SIZE) {
fprintf(stderr, "li1 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li1)->val);
exit(1);
}
// check that li1's last item is now 1
if (list_last(li1)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li1)->val);
exit(1);
}
// check that li2's first item is now SIZE
if (list_first(li2)->val != SIZE) {
fprintf(stderr, "li2 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li2)->val);
exit(1);
}
// check that li2's last item is now 1
if (list_last(li2)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li2)->val);
exit(1);
}
// check that li1's length is still SIZE
if (list_length(li1) != SIZE) {
fprintf(stderr, "li1 size wrong, wanted %d, got %d\n",
SIZE, list_length(li1));
exit(1);
}
// compare li1 and li2 for equality
if (!list_equal(li1, li2)) {
fprintf(stderr, "li1 and li2 are not equal\n");
exit(1);
}
len = list_length(li1);
free(li1);
free(li2);
free(li3);
// return the length of the list
return(len);
}
int main(int argc, char *argv[]) {
int n = ((argc == 2) ? atoi(argv[1]) : 1);
int result = 0;
while(n--) result = test_lists();
printf("%d\n", result);
return 0;
}
|
| lists.bigforth |
\ -*- mode: forth -*-
\ $Id: lists.bigforth,v 1.1 2001/06/19 16:20:46 doug Exp $
\ http://www.bagley.org/~doug/shootout/
\ from Anton Ertl
0. argc @ 1- arg >number 2drop drop constant NUM
10000 constant SIZE
struct
cell% field list-next
cell% field list-val
end-struct list%
: make-list
0 0 SIZE -do
list% %alloc
i over list-val !
tuck list-next !
1 -loop
;
: copy-list
0 { w^ list2 }
list2 begin
over
while
list% %alloc dup >r swap !
dup list-val @ r@ list-val !
list-next @ r> list-next
repeat
off drop list2 @ ;
: move-head-to-tail
\ somehow this is an expensive noop
0 { w^ list2 }
list2 begin
over
while
\ move one element
over list-next dup @ 2>r
over list-next off
! r> r>
repeat
off drop list2 @ ;
: nreverse
\ destructive reverse
0 swap begin
dup
while
dup list-next @ >r
tuck list-next ! r>
repeat
drop ;
: move-tail-to-tail
\ use head-to-tail instead of head-to-head nreverse
nreverse move-head-to-tail ;
: list-equals
begin
dup
while
over
while
over list-val @ over list-val @ <> if
2drop false exit
endif
list-next @ swap list-next @
repeat then
= ;
: list-length
0 begin
over
while
1+ swap list-next @ swap
repeat
nip ;
s" wrong result" exception constant wrong-result
: main
0 NUM 0 ?do
drop
make-list dup copy-list
move-head-to-tail move-tail-to-tail swap nreverse
dup list-val @ SIZE <> wrong-result and throw
tuck list-equals 0= wrong-result and throw
list-length
loop ;
main 0 .r cr bye
|
| lists.csharp |
// $Id: listops.csharp,v 1.0 2002/09/28 10:21:00 dada Exp $
// http://dada.perl.it/shootout/
// contributed by Erik Saltwell
using System;
namespace ListOps
{
class IntDeQueue : ICloneable
{
private int[] data=null;
private int start=0;
private int end=0;
private int size=0;
private int temp=0;
public bool Empty{get{return start==end;}}
public object Clone()
{
IntDeQueue temp =new IntDeQueue(size-1);
temp.start=start;
temp.end=end;
data.CopyTo(temp.data, 0);
return temp;
}
public bool Equals(IntDeQueue other)
{
if(Count!=other.Count)
return false;
int i = this.start;
int iOther = other.start;
while(i!=this.end)
{
if(data[i]!=other.data[iOther])
return false;
Advance(ref i);
other.Advance(ref iOther);
}
return true;
}
public int Count
{
get
{
if(end>=start)
return end-start;
else
return size + end - start;
}
}
public void Reverse()
{
if(Count<2)
return;
Array.Reverse(data);
int endEnd=size-1;
int startEnd=0;
if(end<start)
{
endEnd = 0;
startEnd=size-1;
}
int temp = start;
Regress(ref end);
start = Math.Abs(startEnd - Math.Abs(end - endEnd));
end = Math.Abs(endEnd - Math.Abs(temp - startEnd));
Advance(ref end);
}
public void PushFront(int i)
{
temp = start;
Regress(ref start);
if(start==end)
{
start=temp;
throw new System.Exception("Invalid operation");
}
data[start]=i;
}
public int PopFront()
{
int i=data[start];
if(start!=end)
Advance(ref start);
else
throw new System.Exception("Invalid operation");
return i;
}
public int PeekFront()
{
if(start==end)
throw new System.Exception("Invalid Operation");
return data[start];
}
public int PeekBack()
{
if(start==end)
throw new System.Exception("Invalid Operation");
int temp = end;
Regress(ref temp);
return data[temp];
}
public void PushBack(int i)
{
temp = end;
Advance(ref end);
if(start==end)
{
end= temp;
throw new System.Exception("Invalid operation");
}
data[temp]=i;
}
public int PopBack()
{
if(start!=end)
Regress(ref end);
else
throw new System.Exception("Invalid operation");
return data[end];
}
public IntDeQueue(int Size){data = new int[Size+1];this.size=Size+1;}
private void Advance(ref int item)
{
if((++item)==size)
item=0;
}
private void Regress(ref int item)
{
if(item!=0)
--item;
else
item = (size-1);
}
public void Clear()
{
start=0;
end=0;
}
}
class App
{
public const int SIZE=10000;
[STAThread]
static void Main(string[] args)
{
int n=int.Parse(args[0]);
int result=0;
for(int i=0;i<n;++i)
result = RunLists();
Console.WriteLine(result);
}
static public int RunLists()
{
IntDeQueue q = new IntDeQueue(SIZE);
for(int i=0;i<SIZE;++i)
q.PushBack(i+1);
IntDeQueue q2 = (IntDeQueue)q.Clone();
IntDeQueue q3=new IntDeQueue(SIZE);
while(!q2.Empty)
q3.PushBack(q2.PopFront());
while(!q3.Empty)
q2.PushBack(q3.PopBack());
q.Reverse();
if(q.PeekFront() != SIZE)
{
Console.WriteLine("q.PeekFront()!=SIZE");
return 0;
}
if(!q.Equals(q2))
{
Console.WriteLine("q!=q2");
return 0;
}
return q.Count;
}
}
}
|
| lists.cygperl |
#!/usr/local/bin/perl
# $Id: lists.perl,v 1.3 2001/05/06 15:50:16 doug Exp $
use strict;
my $SIZE = 10000;
my $ITER = $ARGV[0];
$ITER = 1 if ($ITER < 1);
my $result = 0;
while ($ITER--) {
$result = &test_lists();
}
print "$result\n";
sub test_lists {
# create a list of integers (Li1) from 1 to SIZE
my @Li1 = (1..$SIZE);
# copy the list to Li2 (not by individual items)
my @Li2 = @Li1;
my @Li3 = ();
# remove each individual item from left side of Li2 and
# append to right side of Li3 (preserving order)
push(@Li3, shift @Li2) while (@Li2);
# Li2 must now be empty
# remove each individual item from right side of Li3 and
# append to right side of Li2 (reversing list)
push(@Li2, pop @Li3) while (@Li3);
# Li3 must now be empty
# reverse Li1 in place
@Li1 = reverse @Li1;
# check that first item is now SIZE
return(0) if $Li1[0] != $SIZE;
# compare Li1 and Li2 for equality
my $len1 = scalar(@Li1);
my $len2 = scalar(@Li2);
my $lists_equal = ($len1 == $len2);
return(0) if not $lists_equal;
for my $i (0..($len1-1)) {
if ($Li1[$i] != $Li2[$i]) {
$lists_equal = 0;
last;
}
}
return(0) if not $lists_equal;
# return the length of the list
return($len1);
}
|
| lists.delphi |
program lists2;
uses linkedList in 'linkedList.pas';
const SIZE = 10000;
var NUM: cardinal;
code, i, j, k: integer;
l1,l2,l3: TLinkedList;
begin
NUM:=1;
if ParamCount=1 then Val(ParamStr(1),NUM,code);
for i:=1 to NUM do begin
l1:=TLinkedList.Create;
l2:=TLinkedList.Create;
l3:=TLinkedList.Create;
for j:=1 to SIZE do
l1.addTail(j);
if l1.getFirst(j) then
repeat
l2.addTail(j);
until not l1.getNext(j);
for j:=1 to SIZE do
l3.addTail(l2.removeFront);
for j:=1 to SIZE do
l2.addTail(l3.removeTail);
l1.reverse;
l1.getFirst(j);
if j<>SIZE then begin
writeln('l1 has invalid first element'); exit;
end;
if (l1.Count<>SIZE)or(l1.Count<>l2.Count) then begin
writeln('sizes don''t match'); exit;
end;
l1.getFirst(j); l2.getFirst(k);
repeat
if j<>k then begin
writeln('l1 and l2 not equal'); exit;
end;
until not(l1.getNext(j) and l2.getNext(k));
writeln(l1.count);
l1.Destroy; l2.Destroy; l3.Destroy;
end;
end.
|
| lists.fpascal |
Program lists;
uses SysUtils, classes;
const SIZE : longint = 10000;
Function test_lists : integer;
var
i, len1, len2 : longint;
Li1, Li2, Li3 : TList;
lists_equal : Integer;
begin
Li1 := TList.Create;
Li1.Capacity := SIZE;
For i := 0 to SIZE Do
Li1.Add(Pointer(i));
Li2 := TList.Create;
Li2.Capacity := SIZE;
For i:= 0 to SIZE Do
Li2.Add(Li1.Items[i]);
{ remove each individual item from left side of Li2 and
append to right side of Li3 (preserving order) }
Li3 := TList.Create;
Li3.Capacity := SIZE;
For i := 0 to SIZE Do
begin
Li3.Add( Li2.First );
Li2.Remove( Li2.First );
end;
{ remove each individual item from right side of Li3 and
append to right side of Li2 (reversing list) }
For i := 0 To SIZE Do
begin
Li2.Add( Li3.Last );
Li3.Count -= 1;
end;
For i := 0 To (SIZE div 2) Do
begin
Li1.Exchange( i, SIZE-i );
end;
If longint(Li1.first) <> SIZE Then
begin
test_lists := 0;
exit;
end;
len1 := Li1.Count - 1;
len2 := Li2.Count - 1;
If len1 <> len2 Then
begin
test_lists := 0;
exit;
end;
lists_equal := 1;
For i := 0 To len1 Do
begin
If longint(Li1.items[i]) <> longint(Li2.items[i]) Then
begin
lists_equal := 0;
break;
end;
end;
If lists_equal = 0 Then
begin
test_lists := 0;
end
else
test_lists := len1;
end;
var
ITER, i, result: integer;
begin
if ParamCount = 0 then
ITER := 1
else
ITER := StrToInt(ParamStr(1));
if ITER < 1 then ITER := 1;
For i := 1 To ITER Do result := test_lists();
Writeln (IntToStr(result));
end.
|
| lists.gcc |
/* -*- mode: c -*-
* $Id: lists.gcc,v 1.3 2001/04/29 04:39:50 doug Exp $
* http://www.bagley.org/~doug/shootout/
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define SIZE 10000
// a simple Double Linked List
// the head node is special, it's val is length of list
typedef struct DLL {
int val;
struct DLL *next;
struct DLL *prev;
} DLL;
inline int list_length(DLL *head) { return(head->val); }
inline int list_empty(DLL *head) { return(list_length(head) == 0); }
inline DLL *list_first(DLL *head) { return(head->next); }
inline DLL *list_last(DLL *head) { return(head->prev); }
void list_push_tail(DLL *head, DLL *item) {
DLL *tail = head->prev;
tail->next = item;
item->next = head;
head->prev = item;
item->prev = tail;
head->val++;
}
DLL *list_pop_tail(DLL *head) {
DLL *prev, *tail;
if (list_empty(head)) return(NULL);
tail = head->prev;
prev = tail->prev;
prev->next = head;
head->prev = prev;
head->val--;
return(tail);
}
void list_push_head(DLL *head, DLL *item) {
DLL *next = head->next;
head->next = item;
next->prev = item;
item->next = next;
item->prev = head;
head->val++;
}
DLL *list_pop_head(DLL *head) {
DLL *next;
if (list_empty(head)) return(NULL);
next = head->next;
head->next = next->next;
next->next->prev = head;
head->val--;
return(next);
}
int list_equal(DLL *x, DLL *y) {
DLL *xp, *yp;
// first val's checked will be list lengths
for (xp=x, yp=y; xp->next != x; xp=xp->next, yp=yp->next) {
if (xp->val != yp->val) return(0);
}
if (xp->val != yp->val) return(0);
return(yp->next == y);
}
void list_print(char *msg, DLL *x) {
DLL *xp, *first = x->next;
int i = 0;
printf(msg);
printf("length: %d\n", list_length(x));
for (xp=x->next; xp->next != first; xp=xp->next) {
printf("i:%3d v:%3d n:%3d p:%3d\n", ++i,
xp->val, xp->next->val, xp->prev->val);
}
printf("[last entry points to list head]\n");
printf("[val of next of tail is: %d]\n", xp->next->val);
}
DLL *list_new() {
DLL *l = (DLL *)malloc(sizeof(DLL));
l->next = l;
l->prev = l;
l->val = 0;
return(l);
}
DLL *list_sequence(int from, int to) {
int size, tmp, i, j;
DLL *l;
if (from > to) {
tmp = from; from = to; to = tmp;
}
size = to - from + 1;
l = (DLL *)malloc((size+1) * sizeof(DLL));
from--;
for (i=0, j=1; i<size; ++i, ++j) {
l[i].next = &l[i+1];
l[j].prev = &l[j-1];
l[i].val = from++;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].prev = &l[size-1];
l[size].val = from;
l[0].val = size;
return(l);
}
DLL *list_copy(DLL *x) {
int i, j, size = list_length(x);
DLL *xp, *l = (DLL *)malloc((size+1) * sizeof(DLL));
for (i=0, j=1, xp=x; i<size; i++, j++, xp=xp->next) {
l[i].next = &l[j];
l[j].prev = &l[i];
l[i].val = xp->val;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].val = list_last(x)->val;
return(l);
}
void list_reverse (DLL *head) {
DLL *tmp, *p = head;
do {
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = tmp;
} while (p != head);
}
int test_lists() {
int len = 0;
// create a list of integers (li1) from 1 to SIZE
DLL *li1 = list_sequence(1, SIZE);
// copy the list to li2
DLL *li2 = list_copy(li1);
// remove each individual item from left side of li2 and
// append to right side of li3 (preserving order)
DLL *li3 = list_new();
// compare li2 and li1 for equality
if (!list_equal(li2, li1)) {
fprintf(stderr, "li2 and li1 are not equal\n");
exit(1);
}
while (!list_empty(li2)) {
list_push_tail(li3, list_pop_head(li2));
}
// li2 must now be empty
if (!list_empty(li2)) {
fprintf(stderr, "li2 should be empty now\n");
exit(1);
}
// remove each individual item from right side of li3 and
// append to right side of li2 (reversing list)
while (!list_empty(li3)) {
list_push_tail(li2, list_pop_tail(li3));
}
// li3 must now be empty
if (!list_empty(li3)) {
fprintf(stderr, "li3 should be empty now\n");
exit(1);
}
// reverse li1 in place
list_reverse(li1);
// check that li1's first item is now SIZE
if (list_first(li1)->val != SIZE) {
fprintf(stderr, "li1 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li1)->val);
exit(1);
}
// check that li1's last item is now 1
if (list_last(li1)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li1)->val);
exit(1);
}
// check that li2's first item is now SIZE
if (list_first(li2)->val != SIZE) {
fprintf(stderr, "li2 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li2)->val);
exit(1);
}
// check that li2's last item is now 1
if (list_last(li2)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li2)->val);
exit(1);
}
// check that li1's length is still SIZE
if (list_length(li1) != SIZE) {
fprintf(stderr, "li1 size wrong, wanted %d, got %d\n",
SIZE, list_length(li1));
exit(1);
}
// compare li1 and li2 for equality
if (!list_equal(li1, li2)) {
fprintf(stderr, "li1 and li2 are not equal\n");
exit(1);
}
len = list_length(li1);
free(li1);
free(li2);
free(li3);
// return the length of the list
return(len);
}
int main(int argc, char *argv[]) {
int n = ((argc == 2) ? atoi(argv[1]) : 1);
int result = 0;
while(n--) result = test_lists();
printf("%d\n", result);
return 0;
}
|
| lists.gforth |
\ -*- mode: forth -*-
\ $Id: lists.gforth,v 1.1 2001/05/26 20:10:05 doug Exp $
\ http://www.bagley.org/~doug/shootout/
\ from Anton Ertl
0. argc @ 1- arg >number 2drop drop constant NUM
10000 constant SIZE
struct
cell% field list-next
cell% field list-val
end-struct list%
: make-list
0 0 SIZE -do
list% %alloc
i over list-val !
tuck list-next !
1 -loop
;
: copy-list
0 { w^ list2 }
list2 begin
over
while
list% %alloc dup >r swap !
dup list-val @ r@ list-val !
list-next @ r> list-next
repeat
off drop list2 @ ;
: move-head-to-tail
\ somehow this is an expensive noop
0 { w^ list2 }
list2 begin
over
while
\ move one element
over list-next dup @ 2>r
over list-next off
! r> r>
repeat
off drop list2 @ ;
: nreverse
\ destructive reverse
0 swap begin
dup
while
dup list-next @ >r
tuck list-next ! r>
repeat
drop ;
: move-tail-to-tail
\ use head-to-tail instead of head-to-head nreverse
nreverse move-head-to-tail ;
: list-equals
begin
dup
while
over
while
over list-val @ over list-val @ <> if
2drop false exit
endif
list-next @ swap list-next @
repeat then
= ;
: list-length
0 begin
over
while
1+ swap list-next @ swap
repeat
nip ;
s" wrong result" exception constant wrong-result
: main
0 NUM 0 ?do
drop
make-list dup copy-list
move-head-to-tail move-tail-to-tail swap nreverse
dup list-val @ SIZE <> wrong-result and throw
tuck list-equals 0= wrong-result and throw
list-length
loop ;
main 0 .r cr bye
|
| lists.ghc |
-- $Id: lists.ghc,v 1.1 2001/06/12 04:47:12 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- from Michal Gajda
module Main(main) where
import Prelude
copy [] = []
copy (x:xs) = x:copy xs
-- to be honest, in pure functional language the RIGHT
-- thing is copy list = list, because it's not mutable anyway
-- (and the price is paid when doing reverse or (++) anyway)
-- `seq`s below force evaluation of isok1 and isok2
test :: Int -> Int
test size = isok1 `seq` length l3
where single x = [x]
l1 = [1..size]
l2 = copy l1 -- Should be just: "l1"
l3 = foldl (++) [] (map single l2)
l2' = foldr (++) [] (map single l3)
l1' = reverse l1
isok1 = head l1' == size
isok2 = l1' == l2'
main = do s <- getLine
putStrLn . show . test . read $ s
|
| lists.guile |
#!/usr/local/bin/guile \
-e main -s
!#
;;; $Id: lists.guile,v 1.2 2001/06/29 23:12:37 doug Exp $
;;; http://www.bagley.org/~doug/shootout/
;;; from Brad Knotwell
(use-modules (ice-9 format))
(define SIZE 10000)
(define Li1 (cdr (iota (+ SIZE 1))))
(define Li2 (list-copy Li1))
(define Li3 '())
;;; note the reverses
;;; AFAIK, guile doesn't have a primitive for grabbing elts from the
;;; end of a list. no scheme programmer would do this anyway. they'd
;;; reverse the list in place
(define (test-lists)
(begin
(do ((elt (car Li2) (car Li2)))
((eq? (cdr Li2) '()) (begin (set! Li3 (cons elt Li3))
(set! Li2 '())
(set! Li3 (reverse! Li3))))
(begin (set! Li3 (cons elt Li3))
(set! Li2 (cdr Li2))))
(set! Li3 (reverse! Li3))
(do ((elt (car Li3) (car Li3)))
((eq? (cdr Li3) '()) (begin (set! Li2 (cons elt Li2))
(set! Li3 '())
(set! Li2 (reverse! Li2))))
(begin (set! Li2 (cons elt Li2))
(set! Li3 (cdr Li3))))
(set! Li1 (reverse! Li1))
(if (and (= (car Li1) SIZE) (every-2? = Li1 Li2)) (length Li1) 0)))
(define every-2? (lambda (test l1 l2)
(or (null? l1)
(and (test (car l1) (car l2))
(every-2? test (cdr l1) (cdr l2))))))
(define (main args)
(let ((n (or (and (= (length args) 2) (string->;number (cadr args))) 1)))
(do ((i n (set! n (1- n))))
((= n 1) (write-line (test-lists)))
(test-lists))))
|
| lists.ici |
// $Id: lists.ici,v 1.0 2003/01/03 12:20:00 dada Exp $
// http://dada.perl.it/shootout
//
// contributed by Tim Long
NUM = argv[1] ? int(argv[1]) : 1;
static SIZE = 10000;
static
test_lists()
{
li1 = array();
for (i := 0; i < SIZE; )
i = li1[i] = i + 1;
li2 = copy(li1);
li3 = array();
while(nels(li2))
push(li3, rpop(li2));
while (nels(li3))
push(li2, pop(li3));
n := SIZE / 2;
for (i := 0; i < n; ++i)
li1[i] <=> li1[SIZE - i - 1];
if (li1[0] != SIZE || li1 != li2)
return 0;
return nels(li1);
}
for (i = 0; i < NUM; ++i)
result = test_lists();
printf("%d\n", result);
|
| lists.java |
// $Id: lists.java,v 1.1 2001/01/14 18:13:15 doug Exp $
// http://www.bagley.org/~doug/shootout/
import java.io.*;
import java.util.*;
import java.text.*;
public class lists {
static int SIZE = 10000;
public static void main(String args[]) {
int n = Integer.parseInt(args[0]);
int result = 0;
for (int i = 0; i < n; i++) {
result = test_lists();
}
System.out.println(result);
}
public static int test_lists() {
int result = 0;
// create a list of integers (Li1) from 1 to SIZE
LinkedList Li1 = new LinkedList();
for (int i = 1; i < SIZE+1; i++) {
Li1.addLast(new Integer(i));
}
// copy the list to Li2 (not by individual items)
LinkedList Li2 = new LinkedList(Li1);
LinkedList Li3 = new LinkedList();
// remove each individual item from left side of Li2 and
// append to right side of Li3 (preserving order)
while (! Li2.isEmpty()) {
Li3.addLast(Li2.removeFirst());
}
// Li2 must now be empty
// remove each individual item from right side of Li3 and
// append to right side of Li2 (reversing list)
while (! Li3.isEmpty()) {
Li2.addLast(Li3.removeLast());
}
// Li3 must now be empty
// reverse Li1
LinkedList tmp = new LinkedList();
while (! Li1.isEmpty()) {
tmp.addFirst(Li1.removeFirst());
}
Li1 = tmp;
// check that first item is now SIZE
if (((Integer)Li1.getFirst()).intValue() != SIZE) {
System.err.println("first item of Li1 != SIZE");
return(0);
}
// compare Li1 and Li2 for equality
if (! Li1.equals(Li2)) {
System.err.println("Li1 and Li2 differ");
System.err.println("Li1:" + Li1);
System.err.println("Li2:" + Li2);
return(0);
}
// return the length of the list
return(Li1.size());
}
}
|
| lists.jscript |
// -*- mode: java -*-
// $Id: lists.njs,v 1.1 2001/07/08 20:20:06 doug Exp $
// http://www.bagley.org/~doug/shootout/
// from: David Hedbor
// modified by Aldo Calpini <dada@perl.it> for Win32
var SIZE = 10000;
function test_lists()
{
var Li1, Li2, Li3;
var tmp;
// create a list of integers from 1 to SIZE.
Li1 = new Array();
for(tmp = 1; tmp <= SIZE; tmp++) Li1.push(tmp);
// copy the list to Li2.
Li2 = Li1.concat();
// remove each element from left side of Li2 and append to
// the right side of Li3 (preserving order)
Li3 = new Array();
while( (tmp = Li2.shift()) ) {
Li3.push(tmp);
}
// Li2 is now empty.
// Remove each element from right side of Li3 and append to right
// side of Li2
while( (tmp = Li3.pop()) ) {
Li2.push(tmp);
}
// Li2 is now reversed, and Li3 empty.
// Reverse Li1 in place.
Li1.reverse();
if( Li1[0] != SIZE ) return 0;
// compare Li1 and Li2 for equality, and return the length of the list.
for(tmp = 0; tmp < SIZE; tmp++)
if( Li1[tmp] != Li2[tmp] ) return 0;
return Li1.length;
}
ARGS = WScript.Arguments;
if(ARGS.length > 0) {
n = parseInt(ARGS.Item(0), "10");
if(n < 1) n = 1;
} else {
n = 1;
}
var resultl
while( n-- )
result = test_lists();
WScript.Echo(result );
|
| lists.lcc |
/* -*- mode: c -*-
* $Id: lists.gcc,v 1.3 2001/04/29 04:39:50 doug Exp $
* http://www.bagley.org/~doug/shootout/
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define SIZE 10000
// a simple Double Linked List
// the head node is special, it's val is length of list
typedef struct DLL {
int val;
struct DLL *next;
struct DLL *prev;
} DLL;
inline int list_length(DLL *head) { return(head->val); }
inline int list_empty(DLL *head) { return(list_length(head) == 0); }
inline DLL *list_first(DLL *head) { return(head->next); }
inline DLL *list_last(DLL *head) { return(head->prev); }
void list_push_tail(DLL *head, DLL *item) {
DLL *tail = head->prev;
tail->next = item;
item->next = head;
head->prev = item;
item->prev = tail;
head->val++;
}
DLL *list_pop_tail(DLL *head) {
DLL *prev, *tail;
if (list_empty(head)) return(NULL);
tail = head->prev;
prev = tail->prev;
prev->next = head;
head->prev = prev;
head->val--;
return(tail);
}
void list_push_head(DLL *head, DLL *item) {
DLL *next = head->next;
head->next = item;
next->prev = item;
item->next = next;
item->prev = head;
head->val++;
}
DLL *list_pop_head(DLL *head) {
DLL *next;
if (list_empty(head)) return(NULL);
next = head->next;
head->next = next->next;
next->next->prev = head;
head->val--;
return(next);
}
int list_equal(DLL *x, DLL *y) {
DLL *xp, *yp;
// first val's checked will be list lengths
for (xp=x, yp=y; xp->next != x; xp=xp->next, yp=yp->next) {
if (xp->val != yp->val) return(0);
}
if (xp->val != yp->val) return(0);
return(yp->next == y);
}
void list_print(char *msg, DLL *x) {
DLL *xp, *first = x->next;
int i = 0;
printf(msg);
printf("length: %d\n", list_length(x));
for (xp=x->next; xp->next != first; xp=xp->next) {
printf("i:%3d v:%3d n:%3d p:%3d\n", ++i,
xp->val, xp->next->val, xp->prev->val);
}
printf("[last entry points to list head]\n");
printf("[val of next of tail is: %d]\n", xp->next->val);
}
DLL *list_new() {
DLL *l = (DLL *)malloc(sizeof(DLL));
l->next = l;
l->prev = l;
l->val = 0;
return(l);
}
DLL *list_sequence(int from, int to) {
int size, tmp, i, j;
DLL *l;
if (from > to) {
tmp = from; from = to; to = tmp;
}
size = to - from + 1;
l = (DLL *)malloc((size+1) * sizeof(DLL));
from--;
for (i=0, j=1; i<size; ++i, ++j) {
l[i].next = &l[i+1];
l[j].prev = &l[j-1];
l[i].val = from++;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].prev = &l[size-1];
l[size].val = from;
l[0].val = size;
return(l);
}
DLL *list_copy(DLL *x) {
int i, j, size = list_length(x);
DLL *xp, *l = (DLL *)malloc((size+1) * sizeof(DLL));
for (i=0, j=1, xp=x; i<size; i++, j++, xp=xp->next) {
l[i].next = &l[j];
l[j].prev = &l[i];
l[i].val = xp->val;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].val = list_last(x)->val;
return(l);
}
void list_reverse (DLL *head) {
DLL *tmp, *p = head;
do {
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = tmp;
} while (p != head);
}
int test_lists() {
int len = 0;
// create a list of integers (li1) from 1 to SIZE
DLL *li1 = list_sequence(1, SIZE);
// copy the list to li2
DLL *li2 = list_copy(li1);
// remove each individual item from left side of li2 and
// append to right side of li3 (preserving order)
DLL *li3 = list_new();
// compare li2 and li1 for equality
if (!list_equal(li2, li1)) {
fprintf(stderr, "li2 and li1 are not equal\n");
exit(1);
}
while (!list_empty(li2)) {
list_push_tail(li3, list_pop_head(li2));
}
// li2 must now be empty
if (!list_empty(li2)) {
fprintf(stderr, "li2 should be empty now\n");
exit(1);
}
// remove each individual item from right side of li3 and
// append to right side of li2 (reversing list)
while (!list_empty(li3)) {
list_push_tail(li2, list_pop_tail(li3));
}
// li3 must now be empty
if (!list_empty(li3)) {
fprintf(stderr, "li3 should be empty now\n");
exit(1);
}
// reverse li1 in place
list_reverse(li1);
// check that li1's first item is now SIZE
if (list_first(li1)->val != SIZE) {
fprintf(stderr, "li1 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li1)->val);
exit(1);
}
// check that li1's last item is now 1
if (list_last(li1)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li1)->val);
exit(1);
}
// check that li2's first item is now SIZE
if (list_first(li2)->val != SIZE) {
fprintf(stderr, "li2 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li2)->val);
exit(1);
}
// check that li2's last item is now 1
if (list_last(li2)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li2)->val);
exit(1);
}
// check that li1's length is still SIZE
if (list_length(li1) != SIZE) {
fprintf(stderr, "li1 size wrong, wanted %d, got %d\n",
SIZE, list_length(li1));
exit(1);
}
// compare li1 and li2 for equality
if (!list_equal(li1, li2)) {
fprintf(stderr, "li1 and li2 are not equal\n");
exit(1);
}
len = list_length(li1);
free(li1);
free(li2);
free(li3);
// return the length of the list
return(len);
}
int main(int argc, char *argv[]) {
int n = ((argc == 2) ? atoi(argv[1]) : 1);
int result = 0;
while(n--) result = test_lists();
printf("%d\n", result);
return 0;
}
|
| lists.lua |
-- $Id: lists.lua,v 1.6 2001/01/13 22:04:18 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy
--------------------------------------------------------------
-- List module
-- defines a prototipe for lists
--------------------------------------------------------------
List = {first = 0, last = -1}
function List:new ()
local n = {}
for k,v in self do n[k] = v end
return n
end
function List:length ()
return self.last - self.first + 1
end
function List:pushleft (value)
local first = self.first - 1
self.first = first
self[first] = value
end
function List:pushright (value)
local last = self.last + 1
self.last = last
self[last] = value
end
function List:popleft ()
local first = self.first
if first > self.last then error"list is empty" end
local value = self[first]
self[first] = nil -- to allow collection
self.first = first+1
return value
end
function List:popright ()
local last = self.last
if self.first > last then error"list is empty" end
local value = self[last]
self[last] = nil -- to allow collection
self.last = last-1
return value
end
function List:reverse ()
local i, j = self.first, self.last
while i<j do
self[i], self[j] = self[j], self[i]
i = i+1
j = j-1
end
end
function List:equal (otherlist)
if self:length() ~= otherlist:length() then return nil end
local diff = otherlist.first - self.first
for i1=self.first,self.last do
if self[i1] ~= otherlist[i1+diff] then return nil end
end
return 1
end
-----------------------------------------------------------
-----------------------------------------------------------
-- Some tests
function test ()
local SIZE = 10000
-- create a list with elements 1..SIZE
local l1 = List:new()
for i=1,SIZE do
l1:pushright(i)
end
-- creates a copy of l1
local l2 = l1:new()
-- remove each individual item from left side of l2 and
-- append to right side of l3 (preserving order)
local l3 = List:new()
while l2:length() > 0 do
l3:pushright(l2:popleft())
end
-- remove each individual item from right side of l3 and
-- append to right side of l2 (reversing list)
while l3:length() > 0 do
l2:pushright(l3:popright())
end
-- reverse l1 in place
l1:reverse()
-- compare Li1 and Li2 for equality
-- and return length of the list
if not l1:equal(l2) then return nil
else return l1:length()
end
end
N = tonumber((arg and arg[1])) or 1
for i=1, N do
result = test()
end
print(result)
|
| lists.lua5 |
-- $Id: lists.lua,v 1.6 2001/01/13 22:04:18 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy
--------------------------------------------------------------
-- List module
-- defines a prototipe for lists
--------------------------------------------------------------
List = {first = 0, last = -1}
function List:new ()
local n = {}
self.__index = self
setmetatable(n, self)
return n
end
function List:length ()
return self.last - self.first + 1
end
function List:pushleft (value)
local first = self.first - 1
self.first = first
self[first] = value
end
function List:pushright (value)
local last = self.last + 1
self.last = last
self[last] = value
end
function List:popleft ()
local first = self.first
if first > self.last then error"list is empty" end
local value = self[first]
self[first] = nil -- to allow collection
self.first = first+1
return value
end
function List:popright ()
local last = self.last
if self.first > last then error"list is empty" end
local value = self[last]
self[last] = nil -- to allow collection
self.last = last-1
return value
end
function List:reverse ()
local i, j = self.first, self.last
while i<j do
self[i], self[j] = self[j], self[i]
i = i+1
j = j-1
end
end
function List:equal (otherlist)
if self:length() ~= otherlist:length() then return nil end
local diff = otherlist.first - self.first
for i1=self.first,self.last do
if self[i1] ~= otherlist[i1+diff] then return nil end
end
return 1
end
-----------------------------------------------------------
-----------------------------------------------------------
-- Some tests
function test ()
local SIZE = 10000
-- create a list with elements 1..SIZE
local l1 = List:new()
for i=1,SIZE do
l1:pushright(i)
end
-- creates a copy of l1
local l2 = l1:new()
-- remove each individual item from left side of l2 and
-- append to right side of l3 (preserving order)
local l3 = List:new()
while l2:length() > 0 do
l3:pushright(l2:popleft())
end
-- remove each individual item from right side of l3 and
-- append to right side of l2 (reversing list)
while l3:length() > 0 do
l2:pushright(l3:popright())
end
-- reverse l1 in place
l1:reverse()
-- compare Li1 and Li2 for equality
-- and return length of the list
if not l1:equal(l2) then return nil
else return l1:length()
end
end
N = tonumber((arg and arg[1])) or 1
for i=1, N do
result = test()
end
print(result)
|
| lists.mercury |
% ---------------------------------------------------------------------------- %
% lists.m
% Ralph Becket <rbeck@microsoft.com>
% Tue Jan 9 13:50:50 GMT 2001
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix
%
% NOTE: this is not really a fair test since the Mercury list
% library does not implement doubly-linked lists as the C and
% (presumably) Python versions do.
% ---------------------------------------------------------------------------- %
:- module mytest.
:- interface.
:- import_module io.
:- pred main(io__state, io__state).
:- mode main(di, uo) is cc_multi.
:- implementation.
:- import_module string, list, int, require, benchmarking.
main -->
io__command_line_arguments(ArgV),
( { ArgV = [], Repeats = 1 }
; { ArgV = [Arg], Repeats = string__det_to_int(Arg) }
; { ArgV = [_,_|_], error("usage: nestedloops [Repeats]") }
),
{ benchmarking__benchmark_det(test_list_ops, 0, N, Repeats, Time) },
io__format("%d\n", [i(N)]).
:- func size = int.
size = 10000.
:- pred test_list_ops(int, int).
:- mode test_list_ops(in, out) is det.
test_list_ops(_, N) :-
L1 = 1 `..` size, % Build [1, 2, ..., size].
copy(L1, L2), % Make a copy.
% Do a naive reverse.
L3 = list__foldl(func(X, L) = L ++ [X], L2, []),
% Now do a weird copy.
L4 = list__foldr(func(X, L) = L ++ [X], L3, []),
L5 = list__reverse(L1), % Standard reverse.
(
if list__det_head(L5) \= size then N = 0
else if L1 \= L2 then N = 0
else N = list__length(L4)
).
|
| lists.mingw32 |
/* -*- mode: c -*-
* $Id: lists.gcc,v 1.3 2001/04/29 04:39:50 doug Exp $
* http://www.bagley.org/~doug/shootout/
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define SIZE 10000
// a simple Double Linked List
// the head node is special, it's val is length of list
typedef struct DLL {
int val;
struct DLL *next;
struct DLL *prev;
} DLL;
inline int list_length(DLL *head) { return(head->val); }
inline int list_empty(DLL *head) { return(list_length(head) == 0); }
inline DLL *list_first(DLL *head) { return(head->next); }
inline DLL *list_last(DLL *head) { return(head->prev); }
void list_push_tail(DLL *head, DLL *item) {
DLL *tail = head->prev;
tail->next = item;
item->next = head;
head->prev = item;
item->prev = tail;
head->val++;
}
DLL *list_pop_tail(DLL *head) {
DLL *prev, *tail;
if (list_empty(head)) return(NULL);
tail = head->prev;
prev = tail->prev;
prev->next = head;
head->prev = prev;
head->val--;
return(tail);
}
void list_push_head(DLL *head, DLL *item) {
DLL *next = head->next;
head->next = item;
next->prev = item;
item->next = next;
item->prev = head;
head->val++;
}
DLL *list_pop_head(DLL *head) {
DLL *next;
if (list_empty(head)) return(NULL);
next = head->next;
head->next = next->next;
next->next->prev = head;
head->val--;
return(next);
}
int list_equal(DLL *x, DLL *y) {
DLL *xp, *yp;
// first val's checked will be list lengths
for (xp=x, yp=y; xp->next != x; xp=xp->next, yp=yp->next) {
if (xp->val != yp->val) return(0);
}
if (xp->val != yp->val) return(0);
return(yp->next == y);
}
void list_print(char *msg, DLL *x) {
DLL *xp, *first = x->next;
int i = 0;
printf(msg);
printf("length: %d\n", list_length(x));
for (xp=x->next; xp->next != first; xp=xp->next) {
printf("i:%3d v:%3d n:%3d p:%3d\n", ++i,
xp->val, xp->next->val, xp->prev->val);
}
printf("[last entry points to list head]\n");
printf("[val of next of tail is: %d]\n", xp->next->val);
}
DLL *list_new() {
DLL *l = (DLL *)malloc(sizeof(DLL));
l->next = l;
l->prev = l;
l->val = 0;
return(l);
}
DLL *list_sequence(int from, int to) {
int size, tmp, i, j;
DLL *l;
if (from > to) {
tmp = from; from = to; to = tmp;
}
size = to - from + 1;
l = (DLL *)malloc((size+1) * sizeof(DLL));
from--;
for (i=0, j=1; i<size; ++i, ++j) {
l[i].next = &l[i+1];
l[j].prev = &l[j-1];
l[i].val = from++;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].prev = &l[size-1];
l[size].val = from;
l[0].val = size;
return(l);
}
DLL *list_copy(DLL *x) {
int i, j, size = list_length(x);
DLL *xp, *l = (DLL *)malloc((size+1) * sizeof(DLL));
for (i=0, j=1, xp=x; i<size; i++, j++, xp=xp->next) {
l[i].next = &l[j];
l[j].prev = &l[i];
l[i].val = xp->val;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].val = list_last(x)->val;
return(l);
}
void list_reverse (DLL *head) {
DLL *tmp, *p = head;
do {
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = tmp;
} while (p != head);
}
int test_lists() {
int len = 0;
// create a list of integers (li1) from 1 to SIZE
DLL *li1 = list_sequence(1, SIZE);
// copy the list to li2
DLL *li2 = list_copy(li1);
// remove each individual item from left side of li2 and
// append to right side of li3 (preserving order)
DLL *li3 = list_new();
// compare li2 and li1 for equality
if (!list_equal(li2, li1)) {
fprintf(stderr, "li2 and li1 are not equal\n");
exit(1);
}
while (!list_empty(li2)) {
list_push_tail(li3, list_pop_head(li2));
}
// li2 must now be empty
if (!list_empty(li2)) {
fprintf(stderr, "li2 should be empty now\n");
exit(1);
}
// remove each individual item from right side of li3 and
// append to right side of li2 (reversing list)
while (!list_empty(li3)) {
list_push_tail(li2, list_pop_tail(li3));
}
// li3 must now be empty
if (!list_empty(li3)) {
fprintf(stderr, "li3 should be empty now\n");
exit(1);
}
// reverse li1 in place
list_reverse(li1);
// check that li1's first item is now SIZE
if (list_first(li1)->val != SIZE) {
fprintf(stderr, "li1 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li1)->val);
exit(1);
}
// check that li1's last item is now 1
if (list_last(li1)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li1)->val);
exit(1);
}
// check that li2's first item is now SIZE
if (list_first(li2)->val != SIZE) {
fprintf(stderr, "li2 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li2)->val);
exit(1);
}
// check that li2's last item is now 1
if (list_last(li2)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li2)->val);
exit(1);
}
// check that li1's length is still SIZE
if (list_length(li1) != SIZE) {
fprintf(stderr, "li1 size wrong, wanted %d, got %d\n",
SIZE, list_length(li1));
exit(1);
}
// compare li1 and li2 for equality
if (!list_equal(li1, li2)) {
fprintf(stderr, "li1 and li2 are not equal\n");
exit(1);
}
len = list_length(li1);
free(li1);
free(li2);
free(li3);
// return the length of the list
return(len);
}
int main(int argc, char *argv[]) {
int n = ((argc == 2) ? atoi(argv[1]) : 1);
int result = 0;
while(n--) result = test_lists();
printf("%d\n", result);
return 0;
}
|
| lists.modula2 |
(* The Great Win32 Language Shootout http://dada.perl.it/shootout/
contributed by Isaac Gouy (Modula2 novice)
To compile: xc =m lists
To run: lists 16
*)
MODULE Lists;
<* m2extensions + *>
<* storage + *>
(* Prefer unqualified procedures *)
FROM LanguageShootout IMPORT N;
FROM STextIO IMPORT WriteString, WriteLn;
FROM SWholeIO IMPORT WriteCard;
(* We need an ADT let's implement a double-linked list *)
TYPE
Node_Ptr = POINTER TO Queue_Node;
Queue_Node =
RECORD
prev, next: Node_Ptr;
item: CARDINAL;
END;
Queue_Ptr = POINTER TO Queue_Type;
Queue_Type =
RECORD
first, last: Node_Ptr;
length: CARDINAL;
END;
Queue_Positions = (First, Last);
VAR node, node2: Node_Ptr;
PROCEDURE Initialize(VAR q: Queue_Ptr);
BEGIN
NEW(q);
q^.length := 0;
q^.first := NIL;
q^.last := NIL;
END Initialize;
PROCEDURE Add(position: Queue_Positions; VAR q: Queue_Ptr; item: CARDINAL);
BEGIN
NEW(node);
node^.item := item;
INC(q^.length);
IF q^.length = 1 THEN
node^.prev := NIL;
node^.next := NIL;
q^.first := node;
q^.last := node;
ELSE
IF position = First THEN
node^.prev := NIL;
node^.next := q^.first;
q^.first^.prev := node;
q^.first := node;
ELSE
node^.prev := q^.last;
node^.next := NIL;
q^.last^.next := node;
q^.last := node;
END;
END;
END Add;
PROCEDURE Remove(position: Queue_Positions; VAR q: Queue_Ptr): CARDINAL;
VAR item: CARDINAL;
BEGIN
IF q^.length = 0 THEN
RETURN 0;
END;
IF position = First THEN
node := q^.first;
ELSE
node := q^.last;
END;
item := node^.item;
DEC(q^.length);
IF q^.length = 0 THEN
q^.first := NIL;
q^.last := NIL;
ELSE
IF position = First THEN
q^.first := node^.next;
q^.first^.prev := NIL;
ELSE
q^.last := node^.prev;
q^.last^.next := NIL;
END;
END;
DISPOSE(node);
RETURN item;
END Remove;
PROCEDURE Dispose(VAR q: Queue_Ptr);
BEGIN
WHILE q^.first # NIL DO
node := q^.first^.next;
DISPOSE(q^.first);
q^.first := node;
END;
DISPOSE(q);
END Dispose;
PROCEDURE Copy(q: Queue_Ptr; VAR qcopy: Queue_Ptr);
BEGIN
node2 := q^.first ;
WHILE node2 # NIL DO
Add(Last, qcopy, node2^.item);
node2 := node2^.next;
END;
END Copy;
PROCEDURE Reverse(VAR q: Queue_Ptr);
BEGIN
node := q^.first;
q^.first := q^.last;
q^.last := node;
WHILE node # NIL DO
node2 := node^.next;
node^.next := node^.prev;
node^.prev := node2;
node := node2;
END;
END Reverse;
PROCEDURE Length(q: Queue_Ptr): CARDINAL;
BEGIN
RETURN q^.length;
END Length;
PROCEDURE FirstItem(q: Queue_Ptr): CARDINAL;
BEGIN
IF q^.length = 0 THEN
RETURN 0;
ELSE
RETURN q^.first^.item;
END;
END FirstItem;
PROCEDURE Equal(q,q2: Queue_Ptr): BOOLEAN;
BEGIN
IF q^.length # q2^.length THEN
RETURN FALSE;
END;
node := q^.first;
node2 := q2^.first;
WHILE node # NIL DO
IF node^.item # node2^.item THEN
RETURN FALSE;
END;
node := node^.next;
node2 := node2^.next;
END;
RETURN TRUE;
END Equal;
CONST SIZE = 10000;
VAR L1, L2, L3: Queue_Ptr;
i, m, n, lengthL1: CARDINAL;
BEGIN
n := N();
FOR m := 1 TO n DO
NEW(L1);
Initialize(L1);
FOR i := 1 TO SIZE DO
Add(Last, L1, i);
END;
NEW(L2);
Initialize(L2);
Copy(L1, L2);
NEW(L3);
Initialize(L3);
WHILE Length(L2) > 0 DO
Add(Last, L3, ( Remove(First, L2)) );
END;
WHILE Length(L3) > 0 DO
Add(Last, L2, ( Remove(Last, L3) ));
END;
Reverse(L1);
IF FirstItem(L1) # SIZE THEN
WriteString("First item of L1 # SIZE"); WriteLn;
END;
IF NOT Equal(L1, L2) THEN
WriteString("L1 # L2"); WriteLn;
END;
lengthL1 := Length(L1);
Dispose(L1);
Dispose(L2);
Dispose(L3);
END;
WriteCard(lengthL1,1); WriteLn;
END Lists.
|
| lists.nice |
/* The Great Win32 Language Shootout http://dada.perl.it/shootout/
contributed by Isaac Gouy (Nice novice)
To compile:
nicec --sourcepath=.. -d=. -a lists.jar lists
To run:
java -jar lists.jar 16
*/
import ackermann; // reuse toSingleInt
void main(String[] args){
var n = toSingleInt(args);
let nSize = 10000;
int L1Count = 0;
while (n-- > 0){
// initialize L1
ArrayList
|
| lists.ocaml |
(*
* $Id: lists.ocaml,v 1.9 2001/01/31 02:12:48 doug Exp $
* http://www.bagley.org/~doug/shootout/
* from Benedict Rosenau
*)
module Deque:
sig
type 'a t
exception Empty
val make: int -> 'a -> 'a t
val iota: int -> int t
val is_empty: 'a t -> bool
val equal: 'a t -> 'a t -> bool
val length: 'a t -> int
val nth: 'a t -> int -> 'a
val push_front: 'a -> 'a t -> unit
val push_back: 'a t -> 'a -> unit
val take_front: 'a t -> 'a
val take_back: 'a t -> 'a
val copy: 'a t -> 'a t
val reverse: 'a t -> 'a t
end =
struct
type 'a t = {mutable size: int;
mutable first: int;
mutable last: int;
mutable field: 'a array;
fill: 'a}
exception Empty
let make n dummy =
let n = max n 0 in
let nplus = max 1 n in
{size = nplus;
first = nplus lsr 1;
last = (nplus lsr 1) - 1;
field = Array.make nplus dummy;
fill = dummy}
let iota i =
let i = max 0 i in
let iplus = max 1 i in
{size = iplus;
first = 0;
last = i - 1;
field = Array.init iplus (fun n -> n + 1);
fill = i}
let length buf = buf.last - buf.first + 1
let is_empty buf = buf.last < buf.first
let rec array_eq arr1 off1 arr2 off2 = function
| 0 -> true
| n ->
if arr1.(off1) <> arr2.(off2) then false
else array_eq arr1 (off1 + 1) arr2 (off2 + 1) (n - 1)
let equal buf1 buf2 =
let len = length buf1 in
if len <> length buf2 then false
else array_eq buf1.field buf1.first buf2.field buf2.first len
let nth buf n =
if n < 0 or n >= length buf then failwith "nth";
buf.field.(buf.first + n)
let double_shift buf =
let new_size = buf.size lsl 1
and len = length buf in
let new_first = (new_size - len) lsr 1
and new_field = Array.make new_size buf.fill in
Array.blit buf.field buf.first new_field new_first len;
buf.size <- new_size;
buf.field <- new_field;
buf.first <- new_first;
buf.last <- new_first + len - 1
let push_front elem buf =
if buf.first = 0 then double_shift buf;
let new_first = buf.first - 1 in
buf.field.(new_first) <- elem;
buf.first <- new_first
let push_back buf elem =
if buf.last = buf.size - 1 then double_shift buf;
let new_last = buf.last + 1 in
buf.field.(new_last) <- elem;
buf.last <- new_last
let take_front buf =
if is_empty buf then raise Empty;
let old_first = buf.first in
buf.first <- old_first + 1;
buf.field.(old_first)
let take_back buf =
if is_empty buf then raise Empty;
let old_last = buf.last in
buf.last <- old_last - 1;
buf.field.(old_last)
let copy buf =
let len = length buf in
let new_buf = make len buf.fill in
Array.blit buf.field buf.first new_buf.field 0 len;
new_buf.first <- 0;
new_buf.last <- len - 1;
new_buf
let reverse buf =
let len = length buf
and fst = buf.first
and fld = buf.field in
let new_buf = make len buf.fill in
let new_fld = new_buf.field in
for i = 0 to len - 1 do
new_fld.(len - i - 1) <- fld.(fst + i)
done;
new_buf.first <- 0;
new_buf.last <- len - 1;
new_buf
end
open Deque
let empty () = iota 0
let size = 10000
let test_lists () =
let d1 = iota size in
let d2 = copy d1
and d3 = empty () in
for i = 1 to length d2 do
push_back d3 (take_front d2)
done;
for i = 1 to length d3 do
push_back d2 (take_back d3)
done;
let d1 = reverse d1 in
if size <> nth d1 0 then failwith "First test failed";
if length d1 <> length d2 then failwith "Second test failed";
if not (equal d1 d2) then failwith "Third test failed";
length d1
let _ =
let n =
try int_of_string Sys.argv.(1)
with Invalid_argument _ -> 1
and result = ref 0 in
for i = 1 to n do
result := test_lists ()
done;
Printf.printf "%d\n" !result
|
| lists.ocamlb |
(*
* $Id: lists.ocaml,v 1.9 2001/01/31 02:12:48 doug Exp $
* http://www.bagley.org/~doug/shootout/
* from Benedict Rosenau
*)
module Deque:
sig
type 'a t
exception Empty
val make: int -> 'a -> 'a t
val iota: int -> int t
val is_empty: 'a t -> bool
val equal: 'a t -> 'a t -> bool
val length: 'a t -> int
val nth: 'a t -> int -> 'a
val push_front: 'a -> 'a t -> unit
val push_back: 'a t -> 'a -> unit
val take_front: 'a t -> 'a
val take_back: 'a t -> 'a
val copy: 'a t -> 'a t
val reverse: 'a t -> 'a t
end =
struct
type 'a t = {mutable size: int;
mutable first: int;
mutable last: int;
mutable field: 'a array;
fill: 'a}
exception Empty
let make n dummy =
let n = max n 0 in
let nplus = max 1 n in
{size = nplus;
first = nplus lsr 1;
last = (nplus lsr 1) - 1;
field = Array.make nplus dummy;
fill = dummy}
let iota i =
let i = max 0 i in
let iplus = max 1 i in
{size = iplus;
first = 0;
last = i - 1;
field = Array.init iplus (fun n -> n + 1);
fill = i}
let length buf = buf.last - buf.first + 1
let is_empty buf = buf.last < buf.first
let rec array_eq arr1 off1 arr2 off2 = function
| 0 -> true
| n ->
if arr1.(off1) <> arr2.(off2) then false
else array_eq arr1 (off1 + 1) arr2 (off2 + 1) (n - 1)
let equal buf1 buf2 =
let len = length buf1 in
if len <> length buf2 then false
else array_eq buf1.field buf1.first buf2.field buf2.first len
let nth buf n =
if n < 0 or n >= length buf then failwith "nth";
buf.field.(buf.first + n)
let double_shift buf =
let new_size = buf.size lsl 1
and len = length buf in
let new_first = (new_size - len) lsr 1
and new_field = Array.make new_size buf.fill in
Array.blit buf.field buf.first new_field new_first len;
buf.size <- new_size;
buf.field <- new_field;
buf.first <- new_first;
buf.last <- new_first + len - 1
let push_front elem buf =
if buf.first = 0 then double_shift buf;
let new_first = buf.first - 1 in
buf.field.(new_first) <- elem;
buf.first <- new_first
let push_back buf elem =
if buf.last = buf.size - 1 then double_shift buf;
let new_last = buf.last + 1 in
buf.field.(new_last) <- elem;
buf.last <- new_last
let take_front buf =
if is_empty buf then raise Empty;
let old_first = buf.first in
buf.first <- old_first + 1;
buf.field.(old_first)
let take_back buf =
if is_empty buf then raise Empty;
let old_last = buf.last in
buf.last <- old_last - 1;
buf.field.(old_last)
let copy buf =
let len = length buf in
let new_buf = make len buf.fill in
Array.blit buf.field buf.first new_buf.field 0 len;
new_buf.first <- 0;
new_buf.last <- len - 1;
new_buf
let reverse buf =
let len = length buf
and fst = buf.first
and fld = buf.field in
let new_buf = make len buf.fill in
let new_fld = new_buf.field in
for i = 0 to len - 1 do
new_fld.(len - i - 1) <- fld.(fst + i)
done;
new_buf.first <- 0;
new_buf.last <- len - 1;
new_buf
end
open Deque
let empty () = iota 0
let size = 10000
let test_lists () =
let d1 = iota size in
let d2 = copy d1
and d3 = empty () in
for i = 1 to length d2 do
push_back d3 (take_front d2)
done;
for i = 1 to length d3 do
push_back d2 (take_back d3)
done;
let d1 = reverse d1 in
if size <> nth d1 0 then failwith "First test failed";
if length d1 <> length d2 then failwith "Second test failed";
if not (equal d1 d2) then failwith "Third test failed";
length d1
let _ =
let n =
try int_of_string Sys.argv.(1)
with Invalid_argument _ -> 1
and result = ref 0 in
for i = 1 to n do
result := test_lists ()
done;
Printf.printf "%d\n" !result
|
| lists.oz |
functor
import
System
Application
define
local Args N Size L1 L2 L3 Temp Result in
{Application.getCmdArgs plain Args}
if {List.length Args} \= 1 then
N = 1
else
{String.toInt Args.1 N}
end
Size = 10000
L1 = {NewCell nil}
L2 = {NewCell nil}
L3 = {NewCell nil}
Temp = {NewCell nil}
Result = {NewCell 0}
proc {MyMain Q}
%%
%first create a list (L1) of integers from 1 through SIZE (SIZE is currently defined as 10000).
{Assign L1 {List.number 1 Size 1}}
%copy L1 to L2 (can use any builtin list copy function, if available)
{Assign L2 {Access L1}}
%remove each individual item from left side (head) of L2 and append to right side (tail)
% of L3 (preserving order). (L2 should be emptied by one item at a time as that item is
% appended to L3).
{For 1 (Size - 1) 1
proc {$ N}
{Assign Temp {List.nth {Access L2} 1}}
{Assign L2 {List.drop {Access L2} 1}}
{Assign L3 {List.append {Access L3} {Access Temp}|nil}}
end}
%remove each individual item from right side (tail) of L3 and append to right side (tail)
% of L2 (reversing list). (L3 should be emptied by one item at a time as that item is
% appended to L2).
{For 1 (Size - 1) 1
proc {$ N}
{Assign Temp {List.last {Access L3}}}
{Assign L3 {List.take {Access L3} {List.length {Access L3}} - 1}}
{Assign L2 {List.append {Access L2} {Access Temp}|nil}}
end}
%reverse L1 (preferably in place) (can use any builtin function for this, if available).
{Assign L1 {List.reverse {Access L1} $}}
%check that first item of L1 is now == SIZE.
if {Value.'\\=' {List.nth {Access L1} 1} Size} then
% {System.showInfo "Equal!"}
% else
{Assign Result 0}
end
%and compare L1 and L2 for equality and return length of L1 (which should be equal to SIZE). `
if {Value.'==' {Access L1} {Access L2}} then
{Assign Result {List.length {Access L1}}}
else
{Assign Result 0}
end
%%
end
{For 1 N 1 MyMain}
{System.showInfo {Access Result}}
{Application.exit 0}
end
end
|
| lists.perl |
#!/usr/local/bin/perl
# $Id: lists.perl,v 1.3 2001/05/06 15:50:16 doug Exp $
use strict;
my $SIZE = 10000;
my $ITER = $ARGV[0];
$ITER = 1 if ($ITER < 1);
my $result = 0;
while ($ITER--) {
$result = &test_lists();
}
print "$result\n";
sub test_lists {
# create a list of integers (Li1) from 1 to SIZE
my @Li1 = (1..$SIZE);
# copy the list to Li2 (not by individual items)
my @Li2 = @Li1;
my @Li3 = ();
# remove each individual item from left side of Li2 and
# append to right side of Li3 (preserving order)
push(@Li3, shift @Li2) while (@Li2);
# Li2 must now be empty
# remove each individual item from right side of Li3 and
# append to right side of Li2 (reversing list)
push(@Li2, pop @Li3) while (@Li3);
# Li3 must now be empty
# reverse Li1 in place
@Li1 = reverse @Li1;
# check that first item is now SIZE
return(0) if $Li1[0] != $SIZE;
# compare Li1 and Li2 for equality
my $len1 = scalar(@Li1);
my $len2 = scalar(@Li2);
my $lists_equal = ($len1 == $len2);
return(0) if not $lists_equal;
for my $i (0..($len1-1)) {
if ($Li1[$i] != $Li2[$i]) {
$lists_equal = 0;
last;
}
}
return(0) if not $lists_equal;
# return the length of the list
return($len1);
}
|
| lists.pike |
#!/usr/local/bin/pike// -*- mode: pike -*-
// $Id: lists.pike,v 1.2 2000/12/05 16:04:06 doug Exp $
// http://www.bagley.org/~doug/shootout/
// from: Per Hedbor
#define SIZE 10000
#define TB(X) werror( "%s: %.2f\n", X, gauge {
#define TE() })
int test_lists()
{
mixed Li1, Li2, Li3;
// create a list of integers from 1 to SIZE.
Li1 = (string)indices(allocate(SIZE+1))[1..];
// copy the list to Li2.
Li2 = copy_value( Li1 );
// remove each element from left side of Li2 and append to
// the right side of Li3 (preserving order)
Li3 = "";
while( sizeof( Li2 ) )
{
Li3 += Li2[..0];
Li2 = Li2[1..];
}
// Li2 is now empty.
// Remove each element from right side of Li3 and append to right
// side of Li2
while( sizeof( Li3 ) )
{
Li2 += Li3[sizeof( Li3 )-1..];
Li3 = Li3[..sizeof( Li3 )-2];
}
// Li2 is now reversed, and Li3 empty.
// Reverse Li1 in place.
Li1 = reverse( Li1 );
if( Li1[0] != SIZE )
return 0;
// compare Li1 and Li2 for equality, and return the length of the list.
if( equal( Li1, Li2 ) )
return sizeof( Li1 );
return 0;
}
void main(int argc, array argv)
{
int result, num = (int)argv[-1];
if( num <= 0 )
num = 1;
while( num-- )
result = test_lists();
write("%d\n", result );
}
|
| lists.pliant |
# $Id: lists.pliant,v 1.0 2002/02/08 10:09:00 dada Exp $
# http://dada.perl.it/shootout/
module "/pliant/language/context.pli"
gvar Int SIZE := 10000
function reverse l -> r
arg List:Int l
arg List:Int r
var Pointer:Int v
v :> l last
for (var Int i) l:size-1 0 step -1
r += v
v :> l previous v
return r
function test_lists -> r
arg Int r
var List:Int Li1
var List:Int Li2
var List:Int Li3
var Pointer:Int v
var Int len1
var Int len2
var Bool lists_equal := true
var Pointer:Int v1
var Pointer:Int v2
# create a list of integers (Li1) from 1 to SIZE
for (var Int i) 1 SIZE
Li1 += i
# copy the list to Li2 (not by individual items)
Li2 := Li1
# remove each individual item from left side of Li2 and
# append to right side of Li3 (preserving order)
while Li2:size > 0
v :> Li2 first
Li3 += v
Li2 -= v
# Li2 must now be empty
# remove each individual item from right side of Li3 and
# append to right side of Li2 (reversing list)
while Li3:size > 0
v :> Li3 last
Li2 += v
Li3 -= v
# Li3 must now be empty
# reverse Li1 in place
Li1 := reverse Li1
# check that first item is now SIZE
v :> Li1 first
if v <> SIZE
return 0
# compare Li1 and Li2 for equality
len1 := Li1:size
len2 := Li2:size
lists_equal := (len1=len2)
v1 :> Li1 first
v2 :> Li2 first
for (var Int i) 0 len1-1
if v1 <> v2
lists_equal := false
i := len1-1
v1 :> Li1 next v1
v2 :> Li2 next v2
if lists_equal = false
return 0
return len1
gvar Int r
gvar Str s_n := cast ((pliant_script_args translate Address 1) map CStr) Str
if (s_n parse (gvar Int n))
while n > 0
r := test_lists
n := n - 1
console r eol
else
console "usage: lists.pliant <number>" eol
|
| lists.poplisp |
;;; -*- mode: lisp -*-
;;; $Id: lists.poplisp,v 1.0 2002/05/03 12:23:00 dada Exp $
(defparameter *SIZE* 10000)
(declaim (fixnum *SIZE*) (inline xcons push-queue))
(defvar *free-conses*)
(defun xcons (A B)
(let ((x *free-conses*))
(if x (progn (setf *free-conses* (cdr x) (car x) A (cdr x) B) x) (cons A B))))
(defmacro xpop (X)
`(prog1 (car ,x) (psetf ,x (cdr ,x) (cdr ,x) *free-conses* *free-conses* ,x)))
(defun push-queue (item queue &aux (new (xcons item nil)))
(if (cdr queue) (setf (cddr queue) new) (setf (car queue) new))
(setf (cdr queue) new)
(car queue))
(defmacro with-collector ((name) &body body)
(let ((collector (gensym)))
`(let ((,collector (xcons nil nil)))
(flet ((,name (value) (push-queue value ,collector)))
,@body
(car ,collector)))))
(defun test-list ()
(let* ((L1 (with-collector (conc) (loop for x fixnum from 1 to *SIZE* do (conc x))))
(L2 (with-collector (conc) (loop for x in L1 do (conc x))))
(L3 nil))
;; Move items from left of L2 to right of L3 (preserve order)
(setf L3 (with-collector (conc) (loop while L2 do (conc (xpop L2)))))
;; Move from tail of L3 to tail of L2 (reversing list)
;; start by reversing L3 so we can pop from the front
(setf L3 (nreverse L3))
(setf L2 (with-collector (conc) (loop while L3 do (conc (xpop L3)))))
;; Reverse L1 in place
(setf L1 (nreverse L1))
;; Check that (first L1) == *SIZE*
(assert (= (the fixnum (first L1)) *SIZE*))
;; Compare L1 and L2 for equality
(assert (equal L1 L2))
;; Return the length -- and return the conses to the free list
(prog1 (length (the list L1))
(setf *free-conses* (nconc *free-conses* L3 L2 L1)))))
(let ((n (parse-integer (or (car pop11::poparglist) "1")))
(num 0) (*free-conses* nil))
(loop repeat n fixnum do (setf num (test-list)))
(format t "~D~%" num))
|
| lists.python |
#!/usr/local/bin/python
# $Id: lists.python,v 1.7 2001/05/09 01:09:04 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with improvements from Mark Baker
import sys
SIZE = 10000
def test_lists():
Li1 = range(1, SIZE + 1)
Li2 = Li1[:]
Li3 = []
# remove each individual item from left side of Li2 and
# append to right side of Li3 (preserving order)
#
# popping the first element is *expensive*
#
#while Li2:
# Li3.append(Li2.pop(0))
Li2.reverse()
while Li2:
Li3.append(Li2.pop())
while Li3:
Li2.append(Li3.pop())
Li1.reverse()
if Li1[0] != SIZE:
return 0
if Li1 == Li2:
return len(Li1)
else:
return 0
def main():
NUM = int(sys.argv[1])
if NUM < 1:
NUM = 1
while NUM > 0:
result = test_lists()
NUM = NUM - 1
print result
main()
|
| lists.rebol |
REBOL [
Title: "Lists"
Author: "Aldo Calpini"
Date: 03-Jul-2001
File: %lists.r
]
SIZE: 10000
ITER: to-integer to-string system/script/args
ITER: either ITER < 1 [ 1 ] [ ITER ]
test_lists: func [ /local A Li1 Li2 Li3 ] [
comment [
create a list of integers (Li1) from 1 to SIZE
]
Li1: copy []
for A 1 SIZE 1 [
insert tail Li1 A
]
comment[
copy the list to Li2 (not by individual items)
]
Li2: copy Li1
comment [
remove each individual item from left side of Li2 and
append to right side of Li3 (preserving order)
]
Li3: copy []
Li2: head Li2
while[not tail? Li2] [
insert tail Li3 Li2/1
remove Li2
]
comment [
Li2 must now be empty
remove each individual item from right side of Li3 and
append to right side of Li2 (reversing list)
]
Li3: head Li3
while[not tail? Li3] [
last Li3
insert Li2 Li3/1
remove Li3
]
comment [
Li3 must now be empty
reverse Li1 in place
]
reverse Li1
comment [
check that first item is now SIZE
]
if Li1/1 <> SIZE [
return -1
]
Li1: head Li1
Li2: head Li2
while [not tail? Li1] [
if Li1/1 <> Li2/1 [
return 0
]
Li1: next Li1
Li2: next Li2
]
Li1: head Li1
return length? Li1
]
result: 0
while [ ITER > 0 ] [
result: test_lists
ITER: ITER - 1
]
write %output.rebol rejoin [ result ]
|
| lists.rexx |
SIZE = 10000
parse arg ITER
If ITER < 1 Then Do
ITER = 1
End
result = 0
Do While ITER > 0
result = test_lists()
ITER = ITER - 1
End
Say result
exit
test_lists
test_lists:
Do A = 0 To SIZE
Li1.A = A
End
/* [dada] this should work, but does not:
* Li2. = Li1.
*/
Do A = 0 To SIZE
Li2.A = Li1.A
End
Do A = 0 To SIZE
B = SIZE - A
Li3.A = Li2.B
End
Do A = 0 To SIZE
Li2.A = Li3.A
End
Do A = 0 To SIZE
B = SIZE-A
Li4.A = Li1.B
End
Do A = 0 To SIZE
Li1.A = Li4.A
End
If Li1.0 <> SIZE Then Do
return -1
End
Do i = 0 To SIZE
If Li1.i <> Li2.i Then Do
return 0
End
End
return SIZE
|
| lists.ruby |
#!/usr/local/bin/ruby
# -*- mode: ruby -*-
# $Id: lists.ruby,v 1.5 2000/11/27 03:39:25 doug Exp $
# http://www.bagley.org/~doug/shootout/
NUM = Integer(ARGV.shift || 1)
SIZE = 10000
def test_lists()
# create a list of integers (Li1) from 1 to SIZE
li1 = (1..SIZE).to_a
# copy the list to li2 (not by individual items)
li2 = li1.dup
# remove each individual item from left side of li2 and
# append to right side of li3 (preserving order)
li3 = Array.new
while (not li2.empty?)
li3.push(li2.shift)
end
# li2 must now be empty
# remove each individual item from right side of li3 and
# append to right side of li2 (reversing list)
while (not li3.empty?)
li2.push(li3.pop)
end
# li3 must now be empty
# reverse li1 in place
li1.reverse!
# check that first item is now SIZE
if li1[0] != SIZE then
p "not SIZE"
return(0)
end
# compare li1 and li2 for equality
if li1 != li2 then
return(0)
end
# return the length of the list
return(li1.length)
end
for iter in 1 .. NUM
result = test_lists()
end
print result, "\n"
|
| lists.slang |
% $Id: lists.slang,v 1.0 2003/01/03 14:38:00 dada Exp $
% http://dada.perl.it/shootout/
%
% contributed by John E. Davis
define new_list (n)
{
variable l = struct
{
root, tail, data, len
};
l.data = [1:n];
l.root = 0;
l.tail = n;
l.len = n;
return l;
}
define expand_list (l, len)
{
len += 4096;
variable data = Int_Type[len];
variable root = l.root;
variable tail = l.tail;
variable n = (tail - root);
if (n)
data[[0:n-1]] = l.data[[root:tail-1]];
l.data = data;
l.root = 0;
l.tail = n;
l.len = len;
}
define list_append (l, value)
{
variable tail = l.tail;
if (l.tail == l.len)
{
expand_list (l, l.len + 1);
tail = l.tail;
}
l.data[tail] = value;
tail++;
l.tail = tail;
}
define list_pop_right (l)
{
variable tail = l.tail;
if (tail == l.root)
return NULL;
tail--;
l.tail = tail;
return l.data[tail];
}
define list_pop_left (l)
{
variable root = l.root;
if (l.tail == root)
return NULL;
l.root = root+1;
return l.data[root];
}
define list_length (l)
{
return l.tail - l.root;
}
define reverse_list (l)
{
variable tail = l.tail;
variable root = l.root;
if (tail == root)
return;
tail--;
l.data[[root:tail]] = l.data[[tail:root:-1]];
}
define dup_list (l)
{
variable new_l = @l;
new_l.data = @l.data;
return new_l;
}
define list_to_array (a)
{
variable tail, root;
tail = a.tail;
root = a.root;
if (root == tail)
return NULL;
tail--;
return a.data[[root:tail]];
}
define check_eqs (a, b)
{
if (list_length (a) != list_length (b))
return 0;
variable data_a = list_to_array (a);
variable data_b = list_to_array (b);
if (data_a == NULL)
return 1; % same length, but empty
return not length (where (data_a != data_b));
}
variable SIZE = 10000;
define test_lists ()
{
variable L1 = new_list (SIZE);
variable L2 = dup_list (L1);
variable L3 = new_list (0);
forever
{
variable node = list_pop_left (L2);
if (node == NULL)
break;
list_append (L3, node);
}
forever
{
node = list_pop_right (L3);
if (node == NULL)
break;
list_append (L2, node);
}
reverse_list (L1);
if (L1.data[L1.root] != SIZE)
return -1;
if (0 == check_eqs (L1, L2))
return -2;
return list_length (L1);
}
define main ()
{
variable num = integer (__argv[1]);
loop (num)
num = test_lists ();
vmessage ("%d", num);
}
main ();
|
| lists.smlnj |
(* -*- mode: sml -*-
* $Id: lists.smlnj,v 1.2 2001/07/09 00:25:28 doug Exp $
* http://www.bagley.org/~doug/shootout/
* from Stephen Weeks
*)
structure Test : sig
val main : (string * string list) -> OS.Process.status
end = struct
val sub = Array.sub
val update = Array.update
fun for (start, stop, f) =
let
fun loop i =
if i > stop
then ()
else (f i; loop (i + 1))
in
loop start
end
fun failwith s = raise Fail s
structure Deque:
sig
type 'a t
exception Empty
val make: int * 'a -> 'a t
val iota: int -> int t
val is_empty: 'a t -> bool
val equal: ''a t * ''a t -> bool
val length: 'a t -> int
val nth: 'a t * int -> 'a
val push_front: 'a * 'a t -> unit
val push_back: 'a t * 'a -> unit
val take_front: 'a t -> 'a
val take_back: 'a t -> 'a
val copy: 'a t -> 'a t
val reverse: 'a t -> 'a t
end =
struct
type 'a t = {size: int ref,
first: int ref,
last: int ref,
field: 'a array ref,
fill: 'a}
local
fun make sel (d: 'a t) = sel d
in
fun fill z = make #fill z
end
local
fun make sel (d: 'a t) = !(sel d)
in
fun field z = make #field z
fun first z = make #first z
fun last z = make #last z
fun size z = make #size z
end
exception Empty
fun make (n, dummy) =
let
val n = Int.max (n, 0)
val nplus = Int.max (1, n)
in
{size = ref nplus,
first = ref (Int.quot (nplus, 2)),
last = ref (Int.quot (nplus, 2) - 1),
field = ref (Array.array (nplus, dummy)),
fill = dummy}
end
fun iota i =
let
val i = Int.max (0, i)
val iplus = Int.max (1, i)
in
{size = ref iplus,
first = ref 0,
last = ref (i - 1),
field = ref (Array.tabulate (iplus, fn n => n + 1)),
fill = i}
end
fun length buf = last buf - first buf + 1
fun is_empty buf = last buf < first buf
fun array_eq (arr1, off1, arr2, off2, i) =
let
fun loop (off1, off2, i) =
case i of
0 => true
| n =>
sub (arr1, off1) = sub (arr2, off2)
andalso loop (off1 + 1, off2 + 1, n - 1)
in loop (off1, off2, i)
end
fun equal (buf1, buf2) =
let
val len = length buf1
in
len = length buf2
andalso array_eq (field buf1, first buf1,
field buf2, first buf2,
len)
end
fun nth (buf, n) =
if n < 0 orelse n >= length buf
then failwith "nth"
else sub (field buf, first buf + n)
fun double_shift buf =
let
val new_size = size buf * 2
val len = length buf
val new_first = Int.quot (new_size - len, 2)
val new_field = Array.array (new_size, fill buf)
val _ = Array.copy {src = field buf,
si = first buf,
dst = new_field,
di = new_first,
len = SOME len}
in
#size buf := new_size;
#field buf := new_field;
#first buf := new_first;
#last buf := new_first + len - 1
end
fun push_front (elem, buf) =
let
val _ = if first buf = 0 then double_shift buf else ()
val new_first = first buf - 1
in
update (field buf, new_first, elem);
#first buf := new_first
end
fun push_back (buf, elem) =
let
val _ = if last buf = size buf - 1 then double_shift buf else ()
val new_last = last buf + 1
in
update (field buf, new_last, elem);
#last buf := new_last
end
fun take_front buf =
if is_empty buf
then raise Empty
else
let
val old_first = first buf
in
#first buf := old_first + 1;
sub (field buf, old_first)
end
fun take_back buf =
if is_empty buf
then raise Empty
else
let
val old_last = last buf
in
#last buf := old_last - 1;
sub (field buf, old_last)
end
fun copy buf =
let
val len = length buf
val new_buf = make (len, fill buf)
val _ = Array.copy {src = field buf,
si = first buf,
dst = field new_buf,
di = 0,
len = SOME len}
in
#first new_buf := 0;
#last new_buf := len - 1;
new_buf
end
fun reverse buf =
let
val len = length buf
val fst = first buf
val fld = field buf
val new_buf = make (len, fill buf)
val new_fld = field new_buf
val _ =
for (0, len - 1, fn i =>
update (new_fld, len - i - 1, sub (fld, fst + i)))
in
#first new_buf := 0;
#last new_buf := len - 1;
new_buf
end
end
open Deque
fun empty () = iota 0
val size = 10000
fun test_lists () =
let
val d1 = iota size
val d2 = copy d1
val d3 = empty ()
val _ = for (1, length d2, fn _ => push_back (d3, take_front d2))
val _ = for (1, length d3, fn _ => push_back (d2, take_back d3))
val d1 = reverse d1
val _ = if size <> nth (d1, 0) then failwith "First test failed" else ()
val _ = if length d1 <> length d2 then failwith "Second test failed" else ()
val _ = if not (equal (d1, d2)) then failwith "Third test failed" else ()
in
length d1
end
fun main (name, args) =
let
val n =
case Int.fromString (hd (args @ ["1"])) of
NONE => 1
| SOME n => n
val result = ref 0
val _ = for (1, n, fn _ => result := test_lists ())
in
print (concat [Int.toString (!result), "\n"]);
OS.Process.success
end
end
val _ = SMLofNJ.exportFn("lists", Test.main);
|
| lists.tcl |
#!/usr/local/bin/tclsh
# $Id: lists.tcl,v 1.3 2001/04/26 05:29:56 doug Exp $
# http://www.bagley.org/~doug/shootout/
# from Kristoffer Lawson
# Modified by Tom Wilkason
set SIZE 10000
proc K {a b} {set a}
proc ldelete {listName index} {
upvar $listName list
;# Replace a deletion with null, much faster
set list [lreplace [K $list [set list {}]] $index $index]
}
proc lreverse {_list} {
upvar $_list List
for {set i [expr {[llength $List] - 1}]} {$i >= 0} {incr i -1} {
lappend Li1r [lindex $List $i]
}
set List $Li1r
unset Li1r
}
proc test_lists {args} {
# create a list of integers (Li1) from 1 to SIZE
for {set i 1} {$i <= $::SIZE} {incr i} {lappend Li1 $i}
# copy the list to Li2 (not by individual items)
set Li2 $Li1
# remove each individual item from left side of Li2 and
# append to right side of Li3 (preserving order)
lreverse Li2
foreach {item} $Li2 {
lappend Li3 [lindex $Li2 end]
ldelete Li2 end
}
# Li2 must now be empty
# remove each individual item from right side of Li3 and
# append to right side of Li2 (reversing list)
foreach {item} $Li3 {
lappend Li2 [lindex $Li3 end]
ldelete Li3 end
}
# Li3 must now be empty
# reverse Li1 in place
lreverse Li1
# check that first item is now SIZE
if {[lindex $Li1 0] != $::SIZE} {
return "fail size [lindex $Li1 0]"
}
# compare Li1 and Li2 for equality
# and return length of the list
if {$Li1 == $Li2} {
return [llength $Li1]
} else {
return "fail compare"
}
}
proc main {args} {
global argv
set NUM [lindex $argv 0]
if {$NUM < 1} {
set NUM 1
}
while {$NUM > 0} {
set result [test_lists]
incr NUM -1
}
puts $result
}
main
|
| lists.vbscript |
Const SIZE = 10000
ITER = WScript.Arguments(0)
If ITER < 1 Then ITER = 1
result = 0
While ITER
result = test_lists
ITER = ITER - 1
Wend
WSCript.Echo result
Function test_lists()
' create a list of integers (Li1) from 1 to SIZE
Redim Li1(SIZE), Li2(SIZE), Li3(SIZE), Li4(SIZE)
For A = LBound(Li1) To UBound(Li1)
Li1(A) = A
Next
' copy the list to Li2 (not by individual items)
For A = LBound(Li1) To UBound(Li1)
Li2(A) = Li1(A)
Next
' remove each individual item from left side of Li2 and
' append to right side of Li3 (preserving order)
For A = LBound(Li2) To UBound(Li2)
Li3(A) = Li2(SIZE-A)
Next
' Li2 must now be empty
' remove each individual item from right side of Li3 and
' append to right side of Li2 (reversing list)
For A = LBound(Li2) To UBound(Li2)
Li2(A) = Li3(A)
Next
' Li3 must now be empty
' reverse Li1 in place
For A = LBound(Li1) To UBound(Li1)
Li4(A) = Li1(SIZE-A)
Next
For A = LBound(Li4) To UBound(Li4)
Li1(A) = Li4(A)
Next
' check that first item is now SIZE
If Li1(0) <> SIZE Then
test_lists = -1
Exit Function
End If
' compare Li1 and Li2 for equality
For i = LBound(Li1) To UBound(Li1)
'WScript.Echo "I=" & i & " Li1=" & Li1(i) & " Li2=" & Li2(i)
If Li1(i) <> Li2(i) Then
test_lists = 0
Exit Function
End If
Next
test_lists = UBound(Li1)
End Function
|
| lists.vc |
/* -*- mode: c -*-
* $Id: lists.gcc,v 1.3 2001/04/29 04:39:50 doug Exp $
* http://www.bagley.org/~doug/shootout/
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10000
// a simple Double Linked List
// the head node is special, it's val is length of list
typedef struct DLL {
int val;
struct DLL *next;
struct DLL *prev;
} DLL;
int list_length(DLL *head) { return(head->val); }
int list_empty(DLL *head) { return(list_length(head) == 0); }
DLL *list_first(DLL *head) { return(head->next); }
DLL *list_last(DLL *head) { return(head->prev); }
void list_push_tail(DLL *head, DLL *item) {
DLL *tail = head->prev;
tail->next = item;
item->next = head;
head->prev = item;
item->prev = tail;
head->val++;
}
DLL *list_pop_tail(DLL *head) {
DLL *prev, *tail;
if (list_empty(head)) return(NULL);
tail = head->prev;
prev = tail->prev;
prev->next = head;
head->prev = prev;
head->val--;
return(tail);
}
void list_push_head(DLL *head, DLL *item) {
DLL *next = head->next;
head->next = item;
next->prev = item;
item->next = next;
item->prev = head;
head->val++;
}
DLL *list_pop_head(DLL *head) {
DLL *next;
if (list_empty(head)) return(NULL);
next = head->next;
head->next = next->next;
next->next->prev = head;
head->val--;
return(next);
}
int list_equal(DLL *x, DLL *y) {
DLL *xp, *yp;
// first val's checked will be list lengths
for (xp=x, yp=y; xp->next != x; xp=xp->next, yp=yp->next) {
if (xp->val != yp->val) return(0);
}
if (xp->val != yp->val) return(0);
return(yp->next == y);
}
void list_print(char *msg, DLL *x) {
DLL *xp, *first = x->next;
int i = 0;
printf(msg);
printf("length: %d\n", list_length(x));
for (xp=x->next; xp->next != first; xp=xp->next) {
printf("i:%3d v:%3d n:%3d p:%3d\n", ++i,
xp->val, xp->next->val, xp->prev->val);
}
printf("[last entry points to list head]\n");
printf("[val of next of tail is: %d]\n", xp->next->val);
}
DLL *list_new() {
DLL *l = (DLL *)malloc(sizeof(DLL));
l->next = l;
l->prev = l;
l->val = 0;
return(l);
}
DLL *list_sequence(int from, int to) {
int size, tmp, i, j;
DLL *l;
if (from > to) {
tmp = from; from = to; to = tmp;
}
size = to - from + 1;
l = (DLL *)malloc((size+1) * sizeof(DLL));
from--;
for (i=0, j=1; i<size; ++i, ++j) {
l[i].next = &l[i+1];
l[j].prev = &l[j-1];
l[i].val = from++;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].prev = &l[size-1];
l[size].val = from;
l[0].val = size;
return(l);
}
DLL *list_copy(DLL *x) {
int i, j, size = list_length(x);
DLL *xp, *l = (DLL *)malloc((size+1) * sizeof(DLL));
for (i=0, j=1, xp=x; i<size; i++, j++, xp=xp->next) {
l[i].next = &l[j];
l[j].prev = &l[i];
l[i].val = xp->val;
}
l[0].prev = &l[size];
l[size].next = &l[0];
l[size].val = list_last(x)->val;
return(l);
}
void list_reverse (DLL *head) {
DLL *tmp, *p = head;
do {
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = tmp;
} while (p != head);
}
int test_lists() {
int len = 0;
// create a list of integers (li1) from 1 to SIZE
DLL *li1 = list_sequence(1, SIZE);
// copy the list to li2
DLL *li2 = list_copy(li1);
// remove each individual item from left side of li2 and
// append to right side of li3 (preserving order)
DLL *li3 = list_new();
// compare li2 and li1 for equality
if (!list_equal(li2, li1)) {
fprintf(stderr, "li2 and li1 are not equal\n");
exit(1);
}
while (!list_empty(li2)) {
list_push_tail(li3, list_pop_head(li2));
}
// li2 must now be empty
if (!list_empty(li2)) {
fprintf(stderr, "li2 should be empty now\n");
exit(1);
}
// remove each individual item from right side of li3 and
// append to right side of li2 (reversing list)
while (!list_empty(li3)) {
list_push_tail(li2, list_pop_tail(li3));
}
// li3 must now be empty
if (!list_empty(li3)) {
fprintf(stderr, "li3 should be empty now\n");
exit(1);
}
// reverse li1 in place
list_reverse(li1);
// check that li1's first item is now SIZE
if (list_first(li1)->val != SIZE) {
fprintf(stderr, "li1 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li1)->val);
exit(1);
}
// check that li1's last item is now 1
if (list_last(li1)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li1)->val);
exit(1);
}
// check that li2's first item is now SIZE
if (list_first(li2)->val != SIZE) {
fprintf(stderr, "li2 first value wrong, wanted %d, got %d\n",
SIZE, list_first(li2)->val);
exit(1);
}
// check that li2's last item is now 1
if (list_last(li2)->val != 1) {
fprintf(stderr, "last value wrong, wanted %d, got %d\n",
SIZE, list_last(li2)->val);
exit(1);
}
// check that li1's length is still SIZE
if (list_length(li1) != SIZE) {
fprintf(stderr, "li1 size wrong, wanted %d, got %d\n",
SIZE, list_length(li1));
exit(1);
}
// compare li1 and li2 for equality
if (!list_equal(li1, li2)) {
fprintf(stderr, "li1 and li2 are not equal\n");
exit(1);
}
len = list_length(li1);
free(li1);
free(li2);
free(li3);
// return the length of the list
return(len);
}
int main(int argc, char *argv[]) {
int n = ((argc == 2) ? atoi(argv[1]) : 1);
int result = 0;
while(n--) result = test_lists();
printf("%d\n", result);
return 0;
}
|
| lists.vc++ |
// -*- mode: c++ -*-
// $Id: lists.g++,v 1.5 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/
// from Bill Lear
#include <iostream>
#include <list>
#include <numeric>
using namespace std;
const size_t SIZE = 10000;
size_t test_lists() {
std::list<size_t> li1(SIZE);
std::iota(li1.begin(), li1.end(), 1);
std::list<size_t> li2(li1);
std::list<size_t> li3;
size_t N = li2.size();
while (N--) {
li3.push_back(li2.front());
li2.pop_front();
}
N = li3.size();
while (N--) {
li2.push_back(li3.back());
li3.pop_back();
}
li1.reverse();
return (li1.front() == SIZE) && (li1 == li2) ? li1.size() : 0;
}
int main(int argc, char* argv[]) {
size_t ITER = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): 1);
size_t result = 0;
while (ITER > 0) {
result = test_lists();
--ITER;
}
std::cout << result << std::endl;
}
|
| lists.vpascal |
Program lists;
uses SysUtils, Classes;
const SIZE : integer = 10000;
Function test_lists : integer;
var
i, len1, len2 : integer;
Li1, Li2, Li3 : TList;
lists_equal : Integer;
begin
Li1 := TList.Create;
Li1.Capacity := SIZE;
For i := 0 to SIZE Do
Li1.Add(Pointer(i));
Li2 := TList.Create;
Li2.Capacity := SIZE;
For i:= 0 to SIZE Do
Li2.Add(Li1.Items[i]);
{ remove each individual item from left side of Li2 and
append to right side of Li3 (preserving order) }
Li3 := TList.Create;
Li3.Capacity := SIZE;
For i := 0 to SIZE Do
begin
Li3.Add( Li2.First );
Li2.Remove( Li2.First );
end;
{ remove each individual item from right side of Li3 and
append to right side of Li2 (reversing list) }
For i := 0 To SIZE Do
begin
Li2.Add( Li3.Last );
Li3.Count := Li3.Count - 1;
end;
For i := 0 To (SIZE div 2) Do
begin
Li1.Exchange( i, SIZE-i );
end;
If integer(Li1.first) <> SIZE Then
begin
test_lists := 0;
exit;
end;
len1 := Li1.Count - 1;
len2 := Li2.Count - 1;
If len1 <> len2 Then
begin
test_lists := 0;
exit;
end;
lists_equal := 1;
For i := 0 To len1 Do
begin
If integer(Li1.items[i]) <> integer(Li2.items[i]) Then
begin
lists_equal := 0;
break;
end;
end;
If lists_equal = 0 Then
begin
test_lists := 0;
end
else
test_lists := len1;
end;
var
ITER, i, result: integer;
begin
if ParamCount = 0 then
ITER := 1
else
ITER := StrToInt(ParamStr(1));
if ITER < 1 then ITER := 1;
For i := 1 To ITER Do result := test_lists;
Writeln (IntToStr(result));
end.
|