randomaccessset.hxx

Go to the documentation of this file.

#pragma once
#ifndef OPENGM_RANDOM_ACCESS_SET_HXX
#define OPENGM_RANDOM_ACCESS_SET_HXX

#include <vector>
#include <algorithm>
#include <utility>

namespace opengm {
   
template<class Key,class Compare=std::less<Key>,class Alloc=std::allocator<Key> >
class RandomAccessSet {
private:
   typedef std::vector<Key,Alloc> VectorType;

public:
   // typedefs
   typedef Key key_type;
   typedef Key ValueType;
   typedef Key value_type;
   typedef Compare key_compare;
   typedef Compare value_compare;
   typedef Alloc  allocator_type;
   typedef typename Alloc::const_reference const_reference;
   typedef typename VectorType::iterator iterator;
   typedef typename VectorType::const_iterator const_iterator;
   typedef typename VectorType::size_type size_type;
   typedef typename VectorType::difference_type difference_type;
   typedef typename VectorType::const_pointer const_pointer;
   typedef typename VectorType::const_reverse_iterator   const_reverse_iterator;

   // memeber functions:
   // constructor
   RandomAccessSet(const size_t, const Compare& compare=Compare(), const Alloc& alloc=Alloc());
   RandomAccessSet(const Compare& compare=Compare(), const Alloc& alloc=Alloc());
   template <class InputIterator>
      RandomAccessSet(InputIterator, InputIterator, const Compare& compare =Compare(), const Alloc & alloc=Alloc());
   RandomAccessSet(const RandomAccessSet&);

   // operator=
   RandomAccessSet& operator=(const RandomAccessSet &);
   // operator[]
   const value_type& operator[](const size_type) const;
   // iterators
   const_iterator begin() const;
   const_iterator end() const;
   const_iterator rbegin() const;
   const_iterator rend() const;

   iterator begin();
   iterator end();
   iterator rbegin();
   iterator rend();
   bool empty() const;
   size_type size() const;
   size_type max_size() const;
   std::pair< const_iterator,bool> insert(const value_type&);
   template <class InputIterator>
      void insert(InputIterator, InputIterator);
   const_iterator insert(const_iterator , const value_type&);
   void erase(iterator position);
   size_type erase(const key_type& );
   void erase( const_iterator, const_iterator);
   void swap(RandomAccessSet&);
   void clear();
   key_compare key_comp() const;
   value_compare value_comp() const;
   const_iterator find(const key_type&) const;
   iterator find(const key_type&);
   size_type count(const key_type&) const;
   const_iterator lower_bound(const key_type&) const;
   const_iterator upper_bound(const key_type&) const;
   std::pair<const_iterator,const_iterator> equal_range(const key_type&) const;
   iterator lower_bound(const key_type&) ;
   iterator upper_bound(const key_type&) ;
   std::pair<iterator,iterator> equal_range(const key_type&) ;
   allocator_type get_allocator() const;

   // std vector functions
   void reserve(const size_t size){
       vector_.reserve(size);
   }
   size_t capacity()const{
       return vector_.capacity();
   }
   
   template<class SET>
   void assignFromSet(const SET & set){
      vector_.assign(set.begin(),set.end());
   }

private:
   std::vector<Key> vector_;
   Compare compare_;
};

template<class Key, class Compare, class Alloc>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   const size_t reserveSize,
   const Compare& compare,
   const Alloc& alloc
)
:  vector_(alloc),
   compare_(compare) {
   vector_.reserve(reserveSize);
}

template<class Key, class Compare, class Alloc>
inline const typename RandomAccessSet<Key,Compare,Alloc>::value_type&
RandomAccessSet<Key,Compare,Alloc>::operator[]
(
   const typename RandomAccessSet<Key,Compare,Alloc>::size_type  index
) const
{
   return vector_[index];
}

template<class Key, class Compare, class Alloc>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   const Compare& compare,
   const Alloc& alloc
)
:  vector_(alloc),
   compare_(compare)
{}

template<class Key, class Compare, class Alloc>
template <class InputIterator>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   InputIterator beginInput,
   InputIterator endInput,
   const Compare& compare,
   const Alloc& alloc
)
:  vector_(alloc),
   compare_(compare)
{
   while(beginInput!=endInput) {
      this->insert(*beginInput);
      ++beginInput;
   }
}

