1 files changed, 137 insertions, 0 deletions
diff --git a/casa/search/Node.H b/casa/search/Node.H
new file mode 100644
index 0000000..5e5b478
--- /dev/null
+++ b/casa/search/Node.H
@@ -0,0 +1,137 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA.  If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef NODE_H
+#define NODE_H
+
+#include <cassert>
+#include <iostream>
+#include <set>
+
+// Represents an explored state, its heuristic estimate, the best known path
+// leading to that state, and other nodes whose best paths this state is on.
+
+template<class STATE, class COST>class Node {
+protected:
+  typedef Node<STATE,COST>*		Edge;
+
+  // The node immediately preceding this one on a best path.
+  Edge					parent;
+  // The state.
+  const STATE				state;
+  // The distance from the start state along the best path.
+  COST					traveled;
+  // The heuristic estimate of the distance to a goal state.
+  COST					estimate;
+  // The set of nodes who have this one as their parent.
+  std::set<Edge>			children;
+
+public:
+  Node(Edge parent, const STATE&state, COST traveled, COST estimate) :
+    parent(parent),
+    state(state),
+    traveled(traveled),
+    estimate(estimate) {
+    if (parent) {
+      parent->children.insert(this);
+    }
+  }
+
+  virtual ~Node() {
+    if (parent) {
+      parent->removeChild(this);
+    }
+    for (typename std::set<Edge>::iterator
+	   iterator = children.begin(),
+	   end = children.end();
+	 iterator != end;) {
+      Edge child = *iterator;
+      ++iterator;
+      removeChild(child);
+    }
+  }
+
+  const STATE&getState() const {
+    return state;
+  }
+
+  COST getTraveled() const {
+    return traveled;
+  }
+  void setTraveled(COST traveled) {
+    this->traveled = traveled;
+  }
+
+  COST getEstimate() const {
+    return estimate;
+  }
+  void setEstimate(COST estimate) {
+    this->estimate = estimate;
+  }
+
+  Edge getParent() const {
+    return parent;
+  }
+
+  const std::set<Edge>&getChildren() const {
+    return children;
+  }
+
+  void addChild(Edge child) {
+    assert(child);
+    if (child->parent) {
+      if (child->parent == this) {
+	return;
+      }
+      child->parent->removeChild(child);
+    }
+    child->parent = this;
+    children.insert(child);
+  }
+
+  void removeChild(Edge child) {
+    assert(child);
+    if (child->parent != this) {
+      return;
+    }
+    child->parent = NULL;
+    children.erase(child);
+  }
+
+  // Comparisons are made solely by state.
+#define COMP(op) bool operator op(const Node&other) const { \
+    return state op other.state; \
+  }
+  COMP(<);
+  COMP(>);
+  COMP(==);
+  COMP(!=);
+#undef COMP
+};
+
+template<class STATE, class COST>std::ostream&operator <<
+  (std::ostream&out, const Node<STATE, COST>node) {
+  out << node.getState() << '(' << node.getTraveled() << '+' <<
+    node.getEstimate() << "*)";
+  if (node.getParent()) {
+    return out << "<-" << *node.getParent();
+  }
+  return out;
+}
+
+#endif