summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2012-04-26 15:59:18 +0000
committerDavid Robillard <d@drobilla.net>2012-04-26 15:59:18 +0000
commit209101b24ff99090a2b7f379767a50c4cf6b3e41 (patch)
treefa656c9343624ccb87e17449c09923ff4d955e42 /src
parent549647b61924ea8bcd55ad243ff9c6fce6d634cb (diff)
downloadganv-209101b24ff99090a2b7f379767a50c4cf6b3e41.tar.gz
ganv-209101b24ff99090a2b7f379767a50c4cf6b3e41.tar.bz2
ganv-209101b24ff99090a2b7f379767a50c4cf6b3e41.zip
Fix O(n_edges) Canvas::get_edge() to be O(lg(n_nodes)).
git-svn-id: http://svn.drobilla.net/lad/trunk/ganv@4275 a436a847-0d15-0410-975c-d299462d15a1
Diffstat (limited to 'src')
-rw-r--r--src/Canvas.cpp34
1 files changed, 17 insertions, 17 deletions
diff --git a/src/Canvas.cpp b/src/Canvas.cpp
index 2d12c17..b7925d7 100644
--- a/src/Canvas.cpp
+++ b/src/Canvas.cpp
@@ -190,10 +190,10 @@ struct GanvCanvasImpl {
void remove_edge(GanvEdge* c);
bool are_connected(const GanvNode* tail,
- const GanvNode* head);
+ const GanvNode* head) const;
GanvEdge*
get_edge_between(const GanvNode* tail,
- const GanvNode* head);
+ const GanvNode* head) const;
typedef std::set<GanvEdge*, TailHeadOrder> Edges;
typedef std::set<GanvEdge*, HeadTailOrder> DstEdges;
@@ -611,7 +611,7 @@ GanvCanvasImpl::remove_edge(GanvEdge* edge)
GanvEdge*
GanvCanvasImpl::get_edge_between(const GanvNode* tail,
- const GanvNode* head)
+ const GanvNode* head) const
{
GanvEdgeKey key;
make_edge_search_key(&key, tail, head);
@@ -626,7 +626,7 @@ GanvCanvasImpl::get_edge_between(const GanvNode* tail,
*/
bool
GanvCanvasImpl::are_connected(const GanvNode* tail,
- const GanvNode* head)
+ const GanvNode* head) const
{
return get_edge_between(tail, head) != NULL;
}
@@ -1449,23 +1449,15 @@ Canvas::remove_edge(Node* item1, Node* item2)
}
}
-/** Get the edge between two items.
- *
- * Note that edges are directed.
- * This will only return a edge from @a tail to @a head.
- */
Edge*
Canvas::get_edge(Node* tail, Node* head) const
{
- FOREACH_EDGE(impl()->_edges, i) {
- const GanvNode* const t = (*i)->impl->tail;
- const GanvNode* const h = (*i)->impl->head;
-
- if (t == tail->gobj() && h == head->gobj())
- return Glib::wrap(*i);
+ GanvEdge* e = impl()->get_edge_between(tail->gobj(), head->gobj());
+ if (e) {
+ return Glib::wrap(e);
+ } else {
+ return NULL;
}
-
- return NULL;
}
void
@@ -1859,6 +1851,14 @@ ganv_canvas_add_node(GanvCanvas* canvas,
canvas->impl->add_item(node);
}
+GanvEdge*
+ganv_canvas_get_edge(GanvCanvas* canvas,
+ GanvNode* tail,
+ GanvNode* head)
+{
+ return canvas->impl->get_edge_between(tail, head);
+}
+
void
ganv_canvas_remove_edge_between(GanvCanvas* canvas,
GanvNode* tail,