src/test/java/PoliqarpPlusTreeTest.java

import static org.junit.Assert.*;

import org.junit.Test;

import de.ids_mannheim.korap.query.serialize.PoliqarpPlusTree;
import de.ids_mannheim.korap.util.QueryException;

public class PoliqarpPlusTreeTest {
	
	PoliqarpPlusTree ppt;
	String map;

	private boolean equalsContent(String str, Object map) {
		str = str.replaceAll(" ", "");
		String mapStr = map.toString().replaceAll(" ", "");
		return str.equals(mapStr);
	}
	
	private boolean equalsQueryContent(String res, String query) throws QueryException {
		res = res.replaceAll(" ", "");
		ppt = new PoliqarpPlusTree(query);
		String queryMap = ppt.getRequestMap().get("query").toString().replaceAll(" ", "");
		return res.equals(queryMap);
	}
	
//	@Test
	public void testContext() throws QueryException {
		String contextString = "{korap=http://korap.ids-mannheim.de/ns/query, @language=de, operands={@id=korap:operands, @container=@list}, operation={@id=korap:relation, type=korap:relation#types}, class={@id=korap:class, type=xsd:integer}, query=korap:query, filter=korap:filter, meta=korap:meta}";
		ppt = new PoliqarpPlusTree("[base=test]");
//		assertTrue(equalsContent(contextString, ppt.getRequestMap().get("@context")));
		assertEquals(contextString, ppt.getRequestMap().get("@context"));
	}
	
	@Test
	public void testSingleTokens() throws QueryException {
		// [base=Mann]
		String token1 = "{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}";
		assertTrue(equalsQueryContent(token1, "[base=Mann]"));
		
		// [orth!=Frau]
		String token2 = "{type=token, key={type=term, key=Frau, layer=orth, match=ne}}";
		assertTrue(equalsQueryContent(token2, "[orth!=Frau]"));
		
		// [!p=NN]
		String token3 = "{type=token, key={type=term, key=NN, layer=p, match=ne}}";
		assertTrue(equalsQueryContent(token3, "[!p=NN]"));
		
		// [!p!=NN]
		String token4 = "{type=token, key={type=term, key=NN, layer=p, match=eq}}";
		assertTrue(equalsQueryContent(token4, "[!p!=NN]"));
	}
	
	@Test
	public void testElements() throws QueryException {
		// <s>
		String elem1 = "{type=span, key=s}";
		assertTrue(equalsQueryContent(elem1, "<s>"));
		
		// <vp>
		String elem2 = "{type=span, key=vp}";
		assertTrue(equalsQueryContent(elem2, "<vp>"));
	}
	
