Index: /trunk/quest-core-assertions-test/.classpath
===================================================================
--- /trunk/quest-core-assertions-test/.classpath	(revision 518)
+++ /trunk/quest-core-assertions-test/.classpath	(revision 518)
@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/test-classes" path="src/test/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="src" output="target/classes" path="src/main/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
Index: /trunk/quest-core-assertions-test/.project
===================================================================
--- /trunk/quest-core-assertions-test/.project	(revision 518)
+++ /trunk/quest-core-assertions-test/.project	(revision 518)
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>quest-core-assertions-test</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.eclipse.m2e.core.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.m2e.core.maven2Nature</nature>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
Index: /trunk/quest-core-assertions-test/.settings/org.eclipse.jdt.core.prefs
===================================================================
--- /trunk/quest-core-assertions-test/.settings/org.eclipse.jdt.core.prefs	(revision 518)
+++ /trunk/quest-core-assertions-test/.settings/org.eclipse.jdt.core.prefs	(revision 518)
@@ -0,0 +1,5 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
Index: /trunk/quest-core-assertions-test/.settings/org.eclipse.m2e.core.prefs
===================================================================
--- /trunk/quest-core-assertions-test/.settings/org.eclipse.m2e.core.prefs	(revision 518)
+++ /trunk/quest-core-assertions-test/.settings/org.eclipse.m2e.core.prefs	(revision 518)
@@ -0,0 +1,4 @@
+activeProfiles=
+eclipse.preferences.version=1
+resolveWorkspaceProjects=true
+version=1
Index: /trunk/quest-core-assertions-test/pom.xml
===================================================================
--- /trunk/quest-core-assertions-test/pom.xml	(revision 518)
+++ /trunk/quest-core-assertions-test/pom.xml	(revision 518)
@@ -0,0 +1,150 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>de.ugoe.cs.quest</groupId>
+  <artifactId>quest-core-assertions-test</artifactId>
+  <version>0.0.1-SNAPSHOT</version>
+  <name>quest-core-assertions-test</name>
+  <scm>
+    <url>https://quest.informatik.uni-goettingen.de/svn/quest/trunk/quest-core-events-test</url>
+  </scm>
+  <dependencies>
+    <dependency>
+        <groupId>de.ugoe.cs.quest</groupId>
+        <artifactId>quest-core-events</artifactId>
+        <version>0.0.1-SNAPSHOT</version>
+        <scope>test</scope>
+    </dependency>
+    <dependency>
+		<groupId>de.ugoe.cs.quest</groupId>
+		<artifactId>quest-core-assertions</artifactId>
+		<version>0.0.1-SNAPSHOT</version>
+		<scope>test</scope>
+	</dependency>
+	<dependency>
+		<groupId>de.ugoe.cs.quest</groupId>
+		<artifactId>quest-core-events-test</artifactId>
+		<version>0.0.1-SNAPSHOT</version>
+		<scope>test</scope>
+	</dependency>
+    <dependency>
+        <groupId>junit</groupId>
+        <artifactId>junit</artifactId>
+        <version>4.8.1</version>
+        <scope>test</scope>
+    </dependency>
+    <!-- <dependency>
+	  <groupId>junit-addons</groupId>
+	  <artifactId>junit-addons</artifactId>
+	  <version>1.4</version>
+    </dependency>
+    <dependency>
+	  <groupId>nl.jqno.equalsverifier</groupId>
+	  <artifactId>equalsverifier</artifactId>
+	  <version>1.1.3</version>
+    </dependency>-->
+  </dependencies>
+  <build>
+    <pluginManagement>
+      <plugins>
+        <plugin>
+          <groupId>org.eclipse.m2e</groupId>
+          <artifactId>lifecycle-mapping</artifactId>
+          <version>1.0.0</version>
+          <configuration>
+            <lifecycleMappingMetadata>
+              <pluginExecutions>
+                <pluginExecution>
+                  <pluginExecutionFilter>
+                    <groupId>org.apache.maven.plugins</groupId>
+                    <artifactId>maven-dependency-plugin</artifactId>
+                    <versionRange>[1.0.0,)</versionRange>
+                    <goals>
+                      <goal>unpack</goal>
+                    </goals>
+                  </pluginExecutionFilter>
+                  <action>
+                    <ignore/>
+                  </action>
+                </pluginExecution>
+                <pluginExecution>
+                  <pluginExecutionFilter>
+                    <groupId>org.codehaus.mojo</groupId>
+                    <artifactId>emma-maven-plugin</artifactId>
+                    <versionRange>[1.0-alpha-3,)</versionRange>
+                    <goals>
+                      <goal>emma</goal>
+                    </goals>
+                  </pluginExecutionFilter>
+                  <action>
+                    <ignore/>
+                  </action>
+                </pluginExecution>
+              </pluginExecutions>
+            </lifecycleMappingMetadata>
+          </configuration>
+        </plugin>
+      </plugins>
+    </pluginManagement>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <version>2.3.2</version>
+        <configuration>
+          <source>1.6</source>
+          <target>1.6</target>
+        </configuration>
+      </plugin>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-dependency-plugin</artifactId>
+        <version>2.4</version>
+        <executions>
+          <execution>
+            <id>unpack</id>
+            <phase>process-classes</phase>
+            <goals>
+              <goal>unpack</goal>
+            </goals>
+            <configuration>
+              <artifactItems>
+                <artifactItem>
+                  <groupId>de.ugoe.cs.quest</groupId>
+                  <artifactId>quest-core-assertions</artifactId>
+                  <version>0.0.1-SNAPSHOT</version>
+                  <outputDirectory>${project.build.directory}/classes</outputDirectory>
+                </artifactItem>
+              </artifactItems>
+            </configuration>
+          </execution>
+        </executions>
+      </plugin>
+      <plugin>
+        <groupId>org.codehaus.mojo</groupId>
+        <artifactId>emma-maven-plugin</artifactId>
+        <version>1.0-alpha-3</version>
+        <inherited>true</inherited>          
+        <executions>
+          <execution>
+            <phase>process-classes</phase>
+            <goals>
+              <goal>emma</goal>
+            </goals>
+          </execution>
+        </executions>
+      </plugin>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-jar-plugin</artifactId>
+        <version>2.3.2</version>
+        <executions>
+          <execution>
+            <goals>
+              <goal>test-jar</goal>
+            </goals>
+          </execution>
+        </executions>
+      </plugin>
+    </plugins>
+  </build>
+</project>
Index: /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/AssertEventTest.java
===================================================================
--- /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/AssertEventTest.java	(revision 518)
+++ /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/AssertEventTest.java	(revision 518)
@@ -0,0 +1,38 @@
+package de.ugoe.cs.quest.assertions;
+
+import org.junit.*;
+
+import de.ugoe.cs.quest.assertions.AssertEvent;
+import de.ugoe.cs.quest.eventcore.mock.MockReplayable;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>AssertEventTest</code> contains tests for the class
+ * <code>{@link AssertEvent}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class AssertEventTest {
+
+	@Test
+	public void testAssertEvent_1() throws Exception {
+		String type = "typeString";
+
+		AssertEvent<MockReplayable> result = new AssertEvent<MockReplayable>(
+				type);
+
+		assertNotNull(result);
+		assertEquals(type, result.getType());
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testAssertEvent_2() throws Exception {
+
+		new AssertEvent<MockReplayable>(null);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(AssertEventTest.class);
+	}
+}
Index: /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/FileEqualsReplayTest.java
===================================================================
--- /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/FileEqualsReplayTest.java	(revision 518)
+++ /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/FileEqualsReplayTest.java	(revision 518)
@@ -0,0 +1,80 @@
+package de.ugoe.cs.quest.assertions;
+
+import org.junit.*;
+
+import de.ugoe.cs.quest.assertions.FileEqualsReplay;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>FileEqualsReplayTest</code> contains tests for the class
+ * <code>{@link FileEqualsReplay}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class FileEqualsReplayTest {
+
+	private final static String ENDLINE = System.getProperty("line.separator");
+
+	@Test
+	public void testFileEqualsReplay_1() throws Exception {
+		String expectedFile = "expectedFileString";
+		String actualFile = "actualFileString";
+
+		FileEqualsReplay result = new FileEqualsReplay(expectedFile, actualFile);
+
+		assertNotNull(result);
+		assertEquals(expectedFile, result.expectedFile);
+		assertEquals(actualFile, result.actualFile);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testFileEqualsReplay_2() throws Exception {
+		String actualFile = "actualFileString";
+
+		new FileEqualsReplay(null, actualFile);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testFileEqualsReplay_3() throws Exception {
+		String expectedFile = "expectedFileString";
+
+		new FileEqualsReplay(expectedFile, null);
+	}
+
+	@Test
+	public void testGetReplay_1() throws Exception {
+		FileEqualsReplay fixture = new FileEqualsReplay("", "");
+
+		String result = fixture.getReplay();
+
+		assertEquals("  <fileEquals actualFile=\"\" expectedFile=\"\"/>"
+				+ ENDLINE, result);
+	}
+
+	@Test
+	public void testGetReplay_2() throws Exception {
+
+		FileEqualsReplay fixture = new FileEqualsReplay("expectedFileString",
+				"actualFileString");
+
+		String result = fixture.getReplay();
+
+		assertEquals(
+				"  <fileEquals actualFile=\"actualFileString\" expectedFile=\"expectedFileString\"/>"
+						+ ENDLINE, result);
+	}
+
+	@Test
+	public void testGetTarget_1() throws Exception {
+		FileEqualsReplay fixture = new FileEqualsReplay("", "");
+
+		String result = fixture.getTarget();
+
+		assertEquals("targetNotUsed", result);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(FileEqualsReplayTest.class);
+	}
+}
Index: /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/TestAll.java
===================================================================
--- /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/TestAll.java	(revision 518)
+++ /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/TestAll.java	(revision 518)
@@ -0,0 +1,27 @@
+package de.ugoe.cs.quest.assertions;
+
+import org.junit.runner.JUnitCore;
+import org.junit.runner.RunWith;
+import org.junit.runners.Suite;
+
+/**
+ * The class <code>TestAll</code> builds a suite that can be used to run all
+ * of the tests within its package as well as within any subpackages of its
+ * package.
+ *
+ * @generatedBy CodePro at 12/21/11 11:53 AM
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+@RunWith(Suite.class)
+@Suite.SuiteClasses({
+	FileEqualsReplayTest.class,
+	TextEqualsReplayTest.class,
+	AssertEventTest.class
+})
+public class TestAll {
+
+	public static void main(String[] args) {
+		JUnitCore.runClasses(new Class[] { TestAll.class });
+	}
+}
Index: /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/TextEqualsReplayTest.java
===================================================================
--- /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/TextEqualsReplayTest.java	(revision 518)
+++ /trunk/quest-core-assertions-test/src/test/java/de/ugoe/cs/quest/assertions/TextEqualsReplayTest.java	(revision 518)
@@ -0,0 +1,85 @@
+package de.ugoe.cs.quest.assertions;
+
+import org.junit.*;
+
+import de.ugoe.cs.quest.assertions.TextEqualsReplay;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>TextEqualsReplayTest</code> contains tests for the class
+ * <code>{@link TextEqualsReplay}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class TextEqualsReplayTest {
+
+	private final static String ENDLINE = System.getProperty("line.separator");
+
+	@Test
+	public void testTextEqualsReplay_1() throws Exception {
+		String expectedValue = "expectedValueString";
+		String target = "targetString";
+
+		TextEqualsReplay result = new TextEqualsReplay(expectedValue, target);
+
+		assertNotNull(result);
+		assertEquals(expectedValue, result.expectedValue);
+		assertEquals(target, result.target);
+	}
+
+	@Test
+	public void testTextEqualsReplay_2() throws Exception {
+		String target = "targetString";
+
+		TextEqualsReplay result = new TextEqualsReplay(null, target);
+
+		assertNotNull(result);
+		assertEquals(null, result.expectedValue);
+		assertEquals(target, result.target);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testTextEqualsReplay_3() throws Exception {
+		String expectedValue = "expectedValueString";
+
+		new TextEqualsReplay(expectedValue, null);
+	}
+
+	@Test
+	public void testGetReplay_1() throws Exception {
+		TextEqualsReplay fixture = new TextEqualsReplay("", "");
+
+		String result = fixture.getReplay();
+
+		assertEquals(" <textEquals expectedValue=\"\">" + ENDLINE + "<target>"
+				+ ENDLINE + ENDLINE + "</target>" + ENDLINE + "</textEquals>"
+				+ ENDLINE, result);
+	}
+
+	@Test
+	public void testGetReplay_2() throws Exception {
+		TextEqualsReplay fixture = new TextEqualsReplay("expectedValueString",
+				"targetString");
+
+		String result = fixture.getReplay();
+
+		assertEquals(" <textEquals expectedValue=\"expectedValueString\">"
+				+ ENDLINE + "<target>" + ENDLINE + "targetString" + ENDLINE
+				+ "</target>" + ENDLINE + "</textEquals>" + ENDLINE, result);
+	}
+
+	@Test
+	public void testGetTarget_1() throws Exception {
+		TextEqualsReplay fixture = new TextEqualsReplay("expectedValueString",
+				"targetString");
+
+		String result = fixture.getTarget();
+
+		assertEquals("targetString", result);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(TextEqualsReplayTest.class);
+	}
+}
Index: /trunk/quest-core-assertions/.classpath
===================================================================
--- /trunk/quest-core-assertions/.classpath	(revision 518)
+++ /trunk/quest-core-assertions/.classpath	(revision 518)
@@ -0,0 +1,20 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/classes" path="src/main/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
Index: /trunk/quest-core-assertions/.project
===================================================================
--- /trunk/quest-core-assertions/.project	(revision 518)
+++ /trunk/quest-core-assertions/.project	(revision 518)
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>quest-core-assertions</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.eclipse.m2e.core.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.m2e.core.maven2Nature</nature>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
Index: /trunk/quest-core-assertions/.settings/org.eclipse.jdt.core.prefs
===================================================================
--- /trunk/quest-core-assertions/.settings/org.eclipse.jdt.core.prefs	(revision 518)
+++ /trunk/quest-core-assertions/.settings/org.eclipse.jdt.core.prefs	(revision 518)
@@ -0,0 +1,5 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
Index: /trunk/quest-core-assertions/.settings/org.eclipse.m2e.core.prefs
===================================================================
--- /trunk/quest-core-assertions/.settings/org.eclipse.m2e.core.prefs	(revision 518)
+++ /trunk/quest-core-assertions/.settings/org.eclipse.m2e.core.prefs	(revision 518)
@@ -0,0 +1,4 @@
+activeProfiles=
+eclipse.preferences.version=1
+resolveWorkspaceProjects=true
+version=1
Index: /trunk/quest-core-assertions/pom.xml
===================================================================
--- /trunk/quest-core-assertions/pom.xml	(revision 518)
+++ /trunk/quest-core-assertions/pom.xml	(revision 518)
@@ -0,0 +1,29 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>de.ugoe.cs.quest</groupId>
+  <artifactId>quest-core-assertions</artifactId>
+  <version>0.0.1-SNAPSHOT</version>
+  <name>quest-core-assertions</name>
+	<scm>
+		<url>https://quest.informatik.uni-goettingen.de/svn/quest/trunk/quest-core-assertions</url>
+	</scm>
+	<dependencies>
+		<dependency>
+			<groupId>de.ugoe.cs.quest</groupId>
+			<artifactId>quest-core-events</artifactId>
+			<version>0.0.1-SNAPSHOT</version>
+		</dependency>
+	</dependencies>
+	<build>
+		<plugins>
+			<plugin>
+				<artifactId>maven-compiler-plugin</artifactId>
+				<version>2.3.2</version>
+				<configuration>
+					<source>1.6</source>
+					<target>1.6</target>
+				</configuration>
+			</plugin>
+		</plugins>
+	</build>
+</project>
Index: /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/AssertEvent.java
===================================================================
--- /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/AssertEvent.java	(revision 518)
+++ /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/AssertEvent.java	(revision 518)
@@ -0,0 +1,41 @@
+package de.ugoe.cs.quest.assertions;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.eventcore.IReplayable;
+import de.ugoe.cs.quest.eventcore.ReplayableEvent;
+
+/**
+ * <p>
+ * Subclass of {@link ReplayableEvent} for assertions
+ * </p>
+ * 
+ * @author Jeffrey Hall
+ * @version 1.0
+ * 
+ * @param <T>
+ *            Allows only types that extend {@link IReplayable} and is used to
+ *            define the type of the assertion.
+ * 
+ */
+public class AssertEvent<T extends IReplayable> extends ReplayableEvent<T> {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new event with the given type.
+	 * <p>
+	 * 
+	 * @param type
+	 *            type of the event
+	 * @see Event#Event(String)
+	 */
+	public AssertEvent(String type) {
+		super(type);
+	}
+}
Index: /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/FileEqualsReplay.java
===================================================================
--- /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/FileEqualsReplay.java	(revision 518)
+++ /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/FileEqualsReplay.java	(revision 518)
@@ -0,0 +1,91 @@
+package de.ugoe.cs.quest.assertions;
+
+import java.security.InvalidParameterException;
+
+import de.ugoe.cs.quest.eventcore.IReplayable;
+import de.ugoe.cs.util.StringTools;
+
+/**
+ * <p>
+ * This class defines the replay for file equals assertions.
+ * </p>
+ * 
+ * @author Jeffrey Hall, Steffen Herbold
+ * @version 2.0
+ */
+public class FileEqualsReplay implements IReplayable {
+
+	/**
+	 * <p>
+	 * The file that should be equal to expectedFile.
+	 * </p>
+	 */
+	protected final String actualFile;
+
+	/**
+	 * <p>
+	 * The file that is used as the reference.
+	 * </p>
+	 */
+	protected final String expectedFile;
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new FileEqualsReplay.
+	 * </p>
+	 * 
+	 * @param expectedFile
+	 *            name and path of the expected file
+	 * @param actualFile
+	 *            name and path of the actual file
+	 * @throws InvalidParameterException
+	 *             thrown if expectedFile or actualFile are null
+	 */
+	public FileEqualsReplay(String expectedFile, String actualFile) {
+		if (expectedFile == null) {
+			throw new InvalidParameterException(
+					"expected file must not be null");
+		}
+		if (actualFile == null) {
+			throw new InvalidParameterException("actual file must not be null");
+		}
+		this.expectedFile = expectedFile;
+		this.actualFile = actualFile;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.eventcore.IReplayable#getReplay()
+	 */
+	public String getReplay() {
+
+		String actualFileTmp = StringTools.xmlEntityReplacement(actualFile);
+		String expectedFileTmp = StringTools.xmlEntityReplacement(expectedFile);
+
+		StringBuilder currentMsgStr = new StringBuilder(800);
+		currentMsgStr.append("  <fileEquals ");
+		currentMsgStr.append("actualFile=\"" + actualFileTmp + "\" ");
+		currentMsgStr.append("expectedFile=\"" + expectedFileTmp + "\"/>");
+		currentMsgStr.append(StringTools.ENDLINE);
+		return currentMsgStr.toString();
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.eventcore.IReplayable#getTarget()
+	 */
+	@Override
+	public String getTarget() {
+		return "targetNotUsed";
+	}
+
+}
Index: /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/TextEqualsReplay.java
===================================================================
--- /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/TextEqualsReplay.java	(revision 518)
+++ /trunk/quest-core-assertions/src/main/java/de/ugoe/cs/quest/assertions/TextEqualsReplay.java	(revision 518)
@@ -0,0 +1,94 @@
+package de.ugoe.cs.quest.assertions;
+
+import java.security.InvalidParameterException;
+
+import de.ugoe.cs.quest.eventcore.IReplayable;
+import de.ugoe.cs.util.StringTools;
+
+/**
+ * <p>
+ * This class defines the replay for a textEquals assertion.
+ * </p>
+ * 
+ * @author Jeffrey Hall, Steffen Herbold
+ * @version 2.0
+ */
+public class TextEqualsReplay implements IReplayable {
+
+	/**
+	 * <p>
+	 * Reference value which is compared to the targets text.
+	 * </p>
+	 */
+	protected final String expectedValue;
+
+	/**
+	 * <p>
+	 * Target to which the text is compared.
+	 * </p>
+	 */
+	protected final String target;
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new TextEqualsReplay.
+	 * 
+	 * @param expectedValue
+	 *            expected string value
+	 * @param target
+	 *            string description of the target whose string value is
+	 *            compared to the expected value
+	 * @throws InvalidParameterException
+	 *             thrown if target is null
+	 */
+	public TextEqualsReplay(String expectedValue, String target) {
+		if (target == null) {
+			throw new InvalidParameterException("target must not be null");
+		}
+		this.expectedValue = expectedValue;
+		this.target = target;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.eventcore.IReplayable#getReplay()
+	 */
+	@Override
+	public String getReplay() {
+
+		String expectedValueTmp = StringTools.xmlEntityReplacement(expectedValue);
+
+		StringBuilder currentMsgStr = new StringBuilder(400);
+		currentMsgStr.append(" <textEquals expectedValue=\"" + expectedValueTmp
+				+ "\">");
+		currentMsgStr.append(StringTools.ENDLINE);
+		currentMsgStr.append("<target>");
+		currentMsgStr.append(StringTools.ENDLINE);
+		currentMsgStr.append(target);
+		currentMsgStr.append(StringTools.ENDLINE);
+		currentMsgStr.append("</target>");
+		currentMsgStr.append(StringTools.ENDLINE);
+		currentMsgStr.append("</textEquals>");
+		currentMsgStr.append(StringTools.ENDLINE);
+		return currentMsgStr.toString();
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.eventcore.IReplayable#getTarget()
+	 */
+	@Override
+	public String getTarget() {
+		return target;
+	}
+
+}
Index: /trunk/quest-core-coverage-test/.classpath
===================================================================
--- /trunk/quest-core-coverage-test/.classpath	(revision 518)
+++ /trunk/quest-core-coverage-test/.classpath	(revision 518)
@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/test-classes" path="src/test/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="src" output="target/classes" path="src/main/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
Index: /trunk/quest-core-coverage-test/.project
===================================================================
--- /trunk/quest-core-coverage-test/.project	(revision 518)
+++ /trunk/quest-core-coverage-test/.project	(revision 518)
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>quest-core-coverage-test</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.eclipse.m2e.core.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.m2e.core.maven2Nature</nature>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
Index: /trunk/quest-core-coverage-test/.settings/org.eclipse.jdt.core.prefs
===================================================================
--- /trunk/quest-core-coverage-test/.settings/org.eclipse.jdt.core.prefs	(revision 518)
+++ /trunk/quest-core-coverage-test/.settings/org.eclipse.jdt.core.prefs	(revision 518)
@@ -0,0 +1,5 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
Index: /trunk/quest-core-coverage-test/.settings/org.eclipse.m2e.core.prefs
===================================================================
--- /trunk/quest-core-coverage-test/.settings/org.eclipse.m2e.core.prefs	(revision 518)
+++ /trunk/quest-core-coverage-test/.settings/org.eclipse.m2e.core.prefs	(revision 518)
@@ -0,0 +1,4 @@
+activeProfiles=
+eclipse.preferences.version=1
+resolveWorkspaceProjects=true
+version=1
Index: /trunk/quest-core-coverage-test/pom.xml
===================================================================
--- /trunk/quest-core-coverage-test/pom.xml	(revision 518)
+++ /trunk/quest-core-coverage-test/pom.xml	(revision 518)
@@ -0,0 +1,150 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>de.ugoe.cs.quest</groupId>
+  <artifactId>quest-core-coverage-test</artifactId>
+  <version>0.0.1-SNAPSHOT</version>
+  <name>quest-core-coverage-test</name>
+<scm>
+    <url>https://quest.informatik.uni-goettingen.de/svn/quest/trunk/quest-core-events-test</url>
+  </scm>
+  <dependencies>
+    <dependency>
+        <groupId>de.ugoe.cs.quest</groupId>
+        <artifactId>quest-core-events</artifactId>
+        <version>0.0.1-SNAPSHOT</version>
+        <scope>test</scope>
+    </dependency>
+    <dependency>
+			<groupId>de.ugoe.cs.quest</groupId>
+			<artifactId>quest-core-usageprofiles-test</artifactId>
+			<version>0.0.1-SNAPSHOT</version>
+			<scope>test</scope>
+		</dependency>
+		<dependency>
+			<groupId>de.ugoe.cs.quest</groupId>
+			<artifactId>quest-core-coverage</artifactId>
+			<version>0.0.1-SNAPSHOT</version>
+			<scope>test</scope>
+		</dependency>
+    <dependency>
+        <groupId>junit</groupId>
+        <artifactId>junit</artifactId>
+        <version>4.8.1</version>
+        <scope>test</scope>
+    </dependency>
+    <!-- <dependency>
+	  <groupId>junit-addons</groupId>
+	  <artifactId>junit-addons</artifactId>
+	  <version>1.4</version>
+    </dependency>
+    <dependency>
+	  <groupId>nl.jqno.equalsverifier</groupId>
+	  <artifactId>equalsverifier</artifactId>
+	  <version>1.1.3</version>
+    </dependency>-->
+  </dependencies>
+  <build>
+    <pluginManagement>
+      <plugins>
+        <plugin>
+          <groupId>org.eclipse.m2e</groupId>
+          <artifactId>lifecycle-mapping</artifactId>
+          <version>1.0.0</version>
+          <configuration>
+            <lifecycleMappingMetadata>
+              <pluginExecutions>
+                <pluginExecution>
+                  <pluginExecutionFilter>
+                    <groupId>org.apache.maven.plugins</groupId>
+                    <artifactId>maven-dependency-plugin</artifactId>
+                    <versionRange>[1.0.0,)</versionRange>
+                    <goals>
+                      <goal>unpack</goal>
+                    </goals>
+                  </pluginExecutionFilter>
+                  <action>
+                    <ignore/>
+                  </action>
+                </pluginExecution>
+                <pluginExecution>
+                  <pluginExecutionFilter>
+                    <groupId>org.codehaus.mojo</groupId>
+                    <artifactId>emma-maven-plugin</artifactId>
+                    <versionRange>[1.0-alpha-3,)</versionRange>
+                    <goals>
+                      <goal>emma</goal>
+                    </goals>
+                  </pluginExecutionFilter>
+                  <action>
+                    <ignore/>
+                  </action>
+                </pluginExecution>
+              </pluginExecutions>
+            </lifecycleMappingMetadata>
+          </configuration>
+        </plugin>
+      </plugins>
+    </pluginManagement>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <version>2.3.2</version>
+        <configuration>
+          <source>1.6</source>
+          <target>1.6</target>
+        </configuration>
+      </plugin>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-dependency-plugin</artifactId>
+        <version>2.4</version>
+        <executions>
+          <execution>
+            <id>unpack</id>
+            <phase>process-classes</phase>
+            <goals>
+              <goal>unpack</goal>
+            </goals>
+            <configuration>
+              <artifactItems>
+                <artifactItem>
+                  <groupId>de.ugoe.cs.quest</groupId>
+                  <artifactId>quest-core-coverage</artifactId>
+                  <version>0.0.1-SNAPSHOT</version>
+                  <outputDirectory>${project.build.directory}/classes</outputDirectory>
+                </artifactItem>
+              </artifactItems>
+            </configuration>
+          </execution>
+        </executions>
+      </plugin>
+      <plugin>
+        <groupId>org.codehaus.mojo</groupId>
+        <artifactId>emma-maven-plugin</artifactId>
+        <version>1.0-alpha-3</version>
+        <inherited>true</inherited>          
+        <executions>
+          <execution>
+            <phase>process-classes</phase>
+            <goals>
+              <goal>emma</goal>
+            </goals>
+          </execution>
+        </executions>
+      </plugin>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-jar-plugin</artifactId>
+        <version>2.3.2</version>
+        <executions>
+          <execution>
+            <goals>
+              <goal>test-jar</goal>
+            </goals>
+          </execution>
+        </executions>
+      </plugin>
+    </plugins>
+  </build>
+</project>
Index: /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/CoverageCalculatorObservedTest.java
===================================================================
--- /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/CoverageCalculatorObservedTest.java	(revision 518)
+++ /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/CoverageCalculatorObservedTest.java	(revision 518)
@@ -0,0 +1,313 @@
+package de.ugoe.cs.quest.coverage;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import de.ugoe.cs.quest.coverage.CoverageCalculatorObserved;
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.MockTrieBasedModel;
+
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import org.junit.*;
+
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>CoverageCalculatorObservedTest</code> contains tests for the
+ * class <code>{@link CoverageCalculatorObserved}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class CoverageCalculatorObservedTest {
+	
+	Collection<List<? extends Event<?>>> sequencesObserved;
+	
+	Set<List<? extends Event<?>>> sequencesCovered;
+	Set<List<? extends Event<?>>> sequencesCovered2;
+	Set<List<? extends Event<?>>> sequencesNewPossible;
+	
+	MockTrieBasedModel mockProcess;
+	
+	@Test
+	public void testCoverageCalculatorObserved_1() throws Exception {
+		int length = 2;
+
+		CoverageCalculatorObserved result = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		assertNotNull(result);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorObserved_2() throws Exception {
+		int length = 2;
+
+		new CoverageCalculatorObserved(null,sequencesCovered, length);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorObserved_3() throws Exception {
+		int length = 2;
+
+		new CoverageCalculatorObserved(sequencesObserved, null, length);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorObserved_4() throws Exception {
+		int length = 0;
+
+		new CoverageCalculatorObserved(sequencesObserved, sequencesCovered, length);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorObserved_5() throws Exception {
+		int length = -1;
+
+		new CoverageCalculatorObserved(sequencesObserved, sequencesCovered, length);
+	}
+	
+	@Test
+	public void testCoverageObserved_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		double result = fixture.getCoverageObserved();
+		
+		assertEquals(3.0/6.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testCoverageObserved_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered2, length);
+		
+		double result = fixture.getCoverageObserved();
+		
+		assertEquals(2.0/6.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testCoverageObservedWeigth_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		double result = fixture.getCoverageObservedWeigth(mockProcess);
+		
+		assertEquals(6.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testCoverageObservedWeigth_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered2, length);
+		
+		double result = fixture.getCoverageObservedWeigth(mockProcess);
+		
+		assertEquals(4.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testGetNewPercentage_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		double result = fixture.getNewPercentage();
+		
+		assertEquals(1.0/4.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testGetNewPercentage_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered2, length);
+		
+		double result = fixture.getNewPercentage();
+		
+		assertEquals(0.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testCoveragePossibleNew_1() throws Exception {
+		int length = 3;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesNewPossible, length);
+		
+		double result = fixture.getCoveragePossibleNew(mockProcess);
+		
+		assertEquals(1.0/11.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testCoveragePossibleNew_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		double result = fixture.getCoveragePossibleNew(mockProcess);
+		
+		assertEquals(0.0, result, 0.0001);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class ) 
+	public void testCoveragePossibleNew_3() throws Exception {
+		int length = 3;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		fixture.getCoveragePossibleNew(null);
+	}
+	
+	@Test
+	public void testCoveragePossibleNewWeight_1() throws Exception {
+		int length = 3;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesNewPossible, length);
+		
+		double result = fixture.getCoveragePossibleNewWeight(mockProcess);
+		
+		assertEquals(2.0, result, 0.0001);
+	}
+	
+	@Test
+	public void testCoveragePossibleNewWeight_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		double result = fixture.getCoveragePossibleNewWeight(mockProcess);
+		
+		assertEquals(0.0, result, 0.0001);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class ) 
+	public void testCoveragePossibleNewWeight_3() throws Exception {
+		int length = 3;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		fixture.getCoveragePossibleNewWeight(null);
+	}	
+	
+	
+	@Test
+	public void testGetNumObserved_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		int result = fixture.getNumObserved();
+		
+		assertEquals(6, result);
+	}
+	
+	@Test
+	public void testGetNumCovered_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		int result = fixture.getNumCovered();
+		
+		assertEquals(4, result);
+	}
+	
+	@Test
+	public void testGetNumCovered_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered2, length);
+		
+		int result = fixture.getNumCovered();
+		
+		assertEquals(2, result);
+	}
+	
+	@Test
+	public void testGetNumNew_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered, length);
+		
+		int result = fixture.getNumNew();
+		
+		assertEquals(1, result);
+	}
+	
+	@Test
+	public void testGetNumNew_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorObserved fixture = new CoverageCalculatorObserved(
+				sequencesObserved, sequencesCovered2, length);
+		
+		int result = fixture.getNumNew();
+		
+		assertEquals(0, result);
+	}
+	
+	@Before
+	public void setUp() throws Exception {
+		sequencesObserved = new LinkedList<List<? extends Event<?>>>();
+		List<Event<?>> sequence1 = new ArrayList<Event<?>>();
+		sequence1.add(new Event<String>("a"));
+		sequence1.add(new Event<String>("b"));
+		sequence1.add(new Event<String>("r"));
+		sequence1.add(new Event<String>("a"));
+		List<Event<?>> sequence2 = new ArrayList<Event<?>>();
+		sequence2.add(new Event<String>("c"));
+		sequence2.add(new Event<String>("a"));
+		sequence2.add(new Event<String>("d"));
+		sequence2.add(new Event<String>("a"));
+		sequence2.add(new Event<String>("b"));
+		sequence2.add(new Event<String>("r"));
+		sequence2.add(new Event<String>("a"));
+		sequencesObserved.add(sequence1);
+		sequencesObserved.add(sequence2);
+
+		sequencesCovered = new LinkedHashSet<List<? extends Event<?>>>();
+		List<Event<?>> tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("b"));
+		tmpList.add(new Event<String>("r"));
+		sequencesCovered.add(tmpList);
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("b"));
+		tmpList.add(new Event<String>("r"));
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("e"));
+		sequencesCovered.add(tmpList);
+
+		sequencesCovered2 = new LinkedHashSet<List<? extends Event<?>>>();
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("b"));
+		tmpList.add(new Event<String>("r"));
+		sequencesCovered2.add(tmpList);
+		
+		sequencesNewPossible = new LinkedHashSet<List<? extends Event<?>>>();
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("r"));
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("b"));
+		sequencesNewPossible.add(tmpList);
+		
+		int markovOrder = 2;
+		mockProcess = new MockTrieBasedModel(markovOrder, new Random());
+		mockProcess.train(sequencesObserved);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore()
+				.run(CoverageCalculatorObservedTest.class);
+	}
+
+}
Index: /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/CoverageCalculatorProcessTest.java
===================================================================
--- /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/CoverageCalculatorProcessTest.java	(revision 518)
+++ /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/CoverageCalculatorProcessTest.java	(revision 518)
@@ -0,0 +1,236 @@
+package de.ugoe.cs.quest.coverage;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import de.ugoe.cs.quest.coverage.CoverageCalculatorProcess;
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.MockTrieBasedModel;
+
+import org.junit.*;
+
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>CoverageCalculatorProcessTest</code> contains tests for the
+ * class <code>{@link CoverageCalculatorProcess}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class CoverageCalculatorProcessTest {
+
+	Set<List<? extends Event<?>>> sequencesCovered;
+	Set<List<? extends Event<?>>> sequencesCovered2;
+	MockTrieBasedModel mockProcess;
+
+	@Test
+	public void testCoverageCalculatorProcess_1() throws Exception {
+		int length = 2;
+
+		CoverageCalculatorProcess result = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+		assertNotNull(result);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorProcess_2() throws Exception {
+		int length = 2;
+
+		new CoverageCalculatorProcess(null,sequencesCovered, length);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorProcess_3() throws Exception {
+		int length = 2;
+
+		new CoverageCalculatorProcess(mockProcess, null, length);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorProcess_4() throws Exception {
+		int length = 0;
+
+		new CoverageCalculatorProcess(mockProcess, sequencesCovered, length);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testCoverageCalculatorProcess_5() throws Exception {
+		int length = -1;
+
+		new CoverageCalculatorProcess(mockProcess, sequencesCovered, length);
+	}
+
+	@Test
+	public void testGetCoverageAllNoWeight_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+
+		double result = fixture.getCoverageAllNoWeight();
+
+		assertEquals(3.0 / 49.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetCoverageAllNoWeight_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered2, length);
+
+		double result = fixture.getCoverageAllNoWeight();
+
+		assertEquals(2.0 / 49.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetCoveragePossibleNoWeight_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+
+		double result = fixture.getCoveragePossibleNoWeight();
+
+		assertEquals(3.0 / 9.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetCoveragePossibleNoWeight_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered2, length);
+
+		double result = fixture.getCoveragePossibleNoWeight();
+
+		assertEquals(2.0 / 9.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetCoveragePossibleWeight_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+
+		double result = fixture.getCoveragePossibleWeight();
+
+		assertEquals(6.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetCoveragePossibleWeight_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered2, length);
+
+		double result = fixture.getCoveragePossibleWeight();
+
+		assertEquals(4.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetNumCovered_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+
+		int result = fixture.getNumCovered();
+
+		assertEquals(3, result);
+	}
+
+	@Test
+	public void testGetNumCovered_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered2, length);
+
+		int result = fixture.getNumCovered();
+
+		assertEquals(2, result);
+	}
+
+	@Test
+	public void testGetNumPossible_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+
+		int result = fixture.getNumPossible();
+
+		assertEquals(9, result);
+	}
+
+	@Test
+	public void testSetSequences_1() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+
+		fixture.setSequences(sequencesCovered2);
+
+		// testing indirectly if sequences were changed
+		assertEquals(2, fixture.getNumCovered());
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testSetSequences_2() throws Exception {
+		int length = 2;
+		CoverageCalculatorProcess fixture = new CoverageCalculatorProcess(
+				mockProcess, sequencesCovered, length);
+
+		fixture.setSequences(null);
+	}
+
+	@Before
+	public void setUp() throws Exception {
+		Collection<List<? extends Event<?>>> sequences = new LinkedList<List<? extends Event<?>>>();
+		List<Event<?>> sequence1 = new ArrayList<Event<?>>();
+		sequence1.add(new Event<String>("a"));
+		sequence1.add(new Event<String>("b"));
+		sequence1.add(new Event<String>("r"));
+		sequence1.add(new Event<String>("a"));
+		List<Event<?>> sequence2 = new ArrayList<Event<?>>();
+		sequence2.add(new Event<String>("c"));
+		sequence2.add(new Event<String>("a"));
+		sequence2.add(new Event<String>("d"));
+		sequence2.add(new Event<String>("a"));
+		sequence2.add(new Event<String>("b"));
+		sequence2.add(new Event<String>("r"));
+		sequence2.add(new Event<String>("a"));
+		sequences.add(sequence1);
+		sequences.add(sequence2);
+
+		sequencesCovered = new LinkedHashSet<List<? extends Event<?>>>();
+		List<Event<?>> tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("b"));
+		tmpList.add(new Event<String>("r"));
+		sequencesCovered.add(tmpList);
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("b"));
+		tmpList.add(new Event<String>("r"));
+		tmpList.add(new Event<String>("a"));
+		sequencesCovered.add(tmpList);
+
+		sequencesCovered2 = new LinkedHashSet<List<? extends Event<?>>>();
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("b"));
+		tmpList.add(new Event<String>("r"));
+		sequencesCovered2.add(tmpList);
+
+		int markovOrder = 2;
+		mockProcess = new MockTrieBasedModel(markovOrder, new Random());
+		mockProcess.train(sequences);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore()
+				.run(CoverageCalculatorProcessTest.class);
+	}
+}
Index: /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/SequenceToolsTest.java
===================================================================
--- /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/SequenceToolsTest.java	(revision 518)
+++ /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/SequenceToolsTest.java	(revision 518)
@@ -0,0 +1,201 @@
+package de.ugoe.cs.quest.coverage;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Random;
+import java.util.Set;
+import de.ugoe.cs.quest.coverage.SequenceTools;
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.FirstOrderMarkovModel;
+import de.ugoe.cs.quest.usageprofiles.IStochasticProcess;
+import de.ugoe.cs.quest.usageprofiles.MockTrieBasedModel;
+
+import org.junit.*;
+
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>SequenceToolsTest</code> contains tests for the class <code>{@link SequenceTools}</code>.
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class SequenceToolsTest {
+	
+	Collection<List<? extends Event<?>>> sequences;
+	Set<List<? extends Event<?>>> subSequences;
+	MockTrieBasedModel mockProcess;
+	
+	@Test
+	public void testContainedSubSequences_1()
+		throws Exception {
+		int length = 2;
+
+		Set<List<? extends Event<?>>> result = SequenceTools.containedSubSequences(sequences, length);
+
+		assertNotNull(result);
+		assertTrue(result.containsAll(subSequences));
+		assertEquals(subSequences.size(), result.size());
+	}
+	
+	@Test
+	public void testContainedSubSequences_2()
+		throws Exception {
+		int length = 2;
+
+		Set<List<? extends Event<?>>> result = SequenceTools.containedSubSequences(null, length);
+		assertNotNull(result);
+		assertTrue(result.isEmpty());
+	}
+	
+	@Test(expected=java.security.InvalidParameterException.class)
+	public void testContainedSubSequences_3()
+		throws Exception {
+		int length = 0;
+
+		SequenceTools.containedSubSequences(sequences, length);
+	}
+	
+	@Test(expected=java.security.InvalidParameterException.class)
+	public void testContainedSubSequences_4()
+		throws Exception {
+		int length = -1;
+
+		SequenceTools.containedSubSequences(sequences, length);
+	}
+
+	@Test
+	public void testGenerateWeights_1()
+		throws Exception {
+		Map<List<? extends Event<?>>, Double> result = SequenceTools.generateWeights(mockProcess, subSequences);
+
+		assertNotNull(result);
+		Set<Entry<List<? extends Event<?>>, Double>> entrySet = result.entrySet();
+		assertEquals(subSequences.size(),entrySet.size());
+		for( Entry<List<? extends Event<?>>, Double> entry : entrySet ) {
+			assertEquals(Double.valueOf(2.0d), entry.getValue());
+			assertTrue(subSequences.contains(entry.getKey()));
+		}
+	}
+	
+	@Test
+	public void testGenerateWeights_2()
+		throws Exception {
+		Map<List<? extends Event<?>>, Double> result = SequenceTools.generateWeights(null, subSequences);
+		
+		Set<Entry<List<? extends Event<?>>, Double>> entrySet = result.entrySet();
+		assertEquals(subSequences.size(),entrySet.size());
+		for( Entry<List<? extends Event<?>>, Double> entry : entrySet ) {
+			assertEquals(Double.valueOf(0.0d), entry.getValue());
+			assertTrue(subSequences.contains(entry.getKey()));
+		}
+	}
+	
+	@Test
+	public void testGenerateWeights_3()
+		throws Exception {
+		Map<List<? extends Event<?>>, Double> result = SequenceTools.generateWeights(mockProcess, null);
+		
+		assertNotNull(result);
+		assertTrue(result.isEmpty());
+	}
+
+	@Test
+	public void testNumSequences_1()
+		throws Exception {
+		int length = 2;
+		int expected = 49;
+
+		long result = SequenceTools.numSequences(mockProcess, length);
+
+		assertEquals(expected, result);
+	}
+	
+	@Test
+	public void testNumSequences_2()
+		throws Exception {
+		int length = 2;
+		int expected = 49;
+
+		long result = SequenceTools.numSequences(mockProcess, length);
+
+		assertEquals(expected, result);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class )
+	public void testNumSequences_3()
+		throws Exception {
+		int length = 0;
+
+		SequenceTools.numSequences(mockProcess, length);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class )
+	public void testNumSequences_4()
+		throws Exception {
+		IStochasticProcess process = new FirstOrderMarkovModel(new Random());
+		int length = -1;
+
+		SequenceTools.numSequences(process, length);
+	}
+	
+	@Before
+	public void setUp()
+		throws Exception {
+		sequences = new LinkedList<List<? extends Event<?>>>();
+		List<Event<?>> sequence1 = new ArrayList<Event<?>>();
+		sequence1.add(new Event<String>("a"));
+		sequence1.add(new Event<String>("b"));
+		sequence1.add(new Event<String>("r"));
+		sequence1.add(new Event<String>("a"));
+		List<Event<?>> sequence2 = new ArrayList<Event<?>>();
+		sequence2.add(new Event<String>("c"));
+		sequence2.add(new Event<String>("a"));
+		sequence2.add(new Event<String>("d"));
+		sequence2.add(new Event<String>("a"));
+		sequence2.add(new Event<String>("b"));
+		sequence2.add(new Event<String>("r"));
+		sequence2.add(new Event<String>("a"));
+		sequences.add(sequence1);
+		sequences.add(sequence2);
+		
+		subSequences = new LinkedHashSet<List<? extends Event<?>>>();
+		List<Event<?>> tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("b"));
+		subSequences.add(tmpList);
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("b"));
+		tmpList.add(new Event<String>("r"));
+		subSequences.add(tmpList);
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("r"));
+		tmpList.add(new Event<String>("a"));
+		subSequences.add(tmpList);
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("c"));
+		tmpList.add(new Event<String>("a"));
+		subSequences.add(tmpList);
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("a"));
+		tmpList.add(new Event<String>("d"));
+		subSequences.add(tmpList);
+		tmpList = new ArrayList<Event<?>>();
+		tmpList.add(new Event<String>("d"));
+		tmpList.add(new Event<String>("a"));
+		subSequences.add(tmpList);
+		
+		int markovOrder = 2;
+		mockProcess = new MockTrieBasedModel(markovOrder, new Random());
+		mockProcess.train(sequences);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(SequenceToolsTest.class);
+	}
+}
Index: /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/TestAll.java
===================================================================
--- /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/TestAll.java	(revision 518)
+++ /trunk/quest-core-coverage-test/src/test/java/de/ugoe/cs/quest/coverage/TestAll.java	(revision 518)
@@ -0,0 +1,26 @@
+package de.ugoe.cs.quest.coverage;
+
+import org.junit.runner.JUnitCore;
+import org.junit.runner.RunWith;
+import org.junit.runners.Suite;
+
+/**
+ * The class <code>TestAll</code> builds a suite that can be used to run all
+ * of the tests within its package as well as within any subpackages of its
+ * package.
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+@RunWith(Suite.class)
+@Suite.SuiteClasses({
+	CoverageCalculatorObservedTest.class,
+	CoverageCalculatorProcessTest.class,
+	SequenceToolsTest.class
+})
+public class TestAll {
+
+	public static void main(String[] args) {
+		JUnitCore.runClasses(new Class[] { TestAll.class });
+	}
+}
Index: /trunk/quest-core-coverage/.classpath
===================================================================
--- /trunk/quest-core-coverage/.classpath	(revision 518)
+++ /trunk/quest-core-coverage/.classpath	(revision 518)
@@ -0,0 +1,20 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/classes" path="src/main/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
Index: /trunk/quest-core-coverage/.project
===================================================================
--- /trunk/quest-core-coverage/.project	(revision 518)
+++ /trunk/quest-core-coverage/.project	(revision 518)
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>quest-core-coverage</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.eclipse.m2e.core.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.m2e.core.maven2Nature</nature>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
Index: /trunk/quest-core-coverage/.settings/org.eclipse.jdt.core.prefs
===================================================================
--- /trunk/quest-core-coverage/.settings/org.eclipse.jdt.core.prefs	(revision 518)
+++ /trunk/quest-core-coverage/.settings/org.eclipse.jdt.core.prefs	(revision 518)
@@ -0,0 +1,5 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
Index: /trunk/quest-core-coverage/.settings/org.eclipse.m2e.core.prefs
===================================================================
--- /trunk/quest-core-coverage/.settings/org.eclipse.m2e.core.prefs	(revision 518)
+++ /trunk/quest-core-coverage/.settings/org.eclipse.m2e.core.prefs	(revision 518)
@@ -0,0 +1,4 @@
+activeProfiles=
+eclipse.preferences.version=1
+resolveWorkspaceProjects=true
+version=1
Index: /trunk/quest-core-coverage/pom.xml
===================================================================
--- /trunk/quest-core-coverage/pom.xml	(revision 518)
+++ /trunk/quest-core-coverage/pom.xml	(revision 518)
@@ -0,0 +1,34 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>de.ugoe.cs.quest</groupId>
+  <artifactId>quest-core-coverage</artifactId>
+  <version>0.0.1-SNAPSHOT</version>
+  <name>quest-core-coverage</name>
+  <scm>
+		<url>https://quest.informatik.uni-goettingen.de/svn/quest/trunk/quest-core-coverage</url>
+	</scm>
+  	<dependencies>
+		<dependency>
+			<groupId>de.ugoe.cs.quest</groupId>
+			<artifactId>quest-core-events</artifactId>
+			<version>0.0.1-SNAPSHOT</version>
+		</dependency>
+		<dependency>
+			<groupId>de.ugoe.cs.quest</groupId>
+			<artifactId>quest-core-usageprofiles</artifactId>
+			<version>0.0.1-SNAPSHOT</version>
+		</dependency>
+	</dependencies>
+	<build>
+		<plugins>
+			<plugin>
+				<artifactId>maven-compiler-plugin</artifactId>
+				<version>2.3.2</version>
+				<configuration>
+					<source>1.6</source>
+					<target>1.6</target>
+				</configuration>
+			</plugin>
+		</plugins>
+	</build>
+</project>
Index: /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorObserved.java
===================================================================
--- /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorObserved.java	(revision 518)
+++ /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorObserved.java	(revision 518)
@@ -0,0 +1,272 @@
+package de.ugoe.cs.quest.coverage;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.IStochasticProcess;
+
+/**
+ * <p>
+ * This class calculates various types of sequence coverage in relation to a
+ * collection of observed sequences.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class CoverageCalculatorObserved {
+
+	/**
+	 * <p>
+	 * Sequences for which the coverage is calculated.
+	 * </p>
+	 */
+	private final Collection<List<? extends Event<?>>> sequences;
+
+	/**
+	 * <p>
+	 * Observed sequences that are baseline for the coverage calculation.
+	 * </p>
+	 */
+	private final Collection<List<? extends Event<?>>> observedSequences;
+
+	/**
+	 * <p>
+	 * Length of the subsequences in relation to which the covarage is
+	 * calculated.
+	 * </p>
+	 */
+	private final int length;
+
+	/**
+	 * <p>
+	 * All subsequences of {@link #length} of {@link #sequences}.
+	 * </p>
+	 */
+	private Collection<List<? extends Event<?>>> subSeqsGenerated = null;
+
+	/**
+	 * <p>
+	 * All subsequences of {@link #length} of {@link #observedSequences}.
+	 * </p>
+	 */
+	private Collection<List<? extends Event<?>>> subSeqsObserved = null;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new CoverageCalculatorObserved for given
+	 * collections of observed sequences and generated sequences.
+	 * </p>
+	 * 
+	 * @param observedSequences
+	 *            observed sequences in relation to which the coverage is
+	 *            calculated; must not be null
+	 * @param sequences
+	 *            sequences for which the coverage is calculated; must not be
+	 *            null
+	 * @param length
+	 *            length of the subsequences for which the coverage is analyzed;
+	 *            must be >0
+	 * @throws InvalidParameterException
+	 *             thrown if observedSequences or sequences is null or length
+	 *             less than or equal to 0
+	 */
+	public CoverageCalculatorObserved(
+			Collection<List<? extends Event<?>>> observedSequences,
+			Collection<List<? extends Event<?>>> sequences, int length) {
+		if (observedSequences == null) {
+			throw new InvalidParameterException(
+					"observed sequences must not be null");
+		}
+		if (sequences == null) {
+			throw new InvalidParameterException("sequences must not be null");
+		}
+		if (length <= 0) {
+			throw new InvalidParameterException(
+					"length must be >0; actual value: " + length);
+		}
+		this.observedSequences = observedSequences;
+		this.sequences = sequences;
+		this.length = length;
+	}
+
+	/**
+	 * <p>
+	 * Calculates the percentage of subsequences of length k that occur, with
+	 * reference to those that were observed.
+	 * </p>
+	 * 
+	 * @return coverage percentage
+	 */
+	public double getCoverageObserved() {
+		createSubSeqs();
+		Collection<List<? extends Event<?>>> subSeqsObservedCopy = new LinkedHashSet<List<? extends Event<?>>>(
+				subSeqsObserved);
+		subSeqsObservedCopy.retainAll(subSeqsGenerated);
+		return ((double) subSeqsObservedCopy.size()) / subSeqsObserved.size();
+	}
+
+	/**
+	 * <p>
+	 * Calculates the weight of subsequences of length k that occur, with
+	 * reference to those that were observed.
+	 * </p>
+	 * 
+	 * @param process
+	 *            stochastic process in reference to which the weight is
+	 *            calculated
+	 * @return coverage percentage
+	 */
+
+	public double getCoverageObservedWeigth(IStochasticProcess process) {
+		createSubSeqs();
+		Map<List<? extends Event<?>>, Double> weightMap = SequenceTools
+				.generateWeights(process, subSeqsObserved);
+
+		Collection<List<? extends Event<?>>> subSeqsObservedCopy = new LinkedHashSet<List<? extends Event<?>>>(
+				subSeqsObserved);
+		subSeqsObservedCopy.retainAll(subSeqsGenerated);
+		double weight = 0.0d;
+		for (List<? extends Event<?>> subSeq : subSeqsObservedCopy) {
+			weight += weightMap.get(subSeq);
+		}
+		return weight;
+	}
+
+	/**
+	 * <p>
+	 * Calculates the percentage of generated subsequences of length k that
+	 * occur and have not been observed, with reference to all generated
+	 * subsequences.
+	 * </p>
+	 * 
+	 * @return coverage percentage
+	 */
+	public double getNewPercentage() {
+		createSubSeqs();
+		Collection<List<? extends Event<?>>> subSeqsGeneratedCopy = new LinkedHashSet<List<? extends Event<?>>>(
+				subSeqsGenerated);
+		subSeqsGeneratedCopy.removeAll(subSeqsObserved);
+		return ((double) subSeqsGeneratedCopy.size()) / subSeqsGenerated.size();
+	}
+
+	/**
+	 * <p>
+	 * Calculates the percentage of generated subsequences of length k that
+	 * occur and have not been observed, with references to all possible new
+	 * subsequences.
+	 * </p>
+	 * 
+	 * @param process
+	 *            stochastic process which is used to determine which
+	 *            subsequences are possible
+	 * @return coverage percentage
+	 * @throws InvalidParameterException
+	 *             thrown if process is null
+	 */
+	public double getCoveragePossibleNew(IStochasticProcess process) {
+		if (process == null) {
+			throw new InvalidParameterException("process must not be null");
+		}
+		createSubSeqs();
+		Collection<List<? extends Event<?>>> subSeqsGeneratedCopy = new LinkedHashSet<List<? extends Event<?>>>(
+				subSeqsGenerated);
+		Collection<List<? extends Event<?>>> subSeqsPossible = process
+				.generateSequences(length);
+		subSeqsGeneratedCopy.removeAll(subSeqsObserved);
+		subSeqsPossible.removeAll(subSeqsObserved);
+		int possibleSize = subSeqsPossible.size();
+		subSeqsPossible.retainAll(subSeqsGeneratedCopy);
+		return ((double) subSeqsPossible.size()) / possibleSize;
+	}
+
+	/**
+	 * <p>
+	 * Calculates the weight of generated subsequences of length k that occur
+	 * and have not been observed, with references to all possible new
+	 * subsequences.
+	 * </p>
+	 * 
+	 * @param process
+	 *            stochastic process which is used to determine the weights and
+	 *            which subsequences are possible
+	 * @return coverage percentage
+	 * @throws InvalidParameterException
+	 *             thrown if process is null
+	 */
+	public double getCoveragePossibleNewWeight(IStochasticProcess process) {
+		if (process == null) {
+			throw new InvalidParameterException("process must not be null");
+		}
+		createSubSeqs();
+		Collection<List<? extends Event<?>>> subSeqsGeneratedCopy = new LinkedHashSet<List<? extends Event<?>>>(
+				subSeqsGenerated);
+		Collection<List<? extends Event<?>>> subSeqsPossible = process
+				.generateSequences(length);
+		subSeqsGeneratedCopy.removeAll(subSeqsObserved);
+		subSeqsPossible.removeAll(subSeqsObserved);
+		Map<List<? extends Event<?>>, Double> weightMap = SequenceTools
+				.generateWeights(process, subSeqsPossible);
+		double weight = 0.0d;
+		for (List<? extends Event<?>> subSeq : subSeqsGeneratedCopy) {
+			Double currentWeight = weightMap.get(subSeq);
+			if( currentWeight!=null ) {
+				weight += currentWeight;
+			}
+		}
+		return weight;
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of covered subsequences of length k.
+	 * </p>
+	 * 
+	 * @return number of covered subsequences
+	 */
+	public int getNumObserved() {
+		createSubSeqs();
+		return subSeqsObserved.size();
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of covered subsequences of length k.
+	 * </p>
+	 * 
+	 * @return number of covered subsequences
+	 */
+	public int getNumCovered() {
+		createSubSeqs();
+		return subSeqsGenerated.size();
+	}
+
+	public int getNumNew() {
+		createSubSeqs();
+		Collection<List<? extends Event<?>>> subSeqsGeneratedCopy = new LinkedHashSet<List<? extends Event<?>>>(
+				subSeqsGenerated);
+		subSeqsGeneratedCopy.removeAll(subSeqsObserved);
+		return subSeqsGeneratedCopy.size();
+	}
+
+	/**
+	 * <p>
+	 * Helper function that calcuates the subsequences of length k that have
+	 * been observed and generated.
+	 * </p>
+	 */
+	private void createSubSeqs() {
+		if (subSeqsObserved == null) {
+			subSeqsObserved = SequenceTools.containedSubSequences(
+					observedSequences, length);
+		}
+		if (subSeqsGenerated == null) {
+			subSeqsGenerated = SequenceTools.containedSubSequences(sequences,
+					length);
+		}
+	}
+}
Index: /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorProcess.java
===================================================================
--- /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorProcess.java	(revision 518)
+++ /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/CoverageCalculatorProcess.java	(revision 518)
@@ -0,0 +1,218 @@
+package de.ugoe.cs.quest.coverage;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.IStochasticProcess;
+
+/**
+ * <p>
+ * This class calculates various types of sequence coverage in relation to a
+ * stochastic process.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class CoverageCalculatorProcess {
+
+	/**
+	 * <p>
+	 * Stochastic process that is the foundation for probabilistic coverages and
+	 * coverages with reference to all possible sequences.
+	 * </p>
+	 */
+	private final IStochasticProcess process;
+
+	/**
+	 * <p>
+	 * Sequences for which the coverage is calculated.
+	 * </p>
+	 */
+	private Collection<List<? extends Event<?>>> sequences;
+
+	/**
+	 * <p>
+	 * Length of the subsequences in relation to which the coverage is
+	 * calculated.
+	 * </p>
+	 */
+	private final int length;
+
+	/**
+	 * <p>
+	 * All subsequences of {@link #length} of {@link #sequences}.
+	 * </p>
+	 */
+	private Collection<List<? extends Event<?>>> containedSubSeqs = null;
+
+	/**
+	 * <p>
+	 * All subsequences of {@link #length} that can be generated by
+	 * {@link #process}.
+	 * </p>
+	 */
+	private Collection<List<? extends Event<?>>> allPossibleSubSeqs = null;
+
+	/**
+	 * <p>
+	 * The probabilities of all subsequences of {@link #length} according to
+	 * {@link #process}.
+	 * </p>
+	 */
+	private Map<List<? extends Event<?>>, Double> subSeqWeights = null;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new CoverageCalculatorProcess for a given
+	 * stochastic process and generated sequences.
+	 * </p>
+	 * 
+	 * @param process
+	 *            stochastic process used for coverage calculations; must not be
+	 *            null
+	 * @param sequences
+	 *            sequences for which the coverage is calculated; must not be
+	 *            null
+	 * @param length
+	 *            length of the subsequences for which the coverage is analyzed;
+	 *            must be >0
+	 * @throws InvalidParameterException
+	 *             thrown if process or sequences is null or length less than or equal to 0
+	 */
+	public CoverageCalculatorProcess(IStochasticProcess process,
+			Collection<List<? extends Event<?>>> sequences, int length) {
+		if (process == null) {
+			throw new InvalidParameterException("process must not be null");
+		}
+		if (sequences == null) {
+			throw new InvalidParameterException("sequences must not be null");
+		}
+		if (length <= 0) {
+			throw new InvalidParameterException(
+					"length must be >0; actual value: " + length);
+		}
+		this.process = process;
+		this.sequences = sequences;
+		this.length = length;
+	}
+
+	/**
+	 * <p>
+	 * Calculates the percentage of subsequences of length k that occur,
+	 * including those that cannot be generated by {@link #process}.
+	 * </p>
+	 * 
+	 * @return coverage percentage
+	 */
+	public double getCoverageAllNoWeight() {
+		if (containedSubSeqs == null) {
+			containedSubSeqs = SequenceTools.containedSubSequences(sequences,
+					length);
+		}
+		return ((double) containedSubSeqs.size())
+				/ SequenceTools.numSequences(process, length);
+	}
+
+	/**
+	 * <p>
+	 * Calculates the percentage of subsequences of length k that occur and can
+	 * generated by {@link #process}.
+	 * </p>
+	 * 
+	 * @return coverage percentage
+	 */
+	public double getCoveragePossibleNoWeight() {
+		if (containedSubSeqs == null) {
+			containedSubSeqs = SequenceTools.containedSubSequences(sequences,
+					length);
+		}
+		if (allPossibleSubSeqs == null) {
+			allPossibleSubSeqs = process.generateSequences(length);
+		}
+		return ((double) containedSubSeqs.size()) / allPossibleSubSeqs.size();
+	}
+
+	/**
+	 * <p>
+	 * Calculates the weight of the subsequences that occur with relation to
+	 * {@link #process}, i.e., the mass of the subsequence probability covered
+	 * by the subsequences.
+	 * </p>
+	 * 
+	 * @return coverage weight
+	 */
+	public double getCoveragePossibleWeight() {
+		if (containedSubSeqs == null) {
+			containedSubSeqs = SequenceTools.containedSubSequences(sequences,
+					length);
+		}
+		if (allPossibleSubSeqs == null) {
+			allPossibleSubSeqs = process.generateSequences(length);
+		}
+		if (subSeqWeights == null) {
+			subSeqWeights = SequenceTools.generateWeights(process,
+					allPossibleSubSeqs);
+		}
+		double weight = 0.0;
+		for (List<? extends Event<?>> subSeq : containedSubSeqs) {
+			Double curWeight = subSeqWeights.get(subSeq);
+			if( curWeight!=null ) {
+				weight += curWeight;
+			}
+		}
+		return weight;
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of covered subsequences of length k.
+	 * </p>
+	 * 
+	 * @return number of covered subsequences
+	 */
+	public int getNumCovered() {
+		if (containedSubSeqs == null) {
+			containedSubSeqs = SequenceTools.containedSubSequences(sequences,
+					length);
+		}
+		return containedSubSeqs.size();
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of possible subsequences of length k according to the
+	 * stochastic process.
+	 * </p>
+	 * 
+	 * @return number of possible subsequences
+	 */
+	public int getNumPossible() {
+		if (allPossibleSubSeqs == null) {
+			allPossibleSubSeqs = process.generateSequences(length);
+		}
+		return allPossibleSubSeqs.size();
+	}
+
+	/**
+	 * <p>
+	 * Sets a new collection of sequences for which the coverage is analyzed.
+	 * </p>
+	 * 
+	 * @param newSequences
+	 *            new collection of sequences
+	 * @throws InvalidParameterException
+	 *             thrown is newSequences is null
+	 */
+	public void setSequences(Collection<List<? extends Event<?>>> newSequences) {
+		if (newSequences == null) {
+			throw new InvalidParameterException("sequences must not be null");
+		}
+		this.sequences = newSequences;
+		containedSubSeqs = null;
+	}
+
+}
Index: /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/SequenceTools.java
===================================================================
--- /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/SequenceTools.java	(revision 518)
+++ /trunk/quest-core-coverage/src/main/java/de/ugoe/cs/quest/coverage/SequenceTools.java	(revision 518)
@@ -0,0 +1,147 @@
+package de.ugoe.cs.quest.coverage;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.IStochasticProcess;
+
+/**
+ * <p>
+ * This class gathers some helper functions to work with sequences.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class SequenceTools {
+	
+	/**
+	 * <p>
+	 * Private constructor to prevent initializing of the class.
+	 * </p>
+	 */
+	private SequenceTools() {
+		
+	}
+
+	/**
+	 * <p>
+	 * Calculates the weights for all sequences passed to this function as
+	 * defined by the stochastic process and stores them in a {@link Map}. The
+	 * weights are normalized, i.e., the sum of all weights contained in this
+	 * map is 1.
+	 * </p>
+	 * 
+	 * @param process
+	 *            process used for weight calculation
+	 * @param sequences
+	 *            sequences for which the weights are calculated
+	 * @return {@link Map} of weights
+	 */
+	public static Map<List<? extends Event<?>>, Double> generateWeights(
+			IStochasticProcess process,
+			Collection<List<? extends Event<?>>> sequences) {
+		Map<List<? extends Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<? extends Event<?>>, Double>();
+		if (sequences != null && !sequences.isEmpty()) {
+			if (process != null) {
+				double sum = 0.0;
+				for (List<? extends Event<?>> sequence : sequences) {
+					double prob = process.getProbability(sequence);
+					subSeqWeights.put(sequence, prob);
+					sum += prob;
+				}
+				if (sum < 1.0) {
+					for (Map.Entry<List<? extends Event<?>>, Double> entry : subSeqWeights
+							.entrySet()) {
+						entry.setValue(entry.getValue() / sum);
+					}
+				}
+			} else {
+				for( List<? extends Event<?>> sequence : sequences ) {
+					subSeqWeights.put(sequence, 0.0d);
+				}
+			}
+		}
+		return subSeqWeights;
+	}
+
+	/**
+	 * <p>
+	 * Calculates the number of all existing sequences of a given length,
+	 * regardless whether they are possible or not.
+	 * </p>
+	 * 
+	 * @param process
+	 *            stochastic process whose symbols are the basis for this
+	 *            calculation
+	 * @param length
+	 *            lenght of the sequences
+	 * @return numStates^length
+	 * @throws InvalidParameterException
+	 *             thrown if length less or equal to 0
+	 */
+	public static long numSequences(IStochasticProcess process, int length) {
+		if (length <= 0) {
+			throw new InvalidParameterException(
+					"length must be a positive integer");
+		}
+		long result = 0;
+		if (process != null) {
+			result = (long) Math.pow(process.getNumSymbols(), length);
+		}
+		return result;
+	}
+
+	/**
+	 * <p>
+	 * Creates a {@link Set} of all subsequences of a given length that are
+	 * contained in a sequence collection.
+	 * </p>
+	 * 
+	 * @param sequences
+	 *            sequences from which the subsequences are extracted
+	 * @param length
+	 *            length of the subsequences
+	 * @return {@link Set} of all subsequences
+	 * @throws InvalidParameterException
+	 *             thrown if length less or equal to 0
+	 */
+	public static Set<List<? extends Event<?>>> containedSubSequences(
+			Collection<List<? extends Event<?>>> sequences, int length) {
+		if (length <= 0) {
+			throw new InvalidParameterException(
+					"length must be a positive integer");
+		}
+		Set<List<? extends Event<?>>> containedSubSeqs = new LinkedHashSet<List<? extends Event<?>>>();
+		if (sequences != null) {
+			for (List<? extends Event<?>> sequence : sequences) {
+				List<Event<?>> subSeq = new LinkedList<Event<?>>();
+				boolean minLengthReached = false;
+				for (Event<?> event : sequence) {
+					subSeq.add(event);
+					if (!minLengthReached) {
+						if (subSeq.size() == length) {
+							minLengthReached = true;
+						}
+					} else {
+						subSeq.remove(0);
+					}
+					if (minLengthReached) {
+						if (!containedSubSeqs.contains(subSeq)) {
+							containedSubSeqs.add(new LinkedList<Event<?>>(
+									subSeq));
+						}
+					}
+				}
+			}
+		}
+		return containedSubSeqs;
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/.classpath
===================================================================
--- /trunk/quest-core-usageprofiles-test/.classpath	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/.classpath	(revision 518)
@@ -0,0 +1,20 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/test-classes" path="src/test/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
Index: /trunk/quest-core-usageprofiles-test/.project
===================================================================
--- /trunk/quest-core-usageprofiles-test/.project	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/.project	(revision 518)
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>quest-core-usageprofiles-test</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.eclipse.m2e.core.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.m2e.core.maven2Nature</nature>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
Index: /trunk/quest-core-usageprofiles-test/.settings/org.eclipse.jdt.core.prefs
===================================================================
--- /trunk/quest-core-usageprofiles-test/.settings/org.eclipse.jdt.core.prefs	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/.settings/org.eclipse.jdt.core.prefs	(revision 518)
@@ -0,0 +1,5 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
Index: /trunk/quest-core-usageprofiles-test/.settings/org.eclipse.m2e.core.prefs
===================================================================
--- /trunk/quest-core-usageprofiles-test/.settings/org.eclipse.m2e.core.prefs	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/.settings/org.eclipse.m2e.core.prefs	(revision 518)
@@ -0,0 +1,4 @@
+activeProfiles=
+eclipse.preferences.version=1
+resolveWorkspaceProjects=true
+version=1
Index: /trunk/quest-core-usageprofiles-test/pom.xml
===================================================================
--- /trunk/quest-core-usageprofiles-test/pom.xml	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/pom.xml	(revision 518)
@@ -0,0 +1,139 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>de.ugoe.cs.quest</groupId>
+  <artifactId>quest-core-usageprofiles-test</artifactId>
+  <version>0.0.1-SNAPSHOT</version>
+  <name>quest-core-usageprofiles-test</name>
+  <scm>
+    <url>https://quest.informatik.uni-goettingen.de/svn/quest/trunk/quest-core-usageprofiles-test</url>
+  </scm>
+  <dependencies>
+    <dependency>
+        <groupId>de.ugoe.cs.quest</groupId>
+        <artifactId>quest-core-events</artifactId>
+        <version>0.0.1-SNAPSHOT</version>
+        <scope>test</scope>
+    </dependency>
+    <dependency>
+			<groupId>de.ugoe.cs.quest</groupId>
+			<artifactId>quest-core-usageprofiles</artifactId>
+			<version>0.0.1-SNAPSHOT</version>
+			<scope>test</scope>
+		</dependency>
+    <dependency>
+        <groupId>junit</groupId>
+        <artifactId>junit</artifactId>
+        <version>4.8.1</version>
+        <scope>test</scope>
+    </dependency>
+    <dependency>
+	  <groupId>junit-addons</groupId>
+	  <artifactId>junit-addons</artifactId>
+	  <version>1.4</version>
+    </dependency>
+  </dependencies>
+  <build>
+    <pluginManagement>
+      <plugins>
+        <plugin>
+          <groupId>org.eclipse.m2e</groupId>
+          <artifactId>lifecycle-mapping</artifactId>
+          <version>1.0.0</version>
+          <configuration>
+            <lifecycleMappingMetadata>
+              <pluginExecutions>
+                <pluginExecution>
+                  <pluginExecutionFilter>
+                    <groupId>org.apache.maven.plugins</groupId>
+                    <artifactId>maven-dependency-plugin</artifactId>
+                    <versionRange>[1.0.0,)</versionRange>
+                    <goals>
+                      <goal>unpack</goal>
+                    </goals>
+                  </pluginExecutionFilter>
+                  <action>
+                    <ignore/>
+                  </action>
+                </pluginExecution>
+                <pluginExecution>
+                  <pluginExecutionFilter>
+                    <groupId>org.codehaus.mojo</groupId>
+                    <artifactId>emma-maven-plugin</artifactId>
+                    <versionRange>[1.0-alpha-3,)</versionRange>
+                    <goals>
+                      <goal>emma</goal>
+                    </goals>
+                  </pluginExecutionFilter>
+                  <action>
+                    <ignore/>
+                  </action>
+                </pluginExecution>
+              </pluginExecutions>
+            </lifecycleMappingMetadata>
+          </configuration>
+        </plugin>
+      </plugins>
+    </pluginManagement>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <version>2.3.2</version>
+        <configuration>
+          <source>1.6</source>
+          <target>1.6</target>
+        </configuration>
+      </plugin>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-dependency-plugin</artifactId>
+        <version>2.4</version>
+        <executions>
+          <execution>
+            <id>unpack</id>
+            <phase>process-classes</phase>
+            <goals>
+              <goal>unpack</goal>
+            </goals>
+            <configuration>
+              <artifactItems>
+                <artifactItem>
+                  <groupId>de.ugoe.cs.quest</groupId>
+                  <artifactId>quest-core-usageprofiles</artifactId>
+                  <version>0.0.1-SNAPSHOT</version>
+                  <outputDirectory>${project.build.directory}/classes</outputDirectory>
+                </artifactItem>
+              </artifactItems>
+            </configuration>
+          </execution>
+        </executions>
+      </plugin>
+      <plugin>
+        <groupId>org.codehaus.mojo</groupId>
+        <artifactId>emma-maven-plugin</artifactId>
+        <version>1.0-alpha-3</version>
+        <inherited>true</inherited>          
+        <executions>
+          <execution>
+            <phase>process-classes</phase>
+            <goals>
+              <goal>emma</goal>
+            </goals>
+          </execution>
+        </executions>
+      </plugin>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-jar-plugin</artifactId>
+        <version>2.3.2</version>
+        <executions>
+          <execution>
+            <goals>
+              <goal>test-jar</goal>
+            </goals>
+          </execution>
+        </executions>
+      </plugin>
+    </plugins>
+  </build>
+</project>
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomatonTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomatonTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomatonTest.java	(revision 518)
@@ -0,0 +1,157 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.DeterministicFiniteAutomaton;
+
+import java.util.Random;
+import org.junit.*;
+
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>DeterministicFiniteAutomatonTest</code> contains tests for
+ * the class <code>{@link DeterministicFiniteAutomaton}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class DeterministicFiniteAutomatonTest {
+
+	Collection<List<? extends Event<?>>> sequences;
+
+	@Test
+	public void testDeterministicFiniteAutomaton_1() throws Exception {
+		Random r = new Random();
+
+		DeterministicFiniteAutomaton result = new DeterministicFiniteAutomaton(
+				r);
+
+		assertNotNull(result);
+		assertEquals(2, result.trieOrder);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testDeterministicFiniteAutomaton_2() throws Exception {
+		new DeterministicFiniteAutomaton(null);
+	}
+
+	@Test
+	public void testGetProbability_1() throws Exception {
+		DeterministicFiniteAutomaton fixture = new DeterministicFiniteAutomaton(
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+		context.add(new Event<String>("b"));
+
+		Event<String> symbol = new Event<String>("r");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(1.0d, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_2() throws Exception {
+		DeterministicFiniteAutomaton fixture = new DeterministicFiniteAutomaton(
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("b");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(1.0d / 4.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_3() throws Exception {
+		DeterministicFiniteAutomaton fixture = new DeterministicFiniteAutomaton(
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("c");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(1.0d / 4.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_4() throws Exception {
+		DeterministicFiniteAutomaton fixture = new DeterministicFiniteAutomaton(
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("e");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(0.0d, result, 0.0001);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testGetProbability_5() throws Exception {
+		DeterministicFiniteAutomaton fixture = new DeterministicFiniteAutomaton(
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = null;
+
+		fixture.getProbability(context, symbol);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testGetProbability_6() throws Exception {
+		DeterministicFiniteAutomaton fixture = new DeterministicFiniteAutomaton(
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = null;
+
+		Event<String> symbol = new Event<String>("a");
+
+		fixture.getProbability(context, symbol);
+	}
+
+	@Before
+	public void setUp() throws Exception {
+		List<Event<?>> sequence = new ArrayList<Event<?>>();
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("c"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("d"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+
+		sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore()
+				.run(DeterministicFiniteAutomatonTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModelTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModelTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModelTest.java	(revision 518)
@@ -0,0 +1,94 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Random;
+import org.junit.*;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.FirstOrderMarkovModel;
+import de.ugoe.cs.quest.usageprofiles.FirstOrderMarkovModel.MarkovEdge;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>FirstOrderMarkovModelTest</code> contains tests for the class
+ * <code>{@link FirstOrderMarkovModel}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class FirstOrderMarkovModelTest {
+
+	Collection<List<? extends Event<?>>> sequences;
+	
+	@Test
+	public void testFirstOrderMarkovModel_1() throws Exception {
+		Random r = new Random();
+
+		FirstOrderMarkovModel result = new FirstOrderMarkovModel(r);
+
+		assertNotNull(result);
+		assertEquals(r, result.r);
+		assertEquals(2, result.trieOrder);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testFirstOrderMarkovModel_2() throws Exception {
+		new FirstOrderMarkovModel(null);
+	}
+	
+	@Test
+	public void testCalcEntropy() throws Exception {
+		Random r = new Random();
+		FirstOrderMarkovModel fixture = new FirstOrderMarkovModel(r);
+		fixture.train(sequences);
+		
+		double result = fixture.calcEntropy();
+		
+		assertEquals(0.7392d, result, 0.0001);
+	}
+	
+	@Test
+	public void testMarkovEdgeMarkovEdge_1() throws Exception {
+		double weight = 0.2d;
+		
+		MarkovEdge result = new MarkovEdge(weight);
+		
+		assertNotNull(result);
+		assertEquals(weight, result.weight, 0.0001);
+	}
+	
+	@Test
+	public void testMarkovEdgeToString_1() throws Exception {
+		double weight = 0.2d;
+		MarkovEdge fixture = new MarkovEdge(weight);
+		
+		String result = fixture.toString();
+		
+		assertEquals(Double.toString(0.2d), result);
+	}
+	
+	@Before
+	public void setUp() throws Exception {
+		List<Event<?>> sequence = new ArrayList<Event<?>>();
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("c"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("d"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+
+		sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(FirstOrderMarkovModelTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModelTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModelTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModelTest.java	(revision 518)
@@ -0,0 +1,241 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.HighOrderMarkovModel;
+
+import java.util.Random;
+import org.junit.*;
+
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>HighOrderMarkovModelTest</code> contains tests for the class
+ * <code>{@link HighOrderMarkovModel}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class HighOrderMarkovModelTest {
+
+	Collection<List<? extends Event<?>>> sequences;
+
+	@Test
+	public void testHighOrderMarkovModel_1() throws Exception {
+		int maxOrder = 1;
+		Random r = new Random();
+
+		HighOrderMarkovModel result = new HighOrderMarkovModel(maxOrder, r);
+
+		assertNotNull(result);
+		assertEquals(r, result.r);
+		assertEquals(maxOrder + 1, result.trieOrder);
+	}
+
+	@Test
+	public void testHighOrderMarkovModel_2() throws Exception {
+		int maxOrder = 0;
+		Random r = new Random();
+
+		HighOrderMarkovModel result = new HighOrderMarkovModel(maxOrder, r);
+
+		assertNotNull(result);
+		assertEquals(r, result.r);
+		assertEquals(maxOrder + 1, result.trieOrder);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testHighOrderMarkovModel_3() throws Exception {
+		int maxOrder = 1;
+		Random r = null;
+
+		new HighOrderMarkovModel(maxOrder, r);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testHighOrderMarkovModel_4() throws Exception {
+		int maxOrder = -1;
+		Random r = new Random();
+
+		new HighOrderMarkovModel(maxOrder, r);
+	}
+
+	@Test
+	public void testGetProbability_1() throws Exception {
+		int markovOrder = 1;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("b");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(2.0d / 5.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_2() throws Exception {
+		int markovOrder = 1;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("r");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(0.0d / 5.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_3() throws Exception {
+		int markovOrder = 1;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<String>> context = new ArrayList<Event<String>>();
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("c");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(1.0d / 5.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_4() throws Exception {
+		int markovOrder = 1;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("b");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(2.0d / 5.0, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_5() throws Exception {
+		int markovOrder = 2;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("b");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(1.0d, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_6() throws Exception {
+		int markovOrder = 2;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("b"));
+
+		Event<String> symbol = new Event<String>("b");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(0.0d, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_7() throws Exception {
+		int markovOrder = 0;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("b"));
+
+		Event<String> symbol = new Event<String>("a");
+
+		double result = fixture.getProbability(context, symbol);
+
+		assertEquals(5.0d / 13.0, result, 0.0001);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testGetProbability_8() throws Exception {
+		int markovOrder = 0;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("b"));
+
+		Event<String> symbol = null;
+
+		fixture.getProbability(context, symbol);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testGetProbability_9() throws Exception {
+		int markovOrder = 0;
+		HighOrderMarkovModel fixture = new HighOrderMarkovModel(markovOrder,
+				new Random());
+		fixture.train(sequences);
+
+		List<Event<?>> context = null;
+
+		Event<String> symbol = new Event<String>("b");
+
+		fixture.getProbability(context, symbol);
+	}
+
+	@Before
+	public void setUp() throws Exception {
+		List<Event<?>> sequence = new ArrayList<Event<?>>();
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("c"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("d"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+
+		sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(HighOrderMarkovModelTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemoryTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemoryTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemoryTest.java	(revision 518)
@@ -0,0 +1,152 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.List;
+import org.junit.*;
+
+import de.ugoe.cs.quest.usageprofiles.IncompleteMemory;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>IncompleteMemoryTest</code> contains tests for the class <code>{@link IncompleteMemory}</code>.
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class IncompleteMemoryTest {
+
+	@Test
+	public void testIncompleteMemory_1()
+		throws Exception {
+		int length = 1;
+
+		IncompleteMemory<String> result = new IncompleteMemory<String>(length);
+
+		assertNotNull(result);
+		assertEquals(0, result.getLast(1).size());
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testIncompleteMemory_2()
+		throws Exception {
+		int length = 0;
+
+		new IncompleteMemory<String>(length);
+	}
+
+	@Test
+	public void testGetLast_1()
+		throws Exception {
+		int length = 2;
+		IncompleteMemory<String> fixture = new IncompleteMemory<String>(length);
+		fixture.add("1");
+		fixture.add("2");
+		fixture.add("3");
+		int num = -1;
+
+		List<String> result = fixture.getLast(num);
+
+		assertNotNull(result);
+		assertEquals(0, result.size());
+	}
+
+	@Test
+	public void testGetLast_2()
+		throws Exception {
+		int length = 2;
+		IncompleteMemory<String> fixture = new IncompleteMemory<String>(length);
+		fixture.add("1");
+		fixture.add("2");
+		fixture.add("3");
+		int num = 1;
+		
+		List<String> expected = new ArrayList<String>();
+		expected.add("3");
+
+		List<String> result = fixture.getLast(num);
+
+		assertNotNull(result);
+		assertEquals(expected, result);
+	}
+
+	@Test
+	public void testGetLast_3()
+		throws Exception {
+		int length = 2;
+		IncompleteMemory<String> fixture = new IncompleteMemory<String>(length);
+		fixture.add("1");
+		fixture.add("2");
+		fixture.add("3");
+		int num = 2;
+		
+		List<String> expected = new ArrayList<String>();
+		expected.add("2");
+		expected.add("3");
+
+		List<String> result = fixture.getLast(num);
+
+		assertNotNull(result);
+		assertEquals(expected, result);
+	}
+	
+	@Test
+	public void testGetLast_4()
+		throws Exception {
+		int length = 2;
+		IncompleteMemory<String> fixture = new IncompleteMemory<String>(length);
+		fixture.add("1");
+		fixture.add("2");
+		fixture.add("3");
+		int num = 3;
+		
+		List<String> expected = new ArrayList<String>();
+		expected.add("2");
+		expected.add("3");
+
+		List<String> result = fixture.getLast(num);
+
+		assertNotNull(result);
+		assertEquals(expected, result);
+	}
+
+	@Test
+	public void testGetLength_1()
+		throws Exception {
+		int length = 2;
+		IncompleteMemory<String> fixture = new IncompleteMemory<String>(length);
+		
+		int result = fixture.getLength(); 
+
+		assertEquals(0, result);
+	}
+	
+	@Test
+	public void testGetLength_2()
+		throws Exception {
+		int length = 2;
+		IncompleteMemory<String> fixture = new IncompleteMemory<String>(length);
+		fixture.add("1");
+		
+		int result = fixture.getLength(); 
+
+		assertEquals(1, result);
+	}
+	
+	@Test
+	public void testGetLength_3()
+		throws Exception {
+		int length = 2;
+		IncompleteMemory<String> fixture = new IncompleteMemory<String>(length);
+		fixture.add("1");
+		fixture.add("2");
+		fixture.add("3");
+		
+		int result = fixture.getLength(); 
+
+		assertEquals(2, result);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(IncompleteMemoryTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/MockTrieBasedModel.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/MockTrieBasedModel.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/MockTrieBasedModel.java	(revision 518)
@@ -0,0 +1,31 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.TrieBasedModel;
+
+public class MockTrieBasedModel extends TrieBasedModel {
+	private static final long serialVersionUID = 1L;
+
+	public MockTrieBasedModel(int markovOrder, Random r) {
+		super(markovOrder, r);
+	}
+
+	@Override
+	public double getProbability(List<? extends Event<?>> context,
+			Event<?> symbol) {
+		List<Event<?>> list = new ArrayList<Event<?>>();
+		if( context.isEmpty() ) {
+			return 2;
+		}
+		list.add(context.get(context.size()-1));
+		if( trie.find(list).getFollowingSymbols().contains(symbol) ) {
+			return 1;
+		} else {
+			return 0;
+		}
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/ModelFlattenerTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/ModelFlattenerTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/ModelFlattenerTest.java	(revision 518)
@@ -0,0 +1,148 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import org.junit.*;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.FirstOrderMarkovModel;
+import de.ugoe.cs.quest.usageprofiles.HighOrderMarkovModel;
+import de.ugoe.cs.quest.usageprofiles.ModelFlattener;
+import de.ugoe.cs.quest.usageprofiles.PredictionByPartialMatch;
+import de.ugoe.cs.quest.usageprofiles.TrieNode;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>ModelFlattenerTest</code> contains tests for the class <code>{@link ModelFlattener}</code>.
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class ModelFlattenerTest {
+	
+	List<Event<?>> sequence;
+	
+	private static void assertCollectionContent(Collection<?> c1, Collection<?> c2) {
+		assertEquals(c1.size(), c2.size());
+		for( Object obj : c1 ) {
+			assertTrue(c2.contains(obj));
+		}
+	}
+	
+	@Test
+	public void testFlattenHighOrderMarkovModel_1()
+		throws Exception {
+		ModelFlattener fixture = new ModelFlattener();
+		HighOrderMarkovModel model = new HighOrderMarkovModel(2, new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		model.train(sequences);
+		
+		Collection<Event<?>> expectedSymbols = new HashSet<Event<?>>();
+		expectedSymbols.add(new Event<Object>("a-=-END"));
+		expectedSymbols.add(new Event<Object>("a-=-b"));
+		expectedSymbols.add(new Event<Object>("a-=-c"));
+		expectedSymbols.add(new Event<Object>("a-=-d"));
+		expectedSymbols.add(new Event<Object>("b-=-r"));
+		expectedSymbols.add(new Event<Object>("c-=-a"));
+		expectedSymbols.add(new Event<Object>("d-=-a"));
+		expectedSymbols.add(new Event<Object>("r-=-a"));
+		expectedSymbols.add(new Event<Object>("START-=-a"));
+
+		FirstOrderMarkovModel result = fixture.flattenHighOrderMarkovModel(model);
+		
+		assertCollectionContent(expectedSymbols, result.getEvents());
+		
+		TrieNode<Event<?>> root = result.trie.find(null);
+		TrieNode<Event<?>> root_aEnd = root.getChild(new Event<Object>("a-=-END"));
+		TrieNode<Event<?>> root_ab = root.getChild(new Event<Object>("a-=-b"));
+		TrieNode<Event<?>> root_ab_br = root_ab.getChild(new Event<Object>("b-=-r"));
+		TrieNode<Event<?>> root_ac = root.getChild(new Event<Object>("a-=-c"));
+		TrieNode<Event<?>> root_ac_ca = root_ac.getChild(new Event<Object>("c-=-a"));
+		TrieNode<Event<?>> root_ad = root.getChild(new Event<Object>("a-=-d"));
+		TrieNode<Event<?>> root_ad_da = root_ad.getChild(new Event<Object>("d-=-a"));
+		TrieNode<Event<?>> root_br = root.getChild(new Event<Object>("b-=-r"));
+		TrieNode<Event<?>> root_br_ra = root_br.getChild(new Event<Object>("r-=-a"));
+		TrieNode<Event<?>> root_ca = root.getChild(new Event<Object>("c-=-a"));
+		TrieNode<Event<?>> root_ca_ad = root_ca.getChild(new Event<Object>("a-=-d"));
+		TrieNode<Event<?>> root_da = root.getChild(new Event<Object>("d-=-a"));
+		TrieNode<Event<?>> root_da_ab = root_da.getChild(new Event<Object>("a-=-b"));
+		TrieNode<Event<?>> root_ra = root.getChild(new Event<Object>("r-=-a"));
+		TrieNode<Event<?>> root_ra_ac = root_ra.getChild(new Event<Object> ("a-=-c"));
+		TrieNode<Event<?>> root_ra_aEnd = root_ra.getChild(new Event<Object>("a-=-END"));
+		TrieNode<Event<?>> root_startA = root.getChild(new Event<Object>("START-=-a"));
+		TrieNode<Event<?>> root_startA_ab = root_startA.getChild(new Event<Object>("a-=-b"));
+		
+		assertEquals(1, root_aEnd.getCount());
+		assertTrue(root_aEnd.isLeaf());
+		assertEquals(2, root_ab.getCount());
+		assertEquals(1, root_ab.getChildren().size());
+		assertEquals(2, root_ab_br.getCount());
+		assertTrue(root_ab_br.isLeaf());
+		assertEquals(1, root_ac.getCount());
+		assertEquals(1, root_ac.getChildren().size());
+		assertEquals(1, root_ac_ca.getCount());
+		assertTrue(root_ac_ca.isLeaf());
+		assertEquals(1, root_ad.getCount());
+		assertEquals(1, root_ad.getChildren().size());
+		assertEquals(1, root_ad_da.getCount());
+		assertTrue(root_ad_da.isLeaf());
+		assertEquals(2, root_br.getCount());
+		assertEquals(1, root_br.getChildren().size());
+		assertEquals(2, root_br_ra.getCount());
+		assertTrue(root_br_ra.isLeaf());
+		assertEquals(1, root_ca.getCount());
+		assertEquals(1, root_ca.getChildren().size());
+		assertEquals(1, root_ca_ad.getCount());
+		assertTrue(root_ca_ad.isLeaf());
+		assertEquals(1, root_da.getCount());
+		assertEquals(1, root_da.getChildren().size());
+		assertEquals(1, root_da_ab.getCount());
+		assertTrue(root_da_ab.isLeaf());
+		assertEquals(2, root_ra.getCount());
+		assertEquals(2, root_ra.getChildren().size());
+		assertEquals(1, root_ra_ac.getCount());
+		assertTrue(root_ra_ac.isLeaf());
+		assertEquals(1, root_ra_aEnd.getCount());
+		assertTrue(root_ra_aEnd.isLeaf());
+		assertEquals(1, root_startA.getCount());
+		assertEquals(1, root_startA.getChildren().size());
+		assertEquals(1, root_startA_ab.getCount());
+		assertTrue(root_startA_ab.isLeaf());		
+	}
+
+	@Test
+	public void testFlattenPredictionByPartialMatch_1()
+		throws Exception {
+		ModelFlattener fixture = new ModelFlattener();
+		PredictionByPartialMatch model = new PredictionByPartialMatch(1, new Random());
+
+		FirstOrderMarkovModel result = fixture.flattenPredictionByPartialMatch(model);
+		
+		assertEquals(null, result);
+	}
+
+	@Before
+	public void setUp()
+		throws Exception {
+		sequence = new ArrayList<Event<?>>();
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("c"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("d"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(ModelFlattenerTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatchTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatchTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatchTest.java	(revision 518)
@@ -0,0 +1,365 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.PredictionByPartialMatch;
+
+import java.util.Random;
+import org.junit.*;
+
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>PredictionByPartialMatchTest</code> contains tests for the
+ * class <code>{@link PredictionByPartialMatch}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class PredictionByPartialMatchTest {
+
+	Collection<List<? extends Event<?>>> sequences;
+
+	@Test
+	public void testPredictionByPartialMatch_1() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+
+		PredictionByPartialMatch result = new PredictionByPartialMatch(
+				markovOrder, r);
+
+		assertNotNull(result);
+		assertEquals(markovOrder+1, result.trieOrder);
+		assertEquals(0, result.minOrder);
+		assertEquals(r, result.r);
+		assertEquals(0.1, result.probEscape, 0.0001);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_2() throws Exception {
+		int markovOrder = -1;
+		Random r = new Random();
+
+		new PredictionByPartialMatch(markovOrder, r);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_3() throws Exception {
+		int markovOrder = 2;
+		Random r = null;
+
+		new PredictionByPartialMatch(markovOrder, r);
+	}
+	
+	@Test
+	public void testPredictionByPartialMatch_4() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+
+		PredictionByPartialMatch result = new PredictionByPartialMatch(
+				markovOrder, r, probEscape);
+
+		assertNotNull(result);
+		assertEquals(markovOrder+1, result.trieOrder);
+		assertEquals(0, result.minOrder);
+		assertEquals(r, result.r);
+		assertEquals(probEscape, result.probEscape, 0.0001);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_5() throws Exception {
+		int markovOrder = -1;
+		Random r = new Random();
+		double probEscape = 0.2;
+
+		new PredictionByPartialMatch(markovOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_6() throws Exception {
+		int markovOrder = 2;
+		Random r = null;
+		double probEscape = 0.2;
+
+		new PredictionByPartialMatch(markovOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_7() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.0;
+
+		new PredictionByPartialMatch(markovOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_8() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 1.0;
+
+		new PredictionByPartialMatch(markovOrder, r, probEscape);
+	}
+	
+	@Test
+	public void testPredictionByPartialMatch_9() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 1;
+
+		PredictionByPartialMatch result = new PredictionByPartialMatch(
+				markovOrder, minOrder, r, probEscape);
+
+		assertNotNull(result);
+		assertEquals(markovOrder+1, result.trieOrder);
+		assertEquals(minOrder, result.minOrder);
+		assertEquals(r, result.r);
+		assertEquals(probEscape, result.probEscape, 0.0001);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_10() throws Exception {
+		int markovOrder = -1;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 1;
+
+		new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_11() throws Exception {
+		int markovOrder = 2;
+		Random r = null;
+		double probEscape = 0.2;
+		int minOrder = 1;
+
+		new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_12() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.0;
+		int minOrder = 1;
+
+		new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_13() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 1.0;
+		int minOrder = 1;
+
+		new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_14() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 3;
+
+		new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testPredictionByPartialMatch_15() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = -1;
+
+		new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+	}
+
+	@Test
+	public void testGetProbEscape_1() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 1;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+		fixture.probEscape = probEscape;
+		
+		double result = fixture.getProbEscape();
+
+		assertEquals(probEscape, result, 0.0001);
+	}
+
+	@Test
+	public void testGetProbability_1() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 1;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+		fixture.train(sequences);
+		
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("b");
+		
+		double result = fixture.getProbability(context, symbol);
+		
+		assertEquals(0.88d, result, 0.0001);
+	}
+	
+	@Test
+	public void testGetProbability_2() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 1;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+		fixture.train(sequences);
+		
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("c");
+		
+		double result = fixture.getProbability(context, symbol);
+		
+		assertEquals(0.04d, result, 0.0001);
+	}
+	
+	@Test
+	public void testGetProbability_3() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 2;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+		fixture.train(sequences);
+		
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("b");
+		
+		double result = fixture.getProbability(context, symbol);
+		
+		assertEquals(1.0d, result, 0.0001);
+	}
+	
+	@Test
+	public void testGetProbability_4() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 2;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+		fixture.train(sequences);
+		
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("c");
+		
+		double result = fixture.getProbability(context, symbol);
+		
+		assertEquals(0.0d, result, 0.0001);
+	}
+	
+	@Test
+	public void testGetProbability_5() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 0;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+		fixture.train(sequences);
+		
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("b");
+		
+		double result = fixture.getProbability(context, symbol);
+		
+		assertEquals(0.8701d, result, 0.0001);
+	}
+	
+	@Test
+	public void testGetProbability_6() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 0;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+		fixture.train(sequences);
+		
+		List<Event<?>> context = new ArrayList<Event<?>>();
+		context.add(Event.STARTEVENT);
+		context.add(new Event<String>("a"));
+
+		Event<String> symbol = new Event<String>("c");
+		
+		double result = fixture.getProbability(context, symbol);
+		
+		assertEquals(0.0350, result, 0.0001);
+	}
+
+	@Test
+	public void testSetProbEscape_1() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+		double probEscape = 0.2;
+		int minOrder = 1;
+		double newProbEscape = 0.3;
+
+		PredictionByPartialMatch fixture = new PredictionByPartialMatch(markovOrder, minOrder, r, probEscape);
+				
+		fixture.setProbEscape(newProbEscape);
+
+		assertEquals(newProbEscape, fixture.probEscape, 0.0001);
+	}
+
+	@Before
+	public void setUp() throws Exception {
+		List<Event<?>> sequence = new ArrayList<Event<?>>();
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("c"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("d"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+
+		sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore()
+				.run(PredictionByPartialMatchTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModelTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModelTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModelTest.java	(revision 518)
@@ -0,0 +1,635 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.Trie;
+import de.ugoe.cs.quest.usageprofiles.TrieBasedModel;
+import de.ugoe.cs.quest.usageprofiles.TrieNode;
+
+import org.junit.*;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>TrieBasedModelTest</code> contains tests for the class
+ * <code>{@link TrieBasedModel}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class TrieBasedModelTest {
+
+	List<Event<?>> sequence;
+	Collection<Event<?>> symbols;
+
+	private void assertTrieStructure(Trie<Event<?>> trie, int numSequences) {
+		TrieNode<Event<?>> root = trie.find(null);
+		TrieNode<Event<?>> root_a = root.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_a_a = root_a.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_a_b = root_a.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_a_b_a = root_a_b
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_a_b_b = root_a_b
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_a_b_c = root_a_b
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_a_b_d = root_a_b
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_a_b_r = root_a_b
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_a_c = root_a.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_a_c_a = root_a_c
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_a_c_b = root_a_c
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_a_c_c = root_a_c
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_a_c_d = root_a_c
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_a_c_r = root_a_c
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_a_d = root_a.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_a_d_a = root_a_d
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_a_d_b = root_a_d
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_a_d_c = root_a_d
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_a_d_d = root_a_d
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_a_d_r = root_a_d
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_a_r = root_a.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_b = root.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_b_a = root_b.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_b_b = root_b.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_b_c = root_b.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_b_d = root_b.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_b_r = root_b.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_b_r_a = root_b_r
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_b_r_b = root_b_r
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_b_r_c = root_b_r
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_b_r_d = root_b_r
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_b_r_r = root_b_r
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_c = root.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_c_a = root_c.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_c_a_a = root_c_a
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_c_a_b = root_c_a
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_c_a_c = root_c_a
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_c_a_d = root_c_a
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_c_a_r = root_c_a
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_c_b = root_c.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_c_c = root_c.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_c_d = root_c.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_c_r = root_c.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_d = root.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_d_a = root_d.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_d_a_a = root_d_a
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_d_a_b = root_d_a
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_d_a_c = root_d_a
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_d_a_d = root_d_a
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_d_a_r = root_d_a
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_d_b = root_d.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_d_c = root_d.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_d_d = root_d.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_d_r = root_d.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_r = root.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_r_a = root_r.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_r_a_a = root_r_a
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_r_a_b = root_r_a
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_r_a_c = root_r_a
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_r_a_d = root_r_a
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_r_a_r = root_r_a
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_r_a_end = root_r_a.getChild(Event.ENDEVENT);
+		TrieNode<Event<?>> root_r_b = root_r.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_r_c = root_r.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_r_d = root_r.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_r_r = root_r.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_start = root.getChild(Event.STARTEVENT);
+		TrieNode<Event<?>> root_start_a = root_start
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_start_a_a = root_start_a
+				.getChild(new Event<String>("a"));
+		TrieNode<Event<?>> root_start_a_b = root_start_a
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_start_a_c = root_start_a
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_start_a_d = root_start_a
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_start_a_r = root_start_a
+				.getChild(new Event<String>("r"));
+		TrieNode<Event<?>> root_start_b = root_start
+				.getChild(new Event<String>("b"));
+		TrieNode<Event<?>> root_start_c = root_start
+				.getChild(new Event<String>("c"));
+		TrieNode<Event<?>> root_start_d = root_start
+				.getChild(new Event<String>("d"));
+		TrieNode<Event<?>> root_start_r = root_start
+				.getChild(new Event<String>("r"));
+
+		assertEquals(numSequences * 5, root_a.getCount());
+		assertNull(root_a_a);
+		assertEquals(numSequences * 2, root_a_b.getCount());
+		assertNull(root_a_b_a);
+		assertNull(root_a_b_b);
+		assertNull(root_a_b_c);
+		assertNull(root_a_b_d);
+		assertEquals(numSequences * 2, root_a_b_r.getCount());
+		assertEquals(numSequences * 1, root_a_c.getCount());
+		assertEquals(numSequences * 1, root_a_c_a.getCount());
+		assertNull(root_a_c_b);
+		assertNull(root_a_c_c);
+		assertNull(root_a_c_d);
+		assertNull(root_a_c_r);
+		assertEquals(numSequences * 1, root_a_d.getCount());
+		assertEquals(numSequences * 1, root_a_d_a.getCount());
+		assertNull(root_a_d_b);
+		assertNull(root_a_d_c);
+		assertNull(root_a_d_d);
+		assertNull(root_a_d_r);
+		assertNull(root_a_r);
+
+		assertEquals(numSequences * 2, root_b.getCount());
+		assertNull(root_b_a);
+		assertNull(root_b_b);
+		assertNull(root_b_c);
+		assertNull(root_b_d);
+		assertEquals(numSequences * 2, root_b_r.getCount());
+		assertEquals(numSequences * 2, root_b_r_a.getCount());
+		assertNull(root_b_r_b);
+		assertNull(root_b_r_c);
+		assertNull(root_b_r_d);
+		assertNull(root_b_r_r);
+
+		assertEquals(numSequences * 1, root_c.getCount());
+		assertEquals(numSequences * 1, root_c_a.getCount());
+		assertNull(root_c_a_a);
+		assertNull(root_c_a_b);
+		assertNull(root_c_a_c);
+		assertEquals(numSequences * 1, root_c_a_d.getCount());
+		assertNull(root_c_a_r);
+		assertNull(root_c_b);
+		assertNull(root_c_c);
+		assertNull(root_c_d);
+		assertNull(root_c_r);
+
+		assertEquals(numSequences * 1, root_d.getCount());
+		assertEquals(numSequences * 1, root_d_a.getCount());
+		assertNull(root_d_a_a);
+		assertEquals(numSequences * 1, root_d_a_b.getCount());
+		assertNull(root_d_a_c);
+		assertNull(root_d_a_d);
+		assertNull(root_d_a_r);
+		assertNull(root_d_b);
+		assertNull(root_d_c);
+		assertNull(root_d_d);
+		assertNull(root_d_r);
+
+		assertEquals(numSequences * 2, root_r.getCount());
+		assertEquals(numSequences * 2, root_r_a.getCount());
+		assertNull(root_r_a_a);
+		assertNull(root_r_a_b);
+		assertEquals(numSequences * 1, root_r_a_c.getCount());
+		assertNull(root_r_a_d);
+		assertNull(root_r_a_r);
+		assertEquals(numSequences * 1, root_r_a_end.getCount());
+		assertNull(root_r_b);
+		assertNull(root_r_c);
+		assertNull(root_r_d);
+		assertNull(root_r_r);
+
+		assertEquals(numSequences * 1, root_start.getCount());
+		assertEquals(numSequences * 1, root_start_a.getCount());
+		assertNull(root_start_a_a);
+		assertEquals(numSequences * 1, root_start_a_b.getCount());
+		assertNull(root_start_a_c);
+		assertNull(root_start_a_d);
+		assertNull(root_start_a_r);
+		assertNull(root_start_b);
+		assertNull(root_start_c);
+		assertNull(root_start_d);
+		assertNull(root_start_r);
+
+		// check if leafs are really leafs
+		assertTrue(root_a_b_r.isLeaf());
+		assertTrue(root_a_c_a.isLeaf());
+		assertTrue(root_a_d_a.isLeaf());
+		assertTrue(root_b_r_a.isLeaf());
+		assertTrue(root_c_a_d.isLeaf());
+		assertTrue(root_d_a_b.isLeaf());
+		assertTrue(root_r_a_c.isLeaf());
+		assertTrue(root_r_a_end.isLeaf());
+	}
+
+	private static void assertCollectionContent(Collection<?> c1,
+			Collection<?> c2) {
+		assertEquals(c1.size(), c2.size());
+		for (Object obj : c1) {
+			assertTrue(c2.contains(obj));
+		}
+	}
+
+	@Test
+	public void testTrieBasedModel_1() throws Exception {
+		int markovOrder = 2;
+		Random r = new Random();
+
+		MockTrieBasedModel result = new MockTrieBasedModel(markovOrder, r);
+
+		assertNotNull(result);
+		assertEquals(markovOrder + 1, result.trieOrder);
+		assertEquals(r, result.r);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testTrieBasedModel_2() throws Exception {
+		int markovOrder = -1;
+		Random r = new Random();
+
+		new MockTrieBasedModel(markovOrder, r);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testTrieBasedModel_3() throws Exception {
+		int markovOrder = 2;
+		Random r = null;
+
+		new MockTrieBasedModel(markovOrder, r);
+	}
+
+	@Test
+	public void testGenerateSequences_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+		int length = 2;
+
+		Collection<List<Event<?>>> expected = new HashSet<List<Event<?>>>();
+		ArrayList<Event<?>> list;
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("a"));
+		list.add(Event.ENDEVENT);
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("b"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("c"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("d"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("b"));
+		list.add(new Event<String>("r"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("c"));
+		list.add(new Event<String>("a"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("d"));
+		list.add(new Event<String>("a"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(new Event<String>("r"));
+		list.add(new Event<String>("a"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(Event.STARTEVENT);
+		list.add(new Event<String>("a"));
+		expected.add(list);
+
+		Collection<List<? extends Event<?>>> result = fixture
+				.generateSequences(length);
+
+		assertCollectionContent(expected, result);
+	}
+
+	@Test
+	public void testGenerateSequences_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+		int length = 3;
+
+		Collection<List<Event<?>>> expected = new HashSet<List<Event<?>>>();
+		ArrayList<Event<?>> list;
+		list = new ArrayList<Event<?>>();
+		list.add(Event.STARTEVENT);
+		list.add(new Event<String>("a"));
+		list.add(Event.ENDEVENT);
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(Event.STARTEVENT);
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("b"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(Event.STARTEVENT);
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("c"));
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(Event.STARTEVENT);
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("d"));
+		expected.add(list);
+
+		Collection<List<? extends Event<?>>> result = fixture
+				.generateSequences(length, true);
+
+		assertCollectionContent(expected, result);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testGenerateSequences_3() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+		int length = 0;
+
+		fixture.generateSequences(length, false);
+	}
+
+	@Test
+	public void testGenerateValidSequences_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+		int length = 5;
+
+		Collection<List<Event<?>>> expected = new HashSet<List<Event<?>>>();
+		ArrayList<Event<?>> list;
+		list = new ArrayList<Event<?>>();
+		list.add(Event.STARTEVENT);
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("c"));
+		list.add(new Event<String>("a"));
+		list.add(Event.ENDEVENT);
+		expected.add(list);
+		list = new ArrayList<Event<?>>();
+		list.add(Event.STARTEVENT);
+		list.add(new Event<String>("a"));
+		list.add(new Event<String>("d"));
+		list.add(new Event<String>("a"));
+		list.add(Event.ENDEVENT);
+		expected.add(list);
+
+		Collection<List<? extends Event<?>>> result = fixture
+				.generateValidSequences(length);
+
+		assertCollectionContent(expected, result);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testGenerateValidSequences_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+		int length = 0;
+
+		fixture.generateValidSequences(length);
+	}
+
+	@Test
+	public void testGetEvents_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+
+		fixture.train(sequences);
+
+		Collection<? extends Event<?>> result = fixture.getEvents();
+
+		assertCollectionContent(symbols, result);
+	}
+
+	@Test
+	public void testGetEvents_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+
+		Collection<? extends Event<?>> result = fixture.getEvents();
+
+		assertCollectionContent(new HashSet<Event<?>>(), result);
+	}
+
+	@Test
+	public void testGetNumFOMStates_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+
+		fixture.train(sequences);
+
+		int result = fixture.getNumFOMStates();
+
+		assertEquals(10, result);
+	}
+
+	@Test
+	public void testGetNumFOMStates_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		;
+
+		int result = fixture.getNumFOMStates();
+
+		assertEquals(0, result);
+	}
+
+	@Test
+	public void testGetNumSymbols_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+
+		int result = fixture.getNumSymbols();
+
+		assertEquals(7, result);
+	}
+
+	@Test
+	public void testGetNumSymbols_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+
+		int result = fixture.getNumSymbols();
+
+		assertEquals(0, result);
+	}
+
+	@Test
+	public void testGetNumTransitions_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+
+		int result = fixture.getNumTransitions();
+
+		assertEquals(11, result);
+	}
+
+	@Test
+	public void testGetNumTransitions_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+
+		int result = fixture.getNumTransitions();
+
+		assertEquals(0, result);
+	}
+
+	@Test
+	public void testTrain_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+
+		fixture.train(sequences);
+
+		assertCollectionContent(symbols, fixture.getEvents());
+
+		assertTrieStructure(fixture.trie, 1);
+	}
+
+	@Test
+	public void testTrain_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		sequences.add(sequence);
+
+		fixture.train(sequences);
+
+		assertCollectionContent(symbols, fixture.getEvents());
+
+		assertTrieStructure(fixture.trie, 2);
+	}
+	
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testTrain_3() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = null;
+
+		fixture.train(sequences);
+	}
+
+	@Test
+	public void testUpdate_1() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = new ArrayList<List<? extends Event<?>>>();
+		sequences.add(sequence);
+		fixture.train(sequences);
+
+		fixture.update(sequences);
+
+		assertCollectionContent(symbols, fixture.getEvents());
+		assertTrieStructure(fixture.trie, 2);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testUpdate_2() throws Exception {
+		int markovOrder = 2;
+		MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
+				new Random());
+		Collection<List<? extends Event<?>>> sequences = null;
+		fixture.trie = null;
+
+		fixture.update(sequences);
+	}
+
+	@Before
+	public void setUp() throws Exception {
+		sequence = new ArrayList<Event<?>>();
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("c"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("d"));
+		sequence.add(new Event<String>("a"));
+		sequence.add(new Event<String>("b"));
+		sequence.add(new Event<String>("r"));
+		sequence.add(new Event<String>("a"));
+
+		symbols = new HashSet<Event<?>>();
+		symbols.add(new Event<String>("a"));
+		symbols.add(new Event<String>("b"));
+		symbols.add(new Event<String>("c"));
+		symbols.add(new Event<String>("d"));
+		symbols.add(new Event<String>("r"));
+		symbols.add(Event.STARTEVENT);
+		symbols.add(Event.ENDEVENT);
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(TrieBasedModelTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/TrieTest.java
===================================================================
--- /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/TrieTest.java	(revision 518)
+++ /trunk/quest-core-usageprofiles-test/src/test/java/de/ugoe/cs/quest/usageprofiles/TrieTest.java	(revision 518)
@@ -0,0 +1,727 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+
+import junitx.framework.ListAssert;
+
+import org.junit.*;
+
+import de.ugoe.cs.quest.usageprofiles.Trie;
+import de.ugoe.cs.quest.usageprofiles.TrieNode;
+import de.ugoe.cs.quest.usageprofiles.Trie.Edge;
+import de.ugoe.cs.quest.usageprofiles.Trie.TrieVertex;
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>TrieTest</code> contains tests for the class
+ * <code>{@link Trie}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class TrieTest {
+
+	List<String> sequence;
+	Collection<String> symbols;
+
+	private static void assertCollectionContent(Collection<?> c1,
+			Collection<?> c2) {
+		assertEquals(c1.size(), c2.size());
+		for (Object obj : c1) {
+			assertTrue(c2.contains(obj));
+		}
+	}
+
+	@Test
+	public void testTrie_1() throws Exception {
+
+		Trie<String> result = new Trie<String>();
+
+		assertNotNull(result);
+		assertEquals(0, result.getNumLeafs());
+		assertEquals(0, result.getNumSymbols());
+		assertEquals(0, result.getNumLeafAncestors());
+		assertTrue(result.getKnownSymbols().isEmpty());
+	}
+
+	@Test
+	public void testTrie_2() throws Exception {
+		Trie<String> trie1 = new Trie<String>();
+		trie1.train(sequence, 3);
+
+		Trie<String> result = new Trie<String>(trie1);
+
+		assertEquals(trie1, result);
+		assertNotSame(trie1, result);
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testTrie_3() throws Exception {
+		new Trie<String>(null);
+	}
+
+	@Test
+	public void testAdd_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		List<String> seq = new ArrayList<String>();
+		seq.add("a");
+		seq.add("b");
+
+		fixture.add(seq);
+
+		assertEquals(1, fixture.getChild("a").getCount());
+		assertEquals(1, fixture.getChild("a").getChild("b").getCount());
+		assertNull(fixture.getChild("b"));
+	}
+
+	@Test
+	public void testAdd_2() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+
+		fixture.add(new ArrayList<String>());
+
+		assertEquals(0, fixture.getNumSymbols());
+	}
+
+	@Test
+	public void testAdd_3() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+
+		fixture.add(null);
+
+		assertEquals(0, fixture.getNumSymbols());
+	}
+
+	@Test
+	public void testFind_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> findSequence = new ArrayList<String>();
+		findSequence.add("a");
+		findSequence.add("b");
+		findSequence.add("r");
+		TrieNode<String> expected = fixture.getChild("a").getChild("b")
+				.getChild("r");
+
+		TrieNode<String> result = fixture.find(findSequence);
+
+		assertEquals(expected, result);
+	}
+
+	@Test
+	public void testFind_2() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> findSequence = new ArrayList<String>();
+		findSequence.add("c");
+		findSequence.add("a");
+		TrieNode<String> expected = fixture.getChild("c").getChild("a");
+
+		TrieNode<String> result = fixture.find(findSequence);
+
+		assertEquals(expected, result);
+	}
+
+	@Test
+	public void testFind_3() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> findSequence = new ArrayList<String>();
+
+		TrieNode<String> result = fixture.find(findSequence);
+
+		assertTrue(result.isRoot());
+	}
+
+	@Test
+	public void testFind_4() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+
+		TrieNode<String> result = fixture.find(null);
+
+		assertTrue(result.isRoot());
+	}
+
+	@Test
+	public void testGetChildCreate_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		String symbol = "a";
+
+		TrieNode<String> result = fixture.getChildCreate(symbol);
+
+		assertEquals(symbol, result.getSymbol());
+		assertEquals(0, result.getCount());
+		assertTrue(result.isLeaf());
+	}
+
+	@Test(expected = java.security.InvalidParameterException.class)
+	public void testGetChildCreate_2() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.getChildCreate(null);
+	}
+
+	@Test
+	public void testGetContextSuffix_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> context = new ArrayList<String>();
+		context.add("a");
+		context.add("a");
+		context.add("b");
+		List<String> expected = new ArrayList<String>();
+		expected.add("a");
+		expected.add("b");
+
+		List<String> result = fixture.getContextSuffix(context);
+
+		ListAssert.assertEquals(expected, result);
+	}
+
+	@Test
+	public void testGetContextSuffix_2() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> context = new ArrayList<String>();
+		context.add("a");
+		context.add("a");
+		context.add("b");
+		context.add("r");
+		List<String> expected = new ArrayList<String>();
+		expected.add("b");
+		expected.add("r");
+
+		List<String> result = fixture.getContextSuffix(context);
+
+		ListAssert.assertEquals(expected, result);
+	}
+
+	@Test
+	public void testGetContextSuffix_3() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> context = new ArrayList<String>();
+		context.add("a");
+		context.add("a");
+		context.add("b");
+		context.add("x");
+		List<String> expected = new ArrayList<String>();
+
+		List<String> result = fixture.getContextSuffix(context);
+
+		ListAssert.assertEquals(expected, result);
+	}
+
+	@Test
+	public void testGetContextSuffix_4() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+
+		List<String> result = fixture.getContextSuffix(null);
+
+		// add additional test code here
+		assertNotNull(result);
+		assertEquals(0, result.size());
+	}
+
+	@Test
+	public void testGetContextSuffix_5() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> context = new ArrayList<String>();
+		context.add("a");
+		context.add("a");
+		context.add("b");
+		List<String> expected = new ArrayList<String>();
+		expected.add("a");
+		expected.add("b");
+
+		List<String> result = fixture.getContextSuffix(context);
+
+		ListAssert.assertEquals(expected, result);
+	}
+
+	@Test
+	public void testGetCount_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+		subSequence.add("a");
+
+		int result = fixture.getCount(subSequence);
+
+		assertEquals(5, result);
+	}
+
+	@Test
+	public void testGetCount_2() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+		subSequence.add("a");
+		subSequence.add("b");
+
+		int result = fixture.getCount(subSequence);
+
+		assertEquals(2, result);
+	}
+
+	@Test
+	public void testGetCount_3() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+		subSequence.add("x");
+
+		int result = fixture.getCount(subSequence);
+
+		assertEquals(0, result);
+	}
+
+	@Test
+	public void testGetCount_4() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+
+		int result = fixture.getCount(subSequence, "a");
+
+		assertEquals(5, result);
+	}
+
+	@Test
+	public void testGetCount_5() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+		subSequence.add("a");
+		subSequence.add("b");
+
+		int result = fixture.getCount(subSequence, "r");
+
+		assertEquals(2, result);
+	}
+
+	@Test
+	public void testGetCount_6() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+
+		int result = fixture.getCount(subSequence, "x");
+
+		assertEquals(0, result);
+	}
+
+	@Test
+	public void testGetFollowingSymbols_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+		subSequence.add("a");
+		Collection<String> expected = new ArrayList<String>();
+		expected.add("b");
+		expected.add("c");
+		expected.add("d");
+
+		Collection<String> result = fixture.getFollowingSymbols(subSequence);
+
+		assertCollectionContent(expected, result);
+	}
+
+	@Test
+	public void testGetFollowingSymbols_2() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+		subSequence.add("a");
+		subSequence.add("b");
+		subSequence.add("r");
+
+		Collection<String> result = fixture.getFollowingSymbols(subSequence);
+
+		assertEquals(0, result.size());
+	}
+
+	@Test
+	public void testGetFollowingSymbols_3() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+		List<String> subSequence = new ArrayList<String>();
+		subSequence.add("x");
+
+		Collection<String> result = fixture.getFollowingSymbols(subSequence);
+
+		assertEquals(0, result.size());
+	}
+
+	@Test
+	public void testGetNumLeafAncestors_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+
+		int result = fixture.getNumLeafAncestors();
+
+		assertEquals(7, result);
+	}
+
+	@Test
+	public void testGetNumLeafs_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+
+		int result = fixture.getNumLeafs();
+
+		assertEquals(7, result);
+	}
+
+	@Test
+	public void testGetNumSymbols_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+
+		int result = fixture.getNumSymbols();
+
+		assertEquals(5, result);
+	}
+
+	@Test
+	public void testTrain_1() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		int maxOrder = 3;
+
+		fixture.train(sequence, maxOrder);
+
+		// check if symbols are correct
+		assertCollectionContent(symbols, fixture.getKnownSymbols());
+
+		// check if counters are correct and only the correct nodes exist
+		TrieNode<String> root = fixture.find(new ArrayList<String>());
+		TrieNode<String> root_a = root.getChild("a");
+		TrieNode<String> root_a_a = root_a.getChild("a");
+		TrieNode<String> root_a_b = root_a.getChild("b");
+		TrieNode<String> root_a_b_a = root_a_b.getChild("a");
+		TrieNode<String> root_a_b_b = root_a_b.getChild("b");
+		TrieNode<String> root_a_b_c = root_a_b.getChild("c");
+		TrieNode<String> root_a_b_d = root_a_b.getChild("d");
+		TrieNode<String> root_a_b_r = root_a_b.getChild("r");
+		TrieNode<String> root_a_c = root_a.getChild("c");
+		TrieNode<String> root_a_c_a = root_a_c.getChild("a");
+		TrieNode<String> root_a_c_b = root_a_c.getChild("b");
+		TrieNode<String> root_a_c_c = root_a_c.getChild("c");
+		TrieNode<String> root_a_c_d = root_a_c.getChild("d");
+		TrieNode<String> root_a_c_r = root_a_c.getChild("r");
+		TrieNode<String> root_a_d = root_a.getChild("d");
+		TrieNode<String> root_a_d_a = root_a_d.getChild("a");
+		TrieNode<String> root_a_d_b = root_a_d.getChild("b");
+		TrieNode<String> root_a_d_c = root_a_d.getChild("c");
+		TrieNode<String> root_a_d_d = root_a_d.getChild("d");
+		TrieNode<String> root_a_d_r = root_a_d.getChild("r");
+		TrieNode<String> root_a_r = root_a.getChild("r");
+		TrieNode<String> root_b = root.getChild("b");
+		TrieNode<String> root_b_a = root_b.getChild("a");
+		TrieNode<String> root_b_b = root_b.getChild("b");
+		TrieNode<String> root_b_c = root_b.getChild("c");
+		TrieNode<String> root_b_d = root_b.getChild("d");
+		TrieNode<String> root_b_r = root_b.getChild("r");
+		TrieNode<String> root_b_r_a = root_b_r.getChild("a");
+		TrieNode<String> root_b_r_b = root_b_r.getChild("b");
+		TrieNode<String> root_b_r_c = root_b_r.getChild("c");
+		TrieNode<String> root_b_r_d = root_b_r.getChild("d");
+		TrieNode<String> root_b_r_r = root_b_r.getChild("r");
+		TrieNode<String> root_c = root.getChild("c");
+		TrieNode<String> root_c_a = root_c.getChild("a");
+		TrieNode<String> root_c_a_a = root_c_a.getChild("a");
+		TrieNode<String> root_c_a_b = root_c_a.getChild("b");
+		TrieNode<String> root_c_a_c = root_c_a.getChild("c");
+		TrieNode<String> root_c_a_d = root_c_a.getChild("d");
+		TrieNode<String> root_c_a_r = root_c_a.getChild("r");
+		TrieNode<String> root_c_b = root_c.getChild("b");
+		TrieNode<String> root_c_c = root_c.getChild("c");
+		TrieNode<String> root_c_d = root_c.getChild("d");
+		TrieNode<String> root_c_r = root_c.getChild("r");
+		TrieNode<String> root_d = root.getChild("d");
+		TrieNode<String> root_d_a = root_d.getChild("a");
+		TrieNode<String> root_d_a_a = root_d_a.getChild("a");
+		TrieNode<String> root_d_a_b = root_d_a.getChild("b");
+		TrieNode<String> root_d_a_c = root_d_a.getChild("c");
+		TrieNode<String> root_d_a_d = root_d_a.getChild("d");
+		TrieNode<String> root_d_a_r = root_d_a.getChild("r");
+		TrieNode<String> root_d_b = root_d.getChild("b");
+		TrieNode<String> root_d_c = root_d.getChild("c");
+		TrieNode<String> root_d_d = root_d.getChild("d");
+		TrieNode<String> root_d_r = root_d.getChild("r");
+		TrieNode<String> root_r = root.getChild("r");
+		TrieNode<String> root_r_a = root_r.getChild("a");
+		TrieNode<String> root_r_a_a = root_r_a.getChild("a");
+		TrieNode<String> root_r_a_b = root_r_a.getChild("b");
+		TrieNode<String> root_r_a_c = root_r_a.getChild("c");
+		TrieNode<String> root_r_a_d = root_r_a.getChild("d");
+		TrieNode<String> root_r_a_r = root_r_a.getChild("r");
+		TrieNode<String> root_r_b = root_r.getChild("b");
+		TrieNode<String> root_r_c = root_r.getChild("c");
+		TrieNode<String> root_r_d = root_r.getChild("d");
+		TrieNode<String> root_r_r = root_r.getChild("r");
+
+		assertEquals(5, root_a.getCount());
+		assertNull(root_a_a);
+		assertEquals(2, root_a_b.getCount());
+		assertNull(root_a_b_a);
+		assertNull(root_a_b_b);
+		assertNull(root_a_b_c);
+		assertNull(root_a_b_d);
+		assertEquals(2, root_a_b_r.getCount());
+		assertEquals(1, root_a_c.getCount());
+		assertEquals(1, root_a_c_a.getCount());
+		assertNull(root_a_c_b);
+		assertNull(root_a_c_c);
+		assertNull(root_a_c_d);
+		assertNull(root_a_c_r);
+		assertEquals(1, root_a_d.getCount());
+		assertEquals(1, root_a_d_a.getCount());
+		assertNull(root_a_d_b);
+		assertNull(root_a_d_c);
+		assertNull(root_a_d_d);
+		assertNull(root_a_d_r);
+		assertNull(root_a_r);
+
+		assertEquals(2, root_b.getCount());
+		assertNull(root_b_a);
+		assertNull(root_b_b);
+		assertNull(root_b_c);
+		assertNull(root_b_d);
+		assertEquals(2, root_b_r.getCount());
+		assertEquals(2, root_b_r_a.getCount());
+		assertNull(root_b_r_b);
+		assertNull(root_b_r_c);
+		assertNull(root_b_r_d);
+		assertNull(root_b_r_r);
+
+		assertEquals(1, root_c.getCount());
+		assertEquals(1, root_c_a.getCount());
+		assertNull(root_c_a_a);
+		assertNull(root_c_a_b);
+		assertNull(root_c_a_c);
+		assertEquals(1, root_c_a_d.getCount());
+		assertNull(root_c_a_r);
+		assertNull(root_c_b);
+		assertNull(root_c_c);
+		assertNull(root_c_d);
+		assertNull(root_c_r);
+
+		assertEquals(1, root_d.getCount());
+		assertEquals(1, root_d_a.getCount());
+		assertNull(root_d_a_a);
+		assertEquals(1, root_d_a_b.getCount());
+		assertNull(root_d_a_c);
+		assertNull(root_d_a_d);
+		assertNull(root_d_a_r);
+		assertNull(root_d_b);
+		assertNull(root_d_c);
+		assertNull(root_d_d);
+		assertNull(root_d_r);
+
+		assertEquals(2, root_r.getCount());
+		assertEquals(2, root_r_a.getCount());
+		assertNull(root_r_a_a);
+		assertNull(root_r_a_b);
+		assertEquals(1, root_r_a_c.getCount());
+		assertNull(root_r_a_d);
+		assertNull(root_r_a_r);
+		assertNull(root_r_b);
+		assertNull(root_r_c);
+		assertNull(root_r_d);
+		assertNull(root_r_r);
+
+		// check if leafs are really leafs
+		assertTrue(root_a_b_r.isLeaf());
+		assertTrue(root_a_c_a.isLeaf());
+		assertTrue(root_a_d_a.isLeaf());
+		assertTrue(root_b_r_a.isLeaf());
+		assertTrue(root_c_a_d.isLeaf());
+		assertTrue(root_d_a_b.isLeaf());
+		assertTrue(root_r_a_c.isLeaf());
+	}
+
+	@Test
+	public void testTrain_2() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		int maxOrder = 0;
+
+		fixture.train(sequence, maxOrder);
+
+		assertTrue(fixture.getKnownSymbols().isEmpty());
+	}
+
+	@Test
+	public void testTrain_3() throws Exception {
+		Trie<Object> fixture = new Trie<Object>();
+		List<Object> sequence = new ArrayList<Object>();
+		int maxOrder = 1;
+
+		fixture.train(sequence, maxOrder);
+
+		assertTrue(fixture.getKnownSymbols().isEmpty());
+	}
+
+	@Test
+	public void testTrain_4() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		List<String> sequence = new ArrayList<String>();
+		sequence.add("a");
+		sequence.add("b");
+		int maxOrder = 3;
+
+		fixture.train(sequence, maxOrder);
+
+		assertCollectionContent(sequence, fixture.getKnownSymbols());
+		TrieNode<String> root = fixture.find(new ArrayList<String>());
+		TrieNode<String> root_a = root.getChild("a");
+		TrieNode<String> root_a_a = root_a.getChild("a");
+		TrieNode<String> root_a_b = root_a.getChild("b");
+		TrieNode<String> root_b = root.getChild("b");
+		TrieNode<String> root_b_a = root_b.getChild("a");
+		TrieNode<String> root_b_b = root_b.getChild("b");
+
+		assertEquals(1, root_a.getCount());
+		assertNull(root_a_a);
+		assertEquals(1, root_a_b.getCount());
+		assertEquals(1, root_b.getCount());
+		assertNull(root_b_a);
+		assertNull(root_b_b);
+
+		assertTrue(root_a_b.isLeaf());
+		assertTrue(root_b.isLeaf());
+	}
+
+	@Test
+	public void testEdgeEdge_1() throws Exception {
+		Edge result = new Edge();
+
+		assertNotNull(result);
+	}
+
+	@Test
+	public void testTrieVertexTrieVertex_1() throws Exception {
+		String id = "idString";
+
+		TrieVertex result = new TrieVertex(id);
+
+		assertNotNull(result);
+	}
+
+	@Test
+	public void testTrieVertexToString_1() throws Exception {
+		String id = "idString";
+		TrieVertex fixture = new TrieVertex(id);
+
+		String result = fixture.toString();
+
+		assertEquals(id, result);
+	}
+
+	@Test
+	public void testEquals_1() throws Exception {
+		Trie<String> trieOther = new Trie<String>();
+		Trie<String> fixture = new Trie<String>();
+
+		boolean result = fixture.equals(trieOther);
+
+		assertEquals(true, result);
+	}
+
+	@Test
+	public void testEquals_2() throws Exception {
+		Trie<String> trieOther = new Trie<String>();
+		trieOther.train(sequence, 2);
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 2);
+
+		boolean result = fixture.equals(trieOther);
+
+		assertEquals(true, result);
+	}
+
+	@Test
+	public void testEquals_3() throws Exception {
+		Trie<String> trieOther = new Trie<String>();
+		trieOther.train(sequence, 2);
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 3);
+
+		boolean result = fixture.equals(trieOther);
+
+		assertEquals(false, result);
+	}
+
+	@Test
+	public void testEquals_4() throws Exception {
+		Trie<String> trieOther = new Trie<String>();
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 2);
+
+		boolean result = fixture.equals(trieOther);
+
+		assertEquals(false, result);
+	}
+
+	@Test
+	public void testEquals_5() throws Exception {
+		Trie<String> trieOther = new Trie<String>();
+		trieOther.train(sequence, 2);
+		Trie<String> fixture = new Trie<String>();
+
+		boolean result = fixture.equals(trieOther);
+
+		assertEquals(false, result);
+	}
+
+	@Test
+	public void testEquals_6() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 2);
+
+		boolean result = fixture.equals(fixture);
+
+		assertEquals(true, result);
+	}
+
+	@Test
+	public void testEquals_7() throws Exception {
+		Trie<String> fixture = new Trie<String>();
+		fixture.train(sequence, 2);
+
+		boolean result = fixture.equals(null);
+
+		assertEquals(false, result);
+	}
+
+	@Before
+	public void setUp() throws Exception {
+		sequence = new ArrayList<String>();
+		sequence.add("a");
+		sequence.add("b");
+		sequence.add("r");
+		sequence.add("a");
+		sequence.add("c");
+		sequence.add("a");
+		sequence.add("d");
+		sequence.add("a");
+		sequence.add("b");
+		sequence.add("r");
+		sequence.add("a");
+
+		symbols = new HashSet<String>();
+		symbols.add("a");
+		symbols.add("b");
+		symbols.add("c");
+		symbols.add("d");
+		symbols.add("r");
+	}
+
+	public static void main(String[] args) {
+		new org.junit.runner.JUnitCore().run(TrieTest.class);
+	}
+}
Index: /trunk/quest-core-usageprofiles/.classpath
===================================================================
--- /trunk/quest-core-usageprofiles/.classpath	(revision 518)
+++ /trunk/quest-core-usageprofiles/.classpath	(revision 518)
@@ -0,0 +1,20 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/classes" path="src/main/java">
+		<attributes>
+			<attribute name="optional" value="true"/>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER">
+		<attributes>
+			<attribute name="maven.pomderived" value="true"/>
+		</attributes>
+	</classpathentry>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
Index: /trunk/quest-core-usageprofiles/.project
===================================================================
--- /trunk/quest-core-usageprofiles/.project	(revision 518)
+++ /trunk/quest-core-usageprofiles/.project	(revision 518)
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>quest-core-usageprofiles</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+		<buildCommand>
+			<name>org.eclipse.m2e.core.maven2Builder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.m2e.core.maven2Nature</nature>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
Index: /trunk/quest-core-usageprofiles/.settings/org.eclipse.jdt.core.prefs
===================================================================
--- /trunk/quest-core-usageprofiles/.settings/org.eclipse.jdt.core.prefs	(revision 518)
+++ /trunk/quest-core-usageprofiles/.settings/org.eclipse.jdt.core.prefs	(revision 518)
@@ -0,0 +1,5 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
Index: /trunk/quest-core-usageprofiles/.settings/org.eclipse.m2e.core.prefs
===================================================================
--- /trunk/quest-core-usageprofiles/.settings/org.eclipse.m2e.core.prefs	(revision 518)
+++ /trunk/quest-core-usageprofiles/.settings/org.eclipse.m2e.core.prefs	(revision 518)
@@ -0,0 +1,4 @@
+activeProfiles=
+eclipse.preferences.version=1
+resolveWorkspaceProjects=true
+version=1
Index: /trunk/quest-core-usageprofiles/pom.xml
===================================================================
--- /trunk/quest-core-usageprofiles/pom.xml	(revision 518)
+++ /trunk/quest-core-usageprofiles/pom.xml	(revision 518)
@@ -0,0 +1,30 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+	<modelVersion>4.0.0</modelVersion>
+	<groupId>de.ugoe.cs.quest</groupId>
+	<artifactId>quest-core-usageprofiles</artifactId>
+	<version>0.0.1-SNAPSHOT</version>
+	<name>quest-core-usageprofiles</name>
+	<scm>
+		<url>https://quest.informatik.uni-goettingen.de/svn/quest/trunk/quest-core-usageprofiles</url>
+	</scm>
+	<dependencies>
+		<dependency>
+			<groupId>de.ugoe.cs.quest</groupId>
+			<artifactId>quest-core-events</artifactId>
+			<version>0.0.1-SNAPSHOT</version>
+		</dependency>
+	</dependencies>
+	<build>
+		<plugins>
+			<plugin>
+				<artifactId>maven-compiler-plugin</artifactId>
+				<version>2.3.2</version>
+				<configuration>
+					<source>1.6</source>
+					<target>1.6</target>
+				</configuration>
+			</plugin>
+		</plugins>
+	</build>
+</project>
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java	(revision 518)
@@ -0,0 +1,80 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ * <p>
+ * Implements a Deterministic Finite Automata (DFA) capable of random session
+ * generation. It is a special case of a first-order Markov model, where the
+ * transition probability is equally high for all following states.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class DeterministicFiniteAutomaton extends FirstOrderMarkovModel {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new DeterministicFiniteAutomaton.
+	 * </p>
+	 * 
+	 * @param r
+	 *            random number generator used by probabilistic methods of the
+	 *            class
+	 */
+	public DeterministicFiniteAutomaton(Random r) {
+		super(r);
+	}
+
+	/**
+	 * <p>
+	 * Calculates the proability of the next state. Each of the following states
+	 * in the automaton is equally probable.
+	 * </p>
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List,
+	 *      de.ugoe.cs.quest.eventcore.Event)
+	 */
+	@Override
+	public double getProbability(List<? extends Event<?>> context,
+			Event<?> symbol) {
+		if( context==null ) {
+			throw new InvalidParameterException("context must not be null");
+		}
+		if( symbol==null ) {
+			throw new InvalidParameterException("symbol must not be null");
+		}
+		double result = 0.0d;
+
+		List<Event<?>> contextCopy;
+		if (context.size() >= trieOrder) {
+			contextCopy = new LinkedList<Event<?>>(context.subList(
+					context.size() - trieOrder + 1, context.size()));
+		} else {
+			contextCopy = new LinkedList<Event<?>>(context);
+		}
+
+		Collection<Event<?>> followers = trie.getFollowingSymbols(contextCopy);
+
+		if (followers.size() != 0 && followers.contains(symbol)) {
+			result = 1.0d / followers.size();
+		}
+
+		return result;
+	}
+
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/FirstOrderMarkovModel.java	(revision 518)
@@ -0,0 +1,264 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.util.StringTools;
+import de.ugoe.cs.util.console.Console;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.SparseMultigraph;
+import edu.uci.ics.jung.graph.util.EdgeType;
+
+import Jama.Matrix;
+
+/**
+ * <p>
+ * Implements first-order Markov models. The implementation is based on
+ * {@link HighOrderMarkovModel} and restricts the Markov order to 1. In
+ * comparison to {@link HighOrderMarkovModel}, more calculations are possible
+ * with first-order models, e.g., the calculation of the entropy (
+ * {@link #calcEntropy()}).
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class FirstOrderMarkovModel extends HighOrderMarkovModel implements
+		IDotCompatible {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Maximum number of iterations when calculating the stationary distribution
+	 * as the limit of multiplying the transmission matrix with itself.
+	 * </p>
+	 */
+	final static int MAX_STATDIST_ITERATIONS = 1000;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new FirstOrderMarkovModel.
+	 * </p>
+	 * 
+	 * @param r
+	 *            random number generator used by probabilistic methods of the
+	 *            class
+	 */
+	public FirstOrderMarkovModel(Random r) {
+		super(1, r);
+	}
+
+	/**
+	 * <p>
+	 * Generates the transmission matrix of the Markov model.
+	 * </p>
+	 * 
+	 * @return transmission matrix
+	 */
+	private Matrix getTransmissionMatrix() {
+		List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+				trie.getKnownSymbols());
+		int numStates = knownSymbols.size();
+		Matrix transmissionMatrix = new Matrix(numStates, numStates);
+
+		for (int i = 0; i < numStates; i++) {
+			Event<?> currentSymbol = knownSymbols.get(i);
+			List<Event<?>> context = new ArrayList<Event<?>>();
+			context.add(currentSymbol);
+			for (int j = 0; j < numStates; j++) {
+				Event<?> follower = knownSymbols.get(j);
+				double prob = getProbability(context, follower);
+				transmissionMatrix.set(i, j, prob);
+			}
+		}
+		return transmissionMatrix;
+	}
+
+	/**
+	 * <p>
+	 * Calculates the entropy of the model. To make it possible that the model
+	 * is stationary, a transition from {@link Event#ENDEVENT} to
+	 * {@link Event#STARTEVENT} is added.
+	 * </p>
+	 * 
+	 * @return entropy of the model or NaN if it could not be calculated
+	 */
+	public double calcEntropy() {
+		Matrix transmissionMatrix = getTransmissionMatrix();
+		List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+				trie.getKnownSymbols());
+		int numStates = knownSymbols.size();
+
+		List<Integer> startIndexList = new LinkedList<Integer>();
+		List<Integer> endIndexList = new LinkedList<Integer>();
+		for( int i=0 ; i<knownSymbols.size() ; i++ ) {
+			String id = knownSymbols.get(i).getStandardId();
+			if( id.equals(Event.STARTEVENT.getStandardId()) || id.contains(Event.STARTEVENT.getStandardId()+"-=-") ) {
+				startIndexList.add(i);
+			}
+			if( id.equals(Event.ENDEVENT.getStandardId()) || id.contains("-=-"+Event.ENDEVENT.getStandardId()) ) {
+				endIndexList.add(i);
+			}
+		}
+		
+		if (startIndexList.isEmpty()) {	
+			Console.printerrln("Error calculating entropy. Initial state of markov chain not found.");
+			return Double.NaN;
+		}
+		if (endIndexList.isEmpty()) {
+			Console.printerrln("Error calculating entropy. End state of markov chain not found.");
+			return Double.NaN;
+		}
+		for( Integer i : endIndexList ) {
+			for(Integer j : startIndexList ) {
+				transmissionMatrix.set(i, j, 1);
+			}
+		}
+
+		// Calculate stationary distribution by raising the power of the
+		// transmission matrix.
+		// The rank of the matrix should fall to 1 and each two should be the
+		// vector of the stationory distribution.
+		int iter = 0;
+		int rank = transmissionMatrix.rank();
+		Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone();
+		while (iter < MAX_STATDIST_ITERATIONS && rank > 1) {
+			stationaryMatrix = stationaryMatrix.times(stationaryMatrix);
+			rank = stationaryMatrix.rank();
+			iter++;
+		}
+
+		if (rank != 1) {
+			Console.traceln("rank: " + rank);
+			Console.printerrln("Unable to calculate stationary distribution.");
+			return Double.NaN;
+		}
+
+		double entropy = 0.0;
+		for (int i = 0; i < numStates; i++) {
+			for (int j = 0; j < numStates; j++) {
+				if (transmissionMatrix.get(i, j) != 0 && transmissionMatrix.get(i, j)!=1) {
+					double tmp = stationaryMatrix.get(0, i);
+					tmp *= transmissionMatrix.get(i, j);
+					tmp *= Math.log(transmissionMatrix.get(i, j)) / Math.log(2);
+					entropy -= tmp;
+				}
+			}
+		}
+		return entropy;
+	}
+
+	/**
+	 * <p>
+	 * The dot represenation of {@link FirstOrderMarkovModel}s is its graph
+	 * representation with the states as nodes and directed edges weighted with
+	 * transition probabilities.
+	 * </p>
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation()
+	 */
+	@Override
+	public String getDotRepresentation() {
+		StringBuilder stringBuilder = new StringBuilder();
+		stringBuilder.append("digraph model {" + StringTools.ENDLINE);
+
+		List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+				trie.getKnownSymbols());
+		for (Event<?> symbol : knownSymbols) {
+			final String thisSaneId = symbol.getShortId().replace("\"", "\\\"")
+					.replaceAll("[\r\n]", "");
+			stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " [label=\""
+					+ thisSaneId + "\"];" + StringTools.ENDLINE);
+			List<Event<?>> context = new ArrayList<Event<?>>();
+			context.add(symbol);
+			Collection<Event<?>> followers = trie.getFollowingSymbols(context);
+			for (Event<?> follower : followers) {
+				stringBuilder.append(" " + knownSymbols.indexOf(symbol) + " -> "
+						+ knownSymbols.indexOf(follower) + " ");
+				stringBuilder.append("[label=\""
+						+ getProbability(context, follower) + "\"];"
+						+ StringTools.ENDLINE);
+			}
+		}
+		stringBuilder.append('}' + StringTools.ENDLINE);
+		return stringBuilder.toString();
+	}
+
+	/**
+	 * <p>
+	 * Returns a {@link Graph} representation of the model with the states as
+	 * nodes and directed edges weighted with transition probabilities.
+	 * </p>
+	 * 
+	 * @return {@link Graph} of the model
+	 */
+	public Graph<String, MarkovEdge> getGraph() {
+		Graph<String, MarkovEdge> graph = new SparseMultigraph<String, MarkovEdge>();
+
+		List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+				trie.getKnownSymbols());
+
+		for (Event<?> symbol : knownSymbols) {
+			String from = symbol.getShortId();
+			List<Event<?>> context = new ArrayList<Event<?>>();
+			context.add(symbol);
+
+			Collection<Event<?>> followers = trie.getFollowingSymbols(context);
+
+			for (Event<?> follower : followers) {
+				String to = follower.getShortId();
+				MarkovEdge prob = new MarkovEdge(getProbability(context,
+						follower));
+				graph.addEdge(prob, from, to, EdgeType.DIRECTED);
+			}
+		}
+		return graph;
+	}
+
+	/**
+	 * Inner class used for the {@link Graph} representation of the model.
+	 * 
+	 * @author Steffen Herbold
+	 * @version 1.0
+	 */
+	static public class MarkovEdge {
+		/**
+		 * <p>
+		 * Weight of the edge, i.e., its transition probability.
+		 * </p>
+		 */
+		double weight;
+
+		/**
+		 * <p>
+		 * Constructor. Creates a new MarkovEdge.
+		 * </p>
+		 * 
+		 * @param weight
+		 *            weight of the edge, i.e., its transition probability
+		 */
+		MarkovEdge(double weight) {
+			this.weight = weight;
+		}
+
+		/**
+		 * <p>
+		 * The weight of the edge as {@link String}.
+		 * </p>
+		 */
+		public String toString() {
+			return "" + weight;
+		}
+	}
+
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/HighOrderMarkovModel.java	(revision 518)
@@ -0,0 +1,87 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ * <p>
+ * Implements high-order Markov models.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class HighOrderMarkovModel extends TrieBasedModel {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new HighOrderMarkovModel with a defined Markov
+	 * order.
+	 * </p>
+	 * 
+	 * @param maxOrder
+	 *            Markov order of the model
+	 * @param r
+	 *            random number generator used by probabilistic methods of the
+	 *            class
+	 */
+	public HighOrderMarkovModel(int maxOrder, Random r) {
+		super(maxOrder, r);
+	}
+
+	/**
+	 * <p>
+	 * Calculates the probability of the next Event being symbol based on the
+	 * order of the Markov model. The order is defined in the constructor
+	 * {@link #HighOrderMarkovModel(int, Random)}.
+	 * </p>
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List,
+	 *      de.ugoe.cs.quest.eventcore.Event)
+	 */
+	@Override
+	public double getProbability(List<? extends Event<?>> context,
+			Event<?> symbol) {
+		if (context == null) {
+			throw new InvalidParameterException("context must not be null");
+		}
+		if (symbol == null) {
+			throw new InvalidParameterException("symbol must not be null");
+		}
+		double result = 0.0d;
+
+		List<Event<?>> contextCopy;
+		if (context.size() >= trieOrder) {
+			contextCopy = new LinkedList<Event<?>>(context.subList(
+					context.size() - trieOrder + 1, context.size()));
+		} else {
+			contextCopy = new LinkedList<Event<?>>(context);
+		}
+
+		Collection<Event<?>> followers = trie.getFollowingSymbols(contextCopy);
+		int sumCountFollowers = 0; // N(s\sigma')
+		for (Event<?> follower : followers) {
+			sumCountFollowers += trie.getCount(contextCopy, follower);
+		}
+
+		int countSymbol = trie.getCount(contextCopy, symbol);
+		if (sumCountFollowers != 0) {
+			result = ((double) countSymbol / sumCountFollowers);
+		}
+
+		return result;
+	}
+
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IDotCompatible.java	(revision 518)
@@ -0,0 +1,22 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+/**
+ * <p>
+ * Models implementing this interface provide a graph representation of
+ * themselves as a {@link String} with Dot syntax.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public interface IDotCompatible {
+
+	/**
+	 * <p>
+	 * Returns a Dot representation of the model.
+	 * </p>
+	 * 
+	 * @return string with Dot syntax that describes the model.
+	 */
+	public abstract String getDotRepresentation();
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IMemory.java	(revision 518)
@@ -0,0 +1,40 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.List;
+
+/**
+ * <p>
+ * This interface defines basic functions for classes that implement a memory
+ * about the recent events of a sequences.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ * 
+ * @param <T>
+ *            Type of the sequence elements that are memorized.
+ */
+public interface IMemory<T> {
+
+	/**
+	 * Adds an element to the end of the memory.
+	 * 
+	 * @param element
+	 *            Element to be added.
+	 */
+	public void add(T element);
+
+	/**
+	 * <p>
+	 * Returns the last <code>num</code> memorized elements. If the history is
+	 * shorter than <code>num</code>, the length of the returned
+	 * {@link java.util.List} may be less than <code>num</code>.
+	 * </p>
+	 * 
+	 * @param num
+	 *            Number of states from the end of the memory to be returned.
+	 * @return {@link java.util.List} of memorized elements.
+	 */
+	public List<T> getLast(int num);
+
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IStochasticProcess.java	(revision 518)
@@ -0,0 +1,194 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.io.Serializable;
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.List;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ * <p>
+ * This interface defines the functionalities provided by stochastic processes.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public interface IStochasticProcess extends Serializable {
+
+	/**
+	 * <p>
+	 * Returns the probability, that the next event is {@code symbol} given the
+	 * last events are {@code context}. The last element of {@code context} is
+	 * the most recent in the history, the first element is the oldest.
+	 * </p>
+	 * 
+	 * @param context
+	 *            recently observed symbols
+	 * @param symbol
+	 *            event for which the probability is calculated
+	 * @return probabilty the {@code symbol} is the next event, given the last
+	 *         events {@code context}
+	 * @throws InvalidParameterException
+	 *             thrown if context or symbol is null
+	 */
+	double getProbability(List<? extends Event<?>> context, Event<?> symbol);
+
+	/**
+	 * <p>
+	 * Returns the probabilitiy that a given sequence is generated by the
+	 * stochastic process.
+	 * </p>
+	 * 
+	 * @param sequence
+	 *            sequences of which the probability is calculated
+	 * @return probability of the sequences; 1.0 if sequence is empty or null
+	 * @throws InvalidParameterException
+	 *             thrown if sequence is null
+	 */
+	double getProbability(List<? extends Event<?>> sequence);
+
+	/**
+	 * <p>
+	 * Generates a random sequence of events. The sequence starts with
+	 * {@link Event#STARTEVENT} and finishes with {@link Event#ENDEVENT}.
+	 * </p>
+	 * 
+	 * @return randomly generated sequence
+	 */
+	public List<? extends Event<?>> randomSequence();
+
+	/**
+	 * <p>
+	 * Generates a random sequence of events. The sequence starts with
+	 * {@link Event#STARTEVENT} and finishes with
+	 * <ul>
+	 * <li>{@link Event#ENDEVENT} if validEnd==true.</li>
+	 * <li>b) if a generated sequences reaches {@link Event#ENDEVENT} before
+	 * maxLength, the sequence finishes and is shorter than maxLenght.
+	 * Otherwise, the sequence finishes as soon as maxLength is reached and the
+	 * final event of the sequence must not be {@link Event#ENDEVENT}.</li>
+	 * </ul>
+	 * </p>
+	 * 
+	 * @param maxLength
+	 *            maximum length of the generated sequence
+	 * @param validEnd
+	 *            if true, only sequences that finish with
+	 *            {@link Event#ENDEVENT} are generated
+	 * @return randomly generated sequence
+	 * 
+	 */
+	public List<? extends Event<?>> randomSequence(int maxLength,
+			boolean validEnd);
+
+	/**
+	 * <p>
+	 * Generates all sequences of a given length are possible, i.e., have a
+	 * positive probability.<br>
+	 * All states are used as possible starting states.
+	 * </p>
+	 * 
+	 * @param length
+	 *            length of the generated sequences
+	 * @return generated sequences
+	 * @see #generateSequences(int, boolean)
+	 * @throws InvalidParameterException
+	 *             thrown if length is less than or equal to 0
+	 */
+	public Collection<List<? extends Event<?>>> generateSequences(int length);
+
+	/**
+	 * <p>
+	 * Generates all sequences of given length that can are possible, i.e., have
+	 * positive probability.<br>
+	 * If {@code fromStart==true}, all generated sequences start in
+	 * {@link Event#STARTEVENT}. Otherwise this method is the same as
+	 * {@link #generateSequences(int)}.
+	 * </p>
+	 * 
+	 * @param length
+	 *            length of the generated sequences
+	 * @param fromStart
+	 *            if true, all generated sequences start with
+	 *            {@link Event#STARTEVENT}
+	 * @return generated sequences
+	 * @throws InvalidParameterException
+	 *             thrown if length is less than or equal to 0
+	 */
+	public Collection<List<? extends Event<?>>> generateSequences(int length,
+			boolean fromStart);
+
+	/**
+	 * <p>
+	 * Generates all sequences starting with {@link Event#STARTEVENT} and
+	 * finishing with {@link Event#ENDEVENT} of a given length. It is possible
+	 * that no such sequence exists with the defined length and the returned set
+	 * is empty. If {@code length} is less than 2 the returned set is always
+	 * empty.
+	 * </p>
+	 * 
+	 * @param length
+	 * @return generated sequences
+	 * @throws InvalidParameterException
+	 *             thrown if length is less than or equal to 0
+	 */
+	public Collection<List<? extends Event<?>>> generateValidSequences(
+			int length);
+
+	/**
+	 * <p>
+	 * Returns the number of states known by the stochastic process, i.e., the
+	 * size of its alphabet.
+	 * </p>
+	 * 
+	 * @return number of states
+	 */
+	public int getNumSymbols();
+
+	/**
+	 * <p>
+	 * Returns a string representation of all known states.
+	 * </p>
+	 * 
+	 * @return string representation for all known states
+	 */
+	public String[] getSymbolStrings();
+
+	/**
+	 * <p>
+	 * Returns the number of states the process would have if it would be
+	 * flattened through state-splitting to a first-order Markov model.
+	 * </p>
+	 * <p>
+	 * If it is not possible to flatten the model, -1 is returned.
+	 * </p>
+	 * 
+	 * @return number of states an equivalent FOM would have; -1 if not
+	 *         available
+	 */
+	public int getNumFOMStates();
+
+	/**
+	 * <p>
+	 * Returns the number of transitions the process would have if it would be
+	 * flattened through state-splitting to a first-order Markov model.
+	 * </p>
+	 * 
+	 * @return number of transitions an equivalent FOM would have; -1 if not
+	 *         available
+	 */
+	public int getNumTransitions();
+
+	/**
+	 * <p>
+	 * Returns all states known by the stochastic process, i.e., its
+	 * {@link Event}s.
+	 * </p>
+	 * 
+	 * @return events known by the process
+	 */
+	public Collection<? extends Event<?>> getEvents();
+
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/IncompleteMemory.java	(revision 518)
@@ -0,0 +1,95 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * <p>
+ * Implements a round-trip buffered memory of a specified length that can be
+ * used to remember the recent history. Every event that happend longer ago than
+ * the length of the memory is forgotten, hence the memory is incomplete.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ * 
+ * @param <T>
+ *            Type which is memorized.
+ */
+public class IncompleteMemory<T> implements IMemory<T> {
+
+	/**
+	 * <p>
+	 * Maximum length of the memory.
+	 * </p>
+	 */
+	private int length;
+
+	/**
+	 * <p>
+	 * Internal storage of the history.
+	 * </p>
+	 */
+	private List<T> history;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new IncompleteMemory.
+	 * </p>
+	 * 
+	 * @param length
+	 *            number of recent events that are remembered
+	 * @throws InvalidParameterException
+	 *             This exception is thrown if the length is smaller than 1
+	 */
+	public IncompleteMemory(int length) {
+		if (length < 1) {
+			throw new InvalidParameterException(
+					"Length of IncompleteMemory must be at least 1.");
+		}
+		this.length = length;
+		history = new LinkedList<T>();
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IMemory#add(java.lang.Object)
+	 */
+	@Override
+	public void add(T state) {
+		if (history.size() == length) {
+			history.remove(0);
+		}
+		history.add(state);
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IMemory#getLast(int)
+	 */
+	@Override
+	public List<T> getLast(int num) {
+		if( num<1 ) {
+			return new LinkedList<T>();
+		} else {
+		return new LinkedList<T>(history.subList(
+				Math.max(0, history.size() - num),
+				history.size())); // defensive copy
+		}
+	}
+
+	/**
+	 * <p>
+	 * Returns the current length of the memory. This can be less than
+	 * {@link #length}, if the overall history is less than {@link #length}.
+	 * </p>
+	 * 
+	 * @return length of the current memory
+	 */
+	public int getLength() {
+		return history.size();
+	}
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/ModelFlattener.java	(revision 518)
@@ -0,0 +1,137 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.eventcore.ReplayableEvent;
+
+/**
+ * <p>
+ * This class provides functions to create flattened first-order Markov models
+ * from {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch}
+ * models through state splitting.
+ * </p>
+ * <p>
+ * If possible, the normal high-order markov model should be used, as the Events
+ * may be broken by the flattener, as, e.g., the information
+ * {@link ReplayableEvent}s contain is not preserved.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class ModelFlattener {
+
+	private static final String EVENT_SEPARATOR = "-=-";
+
+	Trie<Event<?>> firstOrderTrie;
+
+	/**
+	 * <p>
+	 * Takes a {@link HighOrderMarkovModel} and returns a
+	 * {@link FirstOrderMarkovModel} that conserves the high-order memory
+	 * through state splitting.
+	 * </p>
+	 * 
+	 * @param model
+	 *            model that is flattened
+	 * @return flattened first-order Markov model
+	 */
+	public FirstOrderMarkovModel flattenHighOrderMarkovModel(
+			HighOrderMarkovModel model) {
+		int markovOrder = model.trieOrder - 1;
+		FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel(
+				new Random());
+		firstOrderModel.trieOrder = 2;
+		if (markovOrder == 1) {
+			firstOrderModel.trie = new Trie<Event<?>>(model.trie);
+			firstOrderModel.trieOrder = 2;
+		} else {
+			firstOrderTrie = new Trie<Event<?>>();
+			TrieNode<Event<?>> rootNode = model.trie.find(null);
+			generateFirstOrderTrie(rootNode, new LinkedList<String>(), markovOrder);
+			firstOrderTrie.updateKnownSymbols();
+			firstOrderModel.trie = firstOrderTrie;
+		}
+
+		return firstOrderModel;
+	}
+
+	/**
+	 * <p>
+	 * <b>This method is not available yet and always return null!</b>
+	 * </p>
+	 * <p>
+	 * Takes a {@link PredictionByPartialMatch} model and returns a
+	 * {@link FirstOrderMarkovModel} that conserves the high-order memory
+	 * through state splitting.
+	 * </p>
+	 * 
+	 * @param model
+	 *            model that is flattened
+	 * @return flattened first-order Markov model
+	 */
+	public FirstOrderMarkovModel flattenPredictionByPartialMatch(
+			PredictionByPartialMatch model) {
+		// TODO implement method
+		return null;
+	}
+
+	/**
+	 * <p>
+	 * Converts all nodes of the given depth into first-order node through
+	 * state-splitting. For each node at the given depth a new node is created
+	 * and appropriate transitions will be added.
+	 * </p>
+	 * <p>
+	 * This method traverses through the tree recursively. If the recursion
+	 * reaches the desired depth in the tree, node are added.
+	 * </p>
+	 * 
+	 * @param currentNode
+	 *            node whose sub-trie is currently traversed
+	 * @param parentIDs
+	 *            ID strings of the ancestors of the currentNode
+	 * @param depth
+	 *            depth to go - NOT the current depth.
+	 */
+	private void generateFirstOrderTrie(TrieNode<Event<?>> currentNode,
+			List<String> parentIDs, int depth) {
+		for (TrieNode<Event<?>> child : currentNode.getChildren()) {
+			String currentId = child.getSymbol().getStandardId();
+			if (depth > 1) {
+				List<String> childParentIDs = new LinkedList<String>(parentIDs);
+				childParentIDs.add(currentId);
+				generateFirstOrderTrie(child, childParentIDs, depth - 1);
+
+			} else {
+				StringBuilder firstOrderID = new StringBuilder();
+				for (String parentID : parentIDs) {
+					firstOrderID.append(parentID + EVENT_SEPARATOR);
+				}
+				firstOrderID.append(currentId);
+				TrieNode<Event<?>> firstOrderNode = firstOrderTrie
+						.getChildCreate(new Event<Object>(firstOrderID
+								.toString()));
+				firstOrderNode.setCount(child.getCount());
+				for (TrieNode<Event<?>> transitionChild : child.getChildren()) {
+					StringBuilder transitionID = new StringBuilder();
+					for (String parentID : parentIDs.subList(1,
+							parentIDs.size())) {
+						transitionID.append(parentID + EVENT_SEPARATOR);
+					}
+					transitionID.append(currentId + EVENT_SEPARATOR);
+					transitionID.append(transitionChild.getSymbol()
+							.getStandardId());
+					TrieNode<Event<?>> firstOrderTransitionChild = firstOrderNode
+							.getChildCreate(new Event<Object>(transitionID
+									.toString()));
+					firstOrderTransitionChild.setCount(transitionChild
+							.getCount());
+				}
+			}
+		}
+	}
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java	(revision 518)
@@ -0,0 +1,200 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import de.ugoe.cs.quest.eventcore.Event;
+
+/**
+ * <p>
+ * Implements Prediction by Partial Match (PPM) based on the following formula
+ * (LaTeX-style notation):<br>
+ * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n
+ * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})<br>
+ * P_{MM^i} denotes the probability in an i-th order Markov model.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * 
+ */
+public class PredictionByPartialMatch extends TrieBasedModel {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Minimum order of the Markov model.
+	 * </p>
+	 */
+	protected int minOrder;
+
+	/**
+	 * <p>
+	 * Probability to use a lower-order Markov model
+	 * </p>
+	 */
+	protected double probEscape;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new PredictionByPartialMatch model with a given
+	 * Markov order and a default escape probability of 0.1.
+	 * </p>
+	 * 
+	 * @param markovOrder
+	 *            Markov order of the model
+	 * @param r
+	 *            random number generator used by probabilistic methods of the
+	 *            class
+	 */
+	public PredictionByPartialMatch(int markovOrder, Random r) {
+		this(markovOrder, r, 0.1);
+	}
+
+	/**
+	 * <p>
+	 * Creates a new PredictionByPartialMatch model with a given Markov order
+	 * and escape probability.
+	 * </p>
+	 * 
+	 * @param markovOrder
+	 *            Markov order of the model
+	 * @param r
+	 *            random number generator used by probabilistic methods of the
+	 *            class
+	 * @param probEscape
+	 *            escape probability used by the model
+	 */
+	public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) {
+		this(markovOrder, 0, r, probEscape);
+	}
+
+	/**
+	 * <p>
+	 * Creates a new PredictionByPartialMatch model with a given Markov order
+	 * and escape probability.
+	 * </p>
+	 * 
+	 * @param markovOrder
+	 *            Markov order of the model
+	 * @param minOrder
+	 *            minimum order of the model; if this order is reached, there is
+	 *            no escape
+	 * @param r
+	 *            random number generator used by probabilistic methods of the
+	 *            class
+	 * @param probEscape
+	 *            escape probability used by the model
+	 * @throws InvalidParameterException thrown if minOrder is less than 0 or greater than markovOrder or probEscape is not in the interval (0,1)
+	 */
+	public PredictionByPartialMatch(int markovOrder, int minOrder, Random r,
+			double probEscape) {
+		super(markovOrder, r);
+		if( minOrder< 0 ) {
+			throw new InvalidParameterException("minOrder must be greather than or equal to 0");
+		}
+		if( minOrder>markovOrder) {
+			throw new InvalidParameterException("minOrder must be less than or equal to markovOrder");
+		}
+		if( probEscape<=0.0 || probEscape>=1.0) {
+			throw new InvalidParameterException("probEscape must be in the interval (0,1)");
+		}
+		this.probEscape = probEscape;
+		this.minOrder = minOrder;
+	}
+
+	/**
+	 * <p>
+	 * Sets the escape probability of the model.
+	 * </p>
+	 * 
+	 * @param probEscape
+	 *            new escape probability
+	 */
+	public void setProbEscape(double probEscape) {
+		this.probEscape = probEscape;
+	}
+
+	/**
+	 * <p>
+	 * Returns the escape probability of the model.
+	 * </p>
+	 * 
+	 * @return escape probability of the model
+	 */
+	public double getProbEscape() {
+		return probEscape;
+	}
+
+	/**
+	 * <p>
+	 * Calculates the probability of the next event based on the formula:<br>
+	 * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i}
+	 * P_{MM^i}(X_n
+	 * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},...
+	 * ,X_{n-min})<br>
+	 * P_{MM^i} denotes the probability in an i-th order Markov model.
+	 * </p>
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List,
+	 *      de.ugoe.cs.quest.eventcore.Event)
+	 */
+	@Override
+	public double getProbability(List<? extends Event<?>> context,
+			Event<?> symbol) {
+		if (context == null) {
+			throw new InvalidParameterException("context must not be null");
+		}
+		if (symbol == null) {
+			throw new InvalidParameterException("symbol must not be null");
+		}
+		double result = 0.0d;
+		double resultCurrentContex = 0.0d;
+		double resultShorterContex = 0.0d;
+
+		List<Event<?>> contextCopy;
+		if (context.size() >= trieOrder) {
+			contextCopy = new LinkedList<Event<?>>(context.subList(
+					context.size() - trieOrder + 1, context.size()));
+		} else {
+			contextCopy = new LinkedList<Event<?>>(context);
+		}
+
+		Collection<Event<?>> followers = trie.getFollowingSymbols(contextCopy); // \Sigma'
+		int sumCountFollowers = 0; // N(s\sigma')
+		for (Event<?> follower : followers) {
+			sumCountFollowers += trie.getCount(contextCopy, follower);
+		}
+
+		int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
+		if (sumCountFollowers == 0) {
+			resultCurrentContex = 0.0;
+		} else {
+			resultCurrentContex = (double) countSymbol / sumCountFollowers;
+		}
+		if (contextCopy.size() > minOrder) {
+			resultCurrentContex *= (1 - probEscape);
+			contextCopy.remove(0);
+			if (contextCopy.size() >= minOrder) {
+				double probSuffix = getProbability(contextCopy, symbol);
+
+				if (followers.size() == 0) {
+					resultShorterContex = probSuffix;
+				} else {
+					resultShorterContex = probEscape * probSuffix;
+				}
+			}
+		}
+		result = resultCurrentContex + resultShorterContex;
+
+		return result;
+	}
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/Trie.java	(revision 518)
@@ -0,0 +1,472 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.io.Serializable;
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+
+import de.ugoe.cs.util.StringTools;
+
+import edu.uci.ics.jung.graph.DelegateTree;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.Tree;
+
+/**
+ * <p>
+ * This class implements a <it>trie</it>, i.e., a tree of sequences that the
+ * occurence of subsequences up to a predefined length. This length is the trie
+ * order.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * 
+ * @param <T>
+ *            Type of the symbols that are stored in the trie.
+ * 
+ * @see TrieNode
+ */
+public class Trie<T> implements IDotCompatible, Serializable {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Collection of all symbols occuring in the trie.
+	 * </p>
+	 */
+	private Collection<T> knownSymbols;
+
+	/**
+	 * <p>
+	 * Reference to the root of the trie.
+	 * </p>
+	 */
+	private final TrieNode<T> rootNode;
+
+	/**
+	 * <p>
+	 * Contructor. Creates a new Trie.
+	 * </p>
+	 */
+	public Trie() {
+		rootNode = new TrieNode<T>();
+		knownSymbols = new LinkedHashSet<T>();
+	}
+
+	/**
+	 * <p>
+	 * Copy-Constructor. Creates a new Trie as the copy of other. The other trie
+	 * must noch be null.
+	 * </p>
+	 * 
+	 * @param other
+	 *            Trie that is copied
+	 */
+	public Trie(Trie<T> other) {
+		if (other == null) {
+			throw new InvalidParameterException("other trie must not be null");
+		}
+		rootNode = new TrieNode<T>(other.rootNode);
+		knownSymbols = new LinkedHashSet<T>(other.knownSymbols);
+	}
+
+	/**
+	 * <p>
+	 * Returns a collection of all symbols occuring in the trie.
+	 * </p>
+	 * 
+	 * @return symbols occuring in the trie
+	 */
+	public Collection<T> getKnownSymbols() {
+		return new LinkedHashSet<T>(knownSymbols);
+	}
+
+	/**
+	 * <p>
+	 * Trains the current trie using the given sequence and adds all subsequence
+	 * of length {@code maxOrder}.
+	 * </p>
+	 * 
+	 * @param sequence
+	 *            sequence whose subsequences are added to the trie
+	 * @param maxOrder
+	 *            maximum length of the subsequences added to the trie
+	 */
+	public void train(List<T> sequence, int maxOrder) {
+		if (maxOrder < 1) {
+			return;
+		}
+		IncompleteMemory<T> latestActions = new IncompleteMemory<T>(maxOrder);
+		int i = 0;
+		for (T currentEvent : sequence) {
+			latestActions.add(currentEvent);
+			knownSymbols.add(currentEvent);
+			i++;
+			if (i >= maxOrder) {
+				add(latestActions.getLast(maxOrder));
+			}
+		}
+		int sequenceLength = sequence.size();
+		for (int j = maxOrder - 1; j > 0; j--) {
+			add(sequence.subList(sequenceLength - j, sequenceLength));
+		}
+	}
+
+	/**
+	 * <p>
+	 * Adds a given subsequence to the trie and increases the counters
+	 * accordingly.
+	 * </p>
+	 * 
+	 * @param subsequence
+	 *            subsequence whose counters are increased
+	 * @see TrieNode#add(List)
+	 */
+	protected void add(List<T> subsequence) {
+		if (subsequence != null && !subsequence.isEmpty()) {
+			knownSymbols.addAll(subsequence);
+			subsequence = new LinkedList<T>(subsequence); // defensive copy!
+			T firstSymbol = subsequence.get(0);
+			TrieNode<T> node = getChildCreate(firstSymbol);
+			node.add(subsequence);
+		}
+	}
+
+	/**
+	 * <p>
+	 * Returns the child of the root node associated with the given symbol or
+	 * creates it if it does not exist yet.
+	 * </p>
+	 * 
+	 * @param symbol
+	 *            symbol whose node is required
+	 * @return node associated with the symbol
+	 * @see TrieNode#getChildCreate(Object)
+	 */
+	protected TrieNode<T> getChildCreate(T symbol) {
+		return rootNode.getChildCreate(symbol);
+	}
+
+	/**
+	 * <p>
+	 * Returns the child of the root node associated with the given symbol or
+	 * null if it does not exist.
+	 * </p>
+	 * 
+	 * @param symbol
+	 *            symbol whose node is required
+	 * @return node associated with the symbol; null if no such node exists
+	 * @see TrieNode#getChild(Object)
+	 */
+	protected TrieNode<T> getChild(T symbol) {
+		return rootNode.getChild(symbol);
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of occurences of the given sequence.
+	 * </p>
+	 * 
+	 * @param sequence
+	 *            sequence whose number of occurences is required
+	 * @return number of occurences of the sequence
+	 */
+	public int getCount(List<T> sequence) {
+		int count = 0;
+		TrieNode<T> node = find(sequence);
+		if (node != null) {
+			count = node.getCount();
+		}
+		return count;
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of occurences of the given prefix and a symbol that
+	 * follows it.<br>
+	 * Convenience function to simplify usage of {@link #getCount(List)}.
+	 * </p>
+	 * 
+	 * @param sequence
+	 *            prefix of the sequence
+	 * @param follower
+	 *            suffix of the sequence
+	 * @return number of occurences of the sequence
+	 * @see #getCount(List)
+	 */
+	public int getCount(List<T> sequence, T follower) {
+		List<T> tmpSequence = new LinkedList<T>(sequence);
+		tmpSequence.add(follower);
+		return getCount(tmpSequence);
+
+	}
+
+	/**
+	 * <p>
+	 * Searches the trie for a given sequence and returns the node associated
+	 * with the sequence or null if no such node is found.
+	 * </p>
+	 * 
+	 * @param sequence
+	 *            sequence that is searched for
+	 * @return node associated with the sequence
+	 * @see TrieNode#find(List)
+	 */
+	public TrieNode<T> find(List<T> sequence) {
+		if (sequence == null || sequence.isEmpty()) {
+			return rootNode;
+		}
+		List<T> sequenceCopy = new LinkedList<T>(sequence);
+		TrieNode<T> result = null;
+		TrieNode<T> node = getChild(sequenceCopy.get(0));
+		if (node != null) {
+			sequenceCopy.remove(0);
+			result = node.find(sequenceCopy);
+		}
+		return result;
+	}
+
+	/**
+	 * <p>
+	 * Returns a collection of all symbols that follow a given sequence in the
+	 * trie. In case the sequence is not found or no symbols follow the sequence
+	 * the result will be empty.
+	 * </p>
+	 * 
+	 * @param sequence
+	 *            sequence whose followers are returned
+	 * @return symbols following the given sequence
+	 * @see TrieNode#getFollowingSymbols()
+	 */
+	public Collection<T> getFollowingSymbols(List<T> sequence) {
+		Collection<T> result = new LinkedList<T>();
+		TrieNode<T> node = find(sequence);
+		if (node != null) {
+			result = node.getFollowingSymbols();
+		}
+		return result;
+	}
+
+	/**
+	 * <p>
+	 * Returns the longest suffix of the given context that is contained in the
+	 * tree and whose children are leaves.
+	 * </p>
+	 * 
+	 * @param context
+	 *            context whose suffix is searched for
+	 * @return longest suffix of the context
+	 */
+	public List<T> getContextSuffix(List<T> context) {
+		List<T> contextSuffix;
+		if (context != null) {
+			contextSuffix = new LinkedList<T>(context); // defensive copy
+		} else {
+			contextSuffix = new LinkedList<T>();
+		}
+		boolean suffixFound = false;
+
+		while (!suffixFound) {
+			if (contextSuffix.isEmpty()) {
+				suffixFound = true; // suffix is the empty word
+			} else {
+				TrieNode<T> node = find(contextSuffix);
+				if (node != null) {
+					if (!node.getFollowingSymbols().isEmpty()) {
+						suffixFound = true;
+					}
+				}
+				if (!suffixFound) {
+					contextSuffix.remove(0);
+				}
+			}
+		}
+
+		return contextSuffix;
+	}
+
+	/**
+	 * <p>
+	 * Helper class for graph visualization of a trie.
+	 * </p>
+	 * 
+	 * @author Steffen Herbold
+	 * @version 1.0
+	 */
+	static public class Edge {
+	}
+
+	/**
+	 * <p>
+	 * Helper class for graph visualization of a trie.
+	 * </p>
+	 * 
+	 * @author Steffen Herbold
+	 * @version 1.0
+	 */
+	static public class TrieVertex {
+
+		/**
+		 * <p>
+		 * Id of the vertex.
+		 * </p>
+		 */
+		private String id;
+
+		/**
+		 * <p>
+		 * Contructor. Creates a new TrieVertex.
+		 * </p>
+		 * 
+		 * @param id
+		 *            id of the vertex
+		 */
+		protected TrieVertex(String id) {
+			this.id = id;
+		}
+
+		/**
+		 * <p>
+		 * Returns the id of the vertex.
+		 * </p>
+		 * 
+		 * @see java.lang.Object#toString()
+		 */
+		@Override
+		public String toString() {
+			return id;
+		}
+	}
+
+	/**
+	 * <p>
+	 * Returns a {@link Graph} representation of the trie.
+	 * </p>
+	 * 
+	 * @return {@link Graph} representation of the trie
+	 */
+	protected Tree<TrieVertex, Edge> getGraph() {
+		DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
+		rootNode.getGraph(null, graph);
+		return graph;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation()
+	 */
+	public String getDotRepresentation() {
+		StringBuilder stringBuilder = new StringBuilder();
+		stringBuilder.append("digraph model {" + StringTools.ENDLINE);
+		rootNode.appendDotRepresentation(stringBuilder);
+		stringBuilder.append('}' + StringTools.ENDLINE);
+		return stringBuilder.toString();
+	}
+
+	/**
+	 * <p>
+	 * Returns the string representation of the root node.
+	 * </p>
+	 * 
+	 * @see TrieNode#toString()
+	 * @see java.lang.Object#toString()
+	 */
+	@Override
+	public String toString() {
+		return rootNode.toString();
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of symbols contained in the trie.
+	 * </p>
+	 * 
+	 * @return number of symbols contained in the trie
+	 */
+	public int getNumSymbols() {
+		return knownSymbols.size();
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of trie nodes that are ancestors of a leaf. This is
+	 * the equivalent to the number of states a first-order markov model would
+	 * have.
+	 * <p>
+	 * 
+	 * @return number of trie nodes that are ancestors of leafs.
+	 */
+	public int getNumLeafAncestors() {
+		List<TrieNode<T>> ancestors = new LinkedList<TrieNode<T>>();
+		rootNode.getLeafAncestors(ancestors);
+		return ancestors.size();
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of trie nodes that are leafs.
+	 * </p>
+	 * 
+	 * @return number of leafs in the trie
+	 */
+	public int getNumLeafs() {
+		return rootNode.getNumLeafs();
+	}
+
+	/**
+	 * <p>
+	 * Updates the list of known symbols by replacing it with all symbols that
+	 * are found in the child nodes of the root node. This should be the same as
+	 * all symbols that are contained in the trie.
+	 * </p>
+	 */
+	public void updateKnownSymbols() {
+		knownSymbols = new HashSet<T>();
+		for (TrieNode<T> node : rootNode.getChildren()) {
+			knownSymbols.add(node.getSymbol());
+		}
+	}
+
+	/**
+	 * <p>
+	 * Two Tries are defined as equal, if their {@link #rootNode} are equal.
+	 * </p>
+	 * 
+	 * @see java.lang.Object#equals(java.lang.Object)
+	 */
+	@SuppressWarnings("rawtypes")
+	@Override
+	public boolean equals(Object other) {
+		if (other == this) {
+			return true;
+		}
+		if (other instanceof Trie) {
+			return rootNode.equals(((Trie) other).rootNode);
+		}
+		return false;
+	}
+	
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see java.lang.Object#hashCode()
+	 */
+	@Override
+	public int hashCode() {
+		int multiplier = 17;
+		int hash = 42;
+		if (rootNode != null) {
+			hash = multiplier * hash + rootNode.hashCode();
+		}
+		return hash;
+	}
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieBasedModel.java	(revision 518)
@@ -0,0 +1,416 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.security.InvalidParameterException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.Trie.Edge;
+import de.ugoe.cs.quest.usageprofiles.Trie.TrieVertex;
+import edu.uci.ics.jung.graph.Tree;
+
+/**
+ * <p>
+ * Implements a skeleton for stochastic processes that can calculate
+ * probabilities based on a trie. The skeleton provides all functionalities of
+ * {@link IStochasticProcess} except
+ * {@link IStochasticProcess#getProbability(List, Event)}.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public abstract class TrieBasedModel implements IStochasticProcess {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * The order of the trie, i.e., the maximum length of subsequences stored in
+	 * the trie.
+	 * </p>
+	 */
+	protected int trieOrder;
+
+	/**
+	 * <p>
+	 * Trie on which the probability calculations are based.
+	 * </p>
+	 */
+	protected Trie<Event<?>> trie = null;
+
+	/**
+	 * <p>
+	 * Random number generator used by probabilistic sequence generation
+	 * methods.
+	 * </p>
+	 */
+	protected final Random r;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new TrieBasedModel that can be used for stochastic
+	 * processes with a Markov order less than or equal to {@code markovOrder}.
+	 * </p>
+	 * 
+	 * @param markovOrder
+	 *            Markov order of the model
+	 * @param r
+	 *            random number generator used by probabilistic methods of the
+	 *            class
+	 * @throws InvalidParameterException
+	 *             thrown if markovOrder is less than 0 or the random number
+	 *             generator r is null
+	 */
+	public TrieBasedModel(int markovOrder, Random r) {
+		super();
+		if (markovOrder < 0) {
+			throw new InvalidParameterException(
+					"markov order must not be less than 0");
+		}
+		if (r == null) {
+			throw new InvalidParameterException(
+					"random number generator r must not be null");
+		}
+		this.trieOrder = markovOrder + 1;
+		this.r = r;
+	}
+
+	/**
+	 * <p>
+	 * Trains the model by generating a trie from which probabilities are
+	 * calculated. The trie is newly generated based solely on the passed
+	 * sequences. If an existing model should only be updated, use
+	 * {@link #update(Collection)} instead.
+	 * </p>
+	 * 
+	 * @param sequences
+	 *            training data
+	 * @throws InvalidParameterException
+	 *             thrown is sequences is null
+	 */
+	public void train(Collection<List<? extends Event<?>>> sequences) {
+		trie = null;
+		update(sequences);
+	}
+
+	/**
+	 * <p>
+	 * Trains the model by updating the trie from which the probabilities are
+	 * calculated. This function updates an existing trie. In case no trie
+	 * exists yet, a new trie is generated and the function behaves like
+	 * {@link #train(Collection)}.
+	 * </p>
+	 * 
+	 * @param sequences
+	 *            training data
+	 * @throws InvalidParameterException
+	 *             thrown is sequences is null
+	 */
+	public void update(Collection<List<? extends Event<?>>> sequences) {
+		if (sequences == null) {
+			throw new InvalidParameterException("sequences must not be null");
+		}
+		if (trie == null) {
+			trie = new Trie<Event<?>>();
+		}
+		for (List<? extends Event<?>> sequence : sequences) {
+			List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive
+																					// copy
+			currentSequence.add(0, Event.STARTEVENT);
+			currentSequence.add(Event.ENDEVENT);
+
+			trie.train(currentSequence, trieOrder);
+		}
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#randomSequence()
+	 */
+	@Override
+	public List<? extends Event<?>> randomSequence() {
+		return randomSequence(Integer.MAX_VALUE, true);
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#randomSequence()
+	 */
+	@Override
+	public List<? extends Event<?>> randomSequence(int maxLength,
+			boolean validEnd) {
+		List<Event<?>> sequence = new LinkedList<Event<?>>();
+		if (trie != null) {
+			boolean endFound = false;
+			while (!endFound) { // outer loop for length checking
+				sequence = new LinkedList<Event<?>>();
+				IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(
+						trieOrder - 1);
+				context.add(Event.STARTEVENT);
+
+				while (!endFound && sequence.size() <= maxLength) {
+					double randVal = r.nextDouble();
+					double probSum = 0.0;
+					List<Event<?>> currentContext = context.getLast(trieOrder);
+					for (Event<?> symbol : trie.getKnownSymbols()) {
+						probSum += getProbability(currentContext, symbol);
+						if (probSum >= randVal) {
+							if (!(Event.STARTEVENT.equals(symbol) || Event.ENDEVENT
+									.equals(symbol))) {
+								// only add the symbol the sequence if it is not
+								// START or END
+								context.add(symbol);
+								sequence.add(symbol);
+							}
+							endFound = (Event.ENDEVENT.equals(symbol))
+									|| (!validEnd && sequence.size() == maxLength);
+							break;
+						}
+					}
+				}
+			}
+		}
+		return sequence;
+	}
+
+	/**
+	 * <p>
+	 * Returns a Dot representation of the internal trie.
+	 * </p>
+	 * 
+	 * @return dot representation of the internal trie
+	 */
+	public String getTrieDotRepresentation() {
+		if (trie == null) {
+			return "";
+		} else {
+			return trie.getDotRepresentation();
+		}
+	}
+
+	/**
+	 * <p>
+	 * Returns a {@link Tree} of the internal trie that can be used for
+	 * visualization.
+	 * </p>
+	 * 
+	 * @return {@link Tree} depicting the internal trie
+	 */
+	public Tree<TrieVertex, Edge> getTrieGraph() {
+		if (trie == null) {
+			return null;
+		} else {
+			return trie.getGraph();
+		}
+	}
+
+	/**
+	 * <p>
+	 * The string representation of the model is {@link Trie#toString()} of
+	 * {@link #trie}.
+	 * </p>
+	 * 
+	 * @see java.lang.Object#toString()
+	 */
+	@Override
+	public String toString() {
+		if (trie == null) {
+			return "";
+		} else {
+			return trie.toString();
+		}
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumStates()
+	 */
+	@Override
+	public int getNumSymbols() {
+		if (trie == null) {
+			return 0;
+		} else {
+			return trie.getNumSymbols();
+		}
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getStateStrings()
+	 */
+	@Override
+	public String[] getSymbolStrings() {
+		if (trie == null) {
+			return new String[0];
+		}
+		String[] stateStrings = new String[getNumSymbols()];
+		int i = 0;
+		for (Event<?> symbol : trie.getKnownSymbols()) {
+			if (symbol.toString() == null) {
+				stateStrings[i] = "null";
+			} else {
+				stateStrings[i] = symbol.toString();
+			}
+			i++;
+		}
+		return stateStrings;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getEvents()
+	 */
+	@Override
+	public Collection<? extends Event<?>> getEvents() {
+		if (trie == null) {
+			return new HashSet<Event<?>>();
+		} else {
+			return trie.getKnownSymbols();
+		}
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see
+	 * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateSequences(int)
+	 */
+	@Override
+	public Collection<List<? extends Event<?>>> generateSequences(int length) {
+		return generateSequences(length, false);
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see
+	 * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateSequences(int,
+	 * boolean)
+	 */
+	@Override
+	public Set<List<? extends Event<?>>> generateSequences(int length,
+			boolean fromStart) {
+		Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();
+		if (length < 1) {
+			throw new InvalidParameterException(
+					"Length of generated subsequences must be at least 1.");
+		}
+		if (length == 1) {
+			if (fromStart) {
+				List<Event<?>> subSeq = new LinkedList<Event<?>>();
+				subSeq.add(Event.STARTEVENT);
+				sequenceSet.add(subSeq);
+			} else {
+				for (Event<?> event : getEvents()) {
+					List<Event<?>> subSeq = new LinkedList<Event<?>>();
+					subSeq.add(event);
+					sequenceSet.add(subSeq);
+				}
+			}
+			return sequenceSet;
+		}
+		Collection<? extends Event<?>> events = getEvents();
+		Collection<List<? extends Event<?>>> seqsShorter = generateSequences(
+				length - 1, fromStart);
+		for (Event<?> event : events) {
+			for (List<? extends Event<?>> seqShorter : seqsShorter) {
+				Event<?> lastEvent = event;
+				if (getProbability(seqShorter, lastEvent) > 0.0) {
+					List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
+					subSeq.add(lastEvent);
+					sequenceSet.add(subSeq);
+				}
+			}
+		}
+		return sequenceSet;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see
+	 * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#generateValidSequences
+	 * (int)
+	 */
+	@Override
+	public Collection<List<? extends Event<?>>> generateValidSequences(
+			int length) {
+		// check for min-length implicitly done by generateSequences
+		Collection<List<? extends Event<?>>> allSequences = generateSequences(
+				length, true);
+		Collection<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>();
+		for (List<? extends Event<?>> sequence : allSequences) {
+			if (sequence.size() == length
+					&& Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) {
+				validSequences.add(sequence);
+			}
+		}
+		return validSequences;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see
+	 * de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util
+	 * .List)
+	 */
+	@Override
+	public double getProbability(List<? extends Event<?>> sequence) {
+		if (sequence == null) {
+			throw new InvalidParameterException("sequence must not be null");
+		}
+		double prob = 1.0;
+		List<Event<?>> context = new LinkedList<Event<?>>();
+		for (Event<?> event : sequence) {
+			prob *= getProbability(context, event);
+			context.add(event);
+		}
+		return prob;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumFOMStates()
+	 */
+	@Override
+	public int getNumFOMStates() {
+		if (trie == null) {
+			return 0;
+		} else {
+			return trie.getNumLeafAncestors();
+		}
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getNumTransitions()
+	 */
+	@Override
+	public int getNumTransitions() {
+		if (trie == null) {
+			return 0;
+		} else {
+			return trie.getNumLeafs();
+		}
+	}
+}
Index: /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java
===================================================================
--- /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java	(revision 518)
+++ /trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/TrieNode.java	(revision 518)
@@ -0,0 +1,443 @@
+package de.ugoe.cs.quest.usageprofiles;
+
+import java.io.Serializable;
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+
+import de.ugoe.cs.quest.usageprofiles.Trie.Edge;
+import de.ugoe.cs.quest.usageprofiles.Trie.TrieVertex;
+import de.ugoe.cs.util.StringTools;
+import edu.uci.ics.jung.graph.DelegateTree;
+import edu.uci.ics.jung.graph.Tree;
+
+/**
+ * <p>
+ * This class implements a node of a trie. Each node is associated with a symbol
+ * and has a counter. The counter marks the number of occurences of the sequence
+ * defined by the path from the root of the trie to this node.
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * 
+ * @param <T>
+ *            Type of the symbols that are stored in the trie.
+ * @see Trie
+ */
+class TrieNode<T> implements Serializable {
+
+	/**
+	 * <p>
+	 * Id for object serialization.
+	 * </p>
+	 */
+	private static final long serialVersionUID = 1L;
+
+	/**
+	 * <p>
+	 * Counter for the number of occurences of the sequence.
+	 * </p>
+	 */
+	private int count;
+
+	/**
+	 * <p>
+	 * Symbol associated with the node.
+	 * </p>
+	 */
+	private final T symbol;
+
+	/**
+	 * <p>
+	 * Child nodes of this node. If the node is a leaf this collection is empty.
+	 * </p>
+	 */
+	private Collection<TrieNode<T>> children;
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new TrieNode without a symbol associated.<br>
+	 * <b>This constructor should only be used to create the root node of the
+	 * trie!</b>
+	 * </p>
+	 */
+	TrieNode() {
+		this.symbol = null;
+		count = 0;
+		children = new LinkedList<TrieNode<T>>();
+	}
+
+	/**
+	 * <p>
+	 * Constructor. Creates a new TrieNode. The symbol must not be null.
+	 * </p>
+	 * 
+	 * @param symbol
+	 *            symbol associated with the trie node
+	 */
+	TrieNode(T symbol) {
+		if (symbol == null) {
+			throw new InvalidParameterException(
+					"symbol must not be null. null is reserved for root node!");
+		}
+		this.symbol = symbol;
+		count = 0;
+		children = new LinkedList<TrieNode<T>>();
+	}
+
+	/**
+	 * <p>
+	 * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not
+	 * be null.
+	 * </p>
+	 * 
+	 * @param other
+	 */
+	TrieNode(TrieNode<T> other) {
+		if (other == null) {
+			throw new InvalidParameterException("other must not be null");
+		}
+		symbol = other.symbol;
+		count = other.count;
+		children = new LinkedList<TrieNode<T>>();
+		for (TrieNode<T> child : other.children) {
+			children.add(new TrieNode<T>(child));
+		}
+	}
+
+	/**
+	 * <p>
+	 * Adds a given subsequence to the trie and increases the counters
+	 * accordingly.
+	 * </p>
+	 * 
+	 * @param subsequence
+	 *            subsequence whose counters are increased
+	 * @see Trie#add(List)
+	 */
+	public void add(List<T> subsequence) {
+		if (!subsequence.isEmpty()) {
+			if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by
+														// the
+														// recursion/TrieRoot!
+				throw new AssertionError("Invalid trie operation!");
+			}
+			count++;
+			subsequence.remove(0);
+			if (!subsequence.isEmpty()) {
+				T nextSymbol = subsequence.get(0);
+				getChildCreate(nextSymbol).add(subsequence);
+			}
+		}
+	}
+
+	/**
+	 * <p>
+	 * Returns the symbol associated with the node.
+	 * </p>
+	 * 
+	 * @return symbol associated with the node
+	 */
+	public T getSymbol() {
+		return symbol;
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of occurences of the sequence represented by the node.
+	 * </p>
+	 * 
+	 * @return number of occurences of the sequence represented by the node
+	 */
+	public int getCount() {
+		return count;
+	}
+
+	/**
+	 * <p>
+	 * Returns the child of the node associated with the given symbol or creates
+	 * it if it does not exist yet.
+	 * </p>
+	 * 
+	 * @param symbol
+	 *            symbol whose node is required
+	 * @return node associated with the symbol
+	 * @see Trie#getChildCreate(Object)
+	 */
+	protected TrieNode<T> getChildCreate(T symbol) {
+		TrieNode<T> node = getChild(symbol);
+		if (node == null) {
+			node = new TrieNode<T>(symbol);
+			children.add(node);
+		}
+		return node;
+	}
+
+	/**
+	 * <p>
+	 * Returns the child of the node associated with the given symbol or null if
+	 * it does not exist.
+	 * </p>
+	 * 
+	 * @param symbol
+	 *            symbol whose node is required
+	 * @return node associated with the symbol; null if no such node exists
+	 * @see Trie#getChild(Object)
+	 */
+	protected TrieNode<T> getChild(T symbol) {
+		for (TrieNode<T> child : children) {
+			if (child.getSymbol().equals(symbol)) {
+				return child;
+			}
+		}
+		return null;
+	}
+
+	/**
+	 * <p>
+	 * Returns all children of this node.
+	 * </p>
+	 * 
+	 * @return children of this node
+	 */
+	protected Collection<TrieNode<T>> getChildren() {
+		return children;
+	}
+
+	/**
+	 * <p>
+	 * Searches the sub-trie of this trie node for a given sequence and returns
+	 * the node associated with the sequence or null if no such node is found.
+	 * </p>
+	 * 
+	 * @param sequence
+	 *            sequence that is searched for
+	 * @return node associated with the sequence
+	 * @see Trie#find(List)
+	 */
+	public TrieNode<T> find(List<T> subsequence) {
+		TrieNode<T> result = null;
+		if (subsequence.isEmpty()) {
+			result = this;
+		} else {
+			TrieNode<T> node = getChild(subsequence.get(0));
+			if (node != null) {
+				subsequence.remove(0);
+				result = node.find(subsequence);
+			}
+		}
+		return result;
+	}
+
+	/**
+	 * <p>
+	 * Returns a collection of all symbols that follow a this node, i.e., the
+	 * symbols associated with the children of this node.
+	 * </p>
+	 * 
+	 * @return symbols follow this node
+	 * @see TrieNode#getFollowingSymbols()
+	 */
+	public Collection<T> getFollowingSymbols() {
+		Collection<T> followingSymbols = new LinkedList<T>();
+		for (TrieNode<T> child : children) {
+			followingSymbols.add(child.getSymbol());
+		}
+		return followingSymbols;
+	}
+
+	/**
+	 * <p>
+	 * The string representation of a node is {@code symbol.toString()#count}
+	 * </p>
+	 * 
+	 * @see java.lang.Object#toString()
+	 */
+	@Override
+	public String toString() {
+		String str = symbol.toString() + " #" + count;
+		if (!children.isEmpty()) {
+			str += StringTools.ENDLINE + children.toString();
+		}
+		return str;
+	}
+
+	/**
+	 * <p>
+	 * Generates a {@link Tree} represenation of the trie.
+	 * </p>
+	 * 
+	 * @param parent
+	 *            parent vertex in the generated tree
+	 * @param graph
+	 *            complete tree
+	 */
+	void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
+		TrieVertex currentVertex;
+		if (isRoot()) {
+			currentVertex = new TrieVertex("root");
+			graph.addVertex(currentVertex);
+		} else {
+			currentVertex = new TrieVertex(getSymbol().toString() + "#"
+					+ getCount());
+			graph.addChild(new Edge(), parent, currentVertex);
+		}
+		for (TrieNode<T> node : children) {
+			node.getGraph(currentVertex, graph);
+		}
+	}
+
+	/**
+	 * <p>
+	 * Appends the current node to the dot representation of the trie.
+	 * </p>
+	 * 
+	 * @param stringBuilder
+	 *            {@link StringBuilder} to which the dot representation is
+	 *            appended
+	 */
+	void appendDotRepresentation(StringBuilder stringBuilder) {
+		String thisSaneId;
+		if (isRoot()) {
+			thisSaneId = "root";
+		} else {
+			thisSaneId = symbol.toString().replace("\"", "\\\"")
+					.replaceAll("[\r\n]", "")
+					+ "#" + count;
+		}
+		stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId
+				+ "\"];" + StringTools.ENDLINE);
+		for (TrieNode<T> childNode : children) {
+			stringBuilder.append(" " + hashCode() + " -> "
+					+ childNode.hashCode() + ";" + StringTools.ENDLINE);
+		}
+		for (TrieNode<T> childNode : children) {
+			childNode.appendDotRepresentation(stringBuilder);
+		}
+	}
+
+	/**
+	 * <p>
+	 * Checks if the node is a leaf.
+	 * </p>
+	 * 
+	 * @return true if the node is a leaf, false otherwise.
+	 */
+	protected boolean isLeaf() {
+		return children.isEmpty();
+	}
+
+	/**
+	 * <p>
+	 * Checks if the node is the root.
+	 * </p>
+	 * 
+	 * @return true if the node is the root of the trie, false otherwise
+	 */
+	protected boolean isRoot() {
+		return symbol == null;
+	}
+
+	/**
+	 * <p>
+	 * Recursive methods that collects all nodes that are ancestors of leafs and
+	 * stores them in the set.
+	 * </p>
+	 * 
+	 * @param ancestors
+	 *            set of all ancestors of leafs
+	 */
+	protected void getLeafAncestors(List<TrieNode<T>> ancestors) {
+		boolean isAncestor = false;
+		for (TrieNode<T> child : children) {
+			child.getLeafAncestors(ancestors);
+			isAncestor |= child.isLeaf();
+		}
+		if (isAncestor) {
+			ancestors.add(this);
+		}
+	}
+
+	/**
+	 * <p>
+	 * Returns the number of descendants of this node that are leafs. This does
+	 * not only include direct children of this node, but all leafs in the
+	 * sub-trie with this node as root.
+	 * </p>
+	 * 
+	 * @return number of leafs in this sub-trie
+	 */
+	protected int getNumLeafs() {
+		int numLeafs = 0;
+		for (TrieNode<T> child : children) {
+			if (child.isLeaf()) {
+				numLeafs++;
+			} else {
+				numLeafs += child.getNumLeafs();
+			}
+		}
+		return numLeafs;
+	}
+
+	/**
+	 * <p>
+	 * Sets the {@link #count} of this node.
+	 * </p>
+	 * <p>
+	 * This function should only be used sparingly and very carefully! The count
+	 * is usually maintained automatically by the training procedures.
+	 * </p>
+	 * 
+	 * @param count
+	 *            new count
+	 */
+	protected void setCount(int count) {
+		this.count = count;
+	}
+
+	/**
+	 * <p>
+	 * Two TrieNodes are defined as equal, if their {@link #count},
+	 * {@link #symbol}, and {@link #children} are equal.
+	 * </p>
+	 * 
+	 * @see java.lang.Object#equals(java.lang.Object)
+	 */
+	@SuppressWarnings("rawtypes")
+	@Override
+	public boolean equals(Object other) {
+		if (other == this) {
+			return true;
+		}
+		if (other instanceof TrieNode) {
+			TrieNode otherNode = (TrieNode) other;
+			if (symbol == null) {
+				return count == otherNode.count && otherNode.symbol == null
+						&& children.equals(otherNode.children);
+			} else {
+				return count == otherNode.count
+						&& symbol.equals(((TrieNode) other).symbol)
+						&& children.equals(((TrieNode) other).children);
+			}
+		}
+		return false;
+	}
+
+	/*
+	 * (non-Javadoc)
+	 * 
+	 * @see java.lang.Object#hashCode()
+	 */
+	@Override
+	public int hashCode() {
+		int multiplier = 17;
+		int hash = 42;
+		if (symbol != null) {
+			hash = multiplier * hash + symbol.hashCode();
+		}
+		hash = multiplier * hash + count;
+		hash = multiplier * hash + children.hashCode();
+		return hash;
+	}
+}
