-/*******************************************************************************\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
+/*******************************************************************************
+ * ============LICENSE_START==================================================
+ * * org.onap.dmaap
+ * * ===========================================================================
+ * * Copyright © 2017 AT&T Intellectual Property. All rights reserved.
+ * * ===========================================================================
+ * * Licensed 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.
+ * * ============LICENSE_END====================================================
+ * *
+ * * ECOMP is a trademark and service mark of AT&T Intellectual Property.
+ * *
+ ******************************************************************************/
+
+
+package org.onap.dmaap.datarouter.node;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import org.jetbrains.annotations.Nullable;
+import org.onap.dmaap.datarouter.node.NodeConfig.ProvHop;
+
+/**
+ * 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
+ */
+
+public class PathFinder {
+
+ private ArrayList<String> errors = new ArrayList<>();
+ private HashMap<String, String> routes = new HashMap<>();
+
+ /**
+ * Find routes from a specified origin to all of the nodes given a set of specified next hops.
+ *
+ * @param origin where we start
+ * @param nodes where we can go
+ * @param hops detours along the way
+ */
+ public PathFinder(String origin, String[] nodes, NodeConfig.ProvHop[] hops) {
+ HashSet<String> known = new HashSet<>();
+ HashMap<String, HashMap<String, Hop>> ht = new HashMap<>();
+ for (String n : nodes) {
+ known.add(n);
+ ht.put(n, new HashMap<>());
+ }
+ for (NodeConfig.ProvHop ph : hops) {
+ Hop h = getHop(known, ht, ph);
+ if (h == null) {
+ continue;
+ }
+ if (ph.getVia().equals(ph.getTo())) {
+ errors.add(ph + " gives destination as via");
+ h.bad = true;
+ }
+ }
+ for (String n : known) {
+ if (n.equals(origin)) {
+ routes.put(n, "");
+ }
+ routes.put(n, plot(origin, n, ht.get(n)) + "/");
+ }
+ }
+
+ /**
+ * Get list of errors encountered while finding paths
+ *
+ * @return array of error descriptions
+ */
+ public String[] getErrors() {
+ return (errors.toArray(new String[errors.size()]));
+ }
+
+ /**
+ * Get the route from this node to the specified node
+ *
+ * @param destination node
+ * @return list of node names separated by and ending with "/"
+ */
+ public String getPath(String destination) {
+ String ret = routes.get(destination);
+ if (ret == null) {
+ return ("");
+ }
+ return (ret);
+ }
+
+ private String plot(String from, String to, HashMap<String, Hop> info) {
+ Hop nh = info.get(from);
+ if (nh == null || nh.bad) {
+ return (to);
+ }
+ if (nh.mark) {
+ while (!nh.bad) {
+ nh.bad = true;
+ errors.add(nh.basis + " is part of a cycle");
+ nh = info.get(nh.basis.getVia());
+ }
+ return (to);
+ }
+ nh.mark = true;
+ String x = plot(nh.basis.getVia(), to, info);
+ nh.mark = false;
+ if (nh.bad) {
+ return (to);
+ }
+ return (nh.basis.getVia() + "/" + x);
+ }
+
+ @Nullable
+ private Hop getHop(HashSet<String> known, HashMap<String, HashMap<String, Hop>> ht, ProvHop ph) {
+ if (!known.contains(ph.getFrom())) {
+ errors.add(ph + " references unknown from node");
+ return null;
+ }
+ if (!known.contains(ph.getTo())) {
+ errors.add(ph + " references unknown destination node");
+ return null;
+ }
+ HashMap<String, Hop> ht2 = ht.get(ph.getTo());
+ Hop h = ht2.get(ph.getFrom());
+ if (h != null) {
+ h.bad = true;
+ errors.add(ph + " gives duplicate next hop - previous via was " + h.basis.getVia());
+ return null;
+ }
+ h = new Hop();
+ h.basis = ph;
+ ht2.put(ph.getFrom(), h);
+ if (!known.contains(ph.getVia())) {
+ errors.add(ph + " references unknown via node");
+ h.bad = true;
+ return null;
+ }
+ return h;
+ }
+
+ private static class Hop {
+
+ boolean mark;
+ boolean bad;
+ NodeConfig.ProvHop basis;
+ }
+}
Code Review / dmaap / datarouter.git / blobdiff