Untitled

mail@pastecode.io avatar
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++;
		}
	}

}