# HG changeset patch
# User sugi
# Date 1354174116 -32400
# Node ID 98a1292ae8ef73bba5eee405d4220d19a450b2e2
# Parent  206c7dd9cb484812a9d93c1fbc4b1e66e99dcccc
add merge sort

diff -r 206c7dd9cb48 -r 98a1292ae8ef src/alice/test/topology/mergesort/LocalMergeSort.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/topology/mergesort/LocalMergeSort.java	Thu Nov 29 16:28:36 2012 +0900
@@ -0,0 +1,8 @@
+package alice.test.topology.mergesort;
+
+public class LocalMergeSort {
+	public static void main(String[] args){
+		SortConfig conf = new SortConfig(args);
+		new StartSort(conf).execute();
+	}
+}
diff -r 206c7dd9cb48 -r 98a1292ae8ef src/alice/test/topology/mergesort/MergeArray.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/topology/mergesort/MergeArray.java	Thu Nov 29 16:28:36 2012 +0900
@@ -0,0 +1,74 @@
+package alice.test.topology.mergesort;
+
+import java.util.List;
+
+import org.msgpack.type.Value;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class MergeArray extends CodeSegment{
+	
+	private Receiver info1 = ids.create(CommandType.TAKE);
+	private Receiver info2 = ids.create(CommandType.TAKE);
+
+	int keyNum1;
+	int keyNum2;
+	
+	public MergeArray(int num1, int num2) {
+		keyNum1 = num1;
+		keyNum2 = num2;
+		String key1 = Integer.toString(num1);
+		String key2 = Integer.toString(num2);
+		info1.setKey("local", key1, 1);
+		info2.setKey("local", key2, 1);
+		
+	}
+
+	@Override
+	public void run() {
+		List<Value> list1 = info1.asArray();
+		List<Value> list2 = info2.asArray();
+
+		//System.out.println(list1);
+		//System.out.println(list2);
+		
+		int length = list1.size() + list2.size();
+		int[] array = new int[length];
+		
+		for (int i=0,k=0,j=0;i<length;i++){
+			int array1 = list1.get(j).asIntegerValue().getInt();
+			int array2 = list2.get(k).asIntegerValue().getInt();
+			
+			if (array1<=array2){
+				array[i]=array1;
+				j++;
+				if (j == list1.size()){
+					for (i=i+1;i<length/*&&k!=list2.size()*/;i++,k++){
+						array[i]=list2.get(k).asIntegerValue().getInt();
+					}
+					break;
+				}
+			} else if (array1>array2){
+				array[i]=array2;
+				k++;
+				if (k == list2.size()){
+					for (i=i+1;i<length/*&&j!=list1.size()*/;i++,j++){
+						array[i]=list1.get(j).asIntegerValue().getInt();
+					}
+					break;
+				}
+			}
+		}
+		/*
+		for (int i = 0;i<length;i++){
+			System.out.println(array[i]);
+		}
+		*/
+		int num = (keyNum1-1)/2;
+		String key = Integer.toString(num);
+		
+		ods.put("local", key, array);
+	}
+}
diff -r 206c7dd9cb48 -r 98a1292ae8ef src/alice/test/topology/mergesort/SeparateArray.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/topology/mergesort/SeparateArray.java	Thu Nov 29 16:28:36 2012 +0900
@@ -0,0 +1,61 @@
+package alice.test.topology.mergesort;
+
+import java.util.List;
+
+import org.msgpack.type.Value;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class SeparateArray extends CodeSegment{
+
+	private Receiver info = ids.create(CommandType.TAKE);
+	int keyNum;
+	
+	public SeparateArray(int keyNum) {
+		this.keyNum = keyNum;
+		String key = Integer.toString(keyNum);
+		info.setKey("local", key);
+	}
+	@Override
+	public void run() {
+		List<Value> list = info.asArray();
+		//System.out.println(list);
+		if (list.size() > 2){
+			int num = 2*keyNum + 1;
+			int length = list.size()/2;
+			int[] array1 = new int[length];
+			int[] array2 = new int[length];
+			for (int i = 0;i<length;i++){
+				array1[i] = list.get(i).asIntegerValue().getInt();
+				array2[i] = list.get(i+length).asIntegerValue().getInt();
+			}
+			
+			String key1 = Integer.toString(num);
+			String key2 = Integer.toString(num+1);
+
+			ods.put("local", key1, array1);
+			ods.put("local", key2, array2);			
+			
+			new SeparateArray(num);
+			new SeparateArray(num+1);
+			new MergeArray(num,num+1);
+		} else {
+			String key = Integer.toString(keyNum);
+			int array[] = new int[2];
+			int array1 = list.get(0).asIntegerValue().getInt();
+			int array2 = list.get(1).asIntegerValue().getInt();
+			if (array1<=array2){
+				array[0] = array1;
+				array[1] = array2;
+				ods.put("local",key, array);
+			} else {
+				array[0] = array2;
+				array[1] = array1;			
+				ods.put("local",key, array);
+			}
+		}
+	}
+
+}
diff -r 206c7dd9cb48 -r 98a1292ae8ef src/alice/test/topology/mergesort/ShowResult.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/topology/mergesort/ShowResult.java	Thu Nov 29 16:28:36 2012 +0900
@@ -0,0 +1,37 @@
+package alice.test.topology.mergesort;
+
+import java.util.List;
+
+import org.msgpack.type.Value;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class ShowResult extends CodeSegment{
+
+	private Receiver info = ids.create(CommandType.PEEK);
+	int keyNum;
+	public ShowResult(int keyNum) {
+		this.keyNum = keyNum;
+		String key = Integer.toString(keyNum);
+		info.setKey("local", key, 1);
+		
+	}
+
+	@Override
+	public void run() {
+		System.out.println(System.currentTimeMillis() - StartSort.t +"ms");
+		List<Value> list = info.asArray();
+		for (int i =0; i+1< list.size();i++){
+			if (list.get(i).asIntegerValue().getInt()>list.get(i+1).asIntegerValue().getInt()){
+				System.out.println("MISS");
+				System.exit(0);
+			}
+			//System.out.println(list.get(i).asIntegerValue().getInt()+",");
+		}
+		//System.out.println(list);
+		System.exit(0);
+	}
+
+}
diff -r 206c7dd9cb48 -r 98a1292ae8ef src/alice/test/topology/mergesort/SortConfig.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/topology/mergesort/SortConfig.java	Thu Nov 29 16:28:36 2012 +0900
@@ -0,0 +1,18 @@
+package alice.test.topology.mergesort;
+
+
+
+public class SortConfig {
+	int size;
+	boolean flag;
+	public SortConfig(String[] args){
+		for (int i=0;i<args.length; i++){
+			if ("-size".equals(args[i])){
+				size = Integer.parseInt(args[++i]);	
+			} else if ("-show".equals(args[i])){
+				flag = true;	
+			}
+		}
+	}
+
+}
diff -r 206c7dd9cb48 -r 98a1292ae8ef src/alice/test/topology/mergesort/StartSort.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/topology/mergesort/StartSort.java	Thu Nov 29 16:28:36 2012 +0900
@@ -0,0 +1,38 @@
+package alice.test.topology.mergesort;
+
+import java.io.IOException;
+import java.util.Random;
+
+import alice.codesegment.CodeSegment;
+import alice.codesegment.SingletonMessage;
+
+public class StartSort extends CodeSegment{
+	public static long t = System.currentTimeMillis();
+	SortConfig conf;
+	public StartSort(SortConfig conf){
+		this.conf = conf;
+	}
+	
+	@Override
+	public void run() {
+		int size = conf.size;
+		int[] array = new int[size];
+		for (int i=0;i< size; i++){
+			Random rnd = new Random();
+			array[i] = rnd.nextInt(Integer.MAX_VALUE);
+		}
+		if (conf.flag){
+			try {
+				System.out.println(SingletonMessage.getInstance().unconvert(array));
+			} catch (IOException e) {
+				e.printStackTrace();
+			}
+		}
+		String key = Integer.toString(0);
+		ods.put("local", key, array);
+	
+		new SeparateArray(0);
+		new ShowResult(0);
+	}
+
+}