stlab.adobe.com Adobe Systems Incorporated

forest_bitpath.hpp

Go to the documentation of this file.
00001 /*
00002     Copyright 2005-2007 Adobe Systems Incorporated
00003     Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
00004     or a copy at http://stlab.adobe.com/licenses.html)
00005 */
00006 
00007 /**************************************************************************************************/
00008 
00009 #ifndef ADOBE_FOREST_BITPATH_HPP
00010 #define ADOBE_FOREST_BITPATH_HPP
00011 
00012 /**************************************************************************************************/
00013 
00014 #include <adobe/config.hpp>
00015 
00016 #include <boost/dynamic_bitset.hpp>
00017 #include <boost/operators.hpp>
00018 
00019 #include <adobe/forest.hpp>
00020 #include <adobe/vector.hpp>
00021 
00022 /**************************************************************************************************/
00023 
00024 namespace adobe {
00025 
00026 /**************************************************************************************************/
00027 
00028 enum
00029 {
00030     bitpath_first_child = 0,
00031     bitpath_next_sibling = 1
00032 };
00033 
00034 /**************************************************************************************************/
00035 
00036 struct bitpath_t : boost::totally_ordered<bitpath_t>
00037 {
00038     typedef unsigned char                     value_type;
00039     typedef boost::dynamic_bitset<value_type> path_type;
00040     typedef path_type::size_type              size_type;
00041 
00042     bitpath_t() :
00043         path_m(size_type(1), path_type::block_type(1))
00044     { }
00045 
00046     template <typename ForestFullorderIterator>
00047     bitpath_t(ForestFullorderIterator node,
00048               ForestFullorderIterator root)
00049     {
00050         while (true)
00051         {
00052             node = --adobe::leading_of(node);
00053     
00054             if (node == root)
00055                 break;
00056     
00057             path_m.push_back(node.edge() == adobe::forest_trailing_edge);
00058         }
00059 
00060         path_m.push_back(true);
00061     }
00062 
00063     template <typename Container>
00064     explicit bitpath_t(const Container& x) :
00065         path_m(boost::begin(x), boost::end(x))
00066     {
00067         clip_zero_fill();
00068     }
00069 
00070     explicit bitpath_t(const path_type& path) :
00071         path_m(path)
00072     {
00073         clip_zero_fill();
00074     }
00075 
00076     bitpath_t(const bitpath_t& rhs) :
00077         path_m(rhs.path_m)
00078     { }
00079 
00080     bool empty() const
00081     { return path_m.empty(); }
00082     size_type size() const
00083     { return path_m.size(); }
00084 
00085     bool valid() const
00086     { return !empty() && path_m[path_m.size() - 1] == 1; }
00087 
00088     bool operator[](size_type n) const
00089     { return path_m[n]; }
00090 
00091     void push(bool value = bitpath_first_child)
00092     {
00093         path_m.resize(path_m.size() + 1);
00094     
00095         path_m <<= 1;
00096     
00097         path_m[0] = value;
00098     }
00099 
00100     bool pop()
00101     {
00102         bool result(path_m[0]);
00103 
00104         path_m >>= 1;
00105 
00106         path_m.resize(path_m.size() - 1);
00107 
00108         return result;
00109     }
00110 
00111     adobe::vector<value_type> portable() const
00112     {
00113         adobe::vector<value_type> result;
00114 
00115         result.reserve(path_m.size() / path_m.bits_per_block + 1);
00116 
00117         to_block_range(path_m, std::back_inserter(result));
00118 
00119         return result;
00120     }
00121 
00122     inline friend bool operator==(const bitpath_t& x, const bitpath_t& y)
00123     { return x.size() == y.size() && x.path_m == y.path_m; }
00124 
00125     inline friend bool operator<(const bitpath_t& x, const bitpath_t& y)
00126     {
00127         bitpath_t::size_type xs(x.size());
00128         bitpath_t::size_type ys(y.size());
00129 
00130         // dynamic_bitset asserts if xs != ys
00131 
00132         return xs < ys || (xs == ys && x.path_m < y.path_m);
00133     }
00134 
00135     inline friend std::ostream& operator<<(std::ostream& s, const bitpath_t& x)
00136     { return s << x.path_m; }
00137 
00138 private:
00139     void clip_zero_fill()
00140     {
00141         // bitpaths must always start with a 1, so we
00142         // need to clip the zero-fill from the import.
00143 
00144         size_type orig(path_m.size());
00145         size_type size(orig);
00146     
00147         while (--size)
00148             if (path_m[size])
00149                 break;
00150 
00151         if (orig != ++size)
00152             path_m.resize(size);
00153     }
00154 
00155     path_type path_m;
00156 };
00157 
00158 /**************************************************************************************************/
00159 
00160 inline static const adobe::bitpath_t& nbitpath()
00161 {
00162     static adobe::bitpath_t bitpath_s;
00163 
00164     while (bitpath_s.valid())
00165         bitpath_s.pop();
00166 
00167     return bitpath_s;
00168 }
00169 
00170 /**************************************************************************************************/
00179 inline bool passes_through(const bitpath_t& path, const bitpath_t& candidate)
00180 {
00181     if (!path.valid() || !candidate.valid())
00182         return false;
00183 
00184     bitpath_t::size_type path_size(path.size());
00185     bitpath_t::size_type candidate_size(candidate.size());
00186 
00187     if (path_size < candidate_size)
00188         return false;
00189     else if (path_size == candidate_size)
00190         return path == candidate;
00191 
00192     bitpath_t::size_type offset(path_size - candidate_size);
00193 
00194     while (candidate_size != 0)
00195         if (path[offset + --candidate_size] != candidate[candidate_size])
00196             return false;
00197 
00198     return true;
00199 }
00200 
00201 /**************************************************************************************************/
00202 
00203 template <typename Forest>
00204 typename Forest::iterator traverse(const bitpath_t& path, Forest& f)
00205 {
00206     if (path.empty() || f.empty())
00207         return f.end();
00208 
00209     int                       highest_bit(path.size() - 1);
00210     typename Forest::iterator result(f.begin());
00211 
00212     while (highest_bit-- && result.edge() == forest_leading_edge)
00213     {
00214         // Traversing the forest this way will always leave the
00215         // forest iterator on the leading edge. Should a pivot
00216         // take place it means the node specified by the bitpath
00217         // does not exist in the forest, so we return the closest
00218         // we can get to a successful traversal.
00219 
00220         if (path[highest_bit]) // follow next sibling
00221             result = ++trailing_of(result);
00222         else // follow first child
00223             result = ++leading_of(result);
00224     }
00225 
00226     return result;
00227 }
00228 
00229 /**************************************************************************************************/
00230 
00231 template <typename Forest>
00232 typename Forest::const_iterator traverse(const bitpath_t& path, const Forest& f)
00233 {
00234     return traverse(path, const_cast<Forest&>(f));
00235 }
00236 
00237 /**************************************************************************************************/
00238 
00239 inline bitpath_t parent_of(const bitpath_t& src)
00240 {
00241     bitpath_t result(src);
00242 
00243     while (true)
00244         if (!result.pop() || result.empty())
00245             break;
00246 
00247     return result;
00248 }
00249 
00250 /**************************************************************************************************/
00251 
00252 inline bitpath_t prior_sibling_of(const bitpath_t& src)
00253 {
00254     bitpath_t result(src);
00255 
00256     while (true)
00257         if (result.pop() || result.empty())
00258             break;
00259 
00260     return result;
00261 }
00262 
00263 /**************************************************************************************************/
00264 
00265 inline bitpath_t first_child_of(const bitpath_t& src)
00266 {
00267     bitpath_t result(src);
00268 
00269     result.push();
00270 
00271     return result;
00272 }
00273 
00274 /**************************************************************************************************/
00275 
00276 inline bitpath_t next_sibling_of(const bitpath_t& src)
00277 {
00278     bitpath_t result(src);
00279 
00280     result.push(true);
00281 
00282     return result;
00283 }
00284 
00285 /**************************************************************************************************/
00286 
00287 } // namespace adobe
00288 
00289 /**************************************************************************************************/
00290 
00291 #endif
00292 
00293 /**************************************************************************************************/

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google