Memory System (Prime Solution)

KIM ĐỨC
package MemorySystem;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;
// 1 HASHMAP int -> int
// 1 TreeSet

class UserSolution {
	// map điểm bắt đầu vùng ĐÃ ĐƯỢC LƯU TRỮ và kích cỡ của đoạn lưu trữ đó
	// start -> size
	Map<Integer, Integer> mapStorage;
	// lưu các Memory trống
	TreeSet<Memory> freeSpace;

	public void init(int N) {
		mapStorage = new HashMap<>();
		// định vị theo thứ tự, sắp xếp tăng dần theo start
		freeSpace = new TreeSet<>((a, b) -> a.start - b.start);
		freeSpace.add(new Memory(0, N));
	}

	// tìm freeSpace ngắn nhất >= mSize, nếu có hai đoạn bằng nhau, chọn đoạn có start nhỏ hơn
	// return -1 nếu không tìm thấy
	// nếu tìm thấy, return start của đoạn được allocated
	public int allocate(int mSize) {
		// cần clone freeSpace nhưng theo logic sort khác để sử dụng
		// do cần tìm theo size từ nhỏ đến lớn, thỏa mãn >= mSize
		TreeSet<Memory> sortedBlank = new TreeSet<>((a, b) -> a.size()
				- b.size());
		sortedBlank.addAll(freeSpace); // addAll dùng để clone

		// ceiling, higher, lower chỉ trả về 1 phần tử
		// headSet, tailSet, subSet trả về một SortedSet hoặc Set các phần tử

		// nếu size bằng nhau thì sortedBlank sắp xếp thế nào các phần tử theo start ??? sau khi được clone từ freeSpace
		//		TreeSet<Object> A = new TreeSet<>((a, b) -> a.property1 - b.property1);
		//		TreeSet<Object> B = new TreeSet<>((a, b) -> a.property2 - b.property2);
		//		B.addAll(A);
		//		Object o1 = B.ceiling(new Object(property2, 0, 0));
		//
		//		Nếu có 2 objects có property2 bằng nhau thì khi clone, B sẽ chỉ lấy một phần tử của A, chính là phần tử đầu tiên của A (bỏ qua các phần tử sau)
		//		mà cây A đang sắp xếp các đối tượng theo thứ tự tăng dần của property1 --> property1 nhỏ hơn đứng trước
		//		--> B sẽ chỉ add 1 phần tử property2 có property1 nhỏ nhất

		// tìm phần tử có size nhỏ nhất >= mSize, có start nhỏ nhất >= 0
		// thuộc tính start của thằng này là cái cần return
		Memory memory = sortedBlank.ceiling(new Memory(0, mSize));
		if (memory == null) {
			return -1;
		}
		mapStorage.put(memory.start, mSize); // đặt storage mSize vào freeSpace
		freeSpace.remove(memory);

		// memory được chia làm 2 đoạn, 
		// 1. đã full là Memory(memory.start, memory.start + mSize)
		// 2. free là Memory(memory.start + mSize, memory.end)
		if (mSize < memory.size()) {
			Memory remain = new Memory(memory.start + mSize, memory.end);
			freeSpace.add(remain);
		}
		return memory.start;
	}

	// ngoài chức năng release, return kích cỡ của vùng nhớ được release (ban đầu chỉ được cung cấp start)

	// mAddr là start của vùng lưu trữ đã full 
	// là key của mapStorage 
	// cần xác định vùng nhớ full --> xóa khỏi mapStorage --> thêm vào freeSpace
	// muốn thêm vào freeSpace --> cần định nghĩa Memory blank mới 
	// sau đó gộp với blank xung quang, mới thêm vào freeSpace

	// cần xác định biên của blank xung quanh 
	// dùng TreeSet freeSpace vì cây này lưu theo start tăng dần 
	// việc gộp freeSpace có thể được thực hiện bằng cách mẹo đơn giản là 
	// gán lại thuộc tính start và end --> nới rộng ra
	// lưu ý remove blank space cũ (chưa nới start, end) khỏi freeSpace, sau đó mới thêm lại blank đã gộp
	public int release(int mAddr) {
		if (!mapStorage.containsKey(mAddr)) {
			return -1;
		}
		int size = mapStorage.remove(mAddr);
		Memory memory = new Memory(mAddr, mAddr + size);
		// gộp freeSpace
		Memory front = freeSpace.lower(memory);
		Memory rear = freeSpace.higher(memory);
		// phải xét trường hợp != null vì có thể không tìm thấy lower hoặc higher so với memory
		if (front != null && front.end == mAddr) {
			freeSpace.remove(front);
			memory.start = front.start;
		}
		if (rear != null && rear.start == mAddr + size) {
			freeSpace.remove(rear);
			memory.end = rear.end;
		}
		freeSpace.add(memory);
		return size;
	}

	// Memory khởi tạo cho các blank space nên không cần thuộc tính boolean isFree
	class Memory {
		int start, end;

		Memory(int mStart, int mEnd) {
			start = mStart;
			end = mEnd;
		}

