You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by rv...@apache.org on 2013/01/29 12:23:26 UTC
svn commit: r1439838 - in /jena/trunk/jena-arq/src:
main/java/org/apache/jena/atlas/lib/Trie.java
test/java/org/apache/jena/atlas/lib/TS_Lib.java
test/java/org/apache/jena/atlas/lib/TestTrie.java
Author: rvesse
Date: Tue Jan 29 11:23:26 2013
New Revision: 1439838
URL: http://svn.apache.org/viewvc?rev=1439838&view=rev
Log:
Add some tests for the Trie implementation
Added:
jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TestTrie.java
Modified:
jena/trunk/jena-arq/src/main/java/org/apache/jena/atlas/lib/Trie.java
jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TS_Lib.java
Modified: jena/trunk/jena-arq/src/main/java/org/apache/jena/atlas/lib/Trie.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/org/apache/jena/atlas/lib/Trie.java?rev=1439838&r1=1439837&r2=1439838&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/org/apache/jena/atlas/lib/Trie.java (original)
+++ jena/trunk/jena-arq/src/main/java/org/apache/jena/atlas/lib/Trie.java Tue Jan 29 11:23:26 2013
@@ -26,19 +26,27 @@ import java.util.Map;
/**
* An implementation of a classic Trie, this is a mapping from strings to some
* value type optimized for fast prefix search and match. If you do not need
- * prefix search then you should typically use a standard {@link Map} instead
+ * prefix search then you should typically use a standard {@link Map} instead.
+ * <p>
+ * A Trie cannot store null values since null is used as an internal marker to indicate
+ * that there is no value associated with a key. This is necessary because the nature
+ * of the data structure means that adding a key potentially adds multiple keys many of
+ * which will not be associated with a value.
+ * </p>
*
- * @param <T> Type of the value stored.
+ * @param <T>
+ * Type of the value stored.
*/
public final class Trie<T> {
private TrieNode<T> root = new TrieNode<T>(null);
/**
- * Adds a value to the trie
+ * Adds a value to the trie overwriting any existing value
* <p>
* Note that a null value is treated as if the key does not actually exist
- * in the tree so trying to add a null is a no-op
+ * in the tree so trying to add a null is a no-op. If you want to remove a
+ * key use the {@link #remove(String)} method instead.
* </p>
*
* @param key
@@ -103,8 +111,8 @@ public final class Trie<T> {
}
/**
- * Gets whether a key exists in the trie and has a non-null value mapped
- * to it
+ * Gets whether a key exists in the trie and has a non-null value mapped to
+ * it
*
* @param key
* Key
@@ -115,8 +123,7 @@ public final class Trie<T> {
}
/**
- * Gets whether a key exists in the trie and meets the given value
- * criteria
+ * Gets whether a key exists in the trie and meets the given value criteria
*
* @param key
* Key
@@ -137,39 +144,51 @@ public final class Trie<T> {
return true;
}
}
-
+
/**
* Gets whether a key value pair are present in the trie
- * @param key Key
- * @param value Value
+ *
+ * @param key
+ * Key
+ * @param value
+ * Value
* @return True if the key value pair exists in the trie, false otherwise
*/
public boolean contains(String key, T value) {
TrieNode<T> n = this.find(key);
- if (n == null) return false;
- if (value == null && !n.hasValue()) return true;
+ if (n == null)
+ return false;
+ if (value == null && !n.hasValue())
+ return true;
return value.equals(n.getValue());
}
-
+
/**
* Gets the value associated with a key
- * @param key Key
+ *
+ * @param key
+ * Key
* @return Value
*/
public T get(String key) {
TrieNode<T> n = this.find(key);
- if (n == null) return null;
+ if (n == null)
+ return null;
return n.getValue();
}
-
+
/**
- * Performs a prefix search and returns all values mapped under the given prefix
- * @param prefix Prefix
+ * Performs a prefix search and returns all values mapped under the given
+ * prefix
+ *
+ * @param prefix
+ * Prefix
* @return List of values associated with the given key
*/
public List<T> prefixSearch(String prefix) {
TrieNode<T> n = this.find(prefix);
- if (n == null) return new ArrayList<T>();
+ if (n == null)
+ return new ArrayList<T>();
return Collections.unmodifiableList(n.getValues());
}
@@ -177,7 +196,7 @@ public final class Trie<T> {
* Represents a node in the Trie
*
*/
- private static class TrieNode<T> {
+ private static class TrieNode<T> {
private Map<Character, TrieNode<T>> children = new HashMap<Character, TrieNode<T>>();
private T value;
@@ -245,9 +264,10 @@ public final class Trie<T> {
}
return n;
}
-
+
/**
* Gets all values from a given node and its descendants
+ *
* @return Values
*/
public List<T> getValues() {
Modified: jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TS_Lib.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TS_Lib.java?rev=1439838&r1=1439837&r2=1439838&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TS_Lib.java (original)
+++ jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TS_Lib.java Tue Jan 29 11:23:26 2013
@@ -22,6 +22,10 @@ package org.apache.jena.atlas.lib;
import org.junit.runner.RunWith ;
import org.junit.runners.Suite ;
+/**
+ * Tests for the Atlas lib package
+ *
+ */
@RunWith(Suite.class)
@Suite.SuiteClasses( {
TestAlg.class
@@ -41,6 +45,7 @@ import org.junit.runners.Suite ;
, TestAlarmClock.class
, TestRefLong.class
, TestReverseComparator.class
+ , TestTrie.class
} )
public class TS_Lib
Added: jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TestTrie.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TestTrie.java?rev=1439838&view=auto
==============================================================================
--- jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TestTrie.java (added)
+++ jena/trunk/jena-arq/src/test/java/org/apache/jena/atlas/lib/TestTrie.java Tue Jan 29 11:23:26 2013
@@ -0,0 +1,167 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.atlas.lib;
+
+import java.util.List;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * Tests for the {@link Trie} class
+ *
+ */
+public class TestTrie {
+
+ /**
+ * Add a single key value
+ */
+ @Test
+ public void trie_add_01() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", 123);
+ Assert.assertTrue(trie.contains("test"));
+ Assert.assertEquals((Integer) 123, trie.get("test"));
+ }
+
+ /**
+ * Add two key values
+ */
+ @Test
+ public void trie_add_02() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", 123);
+ trie.add("other", 456);
+ Assert.assertTrue(trie.contains("test"));
+ Assert.assertTrue(trie.contains("other"));
+ Assert.assertEquals((Integer) 123, trie.get("test"));
+ Assert.assertEquals((Integer) 456, trie.get("other"));
+ }
+
+ /**
+ * Replace an existing key value
+ */
+ @Test
+ public void trie_add_03() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", 123);
+ trie.add("test", 456);
+ Assert.assertTrue(trie.contains("test"));
+ Assert.assertEquals((Integer) 456, trie.get("test"));
+ }
+
+ /**
+ * Adding a null value is ignored
+ */
+ @Test
+ public void trie_add_04() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", null);
+ Assert.assertFalse(trie.contains("test"));
+ }
+
+ /**
+ * Test for non-existent key
+ */
+ public void trie_contains_01() {
+ Trie<Integer> trie = new Trie<Integer>();
+ Assert.assertFalse(trie.contains("test"));
+ }
+
+ /**
+ * Test for keys with and without values required
+ */
+ @Test
+ public void trie_contains_02() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", 123);
+ Assert.assertTrue(trie.contains("test"));
+ Assert.assertTrue(trie.contains("test", true));
+ Assert.assertTrue(trie.contains("test", 123));
+
+ // Any prefix of an added key exists if we don't require it to have a
+ // value
+ Assert.assertFalse(trie.contains("t"));
+ Assert.assertTrue(trie.contains("t", false));
+ }
+
+ /**
+ * Removing a key value
+ */
+ @Test
+ public void trie_remove_01() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", 123);
+ Assert.assertTrue(trie.contains("test"));
+ Assert.assertEquals((Integer) 123, trie.get("test"));
+
+ // Removing does not fully remove the key it merely nulls the value
+ trie.remove("test");
+ Assert.assertFalse(trie.contains("test"));
+ Assert.assertTrue(trie.contains("test", false));
+ Assert.assertNull(trie.get("test"));
+ }
+
+ /**
+ * Removing a key value, removing a key which is a prefix of another leaves
+ * the other intact
+ */
+ @Test
+ public void trie_remove_02() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", 123);
+ trie.add("testing", 456);
+ Assert.assertTrue(trie.contains("test"));
+ Assert.assertEquals((Integer) 123, trie.get("test"));
+ Assert.assertTrue(trie.contains("testing"));
+ Assert.assertEquals((Integer) 456, trie.get("testing"));
+
+ // Removing does not fully remove the key it merely nulls the value
+ trie.remove("test");
+ Assert.assertFalse(trie.contains("test"));
+ Assert.assertTrue(trie.contains("test", false));
+ Assert.assertNull(trie.get("test"));
+
+ // It also does not remove any keys who had the removed key as a prefix
+ Assert.assertTrue(trie.contains("testing"));
+ Assert.assertEquals((Integer) 456, trie.get("testing"));
+ }
+
+ /**
+ * Test prefix search
+ */
+ @Test
+ public void trie_prefix_search_01() {
+ Trie<Integer> trie = new Trie<Integer>();
+ trie.add("test", 123);
+ trie.add("testing", 456);
+
+ //Prefix search on "test" should return two values
+ List<Integer> matches = trie.prefixSearch("test");
+ Assert.assertEquals(2, matches.size());
+
+ //Prefix search on "testi" should return one value
+ matches = trie.prefixSearch("testi");
+ Assert.assertEquals(1, matches.size());
+
+ //Prefix search on "testingly" should return no values
+ matches = trie.prefixSearch("testingly");
+ Assert.assertEquals(0, matches.size());
+ }
+}