文件感染 - milo103/Algorithm-Problem GitHub Wiki

static int index =0;
static int SIZE = 40000;
final static int root_key = 10000;
static Node []hashpool = new Node[SIZE+10];
static Node []head = new Node[SIZE+10];
static Node root ;

public static class Node{
	boolean isfile;
    int filesize;
	int oldsize;
	int id;

	Node parent;
	Node child;
	Node brother;
	Node next;
}

Node getNewnode(){
	index++;
	return hashpool[index-1];
}

public static void init(){
	index =0;
	for(int i =0;i< SIZE+10;i++){
		head[i] = new Node();
		hashpool[i]=new Node();
	}

root = new Node();
root.id = root_key;

	insert(root,head[root_key]);
}

public static int getKey(int values){
	return values%(SIZE+10);
}

private Node getNodebyhash(int keypid) {
	int id = getKey(keypid);
	Node newnode = head[id].next;
	while(newnode != null){
		if(newnode.id == id){
			return newnode;
		}
		newnode = newnode.next;
	}
	return null;
}

private Node createNewnode(int id, int filesize) {
	Node newnode = getNewnode();
	newnode.id = id;
	if(filesize!=0){
		newnode.filesize = filesize;
		newnode.oldsize = filesize;
		newnode.isfile = true;
	}else{
		newnode.isfile = false;
	}
	return newnode;
}

public int add(int id, int pid, int fileSize) {
	Node pidnode = getNodebyhash(pid);
	int key = getKey(id);
	Node newnode = createNewnode(key,fileSize);

newnode.brother = pidnode.child;
newnode.parent = pidnode;
pidnode.child = newnode;

insert(newnode,head[key]);

	return getsize(pidnode);
}

public static int getfilenum(Node node){
	int num =0;
	if(node.filesize !=0)
		return 1;
	Node current = node.child;

	while(current != null){
		num += getfilenum(current);
		current = current.brother;
	}
	return num;
}

static void insert(Node newnode, Node parentnode){
	newnode.next = parentnode.next;
	parentnode.next = newnode;
}

public int move(int id, int pid) {
	Node movenode = getNodebyhash(id);
	Node newparentnode = getNodebyhash(pid);

if(movenode.parent.child == movenode){
	movenode.parent.child = movenode.brother;
}else{
	Node current = movenode.parent.child;
	while(current.brother != movenode){
		current = current.brother;
	}
	current.brother = movenode.brother;
}

movenode.parent = newparentnode;
movenode.brother = newparentnode.child;
newparentnode.child = movenode;

return getsize(newparentnode);

}

public int remove(int id) {
	Node movenode = getNodebyhash(id);
	Node parentnode = movenode.parent;

if(parentnode.child == movenode){
	parentnode.child = movenode.brother;
}else{
	Node current = parentnode.child;
	while(current.brother != movenode){
		current = current.brother;
	}
	current.brother = movenode.brother;
}

	return getsize(movenode);
}

public int recover(int id) {
	Node node = getNodebyhash(id);
	updatReover(node);
	return getsize(node);
}

public void updatReover(Node node){
	if(node.filesize!=0){
		node.filesize = node.oldsize;
		return ;
	}
	Node current = node.child;
	while(current!=null){
		updatReover(current);
		current = current.brother;
	}
}

public int infect(int id) {
	int totalsize = getsize(root);
	if(totalsize ==0)
		return 0;

Node infectnode = getNodebyhash(id);
int num = getfilenum(root);
int addsize = totalsize/num;

updateInfect(infectnode, addsize);

	return getsize(infectnode);
}

private void updateInfect(Node node, int addsize) {
	if(node.filesize !=0){
		node.filesize += addsize;
		return ;
	}
	Node current = node.child;

	while(current!= null){
		updateInfect(current,addsize);
		current = current.brother;
	}
}

public int getsize(Node pidnode) {
	int total =0;
	if(pidnode.filesize!=0 )
		return pidnode.filesize;

Node current = pidnode.child;

while(current != null){
	total += getsize(current);
	current = current.brother;
}

	return total;
}

public String getObject(){

StringBuilder sb= new StringBuilder();
int totalsize = getsize(root);
if(totalsize ==0)
	return sb.append("totalsize: 0 file num: 0").toString();

	int num = getfilenum(root);
	int addsize = totalsize/num;
	 sb.append("totalsize: "+totalsize +" file num: "+num +" addsize "+ addsize);
	return sb.toString();
}