SDSL: Succinct Data Structure Library: sdsl/include/sdsl/rmq

Go to the documentation of this file.
00001 /* sdsl - succinct data structures library
00002     Copyright (C) 2009 Simon Gog
00003 
00004     This program is free software: you can redistribute it and/or modify
00005     it under the terms of the GNU General Public License as published by
00006     the Free Software Foundation, either version 3 of the License, or
00007     (at your option) any later version.
00008 
00009     This program is distributed in the hope that it will be useful,
00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012     GNU General Public License for more details.
00013 
00014     You should have received a copy of the GNU General Public License
00015     along with this program.  If not, see http://www.gnu.org/licenses/ .
00016 */
00021 #ifndef INCLUDED_SDSL_RMQ_SUPPORT
00022 #define INCLUDED_SDSL_RMQ_SUPPORT
00023 
00026 template<class RandomAccessContainer, bool Minimum>      // for range minimum queries
00027 struct min_max_trait {
00028     static inline bool strict_compare(const typename RandomAccessContainer::value_type v1, const typename RandomAccessContainer::value_type v2) {
00029         return v1 < v2;
00030     }
00031     static inline bool compare(const typename RandomAccessContainer::value_type v1, const typename RandomAccessContainer::value_type v2) {
00032         return v1 <= v2;
00033     }
00034 };
00035 
00036 template<class RandomAccessContainer> // for range maximum queries
00037 struct min_max_trait<RandomAccessContainer, false> {
00038     static inline bool strict_compare(const typename RandomAccessContainer::value_type v1, const typename RandomAccessContainer::value_type v2) {
00039         return v1 > v2;
00040     }
00041     static inline bool compare(const typename RandomAccessContainer::value_type v1, const typename RandomAccessContainer::value_type v2) {
00042         return v1 >= v2;
00043     }
00044 };
00045 
00046 #include "rmq_support_sparse_table.hpp"
00047 #include "rmq_succinct_sct.hpp"
00048 #include "rmq_succinct_sada.hpp"
00049 
00050 #endif