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++;
}
}
}