OKlibrary  0.2.1.6
AssociativeContainers.hpp
Go to the documentation of this file.
00001 // Matthew Henderson, 4.9.2005 (Swansea)
00002 /* Copyright 2005 - 2007, 2008 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00013 #ifndef ASSOCIATIVECONTAINERS_09646l
00014 #define ASSOCIATIVECONTAINERS_09646l
00015 
00016 #include <string>
00017 #include <set>
00018 #include <functional>
00019 #include <algorithm>
00020 #include <utility>
00021 
00022 #include <boost/range/functions.hpp>
00023 #include <boost/utility.hpp>
00024 
00025 namespace OKlib {
00026   namespace SearchDataStructures {
00027 
00028     // ##############################################################
00029 
00042     template <class Range>
00043     class AssociativePrefixContainer {
00044 
00049       struct SortLexicographical : std::binary_function<const Range&, const Range&, bool> {
00050   bool operator()(const Range& arg1, const Range& arg2) const {
00051     return std::lexicographical_compare(boost::begin(arg1), boost::end(arg1), boost::begin(arg2), boost::end(arg2));
00052 }
00053       };
00054       
00055       typedef typename std::set<Range, SortLexicographical> SetRanges;
00056     
00057       SetRanges prefix_set; // range_type ???????????????????
00058 
00059       template <class Range2>
00060       void prefix_set_assign(const Range2& range) {
00061         prefix_set.clear();
00062         prefix_set.insert(boost::begin(range), boost::end(range));
00063       }
00064 
00065     public:
00066 
00067       typedef Range prefix_type;
00068       typedef typename SetRanges::const_iterator iterator;
00069       typedef iterator const_iterator;
00070       typedef std::pair<iterator,bool> checked_iterator_type;
00071       typedef typename SetRanges::size_type size_type;
00072 
00073       AssociativePrefixContainer() {};
00074 
00075       template <class Range2>
00076       AssociativePrefixContainer(const Range2& range) {
00077         prefix_set_assign(range);
00078       }
00079 
00080       template <class Range2>
00081       void assign(const Range2& range) {
00082         prefix_set_assign(range);
00083       }
00084       
00085       iterator begin() const {
00086   return prefix_set.begin();
00087       }
00088       iterator end() const {
00089   return prefix_set.end();
00090       }
00091 
00092       size_type size() const {
00093         return prefix_set.size();
00094       }
00095 
00096       std::pair<iterator,bool> insert(const Range& x) {
00097   return prefix_set.insert(x);
00098       }
00099 
00100       iterator first_extension(const Range& r) const {
00101         const iterator& lower_bound(prefix_set.lower_bound(r));
00102         const iterator& end(prefix_set.end());
00103         if (lower_bound == end)
00104           return end;
00105         if (boost::distance(r) > boost::distance(*lower_bound))
00106           return end;
00107         if (std::equal(boost::begin(r), boost::end(r), boost::begin(*lower_bound)))
00108           return lower_bound;
00109         else
00110           return end;
00111       }
00112 
00113        checked_iterator_type first_extension_uniqueness_checked(const Range& r) const {
00114        const iterator& first(first_extension(r));
00115        const iterator& end(prefix_set.end());
00116         if (first == end)
00117           return checked_iterator_type(first, true);
00118         const iterator& next(boost::next(first));
00119         if (next == end)
00120           return checked_iterator_type(first, true);
00121         if (boost::distance(r) > boost::distance(*next))
00122           return checked_iterator_type(first, true);
00123         if (std::equal(boost::begin(r), boost::end(r), boost::begin(*next)))
00124           return checked_iterator_type(first, false);
00125         else
00126           return checked_iterator_type(first, true);
00127       }
00128     };
00129 
00130     // ##############################################################
00131 
00132   }
00133 }
00134 
00135 #endif