import static org.junit.Assert.*;

import java.util.Collection;

import org.junit.Before;
import org.junit.Test;

/**
 * Tests for {@link QuadTreeMap}.
 * 
 * @author Michael D. Naper, Jr. <MichaelNaper.com>
 * @version 2012.08.20
 */
public class QuadTreeMapTest {

  // Default leaf node capacity; keep in sync with QuadTreeMap
  private static final int DEFAULT_BUCKET_SIZE = 4;

  private QuadTreeMap<Integer> map;

  @Before
  public void setUp() throws Exception {
    map = new QuadTreeMap<Integer>(0, DEFAULT_BUCKET_SIZE, 0,
        DEFAULT_BUCKET_SIZE);
  }

  /**
   * Test method for
   * {@link QuadTreeMap#QuadTreeMap(double, double, double, double, int)}.
   */
  @Test
  public void testQuadTreeMapDoubleDoubleDoubleDoubleInt() {
    QuadTreeMap<Integer> mapWithBucketSize = new QuadTreeMap<Integer>(0, 10, 0,
        10, DEFAULT_BUCKET_SIZE + 1);
    assertNotNull(mapWithBucketSize);
    assertEquals(DEFAULT_BUCKET_SIZE + 1, mapWithBucketSize.bucketSize());
  }

  /**
   * Test method for
   * {@link QuadTreeMap#QuadTreeMap(double, double, double, double)}.
   */
  @Test
  public void testQuadTreeMapDoubleDoubleDoubleDouble() {
    assertNotNull(map);
    assertEquals(DEFAULT_BUCKET_SIZE, map.bucketSize());
    assertEquals(0, map.size());
    assertTrue(map.isEmpty());
  }

  /**
   * Test method for {@link QuadTreeMap#put(double, double, java.lang.Object)}.
   */
  @Test
  public void testPut() {
    assertNull(map.put(-1, -1, new Integer(-1)));
    assertEquals(0, map.size());
    assertTrue(map.isEmpty());
    assertNull(map.get(0, 0));

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      assertNull(map.put(i, i, new Integer(i)));
      assertEquals(i + 1, map.size());
      assertFalse(map.isEmpty());
      assertEquals(i, map.get(i, i).intValue());
    }

    Integer oldValue;
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      oldValue = map.put(i, i, new Integer(DEFAULT_BUCKET_SIZE + i));
      assertEquals(i, oldValue.intValue());
      assertEquals(DEFAULT_BUCKET_SIZE + 1, map.size());
      assertEquals(DEFAULT_BUCKET_SIZE + i, map.get(i, i).intValue());
    }
  }

  /**
   * Test method for {@link QuadTreeMap#containsKey(double, double)}.
   */
  @Test
  public void testContainsKey() {
    assertFalse(map.containsKey(-1, -1));

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      assertFalse(map.containsKey(i, i));
      map.put(i, i, new Integer(i));
      assertTrue(map.containsKey(i, i));
    }
  }

  /**
   * Test method for {@link QuadTreeMap#get(double, double)}.
   */
  @Test
  public void testGetDoubleDouble() {
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.put(i, i, new Integer(i));
    }

    assertNull(map.get(-1, -1));

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      assertEquals(i, map.get(i, i).intValue());
    }
  }

  /**
   * Test method for {@link QuadTreeMap#get(double, double, double)}.
   */
  @Test
  public void testGetDoubleDoubleDouble() {
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.put(i, i, new Integer(i));
    }

    assertTrue(map.get(-DEFAULT_BUCKET_SIZE, -DEFAULT_BUCKET_SIZE,
        DEFAULT_BUCKET_SIZE).isEmpty());

    Collection<Integer> found = map.get(0, 0, DEFAULT_BUCKET_SIZE);
    int diagonal = (int) (DEFAULT_BUCKET_SIZE / Math.sqrt(2));
    assertEquals(diagonal + 1, found.size());
    int value = 0;
    for (Integer elem : found) {
      assertEquals(value++, elem.intValue());
    }
  }

  /**
   * Test method for {@link QuadTreeMap#get(double, double, double, double)}.
   */
  @Test
  public void testGetDoubleDoubleDoubleDouble() {
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.put(i, i, new Integer(i));
    }

    assertTrue(map.get(-DEFAULT_BUCKET_SIZE, -DEFAULT_BUCKET_SIZE, 0, 0)
        .isEmpty());

    Collection<Integer> found = map.get(0, DEFAULT_BUCKET_SIZE / 2, 0,
        DEFAULT_BUCKET_SIZE / 2);
    assertEquals(DEFAULT_BUCKET_SIZE / 2 + 1, found.size());
    int value = 0;
    for (Integer elem : found) {
      assertEquals(value++, elem.intValue());
    }
  }

  /**
   * Test method for {@link QuadTreeMap#remove(double, double)}.
   */
  @Test
  public void testRemove() {
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.put(i, i, new Integer(i));
    }

    assertNull(map.remove(-1, -1));

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      assertEquals(i, map.remove(i, i).intValue());
    }

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      assertNull(map.remove(i, i));
    }
  }

  /**
   * Test method for {@link QuadTreeMap#clear()}.
   */
  @Test
  public void testClear() {
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.put(i, i, new Integer(i));
    }

    map.clear();
    assertEquals(0, map.size());
    assertTrue(map.isEmpty());
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      assertNull(map.get(i, i));
      assertFalse(map.containsKey(i, i));
    }
  }

  /**
   * Test method for {@link QuadTreeMap#isEmpty()}.
   */
  @Test
  public void testIsEmpty() {
    assertTrue(map.isEmpty());
    map.put(0, 0, new Integer(0));
    assertFalse(map.isEmpty());
    map.remove(0, 0);
    assertTrue(map.isEmpty());
  }

  /**
   * Test method for {@link QuadTreeMap#size()}.
   */
  @Test
  public void testSize() {
    assertEquals(0, map.size());

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.put(i, i, new Integer(i));
      assertEquals(i + 1, map.size());
    }

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.remove(i, i);
      assertEquals(DEFAULT_BUCKET_SIZE - i, map.size());
    }
  }

  /**
   * Test method for {@link QuadTreeMap#bucketSize()}.
   */
  @Test
  public void testBucketSize() {
    assertEquals(DEFAULT_BUCKET_SIZE, map.bucketSize());

    QuadTreeMap<Integer> mapWithBucketSize = new QuadTreeMap<Integer>(0,
        DEFAULT_BUCKET_SIZE + 1, 0, DEFAULT_BUCKET_SIZE + 1,
        DEFAULT_BUCKET_SIZE + 1);
    assertEquals(DEFAULT_BUCKET_SIZE + 1, mapWithBucketSize.bucketSize());
  }

  /**
   * Test method for {@link QuadTreeMap#toString()}.
   */
  @Test
  public void testToString() {
    assertEquals("[]", map.toString());

    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      map.put(i, i, new Integer(i));
    }
    StringBuilder expected = new StringBuilder();
    expected.append("[");
    for (int i = 0; i <= DEFAULT_BUCKET_SIZE; i++) {
      expected.append("[key=(" + i + ".0, " + i + ".0), value=" + i + "], ");
    }
    expected.setLength(expected.length() - 2);
    expected.append("]");
    assertEquals(expected.toString(), map.toString());
  }

}