table_index.hpp

Go to the documentation of this file.

/*
    Copyright 2013 Adobe
    Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
*/
/**************************************************************************************************/
 
#ifndef ADOBE_TABLE_INDEX_HPP
#define ADOBE_TABLE_INDEX_HPP
 
/**************************************************************************************************/
 
#include <adobe/config.hpp>
 
#include <functional>
#include <stdexcept>
#include <vector>
 
#include <boost/iterator/indirect_iterator.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/next_prior.hpp>
#include <boost/operators.hpp>
 
#include <adobe/algorithm/count.hpp>
#include <adobe/algorithm/equal_range.hpp>
#include <adobe/algorithm/lower_bound.hpp>
#include <adobe/algorithm/sort.hpp>
#include <adobe/algorithm/unique.hpp>
#include <adobe/algorithm/upper_bound.hpp>
 
#include <adobe/closed_hash.hpp>
#include <adobe/functional.hpp>
 
/**************************************************************************************************/
 
namespace adobe {
 
/**************************************************************************************************/


























































 
 
template <typename T,                    // models Regular
          typename H = std::hash<T>,     // models UnaryFunction key_type -> size_t
          typename C = std::equal_to<T>, // models EqualityComparison(key_type, key_type)
          typename P = identity<T>>      // models UnaryFunction T -> key_type
class hash_index {
public:
    typedef T value_type;
    typedef P key_function_type;
 
    using key_type = std::remove_reference_t<adobe::invoke_result_t<P, T>>;
 
    typedef H hasher;
    typedef C key_equal;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
 
    typedef unary_compose<key_function_type, indirect<value_type>> indirect_key_function_type;
 
    typedef closed_hash_set<pointer, indirect_key_function_type, hasher, key_equal> index_type;
 
    typedef boost::indirect_iterator<typename index_type::iterator> iterator;
    typedef boost::indirect_iterator<typename index_type::const_iterator> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
    /*
        REVISIT (sparent@adobe.com) : This is a very limited set of constructors - need to have a
        general strategy for which constructors to provide.
    */
 
 
    hash_index() {}
 
    /*
        NOTE: The constructor is templatized so things like mem_fun are not necessary.
    */
 
    template <typename F> // F is convertible to key_function_type
    hash_index(hasher hf, key_equal eq, F kf)
        : index_m(0, hf, eq, compose(key_function_type(kf), indirect<value_type>())) {}
 
    // allocator_type get_allocator() const;
    size_type max_size() const { return index_m.max_size(); }
 
    size_type size() const { return index_m.size(); }
    bool empty() const { return index_m.empty(); }
    size_type capacity() const { return index_m.capacity(); }
 
    void reserve(size_type) { index_m.reserve(); }
 
    iterator begin() { return iterator(index_m.begin()); }
    iterator end() { return iterator(index_m.end()); }
 
    const_iterator begin() const { return const_iterator(index_m.begin()); }
    const_iterator end() const { return const_iterator(index_m.end()); }
 
    reverse_iterator rbegin() { return reverse_iterator(index_m.rbegin()); }
    reverse_iterator rend() { return reverse_iterator(index_m.rend()); }
 
    const_reverse_iterator rbegin() const { return const_reverse_iterator(index_m.rbegin()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(index_m.rend()); }
 
    std::pair<iterator, bool> insert(value_type& x) {
        std::pair<typename index_type::iterator, bool> result = index_m.insert(&x);
        return std::make_pair(iterator(result.first), result.second);
    }
 
    template <typename I>
    void insert(I f, I l) {
        index_m.insert(boost::make_transform_iterator(f, pointer_to<value_type>()),
                       boost::make_transform_iterator(l, pointer_to<value_type>()));
    }
 
    iterator insert(iterator i, value_type& x) { return iterator(index_m.insert(i, &x)); }
 
    iterator erase(iterator i) { return index_m.erase(i.base()); }
    size_type erase(const key_type& x) { return index_m.erase(x); }
 
    void clear() { index_m.clear(); }
 
    index_type& index() { return index_m; }
    const index_type& index() const { return index_m; }
 
    iterator find(const key_type& x) { return iterator(index_m.find(x)); }
    const_iterator find(const key_type& x) const { return const_iterator(index_m.find(x)); }
    size_type count(const key_type& x) const { return index_m.count(x); }
 
    iterator lower_bound(const key_type&) { return iterator(index_m.lower_bound()); }
    const_iterator lower_bound(const key_type&) const {
        return const_iterator(index_m.lower_bound());
    }
    iterator upper_bound(const key_type&) { return iterator(index_m.upper_bound()); }
    const_iterator upper_bound(const key_type&) const {
        return const_iterator(index_m.upper_bound());
    }
 
    std::pair<iterator, iterator> equal_range(const key_type& x) {
        std::pair<typename index_type::iterator, typename index_type::iterator> result =
            index_m.equal_range(x);
        return std::make_pair(iterator(result.first), iterator(result.second));
    }
    std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const {
        std::pair<typename index_type::const_iterator, typename index_type::const_iterator> result =
            index_m.equal_range(x);
 
        return std::make_pair(const_iterator(result.first), const_iterator(result.second));
    }
 
    key_function_type key_function() const { return index_m.key_function(); }
    hasher hash_function() const { return index_m.hash_function(); }
    key_equal key_eq() const { return index_m.key_eq(); }
 
    friend void swap(hash_index& x, hash_index& y) { swap(x.index_m, y.index_m); }
 
private:
    index_type index_m;
};
 
/**************************************************************************************************/
 
template <typename Key,                                  // models Regular
          typename T,                                    // models Regular
          typename Transform = mem_data_t<T, const Key>, // models UnaryFunction Key(T)
          typename Compare = std::less<Key>              // models BinaryFunction bool(Key, Key)
          >
class table_index {
 
public:
    typedef typename std::vector<T*> index_type;
    typedef Transform transform_type;
 
