1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
namespace Yiranzai\File; |
4
|
|
|
|
5
|
|
|
/** |
6
|
|
|
* Class Bucket |
7
|
|
|
* @package Yiranzai\Dht |
8
|
|
|
*/ |
9
|
|
|
class Bucket |
10
|
|
|
{ |
11
|
|
|
/** |
12
|
|
|
* @var Node |
13
|
|
|
*/ |
14
|
|
|
protected $head; |
15
|
|
|
|
16
|
|
|
/** |
17
|
|
|
* Bucket constructor. |
18
|
|
|
* @param $key |
19
|
|
|
* @param $data |
20
|
|
|
*/ |
21
|
6 |
|
public function __construct(string $key, string $data = null) |
22
|
|
|
{ |
23
|
6 |
|
$this->head = new Node($key, $data); |
24
|
6 |
|
} |
25
|
|
|
|
26
|
|
|
/** |
27
|
|
|
* 链表有几个元素 |
28
|
|
|
* |
29
|
|
|
* @return int |
30
|
|
|
*/ |
31
|
3 |
|
public function countNode(): int |
32
|
|
|
{ |
33
|
3 |
|
$cur = $this->head; |
34
|
3 |
|
$i = 1; |
35
|
3 |
|
while ($cur->next !== null) { |
36
|
3 |
|
++$i; |
37
|
3 |
|
$cur = $cur->next; |
38
|
|
|
} |
39
|
3 |
|
return $i; |
40
|
|
|
} |
41
|
|
|
|
42
|
|
|
/** |
43
|
|
|
* 增加节点 |
44
|
|
|
* |
45
|
|
|
* @param string $key |
46
|
|
|
* @param string $data |
47
|
|
|
* @return Bucket |
48
|
|
|
*/ |
49
|
3 |
|
public function addNode(string $key, string $data = null): Bucket |
50
|
|
|
{ |
51
|
3 |
|
$cur = $this->head; |
52
|
3 |
|
while ($cur->next !== null) { |
53
|
3 |
|
$cur = $cur->next; |
54
|
|
|
} |
55
|
3 |
|
$new = new Node($key, $data); |
56
|
3 |
|
$cur->next = $new; |
57
|
3 |
|
return $this; |
58
|
|
|
} |
59
|
|
|
|
60
|
|
|
/** |
61
|
|
|
* 增加节点 |
62
|
|
|
* |
63
|
|
|
* @param string $key |
64
|
|
|
* @param string $data |
65
|
|
|
* @return Bucket |
66
|
|
|
*/ |
67
|
3 |
|
public function putNode(string $key, string $data = null): Bucket |
68
|
|
|
{ |
69
|
3 |
|
$cur = $this->head; |
70
|
3 |
|
if ($cur->key === $key) { |
71
|
3 |
|
$cur->data = $data; |
72
|
3 |
|
return $this; |
73
|
|
|
} |
74
|
3 |
|
while ($cur->next !== null) { |
75
|
3 |
|
$cur = $cur->next; |
76
|
3 |
|
if ($cur->key === $key) { |
77
|
3 |
|
$cur->data = $data; |
78
|
3 |
|
return $this; |
79
|
|
|
} |
80
|
|
|
} |
81
|
3 |
|
$new = new Node($key, $data); |
82
|
3 |
|
$cur->next = $new; |
83
|
3 |
|
return $this; |
84
|
|
|
} |
85
|
|
|
|
86
|
|
|
/** |
87
|
|
|
* 紧接着插在$noNum后 |
88
|
|
|
* |
89
|
|
|
* @param string $k |
90
|
|
|
* @param string $index |
91
|
|
|
* @param string $data |
92
|
|
|
* @return Bucket |
93
|
|
|
*/ |
94
|
3 |
|
public function insertNode(string $k, string $index, string $data = null): Bucket |
95
|
|
|
{ |
96
|
3 |
|
$cur = $this->head; |
97
|
3 |
|
$new = new Node($k, $data); |
98
|
3 |
|
if ($cur->key !== $index) { |
99
|
3 |
|
while ($cur->next !== null) { |
100
|
3 |
|
$cur = $cur->next; |
101
|
3 |
|
if ($cur->key === $index) { |
102
|
3 |
|
break; |
103
|
|
|
} |
104
|
|
|
} |
105
|
|
|
} |
106
|
3 |
|
$new->next = $cur->next; |
107
|
3 |
|
$cur->next = $new; |
108
|
3 |
|
return $this; |
109
|
|
|
} |
110
|
|
|
|
111
|
|
|
/** |
112
|
|
|
* 删除第$no个节点 |
113
|
|
|
* |
114
|
|
|
* @param string $key |
115
|
|
|
* @return Bucket |
116
|
|
|
*/ |
117
|
3 |
|
public function delNode(string $key): Bucket |
118
|
|
|
{ |
119
|
3 |
|
$cur = $this->head; |
120
|
3 |
|
if ($cur->next !== null) { |
121
|
3 |
|
if ($cur->key === $key) { |
122
|
3 |
|
$this->head = $cur->next; |
123
|
|
|
} else { |
124
|
3 |
|
while ($cur->next !== null) { |
125
|
3 |
|
if ($cur->next->key === $key) { |
126
|
3 |
|
$cur->next = $cur->next->next; |
127
|
3 |
|
break; |
128
|
|
|
} |
129
|
3 |
|
$cur = $cur->next; |
130
|
|
|
} |
131
|
|
|
} |
132
|
|
|
} |
133
|
3 |
|
return $this; |
134
|
|
|
} |
135
|
|
|
|
136
|
|
|
/** |
137
|
|
|
* 遍历链表 |
138
|
|
|
* |
139
|
|
|
* @return Bucket |
140
|
|
|
*/ |
141
|
3 |
|
public function showNode(): Bucket |
142
|
|
|
{ |
143
|
3 |
|
$cur = $this->head; |
144
|
3 |
|
while ($cur->next !== null) { |
145
|
3 |
|
$cur = $cur->next; |
146
|
3 |
|
echo $cur->data . PHP_EOL; |
147
|
|
|
} |
148
|
3 |
|
return $this; |
149
|
|
|
} |
150
|
|
|
|
151
|
|
|
/** |
152
|
|
|
* 寻找节点 |
153
|
|
|
* |
154
|
|
|
* @param string $key |
155
|
|
|
* @return Node|null |
156
|
|
|
*/ |
157
|
6 |
|
public function findNode(string $key): ?Node |
158
|
|
|
{ |
159
|
6 |
|
$cur = $this->head; |
160
|
6 |
|
if ($cur->key === $key) { |
161
|
6 |
|
return $cur; |
162
|
|
|
} |
163
|
3 |
|
while ($cur->next !== null) { |
164
|
3 |
|
$cur = $cur->next; |
165
|
3 |
|
if ($cur->key === $key) { |
166
|
3 |
|
return $cur; |
167
|
|
|
} |
168
|
|
|
} |
169
|
3 |
|
return null; |
170
|
|
|
} |
171
|
|
|
|
172
|
|
|
/** |
173
|
|
|
* 寻找某节点的值 |
174
|
|
|
* |
175
|
|
|
* @param string $key |
176
|
|
|
* @return string|null |
177
|
|
|
*/ |
178
|
3 |
|
public function find(string $key): ?string |
179
|
|
|
{ |
180
|
3 |
|
$node = $this->findNode($key); |
181
|
3 |
|
return $node === null ? null : $node->data; |
182
|
|
|
} |
183
|
|
|
} |
184
|
|
|
|