utilidor.h

Go to the documentation of this file.

// File: $Id$
// Author: John Wu <John.Wu at ACM.org>
// Copyright 2008-2012 the Regents of the University of California
#ifndef IBIS_UTILIDOR_H
#define IBIS_UTILIDOR_H

#include <algorithm>
#include "array_t.h"    // array_t

namespace ibis {
    typedef array_t< rid_t > RIDSet;    // RIDSet

    namespace util {

        void FASTBIT_CXX_DLLSPEC sortRIDs(ibis::RIDSet&);
        void FASTBIT_CXX_DLLSPEC sortRIDsq(ibis::RIDSet&, uint32_t, uint32_t);
        void FASTBIT_CXX_DLLSPEC sortRIDsi(ibis::RIDSet&, uint32_t, uint32_t);

        template <typename T>
        void FASTBIT_CXX_DLLSPEC
        reorder(array_t<T> &arr, const array_t<uint32_t> &ind);
        void FASTBIT_CXX_DLLSPEC
        reorder(std::vector<std::string> &arr, const array_t<uint32_t> &ind);
        template <typename T>
        void FASTBIT_CXX_DLLSPEC
        reorder(array_t<T*> &arr, const array_t<uint32_t> &ind);
        template <typename T1, typename T2>
        void FASTBIT_CXX_DLLSPEC
        sortAll(array_t<T1>& arr1, array_t<T2>& arr2);

        int64_t FASTBIT_CXX_DLLSPEC
        sortMerge(std::vector<std::string>& valR, array_t<uint32_t>& indR,
                  std::vector<std::string>& valS, array_t<uint32_t>& indS);
        template <typename T> int64_t FASTBIT_CXX_DLLSPEC
        sortMerge(array_t<T>& valR, array_t<uint32_t>& indR,
                  array_t<T>& valS, array_t<uint32_t>& indS);
        template <typename T> int64_t FASTBIT_CXX_DLLSPEC
        sortMerge(array_t<T>& valR, array_t<uint32_t>& indR,
                  array_t<T>& valS, array_t<uint32_t>& indS,
                  double delta1, double delta2);

        template <typename T1, typename T2>
        void FASTBIT_CXX_DLLSPEC
        sortKeys(array_t<T1>& keys, array_t<T2>& vals);
        void FASTBIT_CXX_DLLSPEC
        sortStrings(std::vector<std::string>& keys, array_t<uint32_t>& vals);
        void FASTBIT_CXX_DLLSPEC
        sortStrings(array_t<const char*>& keys, array_t<uint32_t>& vals);

        template <typename T, class C>
        struct heap {
            std::vector<T*> data_;
            const C comp_;

            heap<T, C>() : data_(), comp_() {}

            bool empty() const {return data_.empty();}

            size_t size() const {return data_.size();}

            void reserve(size_t n) {data_.reserve(n);}

            T* top() const {return data_[0];}

            void push(T* v) {
                data_.push_back(v);
                std::push_heap(data_.begin(), data_.end(), comp_);
            }

            void pop() {
                const size_t oldsize = data_.size();
                std::pop_heap(data_.begin(), data_.end(), comp_);
                data_.resize(oldsize-1);
            }
        }; // minheap
    } // namespace util
} // namespace ibis
#endif