# HG changeset patch
# User Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
# Date 1312856016 -32400
# Node ID 15920e9b562d6a8d401b756b6d9cfd6ed02881ab
# Parent  a9cb12a7f995159a56ea089de79c56f8358b7163
added MulticastQueue.java the BlockingMulticastQueue

diff -r a9cb12a7f995 -r 15920e9b562d src/queue/MulticastQueue.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/queue/MulticastQueue.java	Tue Aug 09 11:13:36 2011 +0900
@@ -0,0 +1,129 @@
+package queue;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.concurrent.CountDownLatch;
+
+public class MulticastQueue<T>
+{
+	public static void main(String args[]) throws IOException
+	{
+		int threads = 5;
+		final MulticastQueue<String> queue = new MulticastQueue<String>();
+		
+		Runnable type2 = new Runnable(){
+
+			@Override
+			public void run()
+			{
+				Client<String> client = queue.newClient();
+				
+				for(;;){
+					String str = client.poll();
+					try {
+						Thread.sleep(10000);
+					} catch (InterruptedException e) {
+						// TODO Auto-generated catch block
+						e.printStackTrace();
+					}
+					System.out.println(Thread.currentThread().getName()+":"+str);
+				}
+			}
+		};
+		
+		Runnable thread = new Runnable(){
+
+			@Override
+			public void run()
+			{
+				Client<String> client = queue.newClient();
+				
+				for(;;){
+					String str = client.poll();
+					System.out.println(Thread.currentThread().getName()+":"+str);
+				}
+			}
+		};
+		
+		for(int i = 0;i < threads;i ++){
+			new Thread(thread).start();
+		}
+		new Thread(type2).start();
+		
+		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+		for(;;){
+			String str = br.readLine();
+			queue.put(str);
+		}
+	}
+	
+	
+	Node<T> tail;
+	
+	public MulticastQueue()
+	{
+		tail = new Node<T>(null);
+	}
+	
+	public synchronized void put(T item)
+	{
+		Node<T> next = new Node<T>(item);
+		tail.set(next);
+		tail = next;
+	}
+	
+	public Client<T> newClient()
+	{
+		return new Client<T>(tail);
+	}
+	
+	static class Client<T>
+	{
+		Node<T> node;
+		
+		Client(Node<T> tail)
+		{
+			node = tail;
+		}
+		
+		public T poll()
+		{
+			Node<T> next = null;
+			
+			try {
+				next = node.next();
+			}catch(InterruptedException _e){
+				_e.printStackTrace();
+			}
+			node = next;
+			return next.item;
+		}
+	}
+	
+	private static class Node<T>
+	{
+		private T item;
+		private Node<T> next;
+		private CountDownLatch latch;
+		
+		public Node(T item)
+		{
+			this.item = item;
+			this.next = null;
+			latch = new CountDownLatch(1);
+		}
+		
+		public void set(Node<T> next)
+		{
+			this.next = next;
+			latch.countDown();
+		}
+		
+		public Node<T> next() throws InterruptedException
+		{
+			latch.await();
+			return next;
+		}
+	}
+}
diff -r a9cb12a7f995 -r 15920e9b562d src/search/LinearSearch.java
--- a/src/search/LinearSearch.java	Wed Jul 06 15:19:52 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,61 +0,0 @@
-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 a9cb12a7f995 -r 15920e9b562d src/test/MapBenchmark.java
--- a/src/test/MapBenchmark.java	Wed Jul 06 15:19:52 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,67 +0,0 @@
-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 a9cb12a7f995 -r 15920e9b562d src/tree/AVLTreeMap.java
--- a/src/tree/AVLTreeMap.java	Wed Jul 06 15:19:52 2011 +0900
+++ b/src/tree/AVLTreeMap.java	Tue Aug 09 11:13:36 2011 +0900
@@ -1,8 +1,5 @@
 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;
@@ -12,22 +9,11 @@
 	{
 		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");
+		map.put(10,"10");
+		map.put(20,"20");
+		map.put(30,"20");
+		map.put(5,"5");
+		map.put(7,"7");
 	}
 	
 	public AVLTreeMap()
@@ -59,7 +45,7 @@
 			}
 			
 			cur.right = _put(cur.right,key,value);
-			cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth);
+			cur.rdepth = Math.max(cur.right.ldepth,cur.right.rdepth) + 1;
 			int diff = cur.rdepth - cur.ldepth;
 			
 			if(diff > 1){
@@ -72,7 +58,6 @@
 					return doubleRotate(cur,OP_RIGHTLEFT);
 				}
 			}
