/*  Copyright (C) 2015  Povilas Kanapickas <povilas@radix.lt>

    This file is part of cppreference-doc

    This work is licensed under the Creative Commons Attribution-ShareAlike 3.0
    Unported License. To view a copy of this license, visit
    http://creativecommons.org/licenses/by-sa/3.0/ or send a letter to Creative
    Commons, 444 Castro Street, Suite 900, Mountain View, California, 94041, USA.

    Permission is granted to copy, distribute and/or modify this document
    under the terms of the GNU Free Documentation License, Version 1.3 or
    any later version published by the Free Software Foundation; with no
    Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
*/

#ifndef CPPREFERENCE_UNORDERED_SET_H
#define CPPREFERENCE_UNORDERED_SET_H

#if CPPREFERENCE_STDVER>= 2011
#include <initializer_list>

#include <cstddef> // for size_t, ptrdiff_t
#include <functional> // for hash
#include <memory> // for std::allocator
#include <utility> // for std::pair

namespace std {

template <
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
    > class unordered_set {
public:
    typedef Key key_type;
    typedef Key value_type;
    typedef size_t size_type; // actual type unspecified
    typedef ptrdiff_t difference_type; // actual type not specified
    typedef Hash hasher;
    typedef KeyEqual key_equal;
    typedef Allocator allocator_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
#if CPPREFERENCE_SIMPLIFY_TYPEDEFS
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
#else
    typedef typename std::allocator_traits<Allocator>::pointer pointer;
    typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
#endif
    typedef value_type* iterator; // actual type is unspecified
    typedef const value_type* const_iterator; // actual type is unspecified
    typedef value_type* local_iterator; // actual type is unspecified
    typedef const value_type* const_local_iterator; // actual type is unspecified

    // constructor
#if CPPREFERENCE_STDVER <2014
    explicit unordered_set(size_type bucket_count = 0 /*implementation-defined*/,
                           const Hash& hash = Hash(),
                           const KeyEqual& equal = KeyEqual(),
                           const Allocator& alloc = Allocator());
#else
    unordered_set();

    explicit unordered_set(size_type bucket_count,
                           const Hash& hash = Hash(),
                           const KeyEqual& equal = KeyEqual(),
                           const Allocator& alloc = Allocator());

    unordered_set(size_type bucket_count,
                  const Allocator& alloc);

    unordered_set(size_type bucket_count,
                  const Hash& hash,
                  const Allocator& alloc);
#endif

    explicit unordered_set(const Allocator& alloc);

    template<class InputIt>
    unordered_set(InputIt first, InputIt last,
                  size_type bucket_count = 0 /*implementation-defined*/,
                  const Hash& hash = Hash(),
                  const KeyEqual& equal = KeyEqual(),
                  const Allocator& alloc = Allocator());

#if CPPREFERENCE_STDVER>= 2014
    template<class InputIt>
    unordered_set(InputIt first, InputIt last,
                  size_type bucket_count,
                  const Allocator& alloc);

    template<class InputIt>
    unordered_set(InputIt first, InputIt last,
                  size_type bucket_count,
                  const Hash& hash,
                  const Allocator& alloc);
#endif

    unordered_set(const unordered_set& other);
    unordered_set(const unordered_set& other, const Allocator& alloc);
    unordered_set(unordered_set&& other);
    unordered_set(unordered_set&& other, const Allocator& alloc);

    unordered_set(std::initializer_list<value_type> init,
                  size_type bucket_count = /*implementation-defined*/0,
                  const Hash& hash = Hash(),
                  const KeyEqual& equal = KeyEqual(),
                  const Allocator& alloc = Allocator());

#if CPPREFERENCE_STDVER>= 2014
    unordered_set(std::initializer_list<value_type> init,
                  size_type bucket_count,
                  const Allocator& alloc);

    unordered_set(std::initializer_list<value_type> init,
                  size_type bucket_count,
                  const Hash& hash,
                  const Allocator& alloc);
#endif

#if CPPREFERENCE_STDVER>= 2014
    unordered_set(std::initializer_list<value_type> init, const Allocator& alloc);
#endif

    ~unordered_set();

    unordered_set& operator=(const unordered_set& other);
    unordered_set& operator=(unordered_set&& other);
    unordered_set& operator=(initializer_list<value_type> ilist);

    allocator_type get_allocator() const;

    // iterators
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;

    const_iterator cbegin() const;
    const_iterator cend() const;

    // capacity
    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    // modifiers
    void clear();

    std::pair<iterator, bool> insert(const value_type& value);
    std::pair<iterator, bool> insert(value_type&& value);
    iterator insert(const_iterator hint, const value_type& value);
    iterator insert(const_iterator hint, value_type&& value);

    template<class InputIt>
    void insert(InputIt first, InputIt last);
    void insert(std::initializer_list<value_type> ilist);

    template<class... Args>
    std::pair<iterator, bool> emplace(Args&& ... args);

    template <class... Args>
    iterator emplace_hint(const_iterator hint, Args&& ... args);

    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    size_type erase(const key_type& key);

    void swap(unordered_set& other);

    // lookup
    size_type count(const Key& key) const;

    iterator find(const Key& key);
    const_iterator find(const Key& key) const;

    std::pair<iterator, iterator> equal_range(const Key& key);
    std::pair<const_iterator, const_iterator> equal_range(const Key& key) const;

    // bucket interface
    local_iterator begin(size_type n);
    const_local_iterator begin(size_type n) const;
    const_local_iterator cbegin(size_type n) const;

    local_iterator end(size_type n);
    const_local_iterator end(size_type n) const;
    const_local_iterator cend(size_type n) const;

    size_type bucket_count() const;
    size_type max_bucket_count() const;
    size_type bucket_size(size_type n) const;
    size_type bucket(const Key& key) const;
    float load_factor() const;
    float max_load_factor() const;
    void max_load_factor(float ml);
    void rehash(size_type count);
    void reserve(size_type count);

    // observers
    hasher hash_function() const;
    key_equal key_eq() const;
};

template<class Key, class Hash, class KeyEqual, class Allocator>
bool operator==(const unordered_set<Key, Hash, KeyEqual, Allocator>& lhs,
                const unordered_set<Key, Hash, KeyEqual, Allocator>& rhs);

template<class Key, class Hash, class KeyEqual, class Allocator>
bool operator!=(const unordered_set<Key, Hash, KeyEqual, Allocator>& lhs,
                const unordered_set<Key, Hash, KeyEqual, Allocator>& rhs);

template<class Key, class Hash, class KeyEqual, class Alloc>
void swap(unordered_set<Key, Hash, KeyEqual, Alloc>& lhs,
          unordered_set<Key, Hash, KeyEqual, Alloc>& rhs);

template <
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
    > class unordered_multiset {
public:
    typedef Key key_type;
    typedef Key value_type;
    typedef size_t size_type; // actual type unspecified
    typedef ptrdiff_t difference_type; // actual type not specified
    typedef Hash hasher;
    typedef KeyEqual key_equal;
    typedef Allocator allocator_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
#if CPPREFERENCE_SIMPLIFY_TYPEDEFS
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
#else
    typedef typename std::allocator_traits<Allocator>::pointer pointer;
    typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
#endif
    typedef Key* iterator; // actual type is unspecified
    typedef const Key* const_iterator; // actual type is unspecified
    typedef Key* local_iterator; // actual type is unspecified
    typedef const Key* const_local_iterator; // actual type is unspecified

    // constructor


#if CPPREFERENCE_STDVER <2014
    explicit unordered_multiset(size_type bucket_count = 0 /*implementation-defined*/,
                                const Hash& hash = Hash(),
                                const KeyEqual& equal = KeyEqual(),
                                const Allocator& alloc = Allocator());
#else
    unordered_multiset();

    explicit unordered_multiset(size_type bucket_count,
                                const Hash& hash = Hash(),
                                const KeyEqual& equal = KeyEqual(),
                                const Allocator& alloc = Allocator());

    unordered_multiset(size_type bucket_count,
                       const Allocator& alloc);

    unordered_multiset(size_type bucket_count,
                       const Hash& hash,
                       const Allocator& alloc);
#endif

    explicit unordered_multiset(const Allocator& alloc);

    template<class InputIt>
    unordered_multiset(InputIt first, InputIt last,
                       size_type bucket_count = 0 /*implementation-defined*/,
                       const Hash& hash = Hash(),
                       const KeyEqual& equal = KeyEqual(),
                       const Allocator& alloc = Allocator());

#if CPPREFERENCE_STDVER>= 2014
    template<class InputIt>
    unordered_multiset(InputIt first, InputIt last,
                       size_type bucket_count,
                       const Allocator& alloc);

    template<class InputIt>
    unordered_multiset(InputIt first, InputIt last,
                       size_type bucket_count,
                       const Hash& hash,
                       const Allocator& alloc);
#endif

    unordered_multiset(const unordered_multiset& other);
    unordered_multiset(const unordered_multiset& other, const Allocator& alloc);
    unordered_multiset(unordered_multiset&& other);
    unordered_multiset(unordered_multiset&& other, const Allocator& alloc);

    unordered_multiset(std::initializer_list<value_type> init,
                       size_type bucket_count = /*implementation-defined*/0,
                       const Hash& hash = Hash(),
                       const KeyEqual& equal = KeyEqual(),
                       const Allocator& alloc = Allocator());

#if CPPREFERENCE_STDVER>= 2014
    unordered_multiset(std::initializer_list<value_type> init,
                       size_type bucket_count,
                       const Allocator& alloc);

    unordered_multiset(std::initializer_list<value_type> init,
                       size_type bucket_count,
                       const Hash& hash,
                       const Allocator& alloc);
#endif

#if CPPREFERENCE_STDVER>= 2014
    unordered_multiset(std::initializer_list<value_type> init, const Allocator& alloc);
#endif

    ~unordered_multiset();

    unordered_multiset& operator=(const unordered_multiset& other);
    unordered_multiset& operator=(unordered_multiset&& other);
    unordered_multiset& operator=(initializer_list<value_type> ilist);

    allocator_type get_allocator() const;

    // iterators
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;

    const_iterator cbegin() const;
    const_iterator cend() const;

    // capacity
    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    // modifiers
    void clear();

    std::pair<iterator, bool> insert(const value_type& value);
    std::pair<iterator, bool> insert(value_type&& value);
    iterator insert(const_iterator hint, const value_type& value);
    iterator insert(const_iterator hint, value_type&& value);

    template<class InputIt>
    void insert(InputIt first, InputIt last);
    void insert(std::initializer_list<value_type> ilist);

    template<class... Args>
    std::pair<iterator, bool> emplace(Args&& ... args);

    template <class... Args>
    iterator emplace_hint(const_iterator hint, Args&& ... args);

    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    size_type erase(const key_type& key);

    void swap(unordered_multiset& other);

    // lookup
    size_type count(const Key& key) const;

    iterator find(const Key& key);
    const_iterator find(const Key& key) const;

    std::pair<iterator, iterator> equal_range(const Key& key);
    std::pair<const_iterator, const_iterator> equal_range(const Key& key) const;

    // bucket interface
    local_iterator begin(size_type n);
    const_local_iterator begin(size_type n) const;
    const_local_iterator cbegin(size_type n) const;

    local_iterator end(size_type n);
    const_local_iterator end(size_type n) const;
    const_local_iterator cend(size_type n) const;

    size_type bucket_count() const;
    size_type max_bucket_count() const;
    size_type bucket_size(size_type n) const;
    size_type bucket(const Key& key) const;
    float load_factor() const;
    float max_load_factor() const;
    void max_load_factor(float ml);
    void rehash(size_type count);
    void reserve(size_type count);

    // observers
    hasher hash_function() const;
    key_equal key_eq() const;
};

template<class Key, class Hash, class KeyEqual, class Allocator>
bool operator==(const unordered_multiset<Key, Hash, KeyEqual, Allocator>& lhs,
                const unordered_multiset<Key, Hash, KeyEqual, Allocator>& rhs);

template<class Key, class Hash, class KeyEqual, class Allocator>
bool operator!=(const unordered_multiset<Key, Hash, KeyEqual, Allocator>& lhs,
                const unordered_multiset<Key, Hash, KeyEqual, Allocator>& rhs);

template<class Key, class Hash, class KeyEqual, class Alloc>
void swap(unordered_multiset<Key, Hash, KeyEqual, Alloc>& lhs,
          unordered_multiset<Key, Hash, KeyEqual, Alloc>& rhs);

} // namespace std

#endif // CPPREFERENCE_STDVER>= 2011

#endif // CPPREFERENCE_UNORDERED_SET_H