package rw;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.concurrent.CyclicBarrier;

import org.junit.Assert;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.Timeout;

public class RedBlackTreeTest 
{
	final static int TIMEOUT = 1000;

	@Rule
	public Timeout globalTimeout = new Timeout(TIMEOUT);

	@Test
	public void testSequential() 
	{
		final int MAX = 100;
		final int NUMBER = 1000;

		final RedBlackTree<Integer> tree = new RedBlackTree<Integer>();
		final Random random = new Random(System.currentTimeMillis());
		final HashSet<Integer> set = new HashSet<Integer>();

		try
		{
			for (int i = 0; i < NUMBER; i ++)
			{
				tree.isValid();
				int element = random.nextInt(MAX);
				Assert.assertEquals(tree.toString(), tree.contains(element), set.contains(element));
				Assert.assertEquals(tree.toString(), tree.add(element), set.add(element));
			}
		}
		catch (RuntimeException e)
		{
			Assert.fail(e.getMessage());
		}
	}

	@Test
	public void testBlockingContains() 
	{
		final RedBlackTree<Integer> tree = new RedBlackTree<Integer>();

		tree.writeLock();

		final Thread container = new Thread() 
		{
			public void run()
			{
				tree.contains(0);
				Assert.fail("contains did not block");
			}
		};

		try
		{
			container.start();
			Thread.sleep(TIMEOUT / 2);
		}
		catch (Exception unexpected)
		{
			Assert.fail("unexpected exception");
		}
	}

	@Test
	public void testBlockingAddRead() 
	{
		final RedBlackTree<Integer> tree = new RedBlackTree<Integer>();

		tree.readLock();

		final Thread adder = new Thread() 
		{
			public void run()
			{
				tree.add(0);
				Assert.fail("add did not block");
			}
		};

		try
		{
			adder.start();
			Thread.sleep(TIMEOUT / 2);
		}
		catch (Exception unexpected)
		{
			Assert.fail("unexpected exception");
		}
	}

	@Test
	public void testBlockingAddWrite() 
	{
		final RedBlackTree<Integer> tree = new RedBlackTree<Integer>();

		tree.writeLock();

		final Thread adder = new Thread() 
		{
			public void run()
			{
				tree.add(0);
				Assert.fail("add did not block");
			}
		};

		try
		{
			adder.start();
			Thread.sleep(TIMEOUT / 2);
		}
		catch (Exception unexpected)
		{
			Assert.fail("unexpected exception");
		}
	}

	private static int xorShift(int random)
	{
		random ^= (random << 6);
		random ^= (random >>> 21);
		random ^= (random << 7);
		return random;
	}

	@Test
	public void testConcurrentAdd() 
	{
		final int THREADS = 10;
		final int RUN = 1000;

		final RedBlackTree<Integer> tree = new RedBlackTree<Integer>();
		final CyclicBarrier barrier = new CyclicBarrier(THREADS + 1);

		for (int t = 0; t < THREADS; t++)
		{
			Thread adder = new Thread() 
			{
				public void run()
				{
					try
					{
						int random = this.hashCode() + (int) System.currentTimeMillis();
						barrier.await();
						for (int r = 0; r < RUN; r++)
						{
							tree.add(random % RUN);
							random = xorShift(random);
						}
						barrier.await();
					}
					catch (Exception e)
					{
						Assert.fail("something went wrong with the barrier");
					}
				}
			};
			adder.start();
		}

		try
		{
			barrier.await();
			barrier.await();
			tree.isValid();
		}
		catch (Exception e)
		{
			Assert.fail("something went wrong with the barrier");
		}
	}

	@Test
	public void testConcurrentAddAndContainsEmpty() 
	{
		final int THREADS = 100;
		final int RUN = 1000;

		final RedBlackTree<Integer> tree = new RedBlackTree<Integer>();
		final CyclicBarrier barrier = new CyclicBarrier(THREADS + 1);

		for (int t = 0; t < THREADS / 2; t++)
		{
			Thread adder = new Thread() 
			{
				public void run()
				{
					try
					{
						int random = this.hashCode() + (int) System.currentTimeMillis();
						barrier.await();
						for (int r = 0; r < RUN; r++)
						{
							tree.add(random % RUN + random % 2); // always even
							random = xorShift(random);
						}
						barrier.await();
					}
					catch (Exception e)
					{
						Assert.fail("something went wrong with the barrier");
					}
				}
			};
			adder.start();

			Thread container = new Thread() 
			{
				public void run()
				{
					try
					{
						int random = this.hashCode() + (int) System.currentTimeMillis();
						barrier.await();
						for (int r = 0; r < RUN; r++)
						{
							Assert.assertFalse(tree.contains(random % RUN + random % 2 + 1)); // always odd
							random = xorShift(random);
						}
						barrier.await();
					}
					catch (Exception e)
					{
						Assert.fail("something went wrong with the barrier");
					}
				}
			};
			container.start();
		}

		try
		{
			barrier.await();
			barrier.await();
			tree.isValid();
		}
		catch (Exception e)
		{
			Assert.fail("something went wrong with the barrier");
		}
	}
	
	@Test
	public void testConcurrentAddAndContainsNonEmpty() 
	{
		final int THREADS = 100;
		final int RUN = 1000;

		final RedBlackTree<Integer> tree = new RedBlackTree<Integer>();
		final CyclicBarrier barrier = new CyclicBarrier(THREADS + 1);
		
		List<Integer> list = new ArrayList<Integer>(THREADS);
		for (int t = 0; t < THREADS; t++)
		{
			list.add(t);
		}
		Collections.shuffle(list);
		for (Integer element : list)
		{
			tree.add(element);
		}
		
		for (int t = 0; t < THREADS / 2; t++)
		{
			Thread adder = new Thread() 
			{
				public void run()
				{
					try
					{
						int random = this.hashCode() + (int) System.currentTimeMillis();
						barrier.await();
						for (int r = 0; r < RUN; r++)
						{
							tree.add(random % RUN + random % 2);
							random = xorShift(random);
						}
						barrier.await();
					}
					catch (Exception e)
					{
						Assert.fail("something went wrong with the barrier");
					}
				}
			};
			adder.start();

			Thread container = new Thread() 
			{
				public void run()
				{
					try
					{
						barrier.await();
						for (int r = 0; r < RUN; r++)
						{
							Assert.assertTrue(tree.contains(r % THREADS));
						}
						barrier.await();
					}
					catch (Exception e)
					{
						Assert.fail("something went wrong with the barrier");
					}
				}
			};
			container.start();
		}

		try
		{
			barrier.await();
			barrier.await();
			tree.isValid();
		}
		catch (Exception e)
		{
			Assert.fail("something went wrong with the barrier");
		}
	}
}