iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/PathPatternTree.java - iotdb - Git at Google

 /*
  * 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.iotdb.commons.path;

 import org.apache.iotdb.commons.conf.IoTDBConstant;
 import org.apache.iotdb.commons.path.PathPatternNode.VoidSerializer;
 import org.apache.iotdb.tsfile.common.constant.TsFileConstant;
 import org.apache.iotdb.tsfile.utils.PublicBAOS;

 import java.io.DataOutputStream;
 import java.io.IOException;
 import java.nio.ByteBuffer;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Deque;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Objects;
 import java.util.Set;

 public class PathPatternTree {

   private PathPatternNode<Void, VoidSerializer> root;

   private List<PartialPath> pathPatternList;

   // set the default value to TRUE to ensure correctness
   private boolean useWildcard = true;
   private boolean containWildcard = false;
   private boolean containFullPath = false;

   public PathPatternTree(boolean useWildcard) {
     this();
     this.useWildcard = useWildcard;
   }

   public PathPatternTree() {
     this.root = new PathPatternNode<>(IoTDBConstant.PATH_ROOT, VoidSerializer.getInstance());
     this.pathPatternList = new LinkedList<>();
   }

   public boolean isContainWildcard() {
     return containWildcard;
   }

   public boolean isContainFullPath() {
     return containFullPath;
   }

   public PathPatternNode<Void, VoidSerializer> getRoot() {
     return root;
   }

   public void setRoot(PathPatternNode<Void, VoidSerializer> root) {
     this.root = root;
   }

   /////////////////////////////////////////////////////////////////////////////////////////////////
   // Operations for constructing tree
   /////////////////////////////////////////////////////////////////////////////////////////////////

   /** Append a fullPath (without wildcards) as a branch on the tree. */
   public void appendFullPath(PartialPath fullPath) {
     appendBranchWithoutPrune(root, fullPath.getNodes(), 0);
   }

   /** Append a fullPath consisting of device and measurement as a branch on the tree. */
   public void appendFullPath(PartialPath devicePath, String measurement) {
     int deviceNodeLength = devicePath.getNodeLength();
     String[] pathNodes = new String[deviceNodeLength + 1];
     System.arraycopy(devicePath.getNodes(), 0, pathNodes, 0, deviceNodeLength);
     pathNodes[deviceNodeLength] = measurement;

     appendBranchWithoutPrune(root, pathNodes, 0);
   }

   /** Add a pathPattern (may contain wildcards) to pathPatternList. */
   public void appendPathPattern(PartialPath pathPattern) {
     if (useWildcard) {
       boolean isExist = false;
       for (PartialPath path : pathPatternList) {
         if (path.include(pathPattern)) {
           // path already exists in pathPatternList
           isExist = true;
           break;
         }
       }
       if (!isExist) {
         // remove duplicate path in pathPatternList
         pathPatternList.removeIf(pathPattern::include);
         pathPatternList.add(pathPattern);
       }
     } else {
       appendBranchWithoutPrune(root, pathPattern.getNodes(), 0);
     }
   }

   /** Construct tree according to the pathPatternList. */
   public void constructTree() {
     for (PartialPath path : pathPatternList) {
       appendBranchWithoutPrune(root, path.getNodes(), 0);
     }
     pathPatternList.clear();
   }

   private void appendBranchWithoutPrune(
       PathPatternNode<Void, VoidSerializer> curNode, String[] pathNodes, int pos) {
     if (pos == pathNodes.length - 1) {
       curNode.markPathPattern(true);
       return;
     }

     PathPatternNode<Void, VoidSerializer> nextNode = curNode.getChildren(pathNodes[pos + 1]);

     if (nextNode != null) {
       appendBranchWithoutPrune(nextNode, pathNodes, pos + 1);
     } else {
       constructBranch(curNode, pathNodes, pos + 1);
     }
   }

   private void constructBranch(
       PathPatternNode<Void, VoidSerializer> curNode, String[] pathNodes, int pos) {
     for (int i = pos; i < pathNodes.length; i++) {
       PathPatternNode<Void, VoidSerializer> newNode =
           new PathPatternNode<>(pathNodes[i], VoidSerializer.getInstance());
       curNode.addChild(newNode);
       processNodeName(pathNodes[i]);
       curNode = newNode;
     }
     curNode.markPathPattern(true);
   }

   private void processNodeName(String nodeName) {
     if (!containWildcard) {
       containWildcard = PathPatternUtil.hasWildcard(nodeName);
     }
     if (!containFullPath) {
       containFullPath = !PathPatternUtil.hasWildcard(nodeName);
     }
   }

   /////////////////////////////////////////////////////////////////////////////////////////////////
   // Operations for querying tree
   /////////////////////////////////////////////////////////////////////////////////////////////////

   public boolean isEmpty() {
     return (root.getChildren() == null || root.getChildren().isEmpty())
         && (pathPatternList == null || pathPatternList.isEmpty());
   }

   public List<String> getAllDevicePatterns() {
     List<String> nodes = new ArrayList<>();
     Set<String> results = new HashSet<>();
     searchDevicePattern(root, nodes, results);
     return new ArrayList<>(results);
   }

   public List<PartialPath> getAllDevicePaths() {
     List<String> nodes = new ArrayList<>();
     Set<List<String>> resultNodesSet = new HashSet<>();
     searchDevicePath(root, nodes, resultNodesSet);

     Set<PartialPath> resultPaths = new HashSet<>();
     for (List<String> resultNodes : resultNodesSet) {
       resultPaths.add(new PartialPath(resultNodes.toArray(new String[0])));
     }
     return new ArrayList<>(resultPaths);
   }

   private void searchDevicePattern(
       PathPatternNode<Void, VoidSerializer> curNode, List<String> nodes, Set<String> results) {
     nodes.add(curNode.getName());
     if (curNode.isPathPattern()) {
       if (!curNode.getName().equals(IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD)) {
         results.add(
             nodes.size() == 1 ? "" : convertNodesToString(nodes.subList(0, nodes.size() - 1)));
       } else {
         // the device of root.sg.d.** is root.sg.d and root.sg.d.**
         if (nodes.size() > 2) {
           results.add(convertNodesToString(nodes.subList(0, nodes.size() - 1)));
         }
         results.add(convertNodesToString(nodes));
       }
       if (curNode.isLeaf()) {
         nodes.remove(nodes.size() - 1);
         return;
       }
     }
     for (PathPatternNode<Void, VoidSerializer> childNode : curNode.getChildren().values()) {
       searchDevicePattern(childNode, nodes, results);
     }
     nodes.remove(nodes.size() - 1);
   }

   private void searchDevicePath(
       PathPatternNode<Void, VoidSerializer> curNode,
       List<String> nodes,
       Set<List<String>> resultNodesSet) {
     nodes.add(curNode.getName());
     if (curNode.isPathPattern()) {
       if (!curNode.getName().equals(IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD)) {
         resultNodesSet.add(
             nodes.size() == 1
                 ? new ArrayList<>()
                 : new ArrayList<>(nodes.subList(0, nodes.size() - 1)));
       } else {
         // the device of root.sg.d.** is root.sg.d and root.sg.d.**
         if (nodes.size() > 2) {
           resultNodesSet.add(new ArrayList<>(nodes.subList(0, nodes.size() - 1)));
         }
         resultNodesSet.add(new ArrayList<>(nodes));
       }
       if (curNode.isLeaf()) {
         nodes.remove(nodes.size() - 1);
         return;
       }
     }
     for (PathPatternNode<Void, VoidSerializer> childNode : curNode.getChildren().values()) {
       searchDevicePath(childNode, nodes, resultNodesSet);
     }
     nodes.remove(nodes.size() - 1);
   }

   public List<PartialPath> getAllPathPatterns() {
     List<PartialPath> result = new ArrayList<>();
     Deque<String> ancestors = new ArrayDeque<>();
     searchPathPattern(root, ancestors, result);
     return result;
   }

   private void searchPathPattern(
       PathPatternNode<Void, VoidSerializer> node,
       Deque<String> ancestors,
       List<PartialPath> fullPaths) {
     if (node.isPathPattern()) {
       fullPaths.add(convertNodesToPartialPath(node, ancestors));
       if (node.isLeaf()) {
         return;
       }
     }

     ancestors.push(node.getName());
     for (PathPatternNode<Void, VoidSerializer> child : node.getChildren().values()) {
       searchPathPattern(child, ancestors, fullPaths);
     }
     ancestors.pop();
   }

   public List<PartialPath> getOverlappedPathPatterns(PartialPath pattern) {
     if (pathPatternList.isEmpty()) {
       pathPatternList = getAllPathPatterns();
     }

     List<PartialPath> results = new ArrayList<>();
     for (PartialPath path : pathPatternList) {
       if (pattern.overlapWith(path)) {
         results.add(path);
       }
     }
     return results;
   }

   private String convertNodesToString(List<String> nodes) {
     StringBuilder fullPathBuilder = new StringBuilder(nodes.get(0));
     for (int i = 1; i < nodes.size(); i++) {
       fullPathBuilder.append(TsFileConstant.PATH_SEPARATOR).append(nodes.get(i));
     }
     return fullPathBuilder.toString();
   }

   private PartialPath convertNodesToPartialPath(
       PathPatternNode<Void, VoidSerializer> node, Deque<String> ancestors) {
     Iterator<String> iterator = ancestors.descendingIterator();
     List<String> nodeList = new ArrayList<>(ancestors.size() + 1);
     while (iterator.hasNext()) {
       nodeList.add(iterator.next());
     }
     nodeList.add(node.getName());
     return new PartialPath(nodeList.toArray(new String[0]));
   }

   public boolean isOverlapWith(PathPatternTree patternTree) {
     // todo improve this implementation
     for (PartialPath pathPattern : getAllPathPatterns()) {
       if (!patternTree.getOverlappedPathPatterns(pathPattern).isEmpty()) {
         return true;
       }
     }
     return false;
   }

   public PathPatternTree intersectWithFullPathPrefixTree(PathPatternTree fullPathPrefixTree) {
     PathPatternTree result = new PathPatternTree(containWildcard);
     List<PartialPath> partialPathList = null;

     for (PartialPath fullPathOrPrefix : fullPathPrefixTree.getAllPathPatterns()) {
       PathPatternNode<Void, VoidSerializer> curNode = root;
       PathPatternNode<Void, VoidSerializer> tarNode = result.root;
       String[] nodes = fullPathOrPrefix.nodes;
       boolean done = false;
       if (fullPathOrPrefix.endWithMultiLevelWildcard()) {
         // if prefix match, directly construct result tree
         for (int i = 1; i < nodes.length - 1; i++) {
           done = true;
           List<PathPatternNode<Void, VoidSerializer>> tmp = curNode.getMatchChildren(nodes[i]);
           if (tmp.size() == 1 && tmp.get(0).getName().equals(nodes[i])) {
             curNode = tmp.get(0);
             if (tarNode.getChildren(nodes[i]) == null) {
               tarNode.addChild(new PathPatternNode<>(nodes[i], VoidSerializer.getInstance()));
             }
             tarNode = tarNode.getChildren(nodes[i]);
           } else {
             done = false;
             break;
           }
         }
       }
       if (done) {
         for (PathPatternNode<Void, VoidSerializer> node : curNode.getChildren().values()) {
           tarNode.addChild(node);
         }
       } else {
         // this branch is to construct intersection one by one
         if (partialPathList == null) {
           partialPathList = getAllPathPatterns();
         }
         for (PartialPath pathPattern : partialPathList) {
           if (fullPathOrPrefix.endWithMultiLevelWildcard()) {
             // prefix
             for (PartialPath temp : pathPattern.intersectWithPrefixPattern(fullPathOrPrefix)) {
               result.appendPathPattern(temp);
             }
           } else {
             // full path
             if (pathPattern.matchFullPath(fullPathOrPrefix)) {
               result.appendPathPattern(fullPathOrPrefix);
             }
           }
         }
       }
     }
     result.constructTree();
     return result;
   }

   /////////////////////////////////////////////////////////////////////////////////////////////////
   // serialize & deserialize
   /////////////////////////////////////////////////////////////////////////////////////////////////

   public void serialize(PublicBAOS outputStream) throws IOException {
     constructTree();
     root.serialize(outputStream);
   }

   public void serialize(DataOutputStream stream) throws IOException {
     constructTree();
     root.serialize(stream);
   }

   public void serialize(ByteBuffer buffer) {
     constructTree();
     root.serialize(buffer);
   }

   public ByteBuffer serialize() throws IOException {
     PublicBAOS baos = new PublicBAOS();
     serialize(baos);
     ByteBuffer serializedPatternTree = ByteBuffer.allocate(baos.size());
     serializedPatternTree.put(baos.getBuf(), 0, baos.size());
     serializedPatternTree.flip();
     return serializedPatternTree;
   }

   public static PathPatternTree deserialize(ByteBuffer buffer) {
     PathPatternTree deserializedPatternTree = new PathPatternTree();
     PathPatternNode<Void, VoidSerializer> root =
         PathPatternNode.deserializeNode(
             buffer, VoidSerializer.getInstance(), deserializedPatternTree::processNodeName);
     deserializedPatternTree.setRoot(root);
     return deserializedPatternTree;
   }

   @Override
   public boolean equals(Object o) {
     if (this == o) return true;
     if (o == null || getClass() != o.getClass()) return false;
     PathPatternTree that = (PathPatternTree) o;
     return Objects.equals(root, that.root);
   }

   @Override
   public int hashCode() {
     return Objects.hash(root);
   }
 }
	/*
	* 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.iotdb.commons.path;

	import org.apache.iotdb.commons.conf.IoTDBConstant;
	import org.apache.iotdb.commons.path.PathPatternNode.VoidSerializer;
	import org.apache.iotdb.tsfile.common.constant.TsFileConstant;
	import org.apache.iotdb.tsfile.utils.PublicBAOS;

	import java.io.DataOutputStream;
	import java.io.IOException;
	import java.nio.ByteBuffer;
	import java.util.ArrayDeque;
	import java.util.ArrayList;
	import java.util.Deque;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Objects;
	import java.util.Set;

	public class PathPatternTree {

	private PathPatternNode<Void, VoidSerializer> root;

	private List<PartialPath> pathPatternList;

	// set the default value to TRUE to ensure correctness
	private boolean useWildcard = true;
	private boolean containWildcard = false;
	private boolean containFullPath = false;

	public PathPatternTree(boolean useWildcard) {
	this();
	this.useWildcard = useWildcard;
	}

	public PathPatternTree() {
	this.root = new PathPatternNode<>(IoTDBConstant.PATH_ROOT, VoidSerializer.getInstance());
	this.pathPatternList = new LinkedList<>();
	}

	public boolean isContainWildcard() {
	return containWildcard;
	}

	public boolean isContainFullPath() {
	return containFullPath;
	}

	public PathPatternNode<Void, VoidSerializer> getRoot() {
	return root;
	}

	public void setRoot(PathPatternNode<Void, VoidSerializer> root) {
	this.root = root;
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////
	// Operations for constructing tree
	/////////////////////////////////////////////////////////////////////////////////////////////////

	/** Append a fullPath (without wildcards) as a branch on the tree. */
	public void appendFullPath(PartialPath fullPath) {
	appendBranchWithoutPrune(root, fullPath.getNodes(), 0);
	}

	/** Append a fullPath consisting of device and measurement as a branch on the tree. */
	public void appendFullPath(PartialPath devicePath, String measurement) {
	int deviceNodeLength = devicePath.getNodeLength();
	String[] pathNodes = new String[deviceNodeLength + 1];
	System.arraycopy(devicePath.getNodes(), 0, pathNodes, 0, deviceNodeLength);
	pathNodes[deviceNodeLength] = measurement;

	appendBranchWithoutPrune(root, pathNodes, 0);
	}

	/** Add a pathPattern (may contain wildcards) to pathPatternList. */
	public void appendPathPattern(PartialPath pathPattern) {
	if (useWildcard) {
	boolean isExist = false;
	for (PartialPath path : pathPatternList) {
	if (path.include(pathPattern)) {
	// path already exists in pathPatternList
	isExist = true;
	break;
	}
	}
	if (!isExist) {
	// remove duplicate path in pathPatternList
	pathPatternList.removeIf(pathPattern::include);
	pathPatternList.add(pathPattern);
	}
	} else {
	appendBranchWithoutPrune(root, pathPattern.getNodes(), 0);
	}
	}

	/** Construct tree according to the pathPatternList. */
	public void constructTree() {
	for (PartialPath path : pathPatternList) {
	appendBranchWithoutPrune(root, path.getNodes(), 0);
	}
	pathPatternList.clear();
	}

	private void appendBranchWithoutPrune(
	PathPatternNode<Void, VoidSerializer> curNode, String[] pathNodes, int pos) {
	if (pos == pathNodes.length - 1) {
	curNode.markPathPattern(true);
	return;
	}

	PathPatternNode<Void, VoidSerializer> nextNode = curNode.getChildren(pathNodes[pos + 1]);

	if (nextNode != null) {
	appendBranchWithoutPrune(nextNode, pathNodes, pos + 1);
	} else {
	constructBranch(curNode, pathNodes, pos + 1);
	}
	}

	private void constructBranch(
	PathPatternNode<Void, VoidSerializer> curNode, String[] pathNodes, int pos) {
	for (int i = pos; i < pathNodes.length; i++) {
	PathPatternNode<Void, VoidSerializer> newNode =
	new PathPatternNode<>(pathNodes[i], VoidSerializer.getInstance());
	curNode.addChild(newNode);
	processNodeName(pathNodes[i]);
	curNode = newNode;
	}
	curNode.markPathPattern(true);
	}

	private void processNodeName(String nodeName) {
	if (!containWildcard) {
	containWildcard = PathPatternUtil.hasWildcard(nodeName);
	}
	if (!containFullPath) {
	containFullPath = !PathPatternUtil.hasWildcard(nodeName);
	}
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////
	// Operations for querying tree
	/////////////////////////////////////////////////////////////////////////////////////////////////

	public boolean isEmpty() {
	return (root.getChildren() == null \|\| root.getChildren().isEmpty())
	&& (pathPatternList == null \|\| pathPatternList.isEmpty());
	}

	public List<String> getAllDevicePatterns() {
	List<String> nodes = new ArrayList<>();
	Set<String> results = new HashSet<>();
	searchDevicePattern(root, nodes, results);
	return new ArrayList<>(results);
	}

	public List<PartialPath> getAllDevicePaths() {
	List<String> nodes = new ArrayList<>();
	Set<List<String>> resultNodesSet = new HashSet<>();
	searchDevicePath(root, nodes, resultNodesSet);

	Set<PartialPath> resultPaths = new HashSet<>();
	for (List<String> resultNodes : resultNodesSet) {
	resultPaths.add(new PartialPath(resultNodes.toArray(new String[0])));
	}
	return new ArrayList<>(resultPaths);
	}

	private void searchDevicePattern(
	PathPatternNode<Void, VoidSerializer> curNode, List<String> nodes, Set<String> results) {
	nodes.add(curNode.getName());
	if (curNode.isPathPattern()) {
	if (!curNode.getName().equals(IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD)) {
	results.add(
	nodes.size() == 1 ? "" : convertNodesToString(nodes.subList(0, nodes.size() - 1)));
	} else {
	// the device of root.sg.d. is root.sg.d and root.sg.d.
	if (nodes.size() > 2) {
	results.add(convertNodesToString(nodes.subList(0, nodes.size() - 1)));
	}
	results.add(convertNodesToString(nodes));
	}
	if (curNode.isLeaf()) {
	nodes.remove(nodes.size() - 1);
	return;
	}
	}
	for (PathPatternNode<Void, VoidSerializer> childNode : curNode.getChildren().values()) {
	searchDevicePattern(childNode, nodes, results);
	}
	nodes.remove(nodes.size() - 1);
	}

	private void searchDevicePath(
	PathPatternNode<Void, VoidSerializer> curNode,
	List<String> nodes,
	Set<List<String>> resultNodesSet) {
	nodes.add(curNode.getName());
	if (curNode.isPathPattern()) {
	if (!curNode.getName().equals(IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD)) {
	resultNodesSet.add(
	nodes.size() == 1
	? new ArrayList<>()
	: new ArrayList<>(nodes.subList(0, nodes.size() - 1)));
	} else {
	// the device of root.sg.d. is root.sg.d and root.sg.d.
	if (nodes.size() > 2) {
	resultNodesSet.add(new ArrayList<>(nodes.subList(0, nodes.size() - 1)));
	}
	resultNodesSet.add(new ArrayList<>(nodes));
	}
	if (curNode.isLeaf()) {
	nodes.remove(nodes.size() - 1);
	return;
	}
	}
	for (PathPatternNode<Void, VoidSerializer> childNode : curNode.getChildren().values()) {
	searchDevicePath(childNode, nodes, resultNodesSet);
	}
	nodes.remove(nodes.size() - 1);
	}

	public List<PartialPath> getAllPathPatterns() {
	List<PartialPath> result = new ArrayList<>();
	Deque<String> ancestors = new ArrayDeque<>();
	searchPathPattern(root, ancestors, result);
	return result;
	}

	private void searchPathPattern(
	PathPatternNode<Void, VoidSerializer> node,
	Deque<String> ancestors,
	List<PartialPath> fullPaths) {
	if (node.isPathPattern()) {
	fullPaths.add(convertNodesToPartialPath(node, ancestors));
	if (node.isLeaf()) {
	return;
	}
	}

	ancestors.push(node.getName());
	for (PathPatternNode<Void, VoidSerializer> child : node.getChildren().values()) {
	searchPathPattern(child, ancestors, fullPaths);
	}
	ancestors.pop();
	}

	public List<PartialPath> getOverlappedPathPatterns(PartialPath pattern) {
	if (pathPatternList.isEmpty()) {
	pathPatternList = getAllPathPatterns();
	}

	List<PartialPath> results = new ArrayList<>();
	for (PartialPath path : pathPatternList) {
	if (pattern.overlapWith(path)) {
	results.add(path);
	}
	}
	return results;
	}

	private String convertNodesToString(List<String> nodes) {
	StringBuilder fullPathBuilder = new StringBuilder(nodes.get(0));
	for (int i = 1; i < nodes.size(); i++) {
	fullPathBuilder.append(TsFileConstant.PATH_SEPARATOR).append(nodes.get(i));
	}
	return fullPathBuilder.toString();
	}

	private PartialPath convertNodesToPartialPath(
	PathPatternNode<Void, VoidSerializer> node, Deque<String> ancestors) {
	Iterator<String> iterator = ancestors.descendingIterator();
	List<String> nodeList = new ArrayList<>(ancestors.size() + 1);
	while (iterator.hasNext()) {
	nodeList.add(iterator.next());
	}
	nodeList.add(node.getName());
	return new PartialPath(nodeList.toArray(new String[0]));
	}

	public boolean isOverlapWith(PathPatternTree patternTree) {
	// todo improve this implementation
	for (PartialPath pathPattern : getAllPathPatterns()) {
	if (!patternTree.getOverlappedPathPatterns(pathPattern).isEmpty()) {
	return true;
	}
	}
	return false;
	}

	public PathPatternTree intersectWithFullPathPrefixTree(PathPatternTree fullPathPrefixTree) {
	PathPatternTree result = new PathPatternTree(containWildcard);
	List<PartialPath> partialPathList = null;

	for (PartialPath fullPathOrPrefix : fullPathPrefixTree.getAllPathPatterns()) {
	PathPatternNode<Void, VoidSerializer> curNode = root;
	PathPatternNode<Void, VoidSerializer> tarNode = result.root;
	String[] nodes = fullPathOrPrefix.nodes;
	boolean done = false;
	if (fullPathOrPrefix.endWithMultiLevelWildcard()) {
	// if prefix match, directly construct result tree
	for (int i = 1; i < nodes.length - 1; i++) {
	done = true;
	List<PathPatternNode<Void, VoidSerializer>> tmp = curNode.getMatchChildren(nodes[i]);
	if (tmp.size() == 1 && tmp.get(0).getName().equals(nodes[i])) {
	curNode = tmp.get(0);
	if (tarNode.getChildren(nodes[i]) == null) {
	tarNode.addChild(new PathPatternNode<>(nodes[i], VoidSerializer.getInstance()));
	}
	tarNode = tarNode.getChildren(nodes[i]);
	} else {
	done = false;
	break;
	}
	}
	}
	if (done) {
	for (PathPatternNode<Void, VoidSerializer> node : curNode.getChildren().values()) {
	tarNode.addChild(node);
	}
	} else {
	// this branch is to construct intersection one by one
	if (partialPathList == null) {
	partialPathList = getAllPathPatterns();
	}
	for (PartialPath pathPattern : partialPathList) {
	if (fullPathOrPrefix.endWithMultiLevelWildcard()) {
	// prefix
	for (PartialPath temp : pathPattern.intersectWithPrefixPattern(fullPathOrPrefix)) {
	result.appendPathPattern(temp);
	}
	} else {
	// full path
	if (pathPattern.matchFullPath(fullPathOrPrefix)) {
	result.appendPathPattern(fullPathOrPrefix);
	}
	}
	}
	}
	}
	result.constructTree();
	return result;
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////
	// serialize & deserialize
	/////////////////////////////////////////////////////////////////////////////////////////////////

	public void serialize(PublicBAOS outputStream) throws IOException {
	constructTree();
	root.serialize(outputStream);
	}

	public void serialize(DataOutputStream stream) throws IOException {
	constructTree();
	root.serialize(stream);
	}

	public void serialize(ByteBuffer buffer) {
	constructTree();
	root.serialize(buffer);
	}

	public ByteBuffer serialize() throws IOException {
	PublicBAOS baos = new PublicBAOS();
	serialize(baos);
	ByteBuffer serializedPatternTree = ByteBuffer.allocate(baos.size());
	serializedPatternTree.put(baos.getBuf(), 0, baos.size());
	serializedPatternTree.flip();
	return serializedPatternTree;
	}

	public static PathPatternTree deserialize(ByteBuffer buffer) {
	PathPatternTree deserializedPatternTree = new PathPatternTree();
	PathPatternNode<Void, VoidSerializer> root =
	PathPatternNode.deserializeNode(
	buffer, VoidSerializer.getInstance(), deserializedPatternTree::processNodeName);
	deserializedPatternTree.setRoot(root);
	return deserializedPatternTree;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) return true;
	if (o == null \|\| getClass() != o.getClass()) return false;
	PathPatternTree that = (PathPatternTree) o;
	return Objects.equals(root, that.root);
	}

	@Override
	public int hashCode() {
	return Objects.hash(root);
	}
	}