[GitHub] [helix] jiajunwang commented on a change in pull request #706: Implement trie routing data

[GitBox <gi...@apache.org>]

jiajunwang commented on a change in pull request #706: Implement trie routing data
URL: https://github.com/apache/helix/pull/706#discussion_r372655452
 
 

 ##########
 File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java
 ##########
 @@ -0,0 +1,161 @@
+package org.apache.helix.rest.metadatastore;
+
+/*
+ * 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.
+ */
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+public class TrieRoutingData implements RoutingData {
+  private final TrieNode _rootNode;
+
+  // TODO: THIS IS A TEMPORARY PLACEHOLDER. A proper constructor will be created, which will not
+  // take in a TrieNode; it instead initializes the rootNode and creates a trie based on
+  // some input data. The constructor is blocked by the implementation of RoutingDataAccessor, and
+  // will therefore be implemented later.
+  public TrieRoutingData(TrieNode rootNode) {
+    _rootNode = rootNode;
+  }
+
+  static class TrieNode {
+    final Map<String, TrieNode> _children;
+    final boolean _isLeaf;
+    final String _zkRealmAddress;
+
+    TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String zkRealmAddress) {
+      _children = children;
+      _isLeaf = isLeaf;
+      _zkRealmAddress = zkRealmAddress;
+    }
+  }
+
+  public Map<String, String> getAllMappingUnderPath(String zkPath) {
+    TrieNode curNode;
+    try {
+      curNode = findTrieNode(zkPath);
+    } catch (IllegalArgumentException e) {
+      return Collections.emptyMap();
+    }
+
+    Map<String, String> resultMap = new HashMap<>();
+    if (zkPath.substring(zkPath.length() - 1).equals("/")) {
+      zkPath = zkPath.substring(0, zkPath.length() - 1);
+    }
+    addAllAddressesToMapping(resultMap, curNode, zkPath);
+    return resultMap;
+  }
+
+  public String getZkRealm(String zkPath) throws IllegalArgumentException {
+    TrieNode leafNode = findLeafTrieNodeAlongPath(zkPath);
+    return leafNode._zkRealmAddress;
+  }
+
+  /**
+   * Using the root node, find the trie node that the given zkPath is pointing to and return it.
+   * Raise IllegalArgumentException if the zkPath does not point to any node.
+   * @param zkPath - the zkPath where the search is conducted
+   * @return the node pointed by the zkPath
+   * @throws IllegalArgumentException - when the zkPath points to nothing
+   */
+  private TrieNode findTrieNode(String zkPath) throws IllegalArgumentException {
+    if (zkPath.equals("/") || zkPath.equals("")) {
+      return _rootNode;
+    }
+
+    if (zkPath.substring(0, 1).equals("/")) {
+      zkPath = zkPath.substring(1);
+    }
+    String[] splitZkPath = zkPath.split("/", 0);
+    TrieNode curNode = _rootNode;
+    Map<String, TrieNode> curChildren = curNode._children;
+    for (String pathSection : splitZkPath) {
+      curNode = curChildren.get(pathSection);
+      if (curNode != null) {
+        curChildren = curNode._children;
+      } else {
+        throw new IllegalArgumentException("the provided zkPath is missing from the trie");
+      }
+    }
+    return curNode;
+  }
+
+  /**
+   * Using the root node, find the leaf node along the provided zkPath. Raise
+   * IllegalArgumentException if the zkPath does not point to any node or if there is no leaf node
+   * along the path.
+   * @param zkPath - the zkPath where the search is conducted
+   * @return the leaf node along the provided zkPath
+   * @throws IllegalArgumentException - when the zkPath points to nothing or when there is no leaf
+   *           node along the path.
+   */
+  private TrieNode findLeafTrieNodeAlongPath(String zkPath) throws IllegalArgumentException {
 
 Review comment:
   This method is 90% the same as the findTrieNode, can we please merge them?

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org