    typedef Key key_type;
    typedef T value_type;
    typedef Compare key_compare; // Revisit?
    //  typedef Allocator                               allocator_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef typename index_type::size_type size_type;
    typedef typename index_type::difference_type difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
 
    typedef boost::indirect_iterator<typename index_type::iterator> iterator;
    typedef boost::indirect_iterator<typename index_type::const_iterator> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
    template <class TransformPrimitive>
    explicit table_index(TransformPrimitive transform, const key_compare& compare = key_compare())
        : transform_m(transform), compare_m(compare) {}
    explicit table_index(const transform_type&, const key_compare& = key_compare());

    template <typename InputIterator, typename TransformPrimitive>
    table_index(InputIterator first, InputIterator last, TransformPrimitive transform,
                const key_compare& compare = key_compare())
        : transform_m(transform), compare_m(compare) {
        insert(begin(), first, last);
    }
 
    // allocator_type get_allocator() const;
    size_type max_size() const;
 
    size_type size() const;
    bool empty() const;
 
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
 
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;
 
    const_reference at(size_type n) const;
    reference at(size_type n);
 
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;
 
    void push_back(value_type&);
    void pop_back();
 
    iterator insert(iterator, value_type&);
    template <class InputIterator>
    void insert(iterator position, InputIterator first, InputIterator last);
 
    iterator erase(iterator location);
    iterator erase(iterator first, iterator last);
    void clear();
 
    index_type& index();
    const index_type& index() const;
 
    /*
        REVISIT (sparent) : If we wanted to allow sort() and unique() - and other algoriths to
        operate directly on the index rather than being built in, what would be required of the
        index interface?
    */
 
    void sort();
 
    // Operations on a sorted index.
 
    void unique();
 
    reference operator[](const key_type&);
    const_reference operator[](const key_type&) const;
 
    iterator find(const key_type& x);
    const_iterator find(const key_type& x) const;
    size_type count(const key_type& x) const;
 
    iterator lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
    iterator upper_bound(const key_type& x);
    const_iterator upper_bound(const key_type& x) const;
 
    std::pair<iterator, iterator> equal_range(const key_type& x);
    std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
 
    transform_type transform() const { return transform_m; }
 
    friend void swap(table_index& x, table_index& y) {
        swap(x.transform_m, y.transform_m);
        swap(x.compare_m, y.compare_m);
        swap(x.index_m, y.index_m);
    }
 
private:
#ifndef ADOBE_NO_DOCUMENTATION
    struct indirect_compare_t {
        typedef bool result_type;
 
        indirect_compare_t(transform_type& transform, const key_compare& compare)
            : transform_m(transform), compare_m(compare) {}
 
        bool operator()(pointer x, pointer y) const {
            return compare_m(transform_m(*x), transform_m(*y));
        }
 
    private:
        transform_type transform_m; /* REVISIT (sparent) : want reference here? */
        key_compare compare_m;
    };
 
#endif
 
