package org.psjava.example.algo;

import org.junit.Assert;
import org.junit.Test;
import org.psjava.algo.sequence.rmq.RangeMinimumQueryBySquareRootApproach;
import org.psjava.algo.sequence.rmq.RangeMinimumQuerySession;
import org.psjava.algo.sequence.rmq.RangeMinimumQueryUsingSegmentTree;
import org.psjava.algo.sequence.rmq.RangeMinimumQueryUsingSparseTable;
import org.psjava.ds.array.Array;
import org.psjava.ds.array.ArrayFromVarargs;
import org.psjava.example.ds.ArrayExample;
import org.psjava.goods.GoodRangeMinimumQuery;
import org.psjava.util.DefaultComparator;

/**
 * @implementation {@link RangeMinimumQueryBySquareRootApproach}
 * @implementation {@link RangeMinimumQueryUsingSegmentTree}
 * @implementation {@link RangeMinimumQueryUsingSparseTable}
 * @see {@link ArrayExample}
 */
public class RangeMinimumQueryExample {

	@Test
	public void example() {
		Array<String> array = ArrayFromVarargs.create("A", "E", "B", "C", "G");

		RangeMinimumQuerySession session = GoodRangeMinimumQuery.getInstance().preprocess(array, new DefaultComparator<String>());

		int index1 = session.getIndex(1, 4); // must be 2, that is the index of "B" among ("E", "B", "C")
		Assert.assertEquals(2, index1);

		int index2 = session.getIndex(0, 3); // must be 0, that is the index of "A" among ("A", "E", "B")
		Assert.assertEquals(0, index2);
	}
}

@@ -75,24 +75,80 @@
 unit.Test;%0D%0A
+import org.psjava.algo.sequence.rmq.RangeMinimumQuery;%0D%0A
 import org.p
@@ -211,16 +211,16 @@
 roach;%0D%0A
-
 import o
@@ -583,32 +583,81 @@
 eMinimumQuery;%0D%0A
+import org.psjava.goods.GoodSegmentTreeFactory;%0D%0A
 import org.psjav
@@ -1432,24 +1432,24 @@
  %22E%22, %22B%22)%0D%0A
-
 %09%09Assert.ass
@@ -1471,15 +1471,465 @@
 dex2);%0D%0A
+%0D%0A%09%09// There are several implementations of range minimum query problem.%0D%0A%09%09// They have different time & space complexity. See the detail in an article of TopCoder%0D%0A%09%09// http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static%0D%0A%0D%0A%09%09RangeMinimumQueryUsingSegmentTree.getInstance(GoodSegmentTreeFactory.getInstance());%0D%0A%09%09RangeMinimumQueryBySquareRootApproach.getInstance();%0D%0A%09%09RangeMinimumQueryUsingSparseTable.getInstance();%0D%0A%0D%0A
 %09%7D%0D%0A%7D%0D%0A

improve RangeMinimumQueryExample.java