Untitled
unknown
plain_text
a year ago
7.9 kB
5
Indexable
import java.util.*; class UserSolution { /* * Giua 2 user co 1 duong di (link) vo huong Moi duong di co so bandwidth * cho truoc */ class User { HashSet<Integer> nei; HashSet<String> file; Node target[]; } class Node { int sourceId, destinationID; ArrayList<Integer> paths; } class File { int size; HashSet<Integer> listUser = new HashSet<Integer>(); } class Request { String nameFile; int sizeFile; ArrayList<Integer> paths; } class Queue { int head = 0, tail = 0; final int queueSize = 10000; int[] queue = new int[queueSize]; void enqueue(int value) { queue[tail] = value; tail++; if (tail >= queueSize) { tail = 0; } } int dequeue() { int value = queue[head]; head++; if (head >= queueSize) { head = 0; } return value; } boolean isEmpty() { return tail == head; } } public User U[]; public HashMap<String, File> mapFile; public HashMap<Integer, Request> mapRequest; public int nUser; public int map[][]; public void init(int N, int mU1[], int mU2[], int mBandwidth[]) { // Khai bao nUser = N; U = new User[N + 1]; for (int i = 1; i <= N; i++) { U[i] = new User(); U[i].file = new HashSet<String>(); U[i].nei = new HashSet<Integer>(); U[i].target = new Node[N + 1]; } mapFile = new HashMap<String, UserSolution.File>(); mapRequest = new HashMap<Integer, UserSolution.Request>(); map = new int[N + 1][N + 1]; for (int i = 0; i < N - 1; i++) { int a = mU1[i]; int b = mU2[i]; map[a][b] = mBandwidth[i]; map[b][a] = mBandwidth[i]; U[a].nei.add(b); U[b].nei.add(a); } // Luu duong di vao queue for (int i = 1; i <= N; i++) { Queue q = new Queue(); int[] visited = new int[N + 1]; q.enqueue(i); while (!q.isEmpty()) { int current = q.dequeue(); visited[current] = 1; Node currentNode = null; if (U[i].target[current] != null) { currentNode = U[i].target[current]; } for (int next : U[current].nei) { if (visited[next] == 0) { q.enqueue(next); Node n = new Node(); n.destinationID = next; n.sourceId = i; n.paths = new ArrayList<Integer>(); // Copy path cua currentNode vao n if (currentNode != null) { for (int path : currentNode.paths) { n.paths.add(path); } } n.paths.add(next); // Add n vao target cua U[i] U[i].target[next] = new Node(); U[i].target[next] = n; } } } } } public int share(int Uid, char mFilename[], int mFilesize) { String fileName = CharToString(mFilename); // Luu file vao mapFile File file = mapFile.get(fileName); if (file == null) { file = new File(); file.size = mFilesize; file.listUser.add(Uid); mapFile.put(fileName, file); } else { file.listUser.add(Uid); mapFile.put(fileName, file); } // Add file vao User U[Uid].file.add(fileName); return U[Uid].file.size(); } public int request(int Uid, char mFilename[], int mTID) { String fileName = CharToString(mFilename); int res_soBuoc = 10000; int res_ID = 10000; int size = 0; // Ktra file duoc luu o User nao, va check duong di tu user do den Uid Request request = new Request(); request.nameFile = fileName; request.sizeFile = size; request.paths = new ArrayList<Integer>(); request.paths.add(Uid); File file = mapFile.get(fileName); if (file != null) { size = file.size; boolean flag = false; for (int user : file.listUser) { int count = U[Uid].target[user].paths.size(); if (count < res_soBuoc) { if (check(Uid, user, size)) { flag = true; res_soBuoc = count; res_ID = user; } } else if (count == res_soBuoc && res_ID > user) { if (check(Uid, user, size)) { flag = true; res_soBuoc = count; res_ID = user; } } } // Add path vao request if (flag == true) { request.sizeFile = size; for (int path : U[Uid].target[res_ID].paths) { request.paths.add(path); } // Cap nhat bandwidth for (int i = 1; i < request.paths.size(); i++) { int a = request.paths.get(i); int b = request.paths.get(i - 1); map[a][b] -= size; map[b][a] -= size; } // add request vao map mapRequest.put(mTID, request); return res_ID; } } mapRequest.put(mTID, request); return -1; } public int complete(int mTID) { Request request = mapRequest.get(mTID); int size = request.sizeFile; String fileName = request.nameFile; // Update bandwidth va add file vao user //Add user vao file if (size > 0) { for (int i = 1; i < request.paths.size(); i++) { int a = request.paths.get(i); int b = request.paths.get(i - 1); map[a][b] += size; map[b][a] += size; if (i == 1) { U[b].file.add(fileName); HashSet<Integer> list = mapFile.get(fileName).listUser; list.add(b); } U[a].file.add(fileName); HashSet<Integer> list = mapFile.get(fileName).listUser; list.add(a); } } return U[request.paths.get(0)].file.size(); } public String CharToString(char a[]) { String ret = ""; int i = 0; while (i < a.length && a[i] != '\0') { ret += a[i]; ++i; } return ret; } public boolean check(int Uid, int user, int size) { Node node = U[Uid].target[user]; boolean flag = true; for (int i = 0; i < node.paths.size() && flag == true; i++) { if (i == 0) { if (map[node.paths.get(i)][node.sourceId] < size) { flag = false; } } else { if (map[node.paths.get(i)][node.paths.get(i - 1)] < size) { flag = false; } } } return flag; } }
Editor is loading...
Leave a Comment