-			
 		}else if(result > 0){
 			//left
 			if(cur.left == NULL_NODE){
@@ -103,6 +88,130 @@
 		return cur;
 	}
 	
+	public V remove(K key)
+	{
+		RemoveResult<K,V> r = findRemoveTarget(root,key);
+		root = r.cur;
+		return r.target.value;
+	}
+	
+	private RemoveResult<K,V> findRemoveTarget(Node<K,V> cur,K key)
+	{
+		int result = cur.key.compareTo(key);
+		if(result < 0){
+			//right
+			if(cur == NULL_NODE){
+				return new RemoveResult<K,V>(cur,NULL_NODE);
+			}
+			
+			RemoveResult<K,V> r = findRemoveTarget(cur.right,key);
+			cur.right = r.cur;
+			cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
+			
+			int diff = cur.rdepth - cur.ldepth;
+			if(diff > 1){
+				int rottype = result * cur.right.key.compareTo(key);
+				if(rottype > 0){
+					r.cur = singleRotate(cur,OP_RIGHT);
+					return r;
+				}else{
+					r.cur = doubleRotate(cur,OP_RIGHTLEFT);
+					return r;
+				}
+			}
+			
+			r.cur = cur;
+			return r;
+		}else if(result > 0 ){
+			//left
+			if(cur == NULL_NODE){
+				return new RemoveResult<K,V>(cur,NULL_NODE);
+			}
+			
+			RemoveResult<K,V> r = findRemoveTarget(cur.left,key);
+			cur.left = r.cur;
+			cur.ldepth = Math.max(cur.left.rdepth,cur.left.ldepth) + 1;
+			
+			int diff = cur.rdepth - cur.ldepth;
+			if(diff > 1){
+				int rottype = result * cur.left.key.compareTo(key);
+				if(rottype > 0){
+					r.cur = singleRotate(cur,OP_LEFT);
+					return r;
+				}else{
+					r.cur = doubleRotate(cur,OP_LEFTRIGHT);
+					return r;
+				}
+			}
+			
+			r.cur = cur;
+			return r;
+		}else{
+			//find
+			if(cur.left == NULL_NODE && cur.right == NULL_NODE){
+				//delete
+				return new RemoveResult<K,V>(NULL_NODE,cur);
+			}
+			
+			if(cur.left != NULL_NODE && cur.right == NULL_NODE){
+				//replace left
+				return new RemoveResult<K,V>(cur.left,cur);
+			}
+			
+			if(cur.left == NULL_NODE && cur.right != NULL_NODE){
+				//replace right
+				return new RemoveResult<K,V>(cur.right,cur);
+			}
+			
+			//both nodes are not null
+			RemoveResult<K,V> r = findSubstituteNode(cur.left);
+			cur.key = r.target.key;
+			cur.value = r.target.value;
+			cur.right = r.cur;
+			cur.rdepth = Math.max(cur.ldepth,cur.rdepth) + 1;
+			
+			int diff = cur.rdepth - cur.ldepth;
+			if(diff > 1){
+				r.cur = doubleRotate(cur,OP_LEFTRIGHT);
+			}
+			
+			return r;
+		}
+	}
+	
+	private RemoveResult<K,V> findSubstituteNode(Node<K,V> cur)
+	{
+		if(cur.right != NULL_NODE){
+			RemoveResult<K,V> result = findSubstituteNode(cur.right);
+			cur.right = result.cur;
+			cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
+			
+			int diff = cur.ldepth - cur.rdepth;
+			if(diff > 1){
+				result.cur = singleRotate(cur.left,OP_LEFT);
+				return result;
+			}
+			
+			result.cur = cur;
+			return result;
+		}
+		
+		RemoveResult<K,V> result = new RemoveResult<K,V>(cur.left,cur);
+		return result;
+	}
+	
+	private static class RemoveResult<K,V>
+	{
+		Node<K,V> cur;
+		Node<K,V> target;
+		
+		public RemoveResult(Node<K,V> cur,Node<K,V> target)
+		{
+			this.cur = cur;
+			this.target = target;
+		}
+	}
+	
 	private static final int OP_LEFT = 1;
 	private static final int OP_RIGHT = 2;
 	
@@ -167,36 +276,25 @@
 		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;
 		
+		int rdepth;
+		int ldepth;
+		
 		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.right = right;
+			this.left = left;
+			this.ldepth = ldepth;
+			this.rdepth = rdepth;
 			this.key = key;
 			this.value = value;
-			this.ldepth = ldepth;
-			this.rdepth = rdepth;
-			this.left = left;
-			this.right = right;
 		}
 		
 		@Override
diff -r a9cb12a7f995 -r 15920e9b562d src/tree/BTreeMap.java
--- a/src/tree/BTreeMap.java	Wed Jul 06 15:19:52 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,84 +0,0 @@
-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);
-		}
-	}
-}