template<class Key, class Compare, class Alloc>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   const RandomAccessSet<Key,Compare,Alloc>& src
)
:  vector_(src.vector_),
   compare_(src.compare_) {
}

template<class Key, class Compare, class Alloc>
inline RandomAccessSet<Key,Compare,Alloc>&
RandomAccessSet<Key,Compare,Alloc>::operator=
(
   const RandomAccessSet<Key,Compare,Alloc> & src
)
{
    if(this!=&src) {
      vector_=src.vector_;
      compare_=src.compare_;
   }
   return *this;
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::begin() const
{
   return vector_.begin();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::end() const
{
    return vector_.end();
}
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::rbegin() const
{
   return vector_.rbegin();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::rend() const
{
    return vector_.rend();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::begin()
{
   return vector_.begin();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::end()
{
    return vector_.end();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::rbegin()
{
   return vector_.rbegin();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::rend()
{
    return vector_.rend();
}

template<class Key, class Compare, class Alloc>
inline bool
RandomAccessSet<Key,Compare,Alloc>::empty() const
{
   return vector_.empty();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::size() const
{
   return vector_.size();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::max_size() const
{
   return vector_.max_size();
}

// modifiers
template<class Key, class Compare, class Alloc>
inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,bool>
RandomAccessSet<Key,Compare,Alloc>::insert
(
   const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
) {
   bool found(true);
   iterator i(lower_bound(static_cast<Key>(value)));
   if(i == end() || compare_(static_cast<Key>(value), *i)) {
      i = vector_.insert(i, static_cast<Key>(value));
      found = false;
   }
   return std::make_pair(i, !found);
}

template<class Key, class Compare, class Alloc>
template <class InputIterator>
inline void
RandomAccessSet<Key,Compare,Alloc>::insert
(
   InputIterator first,
   InputIterator last
)
{
   while(first!=last) {
      this->insert(*first);
      ++first;
   }
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::insert
(
   typename RandomAccessSet<Key,Compare,Alloc>::const_iterator position,
   const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
)
{
   if((position == begin() || this->operator()(*(position-1),value))
   && (position == end() || this->operator()(value, *position))) {
       return vector_.insert(position, value);
   }
   return insert(value).first;
}

template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::erase
(
   typename RandomAccessSet<Key,Compare,Alloc>::iterator position
)
{
   vector_.erase(position);
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::erase
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& x
)
{
   iterator i =find(x);
   if(i!=vector_.end())
   {
      erase(i);
      return 1;
   }
   return 0;
}

template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::erase
(
   const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator first,
   const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator last
)
{
   vector_.erase(first,last);
}

template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::swap
(
   RandomAccessSet<Key,Compare,Alloc>& rhs
)
{
   vector_.swap(rhs.vector_);
   compare_=rhs.compare_;
}

template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::clear()
{
   vector_.clear();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::key_compare
RandomAccessSet<Key,Compare,Alloc>::key_comp() const
{
   return compare_;
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::value_compare
RandomAccessSet<Key,Compare,Alloc>::value_comp() const
{
   return compare_;
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::find
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   const_iterator i(lower_bound(value));
   if (i != end() && compare_(value, *i))
   {
       i = end();
   }
   return i;
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::find
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   iterator i(lower_bound(value));
   if (i != end() && compare_(value, *i))
   {
       i = end();
   }
   return i;
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::count
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type&  value
) const
{
   return find(value) != end();
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::lower_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::lower_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::upper_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
}

template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::upper_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
}

template<class Key, class Compare, class Alloc>
inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,typename RandomAccessSet<Key,Compare,Alloc>::const_iterator>
RandomAccessSet<Key,Compare,Alloc>::equal_range
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
}

template<class Key, class Compare, class Alloc>
inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::iterator,typename RandomAccessSet<Key,Compare,Alloc>::iterator>
RandomAccessSet<Key,Compare,Alloc>::equal_range
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
}
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::allocator_type
RandomAccessSet<Key,Compare,Alloc>::get_allocator() const
{
   return vector_.get_allocator();
}

} // namespace opengm

#endif // OPENGM_RANDOM_ACCESS_SET_HXX