Repository: incubator-falcon Updated Branches: refs/heads/master 9827ac9e1 -> 463f85489
FALCON-823 Add path matching ability to the radix tree. Contributed by Ajay Yadav Project: http://git-wip-us.apache.org/repos/asf/incubator-falcon/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-falcon/commit/06ffdf91 Tree: http://git-wip-us.apache.org/repos/asf/incubator-falcon/tree/06ffdf91 Diff: http://git-wip-us.apache.org/repos/asf/incubator-falcon/diff/06ffdf91 Branch: refs/heads/master Commit: 06ffdf913fed07dcb8eee81f4aa0f0779b051ed0 Parents: 9827ac9 Author: srikanth.sundarrajan <srik...@apache.org> Authored: Fri Dec 26 10:34:16 2014 +0530 Committer: srikanth.sundarrajan <srik...@apache.org> Committed: Fri Dec 26 10:34:16 2014 +0530 ---------------------------------------------------------------------- CHANGES.txt | 3 + .../falcon/entity/common/FeedDataPath.java | 15 +- .../falcon/entity/store/FeedPathStore.java | 5 + .../apache/falcon/util/FalconRadixUtils.java | 314 +++++++++++++++++++ .../java/org/apache/falcon/util/RadixNode.java | 23 ++ .../java/org/apache/falcon/util/RadixTree.java | 38 ++- .../apache/falcon/entity/FeedDataPathTest.java | 124 ++++++++ .../org/apache/falcon/util/RadixNodeTest.java | 18 +- .../org/apache/falcon/util/RadixTreeTest.java | 22 ++ 9 files changed, 544 insertions(+), 18 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 5d529b9..af4bd9e 100755 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -7,6 +7,9 @@ Trunk (Unreleased) NEW FEATURES IMPROVEMENTS + FALCON-823 Add path matching ability to the radix tree (Ajay Yadav + via Srikanth Sundarrajan) + FALCON-329 Falcon client methods should return objects. (Samar via Shwetha GS) FALCON-593 Preserve data type for properties in a vertex. (Ajay http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/main/java/org/apache/falcon/entity/common/FeedDataPath.java ---------------------------------------------------------------------- diff --git a/common/src/main/java/org/apache/falcon/entity/common/FeedDataPath.java b/common/src/main/java/org/apache/falcon/entity/common/FeedDataPath.java index 39e636b..6ededbb 100644 --- a/common/src/main/java/org/apache/falcon/entity/common/FeedDataPath.java +++ b/common/src/main/java/org/apache/falcon/entity/common/FeedDataPath.java @@ -30,14 +30,25 @@ public final class FeedDataPath { * Standard variables for feed time components. */ public static enum VARS { - YEAR("yyyy"), MONTH("MM"), DAY("dd"), HOUR("HH"), MINUTE("mm"); + YEAR("yyyy", "([0-9]{4})"), MONTH("MM", "(0[1-9]|1[0-2])"), DAY("dd", "(0[1-9]|1[0-9]|2[0-9]|3[0-1])"), + HOUR("HH", "([0-1][0-9]|2[0-4])"), MINUTE("mm", "([0-5][0-9]|60)"); private final Pattern pattern; private final String datePattern; + private final String patternRegularExpression; - private VARS(String datePattern) { + private VARS(String datePattern, String patternRegularExpression) { pattern = Pattern.compile("\\$\\{" + name() + "\\}"); this.datePattern = datePattern; + this.patternRegularExpression = patternRegularExpression; + } + + public String getPatternRegularExpression() { + return patternRegularExpression; + } + + public String getDatePattern() { + return datePattern; } public String regex() { http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/main/java/org/apache/falcon/entity/store/FeedPathStore.java ---------------------------------------------------------------------- diff --git a/common/src/main/java/org/apache/falcon/entity/store/FeedPathStore.java b/common/src/main/java/org/apache/falcon/entity/store/FeedPathStore.java index 97d21c1..1be12fe 100644 --- a/common/src/main/java/org/apache/falcon/entity/store/FeedPathStore.java +++ b/common/src/main/java/org/apache/falcon/entity/store/FeedPathStore.java @@ -18,6 +18,8 @@ package org.apache.falcon.entity.store; +import org.apache.falcon.util.FalconRadixUtils; + import javax.annotation.Nonnull; import javax.annotation.Nullable; import java.util.Collection; @@ -34,6 +36,9 @@ public interface FeedPathStore<T> { int getSize(); @Nullable + Collection<T> find(@Nonnull String key, @Nonnull FalconRadixUtils.INodeAlgorithm algorithm); + + @Nullable Collection<T> find(@Nonnull String key); boolean delete(@Nonnull String key, @Nonnull T value); http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/main/java/org/apache/falcon/util/FalconRadixUtils.java ---------------------------------------------------------------------- diff --git a/common/src/main/java/org/apache/falcon/util/FalconRadixUtils.java b/common/src/main/java/org/apache/falcon/util/FalconRadixUtils.java new file mode 100644 index 0000000..bbd73c7 --- /dev/null +++ b/common/src/main/java/org/apache/falcon/util/FalconRadixUtils.java @@ -0,0 +1,314 @@ +/** + * 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.falcon.util; + +import org.apache.commons.lang.StringUtils; +import org.apache.falcon.entity.common.FeedDataPath; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; +import java.util.regex.Matcher; +import java.util.regex.Pattern; + +/** + * Falcon specific utilities for the Radix Tree. + */ +public class FalconRadixUtils { + + /** + * This interface implements the various algorithms to compare node's key with input based on whether you want + * a regular expression based algorithm or a character by character matching algorithm. + */ + public interface INodeAlgorithm { + + /** + * Checks if the given key and input match. + * @param key key of the node + * @param input input String to be matched against key. + * @return true if key and input match. + */ + boolean match(String key, String input); + + boolean startsWith(String key, String input); + + /** + * Finds next node to take for traversal among currentNode's children. + * @param currentNode of RadixTree which has been matched. + * @param input input String to be searched. + * @return Node to be traversed next. + */ + RadixNode getNextCandidate(RadixNode currentNode, String input); + + // for the given node and input key, finds the remainingText to be matched with child sub tree. + String getRemainingText(RadixNode currentNode, String key); + } + + /** + * This Algorithm does a plain string comparison for all + * type of operations on a node. + */ + static class StringAlgorithm implements INodeAlgorithm { + + @Override + public boolean match(String key, String input) { + return StringUtils.equals(key, input); + } + + @Override + public boolean startsWith(String nodeKey, String inputKey) { + return inputKey.startsWith(nodeKey); + } + + @Override + public RadixNode getNextCandidate(RadixNode currentNode, String input) { + RadixNode newRoot = null; + String remainingText = input.substring(currentNode.getKey().length()); + List<RadixNode> result = currentNode.getChildren(); + for(RadixNode child : result){ + if (child.getKey().charAt(0) == remainingText.charAt(0)){ + newRoot = child; + break; + } + } + return newRoot; + } + + @Override + public String getRemainingText(RadixNode currentNode, String key) { + return key.substring(currentNode.getKey().length()); + } + + + } + + static class FeedRegexAlgorithm implements INodeAlgorithm { + + /** + * This function matches a feed path template with feed instance's path string. + * + * Key is assumed to be a feed's path template and inputString is assumed to be an instance's path string. + * Variable/Regex parts of the feed's template are matched against the corresponding parts in inputString + * using regular expression and for other parts a character by character match is performed. + * e.g. Given templateString (/data/cas/${YEAR}/${MONTH}/${DAY}) and inputString (/data/cas/2014/09/09) + * the function will return true. + * @param templateString Node's key (Feed's template path) + * @param inputString inputString String to be matched against templateString(instance's path) + * @return true if the templateString and inputString match, false otherwise. + */ + @Override + public boolean match(String templateString, String inputString) { + if (StringUtils.isBlank(templateString)) { + return false; + } + // Divide the templateString and inputString into templateParts of regex and character matches + List<String> templateParts = getPartsInPathTemplate(templateString); + List<String> inputStringParts = getCorrespondingParts(inputString, templateParts); + + if (inputStringParts.size() != templateParts.size()) { + return false; + } + + int counter = 0; + while (counter < inputStringParts.size()) { + if (!matchPart(templateParts.get(counter), inputStringParts.get(counter))) { + return false; + } + counter++; + } + return true; + } + + + /** + * + * Finds if the current node's key is a prefix of the given inputString or not. + * + * @param inputTemplate inputTemplate String + * @param inputString inputString to be checked + * @return true if inputString starts with inputTemplate, false otherwise. + */ + @Override + public boolean startsWith(String inputTemplate, String inputString) { + + if (StringUtils.isBlank(inputString)) { + return false; + } + if (StringUtils.isBlank(inputTemplate)) { + return true; + } + + // divide inputTemplate and inputString into corresponding templateParts of regex and character only strings + List<String> templateParts = getPartsInPathTemplate(inputTemplate); + List<String> remainingPattern = getCorrespondingParts(inputString, templateParts); + + if (templateParts.size() > remainingPattern.size()) { + return false; + } + + int counter = 0; + // compare part by part till the templateParts end + for (String templatePart : templateParts) { + String part = remainingPattern.get(counter); + if (!matchPart(templatePart, part)) { + return false; + } + counter++; + } + return true; + } + + @Override + public RadixNode getNextCandidate(RadixNode currentNode, String input) { + RadixNode newRoot = null; + // replace the regex with pattern's length + String remainingText = input.substring(getPatternsEffectiveLength(currentNode.getKey())); + List<RadixNode> result = currentNode.getChildren(); + for(RadixNode child : result) { + String key = child.getKey(); + if (key.startsWith("${")) { + // get the regex + String regex = key.substring(0, key.indexOf("}") + 1); + // match the text and the regex + FeedDataPath.VARS var = getMatchingRegex(regex); + if (matchPart(regex, input.substring(0, var.getDatePattern().length()))) { + newRoot = child; // if it matches then this is the newRoot + break; + } + } else if (child.getKey().charAt(0) == remainingText.charAt(0)) { + newRoot = child; + break; + } + } + return newRoot; + } + + @Override + public String getRemainingText(RadixNode currentNode, String inputString) { + // find the match length for current inputString + return inputString.substring(getPatternsEffectiveLength(currentNode.getKey())); + } + + private int getPatternsEffectiveLength(String templateString) { + if (StringUtils.isBlank(templateString)) { + return 0; + } + for (FeedDataPath.VARS var : FeedDataPath.VARS.values()) { + templateString = templateString.replace("${" + var.name() + "}", var.getDatePattern()); + } + return templateString.length(); + } + + /** + * Divide a given template string into parts of regex and character strings + * e.g. /data/cas/${YEAR}/${MONTH}/${DAY} will be converted to + * [/data/cas/, ${YEAR}, /, ${MONTH}, /, ${DAY}] + * @param templateString input string representing a feed's path template + * @return list of parts in input templateString which are either completely regex or normal string. + */ + private List<String> getPartsInPathTemplate(String templateString) { + //divide the node's templateString in parts of regular expression and normal string + List<String> parts = new ArrayList<String>(); + Matcher matcher = FeedDataPath.PATTERN.matcher(templateString); + int currentIndex = 0; + while (matcher.find()) { + parts.add(templateString.substring(currentIndex, matcher.start())); + parts.add(matcher.group()); + currentIndex = matcher.end(); + } + if (currentIndex != templateString.length()) { + parts.add(templateString.substring(currentIndex)); + } + return Collections.unmodifiableList(parts); + } + + + private FeedDataPath.VARS getMatchingRegex(String inputPart) { + //inputPart will be something like ${YEAR} + inputPart = inputPart.replace("${", "\\$\\{"); + inputPart = inputPart.replace("}", "\\}"); + + for (FeedDataPath.VARS var : FeedDataPath.VARS.values()) { + if (StringUtils.equals(inputPart, var.regex())) { + return var; + } + } + return null; + } + + + /** + * Divides a string into corresponding parts for the template to carry out comparison. + * templateParts = [/data/cas/, ${YEAR}, /, ${MONTH}, /, ${DAY}] + * inputString = /data/cas/2014/09/09 + * returns [/data/cas/, 2014, /, 09, /, 09] + * @param inputString normal string representing feed instance path + * @param templateParts parts of feed's path template broken into regex and non-regex units. + * @return a list of strings where each part of the list corresponds to a part in list of template parts. + */ + private List<String> getCorrespondingParts(String inputString, List<String> templateParts) { + List<String> stringParts = new ArrayList<String>(); + int counter = 0; + while (StringUtils.isNotBlank(inputString) && counter < templateParts.size()) { + String currentTemplatePart = templateParts.get(counter); + int length = Math.min(getPatternsEffectiveLength(currentTemplatePart), inputString.length()); + stringParts.add(inputString.substring(0, length)); + inputString = inputString.substring(length); + counter++; + } + if (StringUtils.isNotBlank(inputString)) { + stringParts.add(inputString); + } + return stringParts; + } + + /** + * Compare a pure regex or pure string part with a given string. + * + * @param template template part, which can either be a pure regex or pure non-regex string. + * @param input input String to be matched against the template part. + * @return true if the input string matches the template, in case of a regex component a regex comparison is + * made, else a character by character comparison is made. + */ + private boolean matchPart(String template, String input) { + if (template.startsWith("${")) { // if the part begins with ${ then it's a regex part, do regex match + template = template.replace("${", "\\$\\{"); + template = template.replace("}", "\\}"); + for (FeedDataPath.VARS var : FeedDataPath.VARS.values()) {//find which regex is this + if (StringUtils.equals(var.regex(), template)) {// regex found, do matching + //find part of the input string which should be matched against regex + String desiredPart = input.substring(0, var.getDatePattern().length()); + Pattern pattern = Pattern.compile(var.getPatternRegularExpression()); + Matcher matcher = pattern.matcher(desiredPart); + if (!matcher.matches()) { + return false; + } + return true; + } + } + return false; + } else {// do exact match with normal strings + if (!input.startsWith(template)) { + return false; + } + } + return true; + } + } +} http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/main/java/org/apache/falcon/util/RadixNode.java ---------------------------------------------------------------------- diff --git a/common/src/main/java/org/apache/falcon/util/RadixNode.java b/common/src/main/java/org/apache/falcon/util/RadixNode.java index 564df8e..12227cb 100644 --- a/common/src/main/java/org/apache/falcon/util/RadixNode.java +++ b/common/src/main/java/org/apache/falcon/util/RadixNode.java @@ -124,4 +124,27 @@ public class RadixNode<T> { return matchLength; } + + + /** + * Finds the length of the match between node's key and input. + * + * It can do either a character by character match or a regular expression match(used to match a feed instance path + * with feed location template). Only regular expressions allowed in the feed path are evaluated for matching. + * @param input input string to be matched with the key of the node. + * @param matcher A custom matcher algorithm to match node's key against the input. It is used when matching + * path of a Feed's instance to Feed's path template. + * @return + */ + public boolean matches(String input, FalconRadixUtils.INodeAlgorithm matcher) { + if (input == null) { + return false; + } + + if (matcher == null) { + return StringUtils.equals(getKey(), input); + } + + return matcher.match(this.getKey(), input); + } } http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/main/java/org/apache/falcon/util/RadixTree.java ---------------------------------------------------------------------- diff --git a/common/src/main/java/org/apache/falcon/util/RadixTree.java b/common/src/main/java/org/apache/falcon/util/RadixTree.java index 6dbe160..6cd79f5 100644 --- a/common/src/main/java/org/apache/falcon/util/RadixTree.java +++ b/common/src/main/java/org/apache/falcon/util/RadixTree.java @@ -189,21 +189,35 @@ public class RadixTree<T> implements FeedPathStore<T>, Formattable { */ @Override @Nullable - public synchronized Collection<T> find(@Nonnull String key) { - if (key != null && !key.trim().isEmpty()){ - return recursiveFind(key.trim(), root); + public synchronized Collection<T> find(@Nonnull String key, FalconRadixUtils.INodeAlgorithm algorithm) { + if (key != null && !key.trim().isEmpty()) { + if (algorithm == null) { + algorithm = new FalconRadixUtils.StringAlgorithm(); + } + return recursiveFind(key.trim(), root, algorithm); + } + return null; + } + + @Nullable + @Override + public Collection<T> find(@Nonnull String key) { + if (key != null && !key.trim().isEmpty()) { + FalconRadixUtils.INodeAlgorithm algorithm = new FalconRadixUtils.StringAlgorithm(); + return recursiveFind(key.trim(), root, algorithm); } return null; } - private Collection<T> recursiveFind(String key, RadixNode<T> currentNode){ + private Collection<T> recursiveFind(String key, RadixNode<T> currentNode, + FalconRadixUtils.INodeAlgorithm algorithm){ - if (!key.startsWith(currentNode.getKey())){ + if (!algorithm.startsWith(currentNode.getKey(), key)){ LOG.debug("Current Node key: {} is not a prefix in the input key: {}", currentNode.getKey(), key); return null; } - if (StringUtils.equals(key, currentNode.getKey())){ + if (algorithm.match(currentNode.getKey(), key)){ if (currentNode.isTerminal()){ LOG.debug("Found the terminal node with key: {} for the given input.", currentNode.getKey()); return currentNode.getValues(); @@ -214,21 +228,15 @@ public class RadixTree<T> implements FeedPathStore<T>, Formattable { } //find child to follow, using remaining Text - RadixNode<T> newRoot = null; - String remainingText = key.substring(currentNode.getKey().length()); - for(RadixNode<T> child : currentNode.getChildren()){ - if (child.getKey().charAt(0) == remainingText.charAt(0)){ - newRoot = child; - break; - } - } + RadixNode<T> newRoot = algorithm.getNextCandidate(currentNode, key); + String remainingText = algorithm.getRemainingText(currentNode, key); if (newRoot == null){ LOG.debug("No child found to follow for further processing. Current node key {}"); return null; }else { LOG.debug("Recursing with new key: {} and new remainingText: {}", newRoot.getKey(), remainingText); - return recursiveFind(remainingText, newRoot); + return recursiveFind(remainingText, newRoot, algorithm); } } http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/test/java/org/apache/falcon/entity/FeedDataPathTest.java ---------------------------------------------------------------------- diff --git a/common/src/test/java/org/apache/falcon/entity/FeedDataPathTest.java b/common/src/test/java/org/apache/falcon/entity/FeedDataPathTest.java new file mode 100644 index 0000000..c405556 --- /dev/null +++ b/common/src/test/java/org/apache/falcon/entity/FeedDataPathTest.java @@ -0,0 +1,124 @@ +/** + * 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.falcon.entity; + +import org.apache.falcon.entity.common.FeedDataPath; +import org.testng.Assert; +import org.testng.annotations.Test; + +/** + * + */ +public class FeedDataPathTest { + + @Test + public void testMinutesRegularExpression() { + String monthPattern = FeedDataPath.VARS.MINUTE.getPatternRegularExpression(); + Assert.assertFalse("0".matches(monthPattern)); + Assert.assertFalse("1".matches(monthPattern)); + Assert.assertFalse("61".matches(monthPattern)); + Assert.assertFalse("010".matches(monthPattern)); + Assert.assertFalse("10 ".matches(monthPattern)); + Assert.assertFalse(" 10".matches(monthPattern)); + + + Assert.assertTrue("00".matches(monthPattern)); + Assert.assertTrue("01".matches(monthPattern)); + Assert.assertTrue("60".matches(monthPattern)); + } + + @Test + public void testHourRegularExpression() { + String hourPattern = FeedDataPath.VARS.HOUR.getPatternRegularExpression(); + Assert.assertFalse("0".matches(hourPattern)); + Assert.assertFalse("1".matches(hourPattern)); + Assert.assertFalse("2".matches(hourPattern)); + Assert.assertFalse("25".matches(hourPattern)); + Assert.assertFalse("29".matches(hourPattern)); + Assert.assertFalse("010".matches(hourPattern)); + Assert.assertFalse("10 ".matches(hourPattern)); + Assert.assertFalse(" 10".matches(hourPattern)); + + + Assert.assertTrue("00".matches(hourPattern)); + Assert.assertTrue("01".matches(hourPattern)); + Assert.assertTrue("24".matches(hourPattern)); + Assert.assertTrue("10".matches(hourPattern)); + Assert.assertTrue("19".matches(hourPattern)); + Assert.assertTrue("12".matches(hourPattern)); + } + + + @Test + public void testDayRegularExpression() { + String dayPattern = FeedDataPath.VARS.DAY.getPatternRegularExpression(); + Assert.assertFalse("0".matches(dayPattern)); + Assert.assertFalse("1".matches(dayPattern)); + Assert.assertFalse("32".matches(dayPattern)); + Assert.assertFalse("00".matches(dayPattern)); + Assert.assertFalse("010".matches(dayPattern)); + Assert.assertFalse("10 ".matches(dayPattern)); + Assert.assertFalse(" 10".matches(dayPattern)); + + + Assert.assertTrue("01".matches(dayPattern)); + Assert.assertTrue("10".matches(dayPattern)); + Assert.assertTrue("29".matches(dayPattern)); + Assert.assertTrue("30".matches(dayPattern)); + Assert.assertTrue("31".matches(dayPattern)); + } + + @Test + public void testMonthRegularExpression() { + String monthPattern = FeedDataPath.VARS.MONTH.getPatternRegularExpression(); + Assert.assertFalse("0".matches(monthPattern)); + Assert.assertFalse("1".matches(monthPattern)); + Assert.assertFalse("13".matches(monthPattern)); + Assert.assertFalse("19".matches(monthPattern)); + Assert.assertFalse("00".matches(monthPattern)); + Assert.assertFalse("010".matches(monthPattern)); + Assert.assertFalse("10 ".matches(monthPattern)); + Assert.assertFalse(" 10".matches(monthPattern)); + + + Assert.assertTrue("01".matches(monthPattern)); + Assert.assertTrue("02".matches(monthPattern)); + Assert.assertTrue("10".matches(monthPattern)); + Assert.assertTrue("12".matches(monthPattern)); + } + + @Test + public void testYearRegularExpression() { + String monthPattern = FeedDataPath.VARS.YEAR.getPatternRegularExpression(); + Assert.assertFalse("0".matches(monthPattern)); + Assert.assertFalse("1".matches(monthPattern)); + Assert.assertFalse("13".matches(monthPattern)); + Assert.assertFalse("19".matches(monthPattern)); + Assert.assertFalse("00".matches(monthPattern)); + Assert.assertFalse("010".matches(monthPattern)); + Assert.assertFalse("10 ".matches(monthPattern)); + Assert.assertFalse(" 10".matches(monthPattern)); + + + Assert.assertTrue("0001".matches(monthPattern)); + Assert.assertTrue("2014".matches(monthPattern)); + } + + +} http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/test/java/org/apache/falcon/util/RadixNodeTest.java ---------------------------------------------------------------------- diff --git a/common/src/test/java/org/apache/falcon/util/RadixNodeTest.java b/common/src/test/java/org/apache/falcon/util/RadixNodeTest.java index 4f63806..aea28e6 100644 --- a/common/src/test/java/org/apache/falcon/util/RadixNodeTest.java +++ b/common/src/test/java/org/apache/falcon/util/RadixNodeTest.java @@ -19,7 +19,8 @@ package org.apache.falcon.util; import org.testng.Assert; -import org.testng.annotations.*; +import org.testng.annotations.BeforeMethod; +import org.testng.annotations.Test; import java.util.Arrays; import java.util.HashSet; @@ -90,4 +91,19 @@ public class RadixNodeTest { Assert.assertTrue(normalNode.containsValue("CAS Project")); } + @Test + public void testMatchInput() { + RadixNode<String> node = new RadixNode<String>(); + + FalconRadixUtils.INodeAlgorithm matcher = new FalconRadixUtils.FeedRegexAlgorithm(); + node.setKey("/data/cas/projects/${YEAR}/${MONTH}/${DAY}"); + Assert.assertTrue(node.matches("/data/cas/projects/2014/09/09", matcher)); + Assert.assertFalse(node.matches("/data/cas/projects/20140909", matcher)); + Assert.assertFalse(node.matches("/data/2014/projects/2014/09/09", matcher)); + Assert.assertFalse(node.matches("/data/2014/projects/2014/09/", matcher)); + Assert.assertFalse(node.matches("/data/cas/projects/2014/09/09trail", matcher)); + Assert.assertFalse(node.matches("/data/cas/projects/2014/09/09/", matcher)); + Assert.assertFalse(node.matches("/data/cas/projects/2014/09/", matcher)); + } + } http://git-wip-us.apache.org/repos/asf/incubator-falcon/blob/06ffdf91/common/src/test/java/org/apache/falcon/util/RadixTreeTest.java ---------------------------------------------------------------------- diff --git a/common/src/test/java/org/apache/falcon/util/RadixTreeTest.java b/common/src/test/java/org/apache/falcon/util/RadixTreeTest.java index 28589ed..109c24d 100644 --- a/common/src/test/java/org/apache/falcon/util/RadixTreeTest.java +++ b/common/src/test/java/org/apache/falcon/util/RadixTreeTest.java @@ -34,6 +34,7 @@ import java.util.List; public class RadixTreeTest { private RadixTree<String> tree; + private FalconRadixUtils.INodeAlgorithm regexAlgorithm = new FalconRadixUtils.FeedRegexAlgorithm(); @BeforeMethod public void setUp() { @@ -118,6 +119,27 @@ public class RadixTreeTest { } + //Tests for find using regular expression + @Test + public void testFindUsingRegex() { + tree.insert("/data/cas/${YEAR}/", "rtbd"); + Assert.assertTrue(tree.find("/data/cas/2014/", regexAlgorithm).contains("rtbd")); + Assert.assertNull(tree.find("/data/cas/", regexAlgorithm)); + Assert.assertNull(tree.find("/data/cas/2014/09", regexAlgorithm)); + Assert.assertNull(tree.find("/data/cas/${YEAR}/", regexAlgorithm)); + + tree.insert("/data/cas/${YEAR}/colo", "local"); + tree.insert("/data/cas/${YEAR}/colo", "duplicate-local"); + Assert.assertNull(tree.find("/data/cas/${YEAR}/", regexAlgorithm)); + Assert.assertNull(tree.find("/data/cas/${YEAR}/colo", regexAlgorithm)); + Assert.assertNull(tree.find("/data/cas/", regexAlgorithm)); + Assert.assertTrue(tree.find("/data/cas/2014/", regexAlgorithm).contains("rtbd")); + Assert.assertTrue(tree.find("/data/cas/2014/colo", regexAlgorithm).contains("local")); + Assert.assertTrue(tree.find("/data/cas/2014/colo", regexAlgorithm).contains("duplicate-local")); + + + } + // Tests for delete method @Test public void testDeleteChildOfTerminal() {
