From: Enblend <enb...@li...> - 2011-08-24 14:41:23
|
branch: details: http://enblend.hg.sourceforge.net/hgweb/enblend/enblend/hgrepo/e/en/enblend/enblend/rev/7ee5ac2883fb changeset: 742:7ee5ac2883fb user: Chris <cs...@us...> date: Mon Aug 22 08:58:23 2011 +0200 description: Replace slist containers with std::list. - Type slist is not part of the current C++ standard. - Enblend only uses small (in comparison to the image structures) slists. Therefore, the size advantage is not worth the effort. - Some slist functions have an O(n) complexity, whereas std::list provides O(1); see e.g. http://www.sgi.com/tech/stl/Slist.html. Enblend sometimes uses _exactly_ the worst case O(n) operation: appending to the end of an slist. So, preferring std::list to slist improves performance. diffstat: VERSION | 2 +- configure.in | 7 ------- doc/enblend.info | 0 doc/enfuse.info | 0 doc/versenblend.texi | 4 ++-- doc/versenfuse.texi | 4 ++-- src/anneal.h | 25 +++++++++---------------- src/common.h | 18 ++++++++++++++++++ src/mask.h | 3 +-- src/masktypedefs.h | 11 +++-------- src/postoptimizer.h | 13 ++++++------- 11 files changed, 42 insertions(+), 45 deletions(-) diffs (239 lines): diff -r 21fbcc71f475 -r 7ee5ac2883fb VERSION --- a/VERSION Mon Aug 22 08:55:42 2011 +0200 +++ b/VERSION Mon Aug 22 08:58:23 2011 +0200 @@ -1,1 +1,1 @@ -4.1-4ec3419a85ed +4.1-21fbcc71f475 diff -r 21fbcc71f475 -r 7ee5ac2883fb configure.in --- a/configure.in Mon Aug 22 08:55:42 2011 +0200 +++ b/configure.in Mon Aug 22 08:58:23 2011 +0200 @@ -163,13 +163,6 @@ AC_HEADER_DIRENT AC_HEADER_STDC -# The check for ext/slist fails on OSX, just remove it and declare that -# it is available anyhow (Its part of the GNU stl implementation) -#AC_CHECK_HEADER(ext/slist, -# AC_DEFINE(HAVE_EXT_SLIST, 1, Define if you have the <ext/slist> header file), -# AC_MSG_WARN([ext/slist is required to compile Enblend])) -AC_DEFINE(HAVE_EXT_SLIST, 1, [Define if you have the <ext/slist> header file]) - AC_CHECK_HEADERS([fenv.h limits.h stdlib.h string.h unistd.h]) AC_CHECK_HEADER(tiffio.h, [], diff -r 21fbcc71f475 -r 7ee5ac2883fb doc/enblend.info Binary file doc/enblend.info has changed diff -r 21fbcc71f475 -r 7ee5ac2883fb doc/enfuse.info Binary file doc/enfuse.info has changed diff -r 21fbcc71f475 -r 7ee5ac2883fb doc/versenblend.texi --- a/doc/versenblend.texi Mon Aug 22 08:55:42 2011 +0200 +++ b/doc/versenblend.texi Mon Aug 22 08:58:23 2011 +0200 @@ -1,4 +1,4 @@ @set UPDATED 19 August 2011 @set UPDATED-MONTH August 2011 -@set EDITION 4.1-4ec3419a85ed -@set VERSION 4.1-4ec3419a85ed +@set EDITION 4.1-21fbcc71f475 +@set VERSION 4.1-21fbcc71f475 diff -r 21fbcc71f475 -r 7ee5ac2883fb doc/versenfuse.texi --- a/doc/versenfuse.texi Mon Aug 22 08:55:42 2011 +0200 +++ b/doc/versenfuse.texi Mon Aug 22 08:58:23 2011 +0200 @@ -1,4 +1,4 @@ @set UPDATED 1 January 2011 @set UPDATED-MONTH January 2011 -@set EDITION 4.1-4ec3419a85ed -@set VERSION 4.1-4ec3419a85ed +@set EDITION 4.1-21fbcc71f475 +@set VERSION 4.1-21fbcc71f475 diff -r 21fbcc71f475 -r 7ee5ac2883fb src/anneal.h --- a/src/anneal.h Mon Aug 22 08:55:42 2011 +0200 +++ b/src/anneal.h Mon Aug 22 08:58:23 2011 +0200 @@ -27,11 +27,6 @@ #include <boost/lambda/lambda.hpp> #include <boost/lambda/bind.hpp> #include <boost/lambda/construct.hpp> -#ifdef HAVE_EXT_SLIST -#include <ext/slist> -#else -#include <slist> -#endif #include <algorithm> #include <vector> @@ -49,16 +44,14 @@ #include "vigra/iteratoradapter.hxx" #include "vigra_ext/XMIWrapper.h" +#include "masktypedefs.h" + + using std::for_each; using std::pair; using std::scientific; using std::setprecision; using std::setw; -#ifdef HAVE_EXT_SLIST -using __gnu_cxx::slist; -#else -using std::slist; -#endif using std::vector; using boost::lambda::bind; @@ -71,6 +64,7 @@ using vigra_ext::copyPaintedSetToImage; + namespace enblend { template <typename CostImage, typename VisualizeImage> @@ -81,7 +75,7 @@ typedef typename NumericTraits<CostImagePixelType>::Promote CostImagePromoteType; typedef typename CostImage::const_traverser CostIterator; - GDAConfiguration(const CostImage* const d, slist<pair<bool, Point2D> >* v, VisualizeImage* const vi) : + GDAConfiguration(const CostImage* const d, Segment* v, VisualizeImage* const vi) : costImage(d), visualizeStateSpaceImage(vi) { kMax = 1; distanceWeight = 1.0; @@ -91,9 +85,8 @@ // Determine state space of currentPoint const int stateSpaceWidth = costImageShortDimension / 3; - slist<pair<bool, Point2D> >::iterator last = v->previous(v->end()); - Point2D previousPoint = last->second; - for (slist<pair<bool, Point2D> >::iterator current = v->begin(); current != v->end();) { + Point2D previousPoint = v->back().second; + for (Segment::iterator current = v->begin(); current != v->end();) { bool currentMoveable = current->first; Point2D currentPoint = current->second; ++current; @@ -723,7 +716,7 @@ template <typename CostImage, typename VisualizeImage> void annealSnake(const CostImage* const ci, const pair<double, double>& optimizerWeights, - slist<pair<bool, Point2D> >* snake, + Segment* snake, VisualizeImage* const vi) { GDAConfiguration<CostImage, VisualizeImage> cfg(ci, snake, vi); @@ -732,7 +725,7 @@ cfg.run(); vector<Point2D>::const_iterator annealedPoint = cfg.getCurrentPoints().begin(); - for (slist<pair<bool, Point2D> >::iterator snakePoint = snake->begin(); + for (Segment::iterator snakePoint = snake->begin(); snakePoint != snake->end(); ++snakePoint, ++annealedPoint) { snakePoint->second = *annealedPoint; diff -r 21fbcc71f475 -r 7ee5ac2883fb src/common.h --- a/src/common.h Mon Aug 22 08:55:42 2011 +0200 +++ b/src/common.h Mon Aug 22 08:58:23 2011 +0200 @@ -214,6 +214,24 @@ } nearest_neigbor_metric_t; +/** Answer the previous iterator of i. */ +template <class iterator> +inline iterator +prev(iterator i) +{ + return --i; +} + + +/** Answer the following iterator of i. */ +template <class iterator> +inline iterator +next(iterator i) +{ + return ++i; +} + + /** String tokenizer similar to strtok_r(). * In contrast to strtok_r this function returns an empty string for * each pair of successive delimiters. Function strtok_r skips them. diff -r 21fbcc71f475 -r 7ee5ac2883fb src/mask.h --- a/src/mask.h Mon Aug 22 08:55:42 2011 +0200 +++ b/src/mask.h Mon Aug 22 08:58:23 2011 +0200 @@ -639,8 +639,7 @@ Segment::iterator firstNonmoveableSuccessor = firstNonmoveableVertex; ++firstNonmoveableSuccessor; if (EXPECT_RESULT(firstNonmoveableSuccessor == snake->end(), false)) { - snake->insert_after(firstNonmoveableVertex, - snake->begin(), firstNonmoveableVertex); + snake->insert(enblend::next(firstNonmoveableVertex), snake->begin(), firstNonmoveableVertex); } else { snake->insert(snake->end(), // append at the end snake->begin(), firstNonmoveableSuccessor); diff -r 21fbcc71f475 -r 7ee5ac2883fb src/masktypedefs.h --- a/src/masktypedefs.h Mon Aug 22 08:55:42 2011 +0200 +++ b/src/masktypedefs.h Mon Aug 22 08:58:23 2011 +0200 @@ -20,18 +20,13 @@ #ifndef __MASKTYPEDEFS_H__ #define __MASKTYPEDEFS_H__ -#ifdef HAVE_EXT_SLIST -#include <ext/slist> -using __gnu_cxx::slist; -#else -#include <slist> -using std::slist; -#endif +#include <list> +#include <vector> namespace enblend { typedef std::pair<bool, vigra::Point2D> SegmentPoint; - typedef slist<SegmentPoint> Segment; + typedef std::list<SegmentPoint> Segment; typedef std::vector<Segment*> Contour; typedef std::vector<Contour*> ContourVector; } diff -r 21fbcc71f475 -r 7ee5ac2883fb src/postoptimizer.h --- a/src/postoptimizer.h Mon Aug 22 08:55:42 2011 +0200 +++ b/src/postoptimizer.h Mon Aug 22 08:58:23 2011 +0200 @@ -141,7 +141,7 @@ snake, this->visualizeImage); // Post-process annealed vertices - Segment::iterator lastVertex = snake->previous(snake->end()); + Segment::iterator lastVertex = enblend::prev(snake->end()); for (Segment::iterator vertexIterator = snake->begin(); vertexIterator != snake->end();) { if (vertexIterator->first && @@ -151,7 +151,7 @@ snake->pop_front(); vertexIterator = snake->begin(); } else { - vertexIterator = snake->erase_after(lastVertex); + vertexIterator = snake->erase(enblend::next(lastVertex)); } bool needsBreak = false; @@ -175,8 +175,8 @@ snake->push_front(std::make_pair(true, vertexIterator->second)); lastVertex = snake->begin(); } else { - lastVertex = snake->insert_after(lastVertex, - std::make_pair(true, vertexIterator->second)); + lastVertex = snake->insert(enblend::next(lastVertex), + std::make_pair(true, vertexIterator->second)); } } @@ -306,9 +306,8 @@ for (std::vector<Point2D>::iterator shortPathPoint = shortPath->begin(); shortPathPoint != shortPath->end(); ++shortPathPoint) { - snake->insert_after(currentVertex, - std::make_pair(false, - *shortPathPoint + pointSurround.upperLeft())); + snake->insert(enblend::next(currentVertex), + std::make_pair(false, *shortPathPoint + pointSurround.upperLeft())); if (this->visualizeImage) { (*this->visualizeImage)[*shortPathPoint + pointSurround.upperLeft()] = |