permlib
0.2.6
Library for permutation computations
|
00001 // --------------------------------------------------------------------------- 00002 // 00003 // This file is part of PermLib. 00004 // 00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de> 00006 // All rights reserved. 00007 // 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions 00010 // are met: 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 2. Redistributions in binary form must reproduce the above copyright 00014 // notice, this list of conditions and the following disclaimer in the 00015 // documentation and/or other materials provided with the distribution. 00016 // 3. The name of the author may not be used to endorse or promote products 00017 // derived from this software without specific prior written permission. 00018 // 00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 // 00030 // --------------------------------------------------------------------------- 00031 00032 00033 #ifndef BASESORTER_H 00034 #define BASESORTER_H 00035 00036 #include <boost/utility.hpp> 00037 00038 namespace permlib { 00039 00041 template<class ORDER> 00042 class OrderedSorter : public std::binary_function<unsigned long, unsigned long, bool> { 00043 public: 00045 bool operator() (unsigned long a, unsigned long b) const { 00046 BOOST_ASSERT(a < m_size && b < m_size); 00047 return m_order[a] < m_order[b]; 00048 } 00049 protected: 00051 00054 explicit OrderedSorter(unsigned int size) 00055 : m_size(size), 00056 // initialize m_size elements with value m_size 00057 m_order(m_size, m_size) 00058 {} 00059 00061 explicit OrderedSorter(ORDER order) 00062 : m_size(order.size()), m_order(order) 00063 {} 00064 00066 unsigned int m_size; 00068 ORDER m_order; 00069 }; 00070 00072 00076 class BaseSorter : public OrderedSorter<std::vector<unsigned long> > { 00077 public: 00079 00084 template <class InputIterator> 00085 BaseSorter(unsigned int size, InputIterator begin, InputIterator end) 00086 : OrderedSorter<std::vector<unsigned long> >(size) 00087 { 00088 fillOrder(begin, end, m_order); 00089 } 00090 00092 00097 template <class InputIterator> 00098 static void fillOrder(InputIterator begin, InputIterator end, std::vector<unsigned long>& order) { 00099 InputIterator it; 00100 unsigned int i = 0; 00101 // base elements first 00102 for (it = begin; it != end; ++it) { 00103 order[*it] = ++i; 00104 } 00105 } 00106 }; 00107 00108 00110 00113 class BaseSorterByReference : public OrderedSorter<const std::vector<unsigned long>&> { 00114 public: 00116 explicit BaseSorterByReference(const std::vector<unsigned long>& order) : OrderedSorter<const std::vector<unsigned long>& >(order) 00117 { } 00118 00120 template <class InputIterator> 00121 static std::vector<unsigned long> createOrder(unsigned int size, InputIterator begin, InputIterator end) { 00122 std::vector<unsigned long> order(size,size); 00123 BaseSorter::fillOrder(begin, end, order); 00124 return order; 00125 } 00126 }; 00127 00128 } 00129 00130 #endif // -- BASESORTER_H