Update project structure to org.onap

[dmaap/datarouter.git] / datarouter-node / src / main / java / org / onap / dmaap / datarouter / node / PathFinder.java

diff --git a/datarouter-node/src/main/java/org/onap/dmaap/datarouter/node/PathFinder.java b/datarouter-node/src/main/java/org/onap/dmaap/datarouter/node/PathFinder.java
new file mode 100644 (file)
index 0000000..b99f168
--- /dev/null
+++ b/datarouter-node/src/main/java/org/onap/dmaap/datarouter/node/PathFinder.java
@@ -0,0 +1,132 @@
+/*******************************************************************************\r
+ * ============LICENSE_START==================================================\r
+ * * org.onap.dmaap\r
+ * * ===========================================================================\r
+ * * Copyright © 2017 AT&T Intellectual Property. All rights reserved.\r
+ * * ===========================================================================\r
+ * * Licensed under the Apache License, Version 2.0 (the "License");\r
+ * * you may not use this file except in compliance with the License.\r
+ * * You may obtain a copy of the License at\r
+ * * \r
+ *  *      http://www.apache.org/licenses/LICENSE-2.0\r
+ * * \r
+ *  * Unless required by applicable law or agreed to in writing, software\r
+ * * distributed under the License is distributed on an "AS IS" BASIS,\r
+ * * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ * * See the License for the specific language governing permissions and\r
+ * * limitations under the License.\r
+ * * ============LICENSE_END====================================================\r
+ * *\r
+ * * ECOMP is a trademark and service mark of AT&T Intellectual Property.\r
+ * *\r
+ ******************************************************************************/\r
+\r
+\r
+package org.onap.dmaap.datarouter.node;\r
+\r
+import java.util.*;\r
+\r
+/**\r
+ *     Given a set of node names and next hops, identify and ignore any cycles and figure out the sequence of next hops to get from this node to any other node\r
+ */\r
+\r
+public class PathFinder        {\r
+       private static class Hop        {\r
+               public boolean  mark;\r
+               public boolean  bad;\r
+               public NodeConfig.ProvHop       basis;\r
+       }\r
+       private Vector<String> errors = new Vector<String>();\r
+       private Hashtable<String, String> routes = new Hashtable<String, String>();\r
+       /**\r
+        *      Get list of errors encountered while finding paths\r
+        *      @return array of error descriptions\r
+        */\r
+       public String[] getErrors() {\r
+               return(errors.toArray(new String[errors.size()]));\r
+       }\r
+       /**\r
+        *      Get the route from this node to the specified node\r
+        *      @param destination node\r
+        *      @return list of node names separated by and ending with "/"\r
+        */\r
+       public String getPath(String destination) {\r
+               String ret = routes.get(destination);\r
+               if (ret == null) {\r
+                       return("");\r
+               }\r
+               return(ret);\r
+       }\r
+       private String plot(String from, String to, Hashtable<String, Hop> info) {\r
+               Hop nh = info.get(from);\r
+               if (nh == null || nh.bad) {\r
+                       return(to);\r
+               }\r
+               if (nh.mark) {\r
+                       // loop detected;\r
+                       while (!nh.bad) {\r
+                               nh.bad = true;\r
+                               errors.add(nh.basis + " is part of a cycle");\r
+                               nh = info.get(nh.basis.getVia());\r
+                       }\r
+                       return(to);\r
+               }\r
+               nh.mark = true;\r
+               String x = plot(nh.basis.getVia(), to, info);\r
+               nh.mark = false;\r
+               if (nh.bad) {\r
+                       return(to);\r
+               }\r
+               return(nh.basis.getVia() + "/" + x);\r
+       }\r
+       /**\r
+        *      Find routes from a specified origin to all of the nodes given a set of specified next hops.\r
+        *      @param origin   where we start\r
+        *      @param nodes    where we can go\r
+        *      @param hops     detours along the way\r
+        */\r
+       public PathFinder(String origin, String[] nodes, NodeConfig.ProvHop[] hops) {\r
+               HashSet<String> known = new HashSet<String>();\r
+               Hashtable<String, Hashtable<String, Hop>> ht = new Hashtable<String, Hashtable<String, Hop>>();\r
+               for (String n: nodes) {\r
+                       known.add(n);\r
+                       ht.put(n, new Hashtable<String, Hop>());\r
+               }\r
+               for (NodeConfig.ProvHop ph: hops) {\r
+                       if (!known.contains(ph.getFrom())) {\r
+                               errors.add(ph + " references unknown from node");\r
+                               continue;\r
+                       }\r
+                       if (!known.contains(ph.getTo())) {\r
+                               errors.add(ph + " references unknown destination node");\r
+                               continue;\r
+                       }\r
+                       Hashtable<String, Hop> ht2 = ht.get(ph.getTo());\r
+                       Hop h = ht2.get(ph.getFrom());\r
+                       if (h != null) {\r
+                               h.bad = true;\r
+                               errors.add(ph + " gives duplicate next hop - previous via was " + h.basis.getVia());\r
+                               continue;\r
+                       }\r
+                       h = new Hop();\r
+                       h.basis = ph;\r
+                       ht2.put(ph.getFrom(), h);\r
+                       if (!known.contains(ph.getVia())) {\r
+                               errors.add(ph + " references unknown via node");\r
+                               h.bad = true;\r
+                               continue;\r
+                       }\r
+                       if (ph.getVia().equals(ph.getTo())) {\r
+                               errors.add(ph + " gives destination as via");\r
+                               h.bad = true;\r
+                               continue;\r
+                       }\r
+               }\r
+               for (String n: known) {\r
+                       if (n.equals(origin)) {\r
+                               routes.put(n, "");\r
+                       }\r
+                       routes.put(n, plot(origin, n, ht.get(n)) + "/");\r
+               }\r
+       }\r
+}\r