		int size() {
			return end - start;
			// return end - start + 1 sai ???
			// là vì khi khởi tạo đối tượng Memory bên trên, ta luôn khởi tạo theo công thức: (start, start + size)
		}
	}
}

//[Problem Description]
//There is a memory system. The whole size of memory is N and it has a consecutive unit of storage labeled with an address from 0 to N-1.
//The requested size of memory storage when allocating memory is given as the number of units of storage.
//A single empty space is when consecutive units of storage that were not allocated are grouped together.
//At first, nothing is allocated so there is one empty space whose size is N.  
//When allocating a memory space, it has to be consecutive and cannot be allocated by breaking it up into at least two blocks.
//Thus, in order to allocate the requested memory to a certain empty space,
//the size of the empty space must always be greater than or equal to the requested size. Best Fit Allocation is used for allocation.
//In other words, allocate memory to the smallest-sized empty space among the empty spaces that can be used for storage.
//If there are several smallest-sized empty spaces, allocate the memory to the one that comes first than any other empty spaces.
//When releasing a memory space, the value of starting address, which is the value of address at the very front of a memory space, is given.
//Then, change the memory space into an empty space. If there are empty spaces near it, merge them together.
//Implement allocation and release of memory that operates as mentioned above.
// 
//Implement each required function by referring to the following API description. 
//The following is the description of API to be written in the User Code.
//void init(int N)
//This function is called in the beginning of each test case.
//N, the whole size of memory, is given. They are all empty spaces.
// 
//Parameters
//  N : The size of memory ( 30 ≤ N ≤ 100,000,000 )
//int allocate(int mSize)
//This function requests the memory allocation whose size is mSize.
//Among empty spaces that can store memory, allocate memory to the smallest-sized empty space. Thus, use Best Fit Allocation. If there are several empty spaces whose size are the smallest, allocate memory to the empty space that comes first than any other empty spaces.
//If allocation is successful, return the value of starting address of the allocated memory space.
//If there is NO empty space that can be allocated, return -1.
// 
//Parameters
//  mSize: The size of memory for which allocation is requested ( 1 ≤ mSize ≤ N )
// 
//Returns
//  Return the value of starting address of the allocated memory space.
//  If the allocation fails, return -1.
//int release(int mAddr)
//This function requests the release of the memory whose value of starting address is mAddr.
//If the value of mAddr is not the value of starting address or if it is already an empty space, the release fails. Thus, return -1.
//If that is not the case, change the memory space into an empty space and when there are empty spaces near it, merge them together.
//In addition, return the size of the released memory space.
// 
//Parameters
//  mAddr: The memory address for which release is requested ( 0 ≤ mAddr ≤ N - 1 )
// 
//Returns
//  Return the size of the released memory space.
//  If the release fails, return -1.



package MemorySystem;

import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeSet;
// 1 HashMap int -> Node
// 1 TreeSet

class UserSolution2 {
	// cả HashMap và TreeSet đều được dùng để lưu các ô trống free space
	// mapLimit được dùng để lưu cả các ô full dữ liệu với thuộc tính isBlank = false
	// thuộc tính boolean blank là màng lọc 

	// hashMap start, end -> đối tượng memory --> ta có thể dùng cả start và end để xác định đối tượng
	// mà không cần quan tâm đó là start hay end, sau đó từ đối tượng xác định chính xác các thuộc tính
	// start, end và size
	HashMap<Integer, Memory> mapLimit = new HashMap<>();

	// TreeSet lưu Memory Blank theo thứ tự tăng dần của size, sau đó xét tới start
	TreeSet<Memory> treeBlank = new TreeSet<>(new AscSize());

	public void init(int N) {
		mapLimit.clear();
		treeBlank.clear();
		Memory memory = new Memory(0, N - 1, N);
		treeBlank.add(memory);
		mapLimit.put(memory.start, memory);
		mapLimit.put(memory.end, memory);
	}

	// giống cách 1
	// khác là ở C1, freeSpace lưu các blank chưa được sắp xếp theo size như mong muốn nên cần clone ra một TreeSet mới
	// ở cách này, treeBlank ngay từ đầu đã lưu các blank theo size nên ta ceiling để tìm vùng free thỏa mãn luôn

