From eb07120dfdbb206124f7857016a71b6ef0b9eb99 Mon Sep 17 00:00:00 2001
From: Brian Norris <banorris@uci.edu>
Date: Fri, 25 Jan 2013 16:41:27 -0800
Subject: [PATCH] cyclegraph: add removeEdge(), removeBackEdge()

For popping edges of a node that's about to be merged with another one.

Note that if using these functions, a user has to manage the
'CycleGraph::hasCycles' state. This only handles the inter-Node edge
lists.
---
 cyclegraph.cc | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 cyclegraph.h  |  3 +++
 2 files changed, 51 insertions(+)

diff --git a/cyclegraph.cc b/cyclegraph.cc
index 7a353283..57f8fc8c 100644
--- a/cyclegraph.cc
+++ b/cyclegraph.cc
@@ -320,6 +320,54 @@ unsigned int CycleNode::getNumBackEdges() const
 	return back_edges.size();
 }
 
+/**
+ * @brief Remove an element from a vector
+ * @param v The vector
+ * @param n The element to remove
+ * @return True if the element was found; false otherwise
+ */
+template <typename T>
+static bool vector_remove_node(std::vector<T, SnapshotAlloc<T> >& v, const T n)
+{
+	for (unsigned int i = 0; i < v.size(); i++) {
+		if (v[i] == n) {
+			v.erase(v.begin() + i);
+			return true;
+		}
+	}
+	return false;
+}
+
+/**
+ * @brief Remove a (forward) edge from this CycleNode
+ * @return The CycleNode which was popped, if one exists; otherwise NULL
+ */
+CycleNode * CycleNode::removeEdge()
+{
+	if (edges.empty())
+		return NULL;
+
+	CycleNode *ret = edges.back();
+	edges.pop_back();
+	vector_remove_node(ret->back_edges, this);
+	return ret;
+}
+
+/**
+ * @brief Remove a (back) edge from this CycleNode
+ * @return The CycleNode which was popped, if one exists; otherwise NULL
+ */
+CycleNode * CycleNode::removeBackEdge()
+{
+	if (back_edges.empty())
+		return NULL;
+
+	CycleNode *ret = back_edges.back();
+	back_edges.pop_back();
+	vector_remove_node(ret->edges, this);
+	return ret;
+}
+
 /**
  * Adds an edge from this CycleNode to another CycleNode.
  * @param node The node to which we add a directed edge
diff --git a/cyclegraph.h b/cyclegraph.h
index f7b346c1..a909c10b 100644
--- a/cyclegraph.h
+++ b/cyclegraph.h
@@ -73,6 +73,9 @@ class CycleNode {
 	unsigned int getNumEdges() const;
 	CycleNode * getBackEdge(unsigned int i) const;
 	unsigned int getNumBackEdges() const;
+	CycleNode * removeEdge();
+	CycleNode * removeBackEdge();
+
 	bool setRMW(CycleNode *);
 	CycleNode * getRMW() const;
 	void clearRMW() { hasRMW = NULL; }
-- 
2.34.1