# HG changeset patch
# User misaka
# Date 1309933192 -32400
# Node ID a9cb12a7f995159a56ea089de79c56f8358b7163

hg init

diff -r 000000000000 -r a9cb12a7f995 src/search/LinearSearch.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/search/LinearSearch.java	Wed Jul 06 15:19:52 2011 +0900
@@ -0,0 +1,61 @@
+package search;
+
+public class LinearSearch
+{
+	public static void main(String args[])
+	{
+		LinearSearch table = new LinearSearch();
+		
+		table.add(1,"one");
+		table.add(10,"ten");
+		table.add(2,"two");
+		
+		String x = (String)table.search(10);
+		if(x != null){
+			System.out.println("value = "+x);
+		}else{
+			System.out.println("Not found");
+		}
+	}
+	
+	class Entry
+	{
+		int key;
+		Object data;
+		
+		public Entry(int key,Object data)
+		{
+			this.key = key;
+			this.data = data;
+		}
+	}
+		
+	final static int MAX = 100;
+	final Entry[] table = new Entry[MAX];
+	int n = 0;
+	
+	public void add(int key,Object data)
+	{
+		if(n >= MAX){
+			System.err.println("データの個数が多すぎます。");
+			return;
+		}
+		
+		table[n++] = new Entry(key,data);
+	}
+	
+	public Object search(int key)
+	{
+		int i;
+		
+		i = 0;
+		while(i < n){
+			if(table[i].key == key){
+				return (table[i].data);
+			}
+			i++;
+		}
+		
+		return null;
+	}
+}
diff -r 000000000000 -r a9cb12a7f995 src/test/MapBenchmark.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/MapBenchmark.java	Wed Jul 06 15:19:52 2011 +0900
@@ -0,0 +1,67 @@
+package test;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
+import tree.*;
+
+public class MapBenchmark
+{
+	public static void main(String args[]) throws InterruptedException
+	{
+		int num = 20000;
+		int threads = 5;
+		ExecutorService service = Executors.newFixedThreadPool(threads);
+		
+		Map<Integer,Integer> map = new SynchronizedMap<Integer,Integer>(new AVLTreeMap<Integer,Integer>());
+		//Map<Integer,Integer> map = Collections.synchronizedMap(new TreeMap<Integer,Integer>());
+		
+		
+		LinkedList<Integer> keys[] = new LinkedList[threads];
+		for(int i = 0;i < keys.length;i ++){
+			Random rnd = new Random();
+			keys[i] = new LinkedList<Integer>();
+			for(int j = 0;j < num;j ++){
+				keys[i].add(rnd.nextInt());
+			}
+		}
+		
+		Task<Integer> tasks[] = new Task[threads];
+		for(int i = 0;i < tasks.length;i ++){
+			tasks[i] = new Task<Integer>(keys[i],map);
+		}
+		
+		for(int i = 0;i < tasks.length;i ++){
+			service.execute(tasks[i]);
+		}
+		
+		service.shutdown();
+		service.awaitTermination(Long.MAX_VALUE,TimeUnit.DAYS);
+		
+		System.out.println("");
+	}
+	
+	public static class Task<K> implements Runnable
+	{
+		private Map<K,K> map;
+		private List<K> keys;
+		public Task(List<K> keys,Map<K,K> map)
+		{
+			this.keys = keys;
+			this.map = map;
+		}
+		
+		@Override
+		public void run()
+		{
+			long start = System.currentTimeMillis();
+			for(K key : keys){
+				map.put(key,key);
+			}
+			System.out.println(System.currentTimeMillis() - start);
+		}
+	}
+}
diff -r 000000000000 -r a9cb12a7f995 src/tree/AVLTreeMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/AVLTreeMap.java	Wed Jul 06 15:19:52 2011 +0900
@@ -0,0 +1,208 @@
+package tree;
+
+import java.util.LinkedList;
+import java.util.Random;
+
+public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V>
+{
+	private Node<K,V> root;
+	private final Node<K,V> NULL_NODE = new Node<K,V>(null,null,-1,-1,null,null);
+	
+	public static void main(String args[])
+	{
+		AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>();
+		
+		Random r = new Random();
+		LinkedList<Integer> keys = new LinkedList<Integer>();
+		for(int i = 0;i < 30000;i ++){
+			int num = r.nextInt();
+			keys.add(num);
+			map.put(num,Integer.toString(num));
+		}
+		
+		for(Integer key : keys){
+			String value = map.get(key);
+			if(!key.toString().equals(value)){
+				System.out.println("gehoge");
+			}
+		}
+		
+		System.out.println("hoge");
+	}
+	
+	public AVLTreeMap()
+	{
+		root = null;
+	}
+	
+	@Override
+	public void put(K key,V value)
+	{
+		if(root == null){
+			root = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
+			return;
+		}
+		
+		root = _put(root,key,value);
+	}
+	
+	public Node<K,V> _put(Node<K,V> cur,K key,V value)
+	{
+		int result = cur.key.compareTo(key);
+		
+		if(result < 0){
+			//right
+			if(cur.right == NULL_NODE){
+				cur.right = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
+				cur.rdepth = 1;
+				return cur;
+			}
+			
+			cur.right = _put(cur.right,key,value);
+			cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth);
+			int diff = cur.rdepth - cur.ldepth;
+			
+			if(diff > 1){
+				//一重回転か二重回転か判断する。
+				//以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
+				int rottype = result * cur.right.key.compareTo(key);
+				if(rottype > 0){
+					return singleRotate(cur,OP_RIGHT);
+				}else{
+					return doubleRotate(cur,OP_RIGHTLEFT);
+				}
+			}
+			
+		}else if(result > 0){
+			//left
+			if(cur.left == NULL_NODE){
+				cur.left = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
+				cur.ldepth = 1;
+				return cur;
+			}
+			
+			cur.left = _put(cur.left,key,value);
+			cur.ldepth = Math.max(cur.left.ldepth,cur.left.rdepth) + 1;
+			int diff = cur.ldepth - cur.rdepth;
+			
+			if(diff > 1){
+				//一重回転か二重回転か判断する。
+				//以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
+				int rottype = result * cur.left.key.compareTo(key);
+				if(rottype > 0){
+					return singleRotate(cur,OP_LEFT);
+				}else{
+					return doubleRotate(cur,OP_LEFTRIGHT);
+				}
+			}
+		}else{
+			//find
+			cur.value = value;
+		}
+		
+		return cur;
+	}
+	
+	private static final int OP_LEFT = 1;
+	private static final int OP_RIGHT = 2;
+	
+	public Node<K,V> singleRotate(Node<K,V> target,int type)
+	{
+		switch(type){
+			case OP_LEFT:
+				Node<K,V> left = target.left;
+				target.left = left.right;
+				left.right = target;
+				
+				target.ldepth = Math.max(target.left.rdepth,target.left.ldepth) + 1;
+				left.rdepth = Math.max(left.right.rdepth,left.right.ldepth) + 1;
+				return left;
+			case OP_RIGHT:
+				Node<K,V> right = target.right;
+				target.right = right.left;
+				right.left = target;
+				
+				target.rdepth = Math.max(target.right.rdepth,target.right.ldepth) + 1;
+				right.ldepth = Math.max(right.left.ldepth,right.left.rdepth) + 1;
+				return right;
+			default:
+				throw new IllegalArgumentException("invalid rotation type"); 
+		}
+	}
+	
+	private static final int OP_LEFTRIGHT = 1;
+	private static final int OP_RIGHTLEFT = 2;
+	
+	public Node<K,V> doubleRotate(Node<K,V> target,int type)
+	{
+		switch(type){
+			case OP_LEFTRIGHT:
+				target.left = singleRotate(target.left,OP_RIGHT);
+				return singleRotate(target,OP_LEFT);
+			case OP_RIGHTLEFT:
+				target.right = singleRotate(target.right,OP_LEFT);
+				return singleRotate(target,OP_RIGHT);
+			default:
+				throw new IllegalArgumentException("invalid rotation type.");
+		}
+	}
+	
+	@Override
+	public V get(K key)
+	{
+		Node<K,V> cur = root;
+		
+		while(cur != NULL_NODE){
+			int result = cur.key.compareTo(key);
+			if(result < 0){
+				cur = cur.right;
+			}else if(result > 0){
+				cur = cur.left;
+			}else{
+				//find
+				break;
+			}
+		}
+		
+		return cur.value;
+	}
+	
+	@Override
+	public V remove(K key)
+	{
+		
+	}
+	
+	private Node<K,V> _remove(K key)
+	{
+		
+	}
+	
+	private static class Node<K,V>
+	{
+		K key;
+		V value;
+		
+		Node<K,V> left;
+		Node<K,V> right;
+		
+		int ldepth;
+		int rdepth;
+		
+		public Node(K key,V value,int rdepth,int ldepth,Node<K,V> left,Node<K,V> right)
+		{
+			this.key = key;
+			this.value = value;
+			this.ldepth = ldepth;
+			this.rdepth = rdepth;
+			this.left = left;
+			this.right = right;
+		}
+		
+		@Override
+		public String toString()
+		{
+			return "[" + key + ":" + value + "]";
+		}
+	}
+}
diff -r 000000000000 -r a9cb12a7f995 src/tree/BTreeMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/BTreeMap.java	Wed Jul 06 15:19:52 2011 +0900
@@ -0,0 +1,84 @@
+package tree;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+
+public class BTreeMap<K extends Comparable<K>,V> implements Map<K,V> 
+{
+	private final int order;
+	
+	public BTreeMap(int order)
+	{
+		this.order = order;
+	}
+	
+	@Override
+	public void put(K _key, V _value)
+	{
+	}
+	
+	@Override
+	public V get(K _key)
+	{
+		return null;
+	}
+	
+	public V remove(K _key)
+	{
+		return null;
+	}
+	
+	private static abstract class Node<K extends Comparable<K>,V>
+	{
+		@Override
+		public abstract String toString();
+	}
+	
+	private class Link<K extends Comparable<K>,V>
+	{
+		public K key;
+		public Node<K,V> node;
+		
+		public Link(K key,Node<K,V> node)
+		{
+			this.key = key;
+			this.node = node;
+		}
+	}
+	
+	private class Bucket<K extends Comparable<K>,V> extends Node<K,V>
+	{
+		private final int order;
+		private ArrayList<Link<K,V>> children;
+		
+		public Bucket(int order)
+		{
+			this.order = order;
+			children = new ArrayList<Link<K,V>>(this.order+2);
+		}
+		
+		@Override
+		public String toString()
+		{
+			return "bucket";
+		}
+	}
+	
+	private class Leaf<K extends Comparable<K>,V> extends Node<K,V>
+	{
+		public K key;
+		public V value;
+		
+		public Leaf(K key,V value)
+		{
+			this.key = key;
+			this.value = value;
+		}
+		
+		@Override
+		public String toString()
+		{
+			return String.format("key = %s , value = %s",key,value);
+		}
+	}
+}
diff -r 000000000000 -r a9cb12a7f995 src/tree/Map.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/Map.java	Wed Jul 06 15:19:52 2011 +0900
@@ -0,0 +1,7 @@
+package tree;
+
+public interface Map<K,V>
+{
+	public void put(K _key,V _value);
+	public V get(K _key);
+}
diff -r 000000000000 -r a9cb12a7f995 src/tree/SynchronizedMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/SynchronizedMap.java	Wed Jul 06 15:19:52 2011 +0900
@@ -0,0 +1,24 @@
+package tree;
+
+public class SynchronizedMap<K,V> implements Map<K,V>
+{
+	private Map<K,V> map;
+	
+	public SynchronizedMap(Map<K,V> map)
+	{
+		this.map = map;
+	}
+
+	@Override
+	public synchronized void put(K _key, V _value)
+	{
+		map.put(_key, _value);
+	}
+
+	@Override
+	public synchronized V get(K _key)
+	{
+		return map.get(_key);
+	}
+
+}