	// điểm khác biệt tiếp theo là ở cách này, HashMap chưa tối ưu khi đặt key vừa là start, end --> object Memory
	// điều này là không cần thiết, theo cách 1, chỉ cần start -> size là được
	public int allocate(int mSize) {
		Memory temp = new Memory(-1, 0, mSize); // khởi tạo --> blank
		Memory empty = treeBlank.ceiling(temp);
		if (empty == null) {
			return -1;
		}
		RemoveEmpty(empty); // xóa vùng trống 
		// 		int result = 0;
		// tận dụng temp để chuyển nó thành found free space
		temp.start = empty.start;
		temp.end = temp.start + mSize - 1;
		//		temp.size = mSize;   --> không cần thiết vì temp đã có size = mSize
		temp.isBlank = false;
		mapLimit.put(temp.start, temp);
		mapLimit.put(temp.end, temp);
		// 		result = temp.start;
		if (empty.size > mSize) {
			Memory newBlank = new Memory(empty.start + mSize, empty.end,
					empty.size - mSize); // khởi tạo --> isBlank = true --> ô trống
			mapLimit.put(newBlank.start, newBlank);
			mapLimit.put(newBlank.end, newBlank);
			treeBlank.add(newBlank);
		}
		return temp.start; // return empty.start;
		//		int result = -1;
		//		if (empty != null) {
		//			temp.start = empty.start;
		//			temp.end = temp.start + mSize - 1;
		//			temp.size = mSize;
		//			temp.isBlank = false;
		//			mapLimit.put(temp.start, temp);
		//			mapLimit.put(temp.end, temp);
		//			result = temp.start;
		//			if (empty.size > temp.size) {
		//				Memory newMemory = new Memory(empty.start + mSize, empty.end,
		//						empty.size - mSize);
		//				mapLimit.put(newMemory.start, newMemory);
		//				mapLimit.put(newMemory.end, newMemory);
		//				treeBlank.add(newMemory);
		//			}
		//		}
		//		return result;
	}

	public void RemoveEmpty(Memory empty) {
		treeBlank.remove(empty);
		mapLimit.remove(empty.start);
		mapLimit.remove(empty.end);

		//		if (empty != null) {
		//			treeBlank.remove(empty);
		//			mapLimit.remove(empty.start);
		//			mapLimit.remove(empty.end);
		//		}
	}

	// giống với cách 1, ta xác định vùng cần release và kiểm tra null
	// do mapLimit lưu cả vùng blank và ta cũng không chắc mAddr là start hay end do key của mapLimit là cả start, end
	// nên cần xét thêm 2 trường hợp, tuy nhiên nếu thiếu cũng không có vấn đề vì testcase sẽ đảm bảo mAddr là start của 1 ô allocated
	public int release(int mAddr) {
		Memory storage = mapLimit.get(mAddr);
		if (storage == null || storage.isBlank == true
				|| storage.start != mAddr) {
			return -1;
		}
		// mapLimit.remove(mAddr); // --> không cần thiết ??? 
		// đúng ra cần remove cả ở mapLimit mới đúng quy trình, nhưng nếu ta hiểu rằng
		// nếu storage không được mở rộng hoặc mở rộng về phía khác mAddr thì sẽ được cập nhật khi put
		// nếu storage mở rộng về 2 phía thì đúng quy trình cần xóa, nhưng có thể hiểu là blank space có nút mAddr đã bị ghi đè bởi blank space khác rộng hơn
		storage.isBlank = true;
		int result = storage.size;

		// phải xét cả trường hợp != null vì có thể key storage.start - 1 không tồn tại trong mapLimit
		Memory front = mapLimit.get(storage.start - 1);
		if (front != null && front.isBlank) {
			storage.start = front.start;
			storage.size += front.size;
			treeBlank.remove(front);
		}
		Memory rear = mapLimit.get(storage.end + 1);
		if (rear != null && rear.isBlank) {
			storage.end = rear.end;
			storage.size += rear.size;
			treeBlank.remove(rear);
		}
		// lưu ý là mapLimit ở C2 này quản lý cả free space nên phải add lại
		mapLimit.put(storage.start, storage);
		mapLimit.put(storage.end, storage);
		treeBlank.add(storage);
		return result;

		// return storage.size là sai vì nó sẽ trả về size sau khi đã gộp

		//		Memory temp = mapLimit.get(mAddr);
		//		int result = -1;
		//		if (temp != null && !temp.isBlank && temp.start == mAddr) {
		//			temp.isBlank = true;
		//			result = temp.size;
		//			Memory before = mapLimit.get(temp.start - 1);
		//			if (before != null && before.isBlank) {
		//				temp.start = before.start;
		//				temp.size += before.size;
		//				treeBlank.remove(before);
		//			}
		//			Memory after = mapLimit.get(temp.end + 1);
		//			if (after != null && after.isBlank) {
		//				temp.end = after.end;
		//				temp.size += after.size;
		//				treeBlank.remove(after);
		//			}
		//			mapLimit.put(temp.start, temp);
		//			mapLimit.put(temp.end, temp);
		//			treeBlank.add(temp);
		//		}
		//		return result;
	}

	// sắp xếp tăng dần theo size và start
	class AscSize implements Comparator<Memory> {
		public int compare(Memory n1, Memory n2) {
			if (n1.size == n2.size)
				return n1.start - n2.start;
			return n1.size - n2.size;
		}
	}

	// chỉ dùng được trong init(), nếu không, cần đặt đoạn code này lên trước nơi nó được dùng
	Comparator<Memory> AscSize = new Comparator<Memory>() {
		public int compare(Memory o1, Memory o2) {
			if (o1.size == o2.size) {
				return o1.start - o2.start;
			}
			return o1.size - o2.size;
		}
	};

	class Memory {
		int start;
		int end;
		int size;
		boolean isBlank;

		public Memory(int mStart, int mEnd, int mSize) {
			start = mStart;
			end = mEnd;
			// size = start - end + 1;  --> sai
			size = mSize;
			isBlank = true;
		}
	}
}