# HG changeset patch
# User sugi
# Date 1355135799 -32400
# Node ID 0979827c859b0ebf451bfba9c999f8d51f9e8799
# Parent  d6afa779dd49ed0dd3e113f8d2c20f7a252678c9
Add bitonic sort. But  can not execute.

diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/DataInfo.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/DataInfo.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,16 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import org.msgpack.annotation.Message;
+
+@Message
+public class DataInfo {
+	public int index;
+	public int ptr;
+	
+	public DataInfo(){}
+	
+	public DataInfo(int _index, int _ptr){
+		index = _index;
+		ptr = _ptr;
+	}
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/DataList.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/DataList.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,29 @@
+package alice.test.codesegment.local.bitonicsort;
+
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+
+import org.msgpack.annotation.Message;
+
+@Message
+public class DataList {
+
+	List<Integer> table = new LinkedList<Integer>();
+	public DataList(){};
+	public DataList(List<Integer> numbers){
+		table = numbers;
+	};
+	
+	public DataList getSubList(int start, int size){
+		List<Integer> table2 = new LinkedList<Integer>();
+		ListIterator<Integer> iter = table.listIterator(start);
+		for (int i=start;i<(start+size);i++){
+			table2.add(iter.next());
+		}
+		//System.out.println(table2);
+		return new DataList(table2);
+	}
+	
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/LocalBitonicSort.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/LocalBitonicSort.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,8 @@
+package alice.test.codesegment.local.bitonicsort;
+
+public class LocalBitonicSort {
+	public static void main(String[] args){
+		SortConfig conf = new SortConfig(args);
+		new SetInfo(conf).execute();
+	}
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/MakeData.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,32 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import java.util.Random;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class MakeData extends CodeSegment {
+	
+	private Receiver info1 = ids.create(CommandType.PEEK);
+	private Receiver info2 = ids.create(CommandType.TAKE);
+
+	public MakeData(){
+		info1.setKey("local", "sortconf");
+		info2.setKey("local", "data");
+	}
+	
+	@Override
+	public void run() {
+		SortConfig conf = info1.asClass(SortConfig.class);
+		DataList list = info2.asClass(DataList.class);
+		int size = conf.getLength();
+		for (int i = 0;i<size;i++){
+			Random rnd = new Random();
+			//DataInfo info = new DataInfo(rnd.nextInt(Integer.MAX_VALUE),i);
+			list.table.add(rnd.nextInt(Integer.MAX_VALUE));
+		}
+		
+		ods.update("local", "list", list);
+	}
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/SetInfo.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/SetInfo.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,22 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import alice.codesegment.CodeSegment;
+
+public class SetInfo extends CodeSegment {
+
+	private SortConfig conf;
+	public SetInfo(SortConfig conf) {
+		this.conf = conf;
+	}
+
+	@Override
+	public void run() {
+		ods.put("local", "sortconf", conf);
+		ods.put("local", "data", new DataList());
+		
+		new MakeData();
+		new SetTask();
+	}
+
+	
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/SetTask.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,42 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class SetTask extends CodeSegment {
+	
+	private Receiver info1 = ids.create(CommandType.PEEK);
+	private Receiver info2 = ids.create(CommandType.PEEK);
+	
+	SetTask(){
+		info1.setKey("local","sortconf");
+		info2.setKey("local","list");
+	}
+	
+	@Override
+	public void run() {
+		SortConfig conf = info1.asClass(SortConfig.class);
+		DataList list = info2.asClass(DataList.class);
+		System.out.println(list.table);
+		
+		int half_num = conf.getSplitNum() - 1; 
+		int sort_count = conf.getSplitNum(); // sort完了に必要な回数
+		int block_num = (conf.getLength() + half_num ) / sort_count; // 1つのタスクでsortするdata数
+		int last_block_num = conf.getLength() - (conf.getSplitNum() - 1)*block_num;
+		{
+			String key = "array";
+			int i = 0;
+			for (i = 0;i< conf.getSplitNum()-1; i++){
+				ods.update("local", key+i, list.getSubList(i*block_num, block_num));
+				new Sort(key+i);
+			}
+			// 最後のblockは端数
+			ods.update("local", key+i, list.getSubList(i*block_num, last_block_num));
+			new Sort(key+i);
+		}
+		ods.update("local", "count", sort_count-1);
+		
+	}
+
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/Sort.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,66 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import java.util.LinkedList;
+import java.util.List;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class Sort extends CodeSegment{
+	private Receiver info1 = ids.create(CommandType.PEEK);
+	String key;
+	
+	public Sort(String key){
+		info1.setKey("local",key);
+		
+	}
+	
+	@Override
+	public void run() {
+		DataList list = info1.asClass(DataList.class);
+		if (list.table.size()<2) {ods.update("local",key,list);}
+		list.table = quickSort(list.table);
+		System.out.println(list.table);
+		//System.exit(0);
+		
+	}
+	
+	public List<Integer> quickSort(List<Integer> numbers){
+		if (numbers.size() < 1) 
+			return numbers;
+		/*if (numbers.size() < 400){ 
+			return bubbleSort(numbers);
+			
+		} */
+		int pivot = numbers.size() / 2;
+		List<Integer> lesser = new LinkedList<Integer>();
+		List<Integer> greater = new LinkedList<Integer>();
+		int sameAsPivot = 0;
+		
+		for (int number : numbers){
+			if (number>numbers.get(pivot))
+				greater.add(number);
+			else if (number < numbers.get(pivot))
+				lesser.add(number);
+			else
+				sameAsPivot++;
+		}
+		// size check bubble < quick
+		lesser = quickSort(lesser);
+		greater = quickSort(greater);
+		List<Integer> sorted = new LinkedList<Integer>();
+		for (int number: lesser)
+			sorted.add(number);
+		for (int i=0;i< sameAsPivot;i++)
+			sorted.add(numbers.get(pivot));
+		for (int number: greater)
+			sorted.add(number);
+		return sorted;
+	}
+	
+	public List<Integer> bubbleSort(List<Integer> numbers){
+		List<Integer> sorted = new LinkedList<Integer>();
+		return sorted;
+	}
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/bitonicsort/SortConfig.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/SortConfig.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,38 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import org.msgpack.annotation.Message;
+
+@Message
+public class SortConfig {
+	public int length = 1200;
+	public int MAX_BLOCK_SIZE = 1024;
+	public int cpu = 1;
+	
+	public SortConfig(){}
+	
+	public SortConfig(String[] args){
+		for (int i=0;i<args.length; i++){
+			if ("-l".equals(args[i])){
+				length = Integer.parseInt(args[++i]);	
+			} else if ("-b".equals(args[i])){
+				MAX_BLOCK_SIZE = Integer.parseInt(args[++i]);	
+			}
+		}
+	}
+
+	public int getLength() {
+		return length;
+	}
+
+	public int getblockSize() {
+		return MAX_BLOCK_SIZE;
+	}
+	
+	public int getSplitNum(){
+		if (length / cpu < MAX_BLOCK_SIZE){
+			return cpu;
+		} else {
+			return (length + MAX_BLOCK_SIZE -1) / MAX_BLOCK_SIZE;
+		}
+	}
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/mergesort/LocalMergeSort.java
--- a/src/alice/test/codesegment/local/mergesort/LocalMergeSort.java	Tue Dec 04 15:58:09 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/LocalMergeSort.java	Mon Dec 10 19:36:39 2012 +0900
@@ -3,6 +3,6 @@
 public class LocalMergeSort {
 	public static void main(String[] args){
 		SortConfig conf = new SortConfig(args);
-		new StartSort(conf).execute();
+		new SortStart(conf).execute();
 	}
 }
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/mergesort/ShowResult.java
--- a/src/alice/test/codesegment/local/mergesort/ShowResult.java	Tue Dec 04 15:58:09 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/ShowResult.java	Mon Dec 10 19:36:39 2012 +0900
@@ -21,7 +21,7 @@
 
 	@Override
 	public void run() {
-		System.out.println(System.currentTimeMillis() - StartSort.t);
+		System.out.println(System.currentTimeMillis() - SortStart.t);
 		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()){
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/mergesort/SortStart.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/mergesort/SortStart.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,39 @@
+package alice.test.codesegment.local.mergesort;
+
+import java.io.IOException;
+import java.util.Random;
+
+import alice.codesegment.CodeSegment;
+import alice.codesegment.SingletonMessage;
+
+public class SortStart extends CodeSegment{
+	public static long t;
+	SortConfig conf;
+	public SortStart(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);
+		t = System.currentTimeMillis();
+	}
+
+}
diff -r d6afa779dd49 -r 0979827c859b src/alice/test/codesegment/local/mergesort/StartSort.java
--- a/src/alice/test/codesegment/local/mergesort/StartSort.java	Tue Dec 04 15:58:09 2012 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-package alice.test.codesegment.local.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;
-	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);
-		t = System.currentTimeMillis();
-	}
-
-}