	@Test
	public void testEmptyTokens() throws QueryException {
		// [base=der][][base=Mann]
		String et1 = 
			"{type=group, operation=sequence, inOrder=true, distances=[" +
				"{type=distance, measure=w, min=1, max=1}" +
			"], " +
			"operands=[" +
				"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}" +
			"]}";
		ppt = new PoliqarpPlusTree("[base=der][][base=Mann]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(et1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=der][][][base=Mann]
		String et2 = 
			"{type=group, operation=sequence, inOrder=true, distances=[" +
				"{type=distance, measure=w, min=2, max=2}" +
			"], " +
			"operands=[" +
				"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}" +
			"]}";
		ppt = new PoliqarpPlusTree("[base=der][][][base=Mann]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(et2.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=der][][]?[base=Mann]
		String et3 = 
			"{type=group, operation=sequence, inOrder=true, distances=[" +
				"{type=distance, measure=w, min=1, max=2}" +
			"], " +
			"operands=[" +
				"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}" +
			"]}";
		ppt = new PoliqarpPlusTree("[base=der][][]?[base=Mann]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(et3.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		
		// startswith(<s>, [][base=Mann]
		String et4 = 
			"{type=group, operation=position, frame=startswith, operands=[" +	
				"{type=span, key=s}," +
				"{type=group, operation=sequence, offset-min=1, offset-max=1, operands=[" +
					"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("startswith(<s>, [][base=Mann])");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(et4.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=der][]{2,5}[base=Mann][]?[][base=Frau]   nested distances=
		String et5 = 
				"{type=group, operation=sequence, inOrder=true, distances=[" +
					"{type=distance, measure=w, min=2, max=5}" +
				"], " +
				"operands=[" +
					"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
					"{type=group, operation=sequence, inOrder=true, distances=[" +
						"{type=distance, measure=w, min=1, max=2}" +
					"], " +
					"operands=[" +
						"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}," +
						"{type=token, key={type=term, key=Frau, layer=lemma, match=eq}}" +
					"]}" +
				"]}";
		ppt = new PoliqarpPlusTree("[base=der][]{2,5}[base=Mann][]?[][base=Frau]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(et5.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
	}

	@Test
	public void testCoordinatedFields() throws QueryException {
		// [base=Mann&(cas=N|cas=A)]
		String cof1 = 
			"{type=token, key=" +
				"{type=group, operands=[" +
					"{type=term, key=Mann, layer=lemma, match=eq}," +
					"{type=group, operands=[" +
						"{type=term, key=N, layer=cas, match=eq}," +
						"{type=term, key=A, layer=cas, match=eq}" +
					"], operation=or}" +
				"], operation=and}" +
			"}";
		ppt = new PoliqarpPlusTree("[base=Mann&(cas=N|cas=A)]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(cof1.replaceAll(" ", ""), map.replaceAll(" ", ""));


		assertEquals(
		    new PoliqarpPlusTree(" [ base=Mann & ( cas=N | cas=A)] ").getRequestMap().get("query").toString(),
		    new PoliqarpPlusTree("[base=Mann &(cas=N|cas=A)]").getRequestMap().get("query").toString()
	        );
		
		// [base=Mann&cas=N&gen=m]
		String cof2 = 
			"{type=token, key=" +
				"{type=group, operands=[" +
					"{type=term, key=Mann, layer=lemma, match=eq}," +
					"{type=term, key=N, layer=cas, match=eq}," +
					"{type=term, key=m, layer=gen, match=eq}" +
				"], operation=and}" +
			"}";
		ppt = new PoliqarpPlusTree("[base=Mann&cas=N&gen=m]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(cof2.replaceAll(" ", ""), map.replaceAll(" ", ""));
	}
	
	@Test
	public void testOccurrence() throws QueryException {
		// [base=foo]*
		String occ1 = "{type=group, operands=[" +
					     "{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
					  "], operation=repetition, @min=0, @max=100}"; 
		ppt = new PoliqarpPlusTree("[base=foo]*");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=foo]*[base=bar]
		String occ2 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=group, operands=[" +
					     "{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
					"], operation=repetition, @min=0, @max=100 }," +
					"{type=token, key={type=term, key=bar, layer=lemma, match=eq}}" +
				"]}"; 
		ppt = new PoliqarpPlusTree("[base=foo]*[base=bar]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ2.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=bar][base=foo]*
		String occ3 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=bar, layer=lemma, match=eq}}," +
					"{type=group, operands=[" +
					     "{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
					"], operation=repetition, @min=0, @max=100 }" +
				"]}"; 
		ppt = new PoliqarpPlusTree("[base=bar][base=foo]*");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ3.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// ([base=bar][base=foo])*
		String occ4 = 
				"{type=group, operands=[" +	
					"{type=group, operation=sequence, operands=[" +
						"{type=token, key={type=term, key=bar, layer=lemma, match=eq}}," +
						"{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
					"]}" +
				"], operation=repetition, @min=0, @max=100 }" ;
		ppt = new PoliqarpPlusTree("([base=bar][base=foo])*");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ4.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// <s>([base=bar][base=foo])*
		String occ5 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=span, key=s}," +
					"{type=group, operands=[" +	
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=bar, layer=lemma, match=eq}}," +
							"{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
						"]}" +
					"], operation=repetition, @min=0, @max=100 }" +
				"]}" ;
		ppt = new PoliqarpPlusTree("<s>([base=bar][base=foo])*");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ5.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// <s><np>([base=bar][base=foo])*
		String occ6 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=span, key=s}," +
					"{type=span, key=np}," +
					"{type=group, operands=[" +	
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=bar, layer=lemma, match=eq}}," +
							"{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
						"]}" +
					"], operation=repetition, @min=0, @max=100 }" +
				"]}" ;
		ppt = new PoliqarpPlusTree("<s><np>([base=bar][base=foo])*");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ6.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// <s><np>([base=bar][base=foo])*[p=NN]
		// comment: embedded sequence shouldn't really be here, but does not really hurt, either. (?)
		// really hard to get this behaviour out of the PQPlus grammar...
		String occ7 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=span, key=s}," +
					"{type=span, key=np}," +
					"{type=group, operands=[" +	
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=bar, layer=lemma, match=eq}}," +
							"{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
						"]}" +
					"], operation=repetition, @min=0, @max=100 }," +
					"{type=token, key={type=term, key=NN, layer=p, match=eq}}" +
				"]}" ;
		ppt = new PoliqarpPlusTree("<s><np>([base=bar][base=foo])*[p=NN]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ7.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// ([base=bar][base=foo])*[p=NN]
		String occ8 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=group, operands=[" +	
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=bar, layer=lemma, match=eq}}," +
							"{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
						"]}" +
					"], operation=repetition, @min=0, @max=100 }," +
					"{type=token, key={type=term, key=NN, layer=p, match=eq}}" +
				"]}" ;
		ppt = new PoliqarpPlusTree("([base=bar][base=foo])*[p=NN]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ8.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=foo]+
		String occ9 = "{type=group, operands=[" +
					     "{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
					  "], operation=repetition, @min=1, @max=100}"; 
		ppt = new PoliqarpPlusTree("[base=foo]+");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ9.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=foo]?
		String occ10 = "{type=group, operands=[" +
					     "{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
					  "], operation=repetition, @min=0, @max=1}"; 
		ppt = new PoliqarpPlusTree("[base=foo]?");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ10.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=foo]{2,5}
		String occ11 = "{type=group, operands=[" +
					     "{type=token, key={type=term, key=foo, layer=lemma, match=eq}}" +
					  "], operation=repetition, @min=2, @max=5}"; 
		ppt = new PoliqarpPlusTree("[base=foo]{2,5}");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(occ11.replaceAll(" ", ""), map.replaceAll(" ", ""));
	}
	
	@Test
	public void testTokenSequence() throws QueryException {
		// [base=Mann][orth=Frau]
		String seq1 = "{type=group, operation=sequence, operands=[" +
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}, " +
				"{type=token, key={type=term, key=Frau, layer=orth, match=eq}}" +
				"]}";
		assertTrue(equalsQueryContent(seq1, "[base=Mann][orth=Frau]"));
		
		// [base=Mann][orth=Frau][p=NN]
		String seq2 = "{type=group, operation=sequence, operands=[" +
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}, " +
				"{type=token, key={type=term, key=Frau, layer=orth, match=eq}}, " +
				"{type=token, key={type=term, key=NN,layer=p, match=eq}}" +
				"]}";
		assertTrue(equalsQueryContent(seq2, "[base=Mann][orth=Frau][p=NN]"));
	}
	
	@Test
	public void testDisjSegments() throws QueryException {
		// ([base=der]|[base=das])[base=Schild]
		String disj1 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=group, operation=or, operands=[" +
						"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
						"{type=token, key={type=term, key=das, layer=lemma, match=eq}}" +
					"]}," +
					"{type=token, key={type=term, key=Schild, layer=lemma, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("([base=der]|[base=das])[base=Schild]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(disj1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=Schild]([base=der]|[base=das])
		String disj2 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=Schild, layer=lemma, match=eq}}," +
					"{type=group, operation=or, operands=[" +
						"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
						"{type=token, key={type=term, key=das, layer=lemma, match=eq}}" +
					"]}" +
				"]}";
		ppt = new PoliqarpPlusTree("[base=Schild]([base=der]|[base=das])");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(disj2.replaceAll(" ", ""), map.replaceAll(" ", ""));
	}
	
	@Test
	public void testTokenElemSequence() throws QueryException {
		// [base=Mann]<vp>
		String seq1 = "{type=group, operation=sequence, operands=[" +
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}, " +
				"{type=span, key=vp}" +
				"]}";
		assertTrue(equalsQueryContent(seq1, "[base=Mann]<vp>"));
		
		// <vp>[base=Mann]
		String seq2 = "{type=group, operation=sequence, operands=[" +
				"{type=span, key=vp}, "+
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}} " +
				"]}";
		assertTrue(equalsQueryContent(seq2, "<vp>[base=Mann]"));
		
		// <vp>[base=Mann]<pp>
		String seq3 = "{type=group, operation=sequence, operands=[" +
				"{type=span, key=vp}, "+
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}, " +
				"{type=span, key=pp} "+
				"]}";
		assertTrue(equalsQueryContent(seq3, "<vp>[base=Mann]<pp>"));
	}
	
	@Test
	public void testElemSequence() throws QueryException {
		// <np><vp>
		String seq1 = "{type=group, operation=sequence, operands=[" +
				"{type=span, key=np}," +
				"{type=span, key=vp}" +
				"]}";
		assertTrue(equalsQueryContent(seq1, "<np><vp>"));
		
		// <np><vp><pp>
		String seq2 = "{type=group, operation=sequence, operands=[" +
				"{type=span, key=np}," +
				"{type=span, key=vp}," +
				"{type=span, key=pp}" +
				"]}";
		assertTrue(equalsQueryContent(seq2, "<np><vp><pp>"));
	}
	
	@Test 
	public void testClasses() throws QueryException {
		// {[base=Mann]}
		String cls1 = "{type=group, operation=class, class=0, operands=[" +
				"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("{[base=Mann]}");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(cls1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// {[base=Mann][orth=Frau]}
		String cls2 = "{type=group, operation=class, class=0, operands=[" +
				 "{type=group, operation=sequence, operands=[" +
				  "{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}," +
				  "{type=token, key={type=term, key=Frau, layer=orth, match=eq}}" +
				 "]}" +
				"]}";
		assertTrue(equalsQueryContent(cls2, "{[base=Mann][orth=Frau]}"));
		
		// [p=NN]{[base=Mann][orth=Frau]}
		String cls3 = "{type=group, operation=sequence, operands=[" +
						"{type=token, key={type=term, key=NN, layer=p, match=eq}}," +
						"{type=group, operation=class, class=0, operands=[" +
							"{type=group, operation=sequence, operands=[" +
								"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}," +
								"{type=token, key={type=term, key=Frau, layer=orth, match=eq}}" +
							"]}" +
						"]}" +
					  "]}";
		assertTrue(equalsQueryContent(cls3, "[p=NN]{[base=Mann][orth=Frau]}"));
		
		// {[base=Mann][orth=Frau]}[p=NN]
		String cls4 = "{type=group, operation=sequence, operands=[" +
						"{type=group, operation=class, class=0, operands=[" +
						   "{type=group, operation=sequence, operands=[" +
						     "{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}," +
						     "{type=token, key={type=term, key=Frau, layer=orth, match=eq}}" +
						   "]}" +
						"]}," +
						"{type=token, key={type=term, key=NN, layer=p, match=eq}}" +
					  "]}";
		ppt = new PoliqarpPlusTree("{[base=Mann][orth=Frau]}[p=NN]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(cls4.replaceAll(" ", ""), map.replaceAll(" ", ""));

		// {2:{1:[tt/p=ADJA]}[mate/p=NN]}"
		String cls5 = "{type=group, operation=class, class=2, operands=[" +
						"{type=group, operation=sequence, operands=[" +
						   "{type=group, operation=class, class=1, operands=[" +
						     "{type=token, key={type=term, key=ADJA, layer=p, foundry=tt, match=eq}}" +
						   "]}," +
						   "{type=token, key={type=term, key=NN, layer=p, foundry=mate, match=eq}}" + 
						"]}" +
					  "]}";
		ppt = new PoliqarpPlusTree("{2: {1:[tt/p=ADJA]}[mate/p=NN]}");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(cls5.replaceAll(" ", ""), map.replaceAll(" ", ""));
	}
	
	@Test
	public void testPositions() throws QueryException {
		// contains(<s>,<np>)
		String pos1 = "{type=group, operation=position, frame=contains, operands=[" +
				  "{type=span, key=s}," +
				  "{type=span, key=np}" +
				"]}";
		assertTrue(equalsQueryContent(pos1, "contains(<s>,<np>)"));
		
		// contains(<s>,[base=Mann])
		String pos2 = "{type=group, operation=position, frame=contains, operands=[" +
				  "{type=span, key=s}," +
				  "{type=token, key= {type=term, key=Mann, layer=lemma, match=eq}}" +
				"]}";
		assertTrue(equalsQueryContent(pos2, "contains(<s>,[base=Mann])"));
		
		// contains(<s>,[orth=der][orth=Mann])
		String pos3 = "{type=group, operation=position, frame=contains, operands=[" +
				  	"{type=span, key=s}," +
				  	"{type=group, operation=sequence, operands=[" +
				  		"{type=token, key={type=term, key=der, layer=orth, match=eq}}," +
				  		"{type=token, key={type=term, key=Mann, layer=orth, match=eq}}" +
				  	"]}" +
				  "]}";
		ppt = new PoliqarpPlusTree("contains(<s>,[orth=der][orth=Mann])");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(pos3.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [base=Auto]contains(<s>,[base=Mann])
		String pos4 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=Auto, layer=lemma, match=eq}}," +
					"{type=group, operation=position, frame=contains, operands=[" +
				  		"{type=span, key=s}," +
				  		"{type=token, key={type=term, key=Mann, layer=lemma, match=eq}}" +
				  	"]}" +
				"]}";
		ppt = new PoliqarpPlusTree("[base=Auto]contains(<s>,[base=Mann])");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(pos4.replaceAll(" ", ""), map.replaceAll(" ", ""));
	}
	
	@Test
	public void testNestedPositions() throws QueryException {
		// contains(<s>,startswith(<np>,[orth=Der]))
		String npos1 = 
			"{type=group, operation=position, frame=contains, operands=[" +
				"{type=span, key=s}," +
				"{type=group, operation=position, frame=startswith, operands=[" +
					"{type=span, key=np}," +
					"{type=token, key={type=term, key=Der, layer=orth, match=eq}}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("contains(<s>, startswith(<np>,[orth=Der]))");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(npos1.replaceAll(" ", ""), map.replaceAll(" ", ""));
	}
	
	@Test
	public void testShrinkSplit() throws QueryException {
		// shrink([orth=Der]{[orth=Mann]})
		String shr1 = 
			"{type=group, operation=submatch, classRef=[0], operands=[" +
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=Der, layer=orth, match=eq}}," +
					"{type=group, operation=class, class=0, operands=[" +
						"{type=token, key={type=term, key=Mann, layer=orth, match=eq}}" +
					"]}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("shrink([orth=Der]{[orth=Mann]})");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(shr1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// shrink([orth=Der]{[orth=Mann][orth=geht]})
		String shr2 = 
			"{type=group, operation=submatch, classRef=[0], operands=[" +
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=Der, layer=orth, match=eq}}," +
					"{type=group, operation=class, class=0, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=Mann, layer=orth, match=eq}}," +
							"{type=token, key={type=term, key=geht, layer=orth, match=eq}}" +
						"]}" +
					"]}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("shrink([orth=Der]{[orth=Mann][orth=geht]})");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(shr2.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// shrink(1:[orth=Der]{1:[orth=Mann][orth=geht]})
		String shr3 = 
			"{type=group, operation=submatch, classRef=[1], operands=[" +
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=Der, layer=orth, match=eq}}," +
					"{type=group, operation=class, class=1, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=Mann, layer=orth, match=eq}}," +
							"{type=token, key={type=term, key=geht, layer=orth, match=eq}}" +
						"]}" +
					"]}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("shrink(1:[orth=Der]{1:[orth=Mann][orth=geht]})");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(shr3.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// shrink(1:startswith(<s>,{1:<np>}))
		String shr4 = 
			"{type=group, operation=submatch, classRef=[1], operands=[" +
				"{type=group, operation=position, frame=startswith, operands=[" +
					"{type=span, key=s}," +
					"{type=group, operation=class, class=1, operands=[" +
						"{type=span, key=np}" +
					"]}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("shrink(1:startswith(<s>,{1:<np>}))");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(shr4.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// shrink(3: startswith(<s>, {3:[base=der]{1:[mate/p=ADJA]{2:[tt/p=NN]}}})) 
		String shr5 = 
			"{type=group, operation=submatch, classRef=[3], operands=[" +
				"{type=group, operation=position, frame=startswith, operands=[" +
					"{type=span, key=s}," +
					"{type=group, operation=class, class=3, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
							"{type=group, operation=class, class=1, operands=[" +
								"{type=group, operation=sequence, operands=[" +
									"{type=token, key={type=term, key=ADJA, layer=p, foundry=mate, match=eq}}," +
									"{type=group, operation=class, class=2, operands=[" +
										"{type=token, key={type=term, key=NN, layer=p, foundry=tt, match=eq}}" +
									"]}" + 
								"]}" +
							"]}" +
						"]}" +
					"]}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("shrink(3:startswith(<s>,{3:[base=der]{1:[mate/p=ADJA]{2:[tt/p=NN]}}})) ");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(shr5.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// split(3: startswith(<s>, {3:[base=der]{1:[mate/p=ADJA]{2:[tt/p=NN]}}})) 
		String shr6 = 
			"{type=group, operation=split, classRef=[3], operands=[" +
				"{type=group, operation=position, frame=startswith, operands=[" +
					"{type=span, key=s}," +
					"{type=group, operation=class, class=3, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
							"{type=group, operation=class, class=1, operands=[" +
								"{type=group, operation=sequence, operands=[" +
									"{type=token, key={type=term, key=ADJA, layer=p, foundry=mate, match=eq}}," +
									"{type=group, operation=class, class=2, operands=[" +
										"{type=token, key={type=term, key=NN, layer=p, foundry=tt, match=eq}}" +
									"]}" + 
								"]}" +
							"]}" +
						"]}" +
					"]}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("split(3:startswith(<s>,{3:[base=der]{1:[mate/p=ADJA]{2:[tt/p=NN]}}})) ");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(shr6.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// split(2|3: startswith(<s>, {3:[base=der]{1:[mate/p=ADJA]{2:[tt/p=NN]}}})) 
		String shr7 = 
			"{type=group, operation=split, classRef=[2, 3], classRefOp=intersection, operands=[" +
				"{type=group, operation=position, frame=startswith, operands=[" +
					"{type=span, key=s}," +
					"{type=group, operation=class, class=3, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=der, layer=lemma, match=eq}}," +
							"{type=group, operation=class, class=1, operands=[" +
								"{type=group, operation=sequence, operands=[" +
									"{type=token, key={type=term, key=ADJA, layer=p, foundry=mate, match=eq}}," +
									"{type=group, operation=class, class=2, operands=[" +
										"{type=token, key={type=term, key=NN, layer=p, foundry=tt, match=eq}}" +
									"]}" + 
								"]}" +
							"]}" +
						"]}" +
					"]}" +
				"]}" +
			"]}";
		ppt = new PoliqarpPlusTree("split(2|3:startswith(<s>,{3:[base=der]{1:[mate/p=ADJA]{2:[tt/p=NN]}}})) ");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(shr7.replaceAll(" ", ""), map.replaceAll(" ", ""));
	}
	
	
	@Test
	public void testFoundries() throws QueryException {
		// [tt/base=Mann]
		String layer1 = "{type=token, key={type=term, key=Mann, layer=base, foundry=tt, match=eq}}";
		ppt = new PoliqarpPlusTree("[tt/base=Mann]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(layer1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
	}
	
	@Test
	public void testAlign() throws QueryException {
		// [orth=der]^[orth=Mann]
		String align1 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=der, layer=orth, match=eq}}," +
					"{type=group, alignment=left, operands=[" +
						"{type=token, key={type=term, key=Mann, layer=orth, match=eq}}" +
					"]}" +
				"]}";
		ppt = new PoliqarpPlusTree("[orth=der]^[orth=Mann]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(align1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// [orth=der]^[orth=große][orth=Mann]
		String query = "[orth=der]^[orth=große][orth=Mann]";
		String align1b = 
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=der, layer=orth, match=eq}}," +
					"{type=group, alignment=left, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=große, layer=orth, match=eq}}," +
							"{type=token, key={type=term, key=Mann, layer=orth, match=eq}}" +
						"]}" +
					"]}" +
				"]}";
		ppt = new PoliqarpPlusTree(query);
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(align1b.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// "([base=a]^[base=b])|[base=c]",
		String align2 = 
				"{type=group, operation=or, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=a, layer=lemma, match=eq}}," +
							"{type=group, alignment=left, operands=[" +
								"{type=token, key={type=term, key=b, layer=lemma, match=eq}}" +
							"]}" +
						"]}," +
						"{type=token, key={type=term, key=c, layer=lemma, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("([base=a]^[base=b])|[base=c]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(align2.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// "([base=a]^[base=b][base=c])|[base=d]",
		String align3 = 
				"{type=group, operation=or, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=a, layer=lemma, match=eq}}," +
							"{type=group, alignment=left, operands=[" +
								"{type=group, operation=sequence, operands=[" +
									"{type=token, key={type=term, key=b, layer=lemma, match=eq}}," +
									"{type=token, key={type=term, key=c, layer=lemma, match=eq}}" +
								"]}" +
							"]}" +
						"]}," +
						"{type=token, key={type=term, key=d, layer=lemma, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("([base=a]^[base=b][base=c])|[base=d]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(align3.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// "([base=a]^[base=b]^[base=c])|[base=d]",
		String align4 = 
				"{type=group, operation=or, operands=[" +
						"{type=group, operation=sequence, operands=[" +
							"{type=token, key={type=term, key=a, layer=lemma, match=eq}}," +
							"{type=group, alignment=left, operands=[" +
								"{type=group, operation=sequence, operands=[" +
									"{type=token, key={type=term, key=b, layer=lemma, match=eq}}," +
									"{type=group, alignment=left, operands=[" +
										"{type=token, key={type=term, key=c, layer=lemma, match=eq}}" +
									"]}" +
								"]}" +
							"]}" +
						"]}," +
						"{type=token, key={type=term, key=d, layer=lemma, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("([base=a]^[base=b]^[base=c])|[base=d]");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(align4.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		
	}
	
	@Test
	public void testSimpleQueries() throws QueryException {
		// Baum
		String simple1 = 
				"{type=token, key={type=term, key=Baum, layer=orth, match=eq}}";
		ppt = new PoliqarpPlusTree("Baum");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(simple1.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// Der Baum
		String simple2 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=Der, layer=orth, match=eq}}, " +
					"{type=token, key={type=term, key=Baum, layer=orth, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("Der Baum");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(simple2.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// Der große Baum
		String simple3 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=token, key={type=term, key=Der, layer=orth, match=eq}}, " +
					"{type=token, key={type=term, key=große, layer=orth, match=eq}}, " +						
					"{type=token, key={type=term, key=Baum, layer=orth, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("Der große Baum");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(simple3.replaceAll(" ", ""), map.replaceAll(" ", ""));
		
		// Baum | Stein
		String simple4 = 
				"{type=group, operation=or, operands=[" +
					"{type=token, key={type=term, key=Baum, layer=orth, match=eq}}, " +						
					"{type=token, key={type=term, key=Stein, layer=orth, match=eq}}" +
				"]}";
		ppt = new PoliqarpPlusTree("Baum | Stein");
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(simple4.replaceAll(" ", ""), map.replaceAll(" ", ""));		
		
		// Baum | Stein Haus
		String query = "(Baum | Stein) Haus";
		String simple5 = 
				"{type=group, operation=sequence, operands=[" +
					"{type=group, operation=or, operands=[" +
						"{type=token, key={type=term, key=Baum, layer=orth, match=eq}}, " +						
						"{type=token, key={type=term, key=Stein, layer=orth, match=eq}}" +
					"]}," +
					"{type=token, key={type=term, key=Haus, layer=orth, match=eq}} " +			
				"]}";
		ppt = new PoliqarpPlusTree(query);
		map = ppt.getRequestMap().get("query").toString();
		assertEquals(simple5.replaceAll(" ", ""), map.replaceAll(" ", ""));		
	}
}