    transform_type transform_m;
    key_compare compare_m;
    index_type index_m;
};
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
table_index<Key, T, Compare, Transform>::table_index(const transform_type& transform,
                                                     const key_compare& compare)
    : transform_m(transform), compare_m(compare) {}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::begin() {
    return iterator(index_m.begin());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_iterator
table_index<Key, T, Compare, Transform>::begin() const {
    return const_iterator(index_m.begin());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::end() {
    return iterator(index_m.end());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_iterator
table_index<Key, T, Compare, Transform>::end() const {
    return const_iterator(index_m.end());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::reverse_iterator
table_index<Key, T, Compare, Transform>::rbegin() {
    return reverse_iterator(index_m.rbegin());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_reverse_iterator
table_index<Key, T, Compare, Transform>::rbegin() const {
    return const_reverse_iterator(index_m.rbegin());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::reverse_iterator
table_index<Key, T, Compare, Transform>::rend() {
    return reverse_iterator(index_m.rend());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_reverse_iterator
table_index<Key, T, Compare, Transform>::rend() const {
    return reverse_iterator(index_m.rend());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::size_type
table_index<Key, T, Compare, Transform>::max_size() const {
    return index_m.max_size();
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::size_type
table_index<Key, T, Compare, Transform>::size() const {
    return index_m.size();
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline bool table_index<Key, T, Compare, Transform>::empty() const {
    return index_m.empty();
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline void table_index<Key, T, Compare, Transform>::push_back(value_type& x) {
    index_m.push_back(&x);
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline void table_index<Key, T, Compare, Transform>::pop_back() {
    index_m.pop_back();
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::insert(iterator position, value_type& x) {
    return index_m.insert(position, &x);
}
 
/**************************************************************************************************/
 
/*
    REVISIT (sparent) : We should be able to greatly improve the table_index class - this function
    in particular could be much more efficient.
*/
 
template <class Key, class T, class Compare, class Transform>
template <class InputIterator>
inline void table_index<Key, T, Compare, Transform>::insert(iterator position, InputIterator first,
                                                            InputIterator last) {
    typename index_type::iterator iter = position.base();
 
    while (first != last) {
        iter = index_m.insert(iter, &*first);
        ++iter;
        ++first;
    }
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::erase(iterator position) {
    return index_m.erase(position.base());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::erase(iterator first, iterator last) {
    return index_m.erase(first.base(), last.base());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline void table_index<Key, T, Compare, Transform>::clear() {
    index_m.clear();
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
void table_index<Key, T, Compare, Transform>::sort() {
    adobe::sort(index_m, indirect_compare_t(transform_m, compare_m));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
void table_index<Key, T, Compare, Transform>::unique() {
    typename index_type::iterator i(
        adobe::unique(index_m, indirect_compare_t(transform_m, compare_m)));
    index_m.erase(i, index_m.end());
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::reference
table_index<Key, T, Compare, Transform>::at(const size_type n) {
    return *index_m.at(n);
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_reference
table_index<Key, T, Compare, Transform>::at(const size_type n) const {
    return *index_m.at(n);
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::reference
table_index<Key, T, Compare, Transform>::operator[](const key_type& key) {
    iterator iter(find(key));
 
    if (iter == end())
        throw std::range_error("Key not present in table.");
 
    return *iter;
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_reference
table_index<Key, T, Compare, Transform>::operator[](const key_type& key) const {
    const_iterator iter(find(key));
 
    if (iter == end())
        throw std::range_error("Key not present in table.");
 
    return *iter;
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::find(const key_type& key) {
    typename index_type::iterator iter = lower_bound(key).base();
 
    if (iter != index_m.end() && transform_m(**iter) != key)
        iter = index_m.end();
 
    return iter;
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_iterator
table_index<Key, T, Compare, Transform>::find(const key_type& key) const {
    typename index_type::const_iterator iter = lower_bound(key).base();
 
    if (iter != index_m.end() && transform_m(**iter) != key)
        iter = index_m.end();
 
    return iter;
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::size_type
table_index<Key, T, Compare, Transform>::count(const key_type& key) const {
    return adobe::count_if(index_m, bound_predicate_t(key, transform_m, compare_m));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::lower_bound(const key_type& key) {
    return adobe::lower_bound(
        index_m, key, compare_m,
        std::bind(transform_m, bind(indirect<value_type>(), std::placeholders::_1)));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_iterator
table_index<Key, T, Compare, Transform>::lower_bound(const key_type& key) const {
    return adobe::lower_bound(
        index_m, key, compare_m,
        std::bind(transform_m, bind(indirect<value_type>(), std::placeholders::_1)));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::iterator
table_index<Key, T, Compare, Transform>::upper_bound(const key_type& key) {
    return adobe::upper_bound(
        index_m, key, compare_m,
        std::bind(transform_m, bind(indirect<value_type>(), std::placeholders::_1)));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::const_iterator
table_index<Key, T, Compare, Transform>::upper_bound(const key_type& key) const {
    return adobe::upper_bound(
        index_m, key, compare_m,
        std::bind(transform_m, bind(indirect<value_type>(), std::placeholders::_1)));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline std::pair<typename table_index<Key, T, Compare, Transform>::iterator,
                 typename table_index<Key, T, Compare, Transform>::iterator>
table_index<Key, T, Compare, Transform>::equal_range(const key_type& key) {
    return adobe::equal_range(
        index_m, key, compare_m,
        std::bind(transform_m, bind(indirect<value_type>(), std::placeholders::_1)));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline std::pair<typename table_index<Key, T, Compare, Transform>::const_iterator,
                 typename table_index<Key, T, Compare, Transform>::const_iterator>
table_index<Key, T, Compare, Transform>::equal_range(const key_type& key) const {
    return adobe::equal_range(
        index_m, key, compare_m,
        std::bind(transform_m, bind(indirect<value_type>(), std::placeholders::_1)));
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline typename table_index<Key, T, Compare, Transform>::index_type&
table_index<Key, T, Compare, Transform>::index() {
    return index_m;
}
 
/**************************************************************************************************/
 
template <class Key, class T, class Compare, class Transform>
inline const typename table_index<Key, T, Compare, Transform>::index_type&
table_index<Key, T, Compare, Transform>::index() const {
    return index_m;
}
 
/**************************************************************************************************/
 
} // namespace adobe
 
/**************************************************************************************************/
 
#endif
 
/**************************************************************************************************/