Skip to content

Commit 5b88f6b

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#180 from eloiseSJTU/master
merge to liuxin
2 parents fe2e9c3 + 280c488 commit 5b88f6b

File tree

184 files changed

+10741
-2543
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

184 files changed

+10741
-2543
lines changed

‎group02/562768642/src/com/github/orajavac/coding2017/basic/linklist/LRUPageFrame.java

Lines changed: 245 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,245 @@
1+
package com.github.orajavac.coding2017.basic.linklist;
2+
3+
public class LRUPageFrame {
4+
private static class Node {
5+
6+
Node prev;
7+
Node next;
8+
Object pageNum=10000;
9+
String flag;
10+
11+
Node() {
12+
}
13+
}
14+
15+
private int capacity;
16+
private int length;
17+
18+
19+
private Node first;// 链表头
20+
private Node last;// 链表尾
21+
22+
public LRUPageFrame(){
23+
init();
24+
}
25+
26+
public LRUPageFrame(int capacity) {
27+
28+
this.capacity = capacity;
29+
30+
init();
31+
}
32+
33+
public void init(){
34+
first = new Node();
35+
last = new Node();
36+
last.flag = "last"; //用来标识最后一个节点是链表尾，在这里链表尾并不算做内存页
37+
first.flag = "first"; //用来标识链表头，在这里链表头并不算做内存页
38+
first.next = last;
39+
last.prev=first;
40+
}
41+
42+
/**
43+
* 获取缓存中对象
44+
*
45+
* @param key
46+
* @return
47+
*/
48+
public void access(int pageNum) {
49+
if(lookup(pageNum)){
50+
;
51+
}else{
52+
if (length<capacity){
53+
addFirst(pageNum);
54+
}else{
55+
remove(pageNum); //删除尾元素
56+
addFirst(pageNum);
57+
}
58+
}
59+
}
60+
61+
public boolean lookup(int pageNum){
62+
Node nodef = first;
63+
Node nodel = last;
64+
65+
//判断要找的元素是否在第一个节点里
66+
if (nodef.next.pageNum.equals(pageNum)){
67+
return true;
68+
}
69+
70+
//判断要找的元素是否在最后一个节点里
71+
if (nodel.prev.pageNum.equals(pageNum)){
72+
remove(pageNum); //删除尾元素
73+
addFirst(pageNum); //把访问pageNum添加到第一个节点里
74+
return true;
75+
}
76+
77+
while(nodef.next!=null&&!nodef.next.pageNum.equals(999)){
78+
if (nodef.next.pageNum.equals(pageNum)){
79+
nodef.next = nodef.next.next; //先删除元素
80+
nodef.next.prev = nodef;
81+
addFirst(pageNum); //再把访问添加元素
82+
return true;
83+
}
84+
nodef = nodef.next;
85+
}
86+
return false;
87+
}
88+
89+
public Node getFirst() {
90+
return first;
91+
}
92+
93+
public void setFirst(Node first) {
94+
this.first = first;
95+
}
96+
97+
public Node getLast() {
98+
return last;
99+
}
100+
101+
public void setLast(Node last) {
102+
this.last = last;
103+
}
104+
105+
public void remove(Object pageNum){
106+
length--;
107+
Node n = last.prev;
108+
last.prev = n.prev;
109+
n.prev.next = last;
110+
}
111+
112+
public void addFirst(Object pageNum){
113+
Node s = first.next;
114+
Node n = new Node();
115+
n.pageNum=pageNum;
116+
n.next=s;
117+
s.prev=n;
118+
first.next=n;
119+
length++;
120+
}
121+
122+
public void add(Object pageNum){
123+
Node node = first.next;
124+
while (node.next!=null){
125+
node = node.next;
126+
}
127+
Node e = new Node();
128+
e.pageNum = pageNum;
129+
Node prev = node.prev;
130+
prev.next = e;
131+
e.prev = prev;
132+
e.next = node;
133+
node.prev = e;
134+
length++;
135+
}
136+
137+
public String toString(){
138+
StringBuilder buffer = new StringBuilder();
139+
Node node = first;
140+
while(node.next.flag != "last"){
141+
buffer.append(node.next.pageNum);
142+
143+
node = node.next;
144+
145+
if(node.next.flag != "last"){
146+
buffer.append(",");
147+
}
148+
149+
}
150+
return buffer.toString();
151+
}
152+
153+
/**
154+
* 测试双向链表逆序输出
155+
* @return
156+
*/
157+
public String lastToString(){
158+
StringBuilder buffer = new StringBuilder();
159+
Node node = last;
160+
while(node.prev!=null&&node.prev.flag != "first"){
161+
buffer.append(node.prev.pageNum);
162+
163+
node = node.prev;
164+
165+
if(node.prev!=null&&node.prev.flag != "first"){
166+
buffer.append(",");
167+
}
168+
}
169+
return buffer.toString();
170+
}
171+
172+
public Object getFirstNode(){
173+
return first.next.pageNum;
174+
}
175+
176+
/**
177+
* StackUtil 使用
178+
* @param len
179+
* @return
180+
*/
181+
public Object[] getElements(int len){
182+
Object[] obj = new Object[len];
183+
int i=0;
184+
Node node = first;
185+
while(node.next.flag != "last"){
186+
obj[i] = node.next.pageNum;
187+
node = node.next;
188+
if (i == len-1){
189+
return obj;
190+
}
191+
i++;
192+
}
193+
return null;
194+
}
195+
196+
/**
197+
* StackUtil 使用
198+
* @param obj
199+
* @param o
200+
*/
201+
public void remove(Object obj,Object o){
202+
Node nodef = first;
203+
while(nodef.next!=null&&!nodef.next.pageNum.equals(999)){
204+
if (nodef.next.pageNum.equals(obj)){
205+
nodef.next = nodef.next.next; //先删除元素
206+
nodef.next.prev = nodef;
207+
length--;
208+
break;
209+
}
210+
nodef = nodef.next;
211+
}
212+
}
213+
214+
/**
215+
* Stack 使用
216+
* @return
217+
*/
218+
public int getLength(){
219+
return length;
220+
}
221+
222+
/**
223+
* Stack 使用 pop
224+
* @return
225+
*/
226+
public Object remove(){
227+
length--;
228+
Node n = last.prev;
229+
last.prev = n.prev;
230+
n.prev.next = last;
231+
return n.pageNum;
232+
}
233+
234+
/**
235+
* Stack 使用 pop
236+
* @return
237+
*/
238+
public Object removeLow(){
239+
length--;
240+
Node n = first.next;
241+
first.next = n.next;
242+
n.next.prev = first;
243+
return n.pageNum;
244+
}
245+
}

‎group02/562768642/src/com/github/orajavac/coding2017/basic/linklist/LRUPageFrameTest.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.github.orajavac.coding2017.basic.linklist;
2+
3+
import org.junit.Test;
4+
5+
import junit.framework.Assert;
6+
7+
public class LRUPageFrameTest {
8+
9+
@Test
10+
public void testAccess() {
11+
LRUPageFrame frame = new LRUPageFrame(3);
12+
frame.access(7);
13+
frame.access(0);
14+
frame.access(1);
15+
Assert.assertEquals("1,0,7", frame.toString());
16+
frame.access(2);
17+
Assert.assertEquals("2,1,0", frame.toString());
18+
frame.access(0);
19+
Assert.assertEquals("0,2,1", frame.toString());
20+
frame.access(0);
21+
Assert.assertEquals("0,2,1", frame.toString());
22+
frame.access(3);
23+
Assert.assertEquals("3,0,2", frame.toString());
24+
frame.access(0);
25+
Assert.assertEquals("0,3,2", frame.toString());
26+
frame.access(4);
27+
Assert.assertEquals("4,0,3", frame.toString());
28+
}
29+
}

0 commit comments

Comments
 (0)