Untitled
unknown
plain_text
a year ago
7.5 kB
4
Indexable
Never
package Electronic_heap; import javax.sound.midi.MidiDevice.Info; public class UserSolution { private static final int MAX_POST = 50001; private static final int MAX_USER = 10001; private static final int MAX_HASH1 = 10007; private static final int MAX_HASH2 = 50021; private static final int MAX_L = 11; long hash(char[] name) { long ret = 0; for (int i = 0; name[i] != '\0'; i++) { // long a=; // long b=; ret = (long) (ret * 31 + name[i] - 'a' + 1); } return ret; } // Infor class InFo { long id; int totalPoint; InFo hasNext; int objIdx; int heapIdx; } InFo[] infor = new InFo[MAX_POST + MAX_USER]; int objcnt; // User class User { char[] name; InFo info; public User() { super(); this.name = new char[MAX_L]; } } User[] users = new User[MAX_USER]; int num_user; // Post class Post { int point; InFo info; Post parent; User user; // LinkedList Post next; Post child; } Post[] posts = new Post[MAX_POST]; int numPost; // Heap InFo[] userHeap = new InFo[MAX_USER]; int userHeapSize; InFo[] postHeap = new InFo[MAX_POST]; int postHeapSize; boolean isBetter(InFo info1, InFo info2) { if (info1.totalPoint == info2.totalPoint) { return info1.id < info2.id; } return info1.totalPoint > info2.totalPoint; } void upHeap(InFo[] heap, int pos) { InFo cur = heap[pos]; for (; pos > 1 && isBetter(cur, heap[pos >> 1]); pos >>= 1) { heap[pos] = heap[pos >> 1]; heap[pos].heapIdx = pos; } heap[pos] = cur; heap[pos].heapIdx = pos; } void downHeap(InFo[] heap, int size, int pos) { InFo cur = heap[pos]; int child; while ((child = pos << 1) <= size) { if (child < size && isBetter(heap[child + 1], heap[child])) { child++; } if (isBetter(heap[child], cur)) { heap[pos] = heap[child]; heap[pos].heapIdx = pos; pos = child; } else break; } heap[pos] = cur; heap[pos].heapIdx = pos; } int heapPush(InFo[] heap, int size, InFo info) { heap[++size] = info; upHeap(heap, size); return size; } void heapUpdate(InFo[] heap, int size, InFo info) { int pos = info.heapIdx; upHeap(heap, pos); downHeap(heap, size, pos); } void heapRemove(InFo[] heap, int size, InFo info) { int pos = info.heapIdx; heap[pos] = heap[size--]; heap[pos].heapIdx = pos; heapUpdate(heap, size, heap[pos]); } InFo heapPop(InFo[] heap, int size) { InFo ret = heap[1]; heapRemove(heap, size, heap[1]); return ret; } // /hashmap InFo[] userMap = new InFo[MAX_HASH1]; InFo[] postMap = new InFo[MAX_HASH2]; Post findPost(int postID) { for (InFo info = postMap[postID % MAX_HASH2]; info != null; info = info.hasNext) { if (postID == info.id) return posts[info.objIdx]; } return null; } String charttoString(char[] a) { String str = ""; int i = 0; while (a[i] != '\0') { str += a[i]; i++; } return str; } User findUser(char[] name) { long hashval = hash(name); for (InFo info = userMap[(int) (hashval % MAX_HASH1)]; info != null; info = info.hasNext) { if (hashval == info.id) { return users[info.objIdx]; } } InFo info = infor[objcnt++]; info.id = hashval; info.objIdx = num_user; info.totalPoint = 0; int index = (int) (hashval % MAX_HASH1); info.hasNext = userMap[index]; userMap[index] = info; userHeap[++userHeapSize] = info; info.heapIdx = userHeapSize; users[num_user].name = name; users[num_user].info = info; return users[num_user++]; } int addnewPost(User user, int mID, int mPoint, Post parent) { user.info.totalPoint += mPoint; heapUpdate(userHeap, userHeapSize, user.info); InFo postInfo = infor[objcnt++]; postInfo.id = mID; postInfo.totalPoint = mPoint; postInfo.objIdx = numPost; int index = (mID % MAX_HASH2); postInfo.hasNext = postMap[index]; postMap[index] = postInfo; Post post = posts[numPost++]; post.info = postInfo; post.point = mPoint; post.user = user; post.child = null; post.parent = parent; if (parent != null) { post.next = parent.child; parent.child = post; parent.info.totalPoint += mPoint; if (parent.parent != null) { parent = parent.parent; parent.info.totalPoint += mPoint; } heapUpdate(postHeap, postHeapSize, parent.info); return parent.info.totalPoint; } heapPush(postHeap, postHeapSize, postInfo); postHeapSize++; post.next = null; return user.info.totalPoint; } void init() { objcnt = num_user = numPost = userHeapSize = postHeapSize = 0; userMap = new InFo[MAX_HASH1]; postMap = new InFo[MAX_HASH2]; for (int i = 0; i < MAX_POST + MAX_USER; i++) { infor[i] = new InFo(); } for (int i = 0; i < MAX_POST; i++) { postHeap[i] = new InFo(); // postMap[i]=new InFo(); posts[i] = new Post(); } for (int i = 0; i < MAX_USER; i++) { userHeap[i] = new InFo(); // userMap[i]=new InFo(); users[i] = new User(); } for (int i = 0; i < MAX_HASH1; i++) { userMap[i] = new InFo(); } for (int i = 0; i < MAX_HASH2; i++) { postMap[i] = new InFo(); } } int writeMessage(char mUser[], int mID, int mPoint) { User user = findUser(mUser); return addnewPost(user, mID, mPoint, null); } int commentTo(char mUser[], int mID, int mTargetID, int mPoint) { User user = findUser(mUser); Post target = findPost(mTargetID); return addnewPost(user, mID, mPoint, target); } void updateUserPoint(Post post) { post.user.info.totalPoint -= post.point; heapUpdate(userHeap, userHeapSize, post.user.info); for (Post chld = post.child; chld != null; chld = chld.next) updateUserPoint(chld); } int erase(int mID) { Post post = findPost(mID); updateUserPoint(post); Post parent = post.parent; if (parent != null) {// this post is a comment or reply // delete from parent's list if (post == parent.child) parent.child = post.next; else { for (Post i = parent.child; i.next != null; i = i.next) { if (post == i.next) { i.next = i.next.next; break; } } } parent.info.totalPoint -= post.info.totalPoint; if (parent.parent != null) { // this post is a reply parent = parent.parent; parent.info.totalPoint -= post.info.totalPoint; } heapUpdate(postHeap, postHeapSize, parent.info); return parent.info.totalPoint; } // this is a message heapRemove(postHeap, postHeapSize, post.info); postHeapSize--; return post.user.info.totalPoint; } InFo[] bestInfos = new InFo[5]; void getBestMessages(int mBestMessageList[]) { for (int i = 0; i < 5; i++) { bestInfos[i] = heapPop(postHeap, postHeapSize); postHeapSize--; int a = (int) (bestInfos[i].id); mBestMessageList[i] = a; } for (int i = 0; i < 5; i++) { heapPush(postHeap, postHeapSize, bestInfos[i]); postHeapSize++; } } void getBestUsers(char[][] mBestUserList) { for (int i = 0; i < 5; i++) { bestInfos[i] = heapPop(userHeap, userHeapSize); // strCpy(mBestUserList[i], users[bestInfos[i].objectIdx].name); mBestUserList[i] = users[bestInfos[i].objIdx].name; } for (int i = 0; i < 5; i++) { heapPush(userHeap, userHeapSize, bestInfos[i]); //userHeapSize++; } } }