diff options
| author | David Robillard <d@drobilla.net> | 2012-04-26 15:59:18 +0000 |
|---|---|---|
| committer | David Robillard <d@drobilla.net> | 2012-04-26 15:59:18 +0000 |
| commit | 209101b24ff99090a2b7f379767a50c4cf6b3e41 (patch) | |
| tree | fa656c9343624ccb87e17449c09923ff4d955e42 /src/Canvas.cpp | |
| parent | 549647b61924ea8bcd55ad243ff9c6fce6d634cb (diff) | |
| download | ganv-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/Canvas.cpp')
| -rw-r--r-- | src/Canvas.cpp | 34 |
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, |