1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#!/usr/bin/perl
use warnings;
use strict;
{ package My::Node;
sub new {
my ($class, $value) = @_;
bless [ $value, undef ], $class
}
sub Next { $_[0][1] }
sub value { $_[0][0] }
sub disconnect {
my ($self) = @_;
my $next = $self->Next;
undef $self->[1];
return $next
}
sub attach {
my ($self, $new_next) = @_;
die "Already attached" if defined $self->Next;
$self->[1] = $new_next;
}
sub Last {
my ($self) = @_;
my $node = $self;
$node = $node->Next while $node->Next;
return $node
}
sub append {
my ($self, $new) = @_;
if (defined $new) {
$new->Last->attach($self);
} else {
$_[1] = $self;
}
}
}
{ package My::LinkedList;
sub new {
my ($class, @list) = @_;
my $top;
while (@list) {
my $value = pop @list;
my $node = 'My::Node'->new($value);
$node->attach($top) if $top;
$top = $node;
}
bless { head => $top }, $class
}
sub head {
my ($self, $head) = @_;
$self->{head} = $head if @_ > 1;
return $self->{head}
}
sub Values {
my ($self) = @_;
my $node = $self->head;
my @values;
while ($node) {
push @values, $node->value;
$node = $node->Next;
}
return \@values
}
sub partition {
my ($self, $k) = @_;
my $node = $self->head;
my ($head, $tail);
while ($node) {
my $next = $node->disconnect;
$node->append($node->value >= $k ? $tail : $head);
$node = $next;
}
$tail->append($head) if $head && $tail;
$_[0]{head} = $head || $tail;
}
}
use Test::More;
my $head = 'My::Node'->new(2);
my $body = 'My::Node'->new(1);
my $list = 'My::LinkedList'->new;
$list->head($head);
$head->attach($body);
is_deeply $list->Values, [2, 1], 'values';
$list->partition(2);
is_deeply $list->Values, [1, 2], 'pair partition';
my $ll = 'My::LinkedList'->new(1, 4, 3, 2, 5, 2);
is_deeply $ll->Values, [1, 4, 3, 2, 5, 2], 'constructor args';
$ll->partition(3);
is_deeply $ll->Values, [1, 2, 2, 4, 3, 5], 'sample partition';
my $repeated = 'My::LinkedList'->new(1, 2, 3, 1, 2, 3);
$repeated->partition(2);
is_deeply $repeated->Values, [1, 1, 2, 3, 2, 3], 'repeated';
my $short = 'My::LinkedList'->new(1);
$short->partition(1);
is_deeply $short->Values, [1], 'short';
$short->partition(2);
is_deeply $short->Values, [1], 'short over';
done_testing();
|
