/**
 * Divide a big queue into memory sortable sub-queues, sort these sub-queues in turn, and 
 * return a queue with all sorted sub-queues.
 * 
 * This method is thread safe.
 * 
 * @param bigQueue the big queue to be sorted
 * @param maxInMemSortNumOfItems max number of items that can be sorted in memory in one pass
 * @param queueOfSortedQueues queue of sorted sub-queues
 * @throws IOException exception thrown if there is IO error during queue making operation.
 */
public static void makeQueueOfSortedQueues(IBigQueue bigQueue, int maxInMemSortNumOfItems, Queue<IBigQueue> queueOfSortedQueues) throws IOException {
	List<String> list = new ArrayList<String>();
	
	while(true) {
		// continously extract items from big queue
		byte[] data = bigQueue.dequeue();
		if (data != null) {
			list.add(new String(data));
		}
		// if we get max number of items sortable in memory, then sort them and make a sub-queue
		if (list.size() == maxInMemSortNumOfItems || data == null) {
			long begin = System.currentTimeMillis();
			String[] stringArray = list.toArray(new String[0]);
			if (stringArray.length == 0) break;
			// sort in memory
			inMemSort(stringArray);
			String newQueueName = getNextTempQueueName();
			IBigQueue newBigQueue = new BigQueueImpl(SAMPLE_DIR, newQueueName);
			// make sorted sub-queue
			for(String item : stringArray) {
				newBigQueue.enqueue(item.getBytes());
			}
			// put the sub-queue into output queue
			queueOfSortedQueues.offer(newBigQueue);
			newBigQueue.close();
			
			if (data == null) break;
			list.clear();
			long end = System.currentTimeMillis();
			output("Time used to make one sorted queue " + (end - begin) + " ms, maxInMemSortNumOfItems = " + maxInMemSortNumOfItems);
		}
	}
}
 

@Before
public void setup() throws IOException {
    String queueDir = System.getProperty("user.home");
    String queueName = "baeldung-queue";
    bigQueue = new BigQueueImpl(queueDir, queueName);
}
 

static void mergeSort() throws IOException {
	MergeSortHelper.output("Single thread sort begin ...");
	MergeSortHelper.output("Generating random big queue ...");
	IBigQueue srcBigQueue = new BigQueueImpl(MergeSortHelper.SAMPLE_DIR, "srcq");
	MergeSortHelper.populateBigQueue(srcBigQueue, maxNumOfItems, itemSize);
	
	long start = System.currentTimeMillis();
	MergeSortHelper.output("Making queue of sorted queues ...");
	Queue<IBigQueue> queueOfSortedQueues = new LinkedList<IBigQueue>();
	MergeSortHelper.makeQueueOfSortedQueues(srcBigQueue, maxInMemSortNumOfItems, queueOfSortedQueues);
	// have done with source queue, empty it and delete back data files to save disk space
	srcBigQueue.removeAll();
	srcBigQueue.close();
	
	MergeSortHelper.output("Merging and sorting the queues ...");
	MergeSortHelper.mergeSort(queueOfSortedQueues, maxMergeSortWays);
	long end = System.currentTimeMillis();
	MergeSortHelper.output("Mergesort finished.");
	
	MergeSortHelper.output("Time used to sort " + maxNumOfItems + " string items is " + (end - start) + "ms");
	MergeSortHelper.output("Item size each is " + itemSize + " bytes");
	MergeSortHelper.output("Total size sorted " + (long)(maxNumOfItems * itemSize) / (1024 * 1024) + "MB");
	
	IBigQueue targetSortedQueue = queueOfSortedQueues.poll(); // last and only one is the target sorted queue
	
	MergeSortHelper.output("Validation begin ....");
	long targetSize = targetSortedQueue.size();
	if(targetSize != maxNumOfItems) {
   		System.err.println("target queue size is not correct!, target queue size is " + targetSize + " expected queue size is " + maxNumOfItems);
	}
	
	// first sorted item
	String previousItem = new String(targetSortedQueue.dequeue());
	
	// put sorted items in a big array so we can binary search it later
	// validate the sorted queue at the same time
	IBigArray bigArray = new BigArrayImpl(MergeSortHelper.SAMPLE_DIR, "sample_array");
	bigArray.append(previousItem.getBytes());
	for(int i = 1; i < targetSize; i++) {
		String item = new String(targetSortedQueue.dequeue());
		if (item.compareTo(previousItem) < 0) {
			System.err.println("target queue is not in sorted order!");
		}
		bigArray.append(item.getBytes());
		previousItem = item;
	}
	MergeSortHelper.output("Validation finished.");
	
	// have done with target sorted queue, empty it and delete back data files to save disk space
	targetSortedQueue.removeAll();
	targetSortedQueue.close();
	
	bigArray.close();
}