#ifndef cathlibcpp_map_H
#define cathlibcpp_map_H

// File:       map.h
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ map and multimap class templates


#ifndef cathlibcpp_assocbase_H
#include "assocbase.h"
#endif

#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_iterator_H
#include "iterator.h"
#endif

#ifndef cathlibcpp_newcasts_H
#include "newcasts.h"
#endif

#ifndef cathlibcpp_utility_H
#include "utility.h"                 // for pair<T1, T2>
#endif


#ifdef PROBLEM_LONG_NAMES

// abbreviations to stop CFront choking on long names

#define map_value_type               __mvt
#define map_iterator                 __mi
#define map_const_iterator           __mci

#endif


// class map<Key, T, Compare>


template<class Key, class T, class Compare>
class map_iterator;

template<class Key, class T, class Compare>
class map_const_iterator;

template<class Key, class T>
class map_value_type;


template<class Key, class T, class Compare>
class map
{
  friend bool operator==(map<Key, T, Compare> const& x, map<Key, T, Compare> const& y);
  friend bool operator< (map<Key, T, Compare> const& x, map<Key, T, Compare> const& y);

  public:

#   define map_type                  map<Key, T, Compare>
#   define key_type                  Key
#   define mapped_type               T
#   define value_type                map_value_type<Key, T>
#   define reference                 T&
#   define const_reference           T const&
#   define iterator                  map_iterator<Key, T, Compare>
#   define const_iterator            map_const_iterator<Key, T, Compare>
#   define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type&>
#   define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#   define size_type                 size_t
#   define difference_type           ptrdiff_t

    // constructors
    map();
    map(Compare const& cmp);
    map(iterator const& first, iterator const& last);
    map(iterator const& first, iterator const& last, Compare const& cmp);
    map(value_type const* first, value_type const* last);
    map(value_type const* first, value_type const* last, Compare const& cmp);
    map(map<Key, T, Compare> const& rhs);
    ~map();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    const_rev_iterator rbegin() const;
    const_rev_iterator rend() const;

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

    mapped_type const& operator[](key_type const& x) const;

    const_iterator find(key_type const& x) const;

    size_type count(key_type const& x) const;

    const_iterator lower_bound(key_type const& x) const;
    const_iterator upper_bound(key_type const& x) const;
    pair<const_iterator, const_iterator> equal_range(key_type const& x) const;

    Compare key_compare() const;

    // mutators
    map<Key, T, Compare>& operator=(map<Key, T, Compare> const& rhs);

    iterator begin();
    iterator end();

    rev_iterator rbegin();
    rev_iterator rend();

    mapped_type& operator[](key_type const& x);

    pair<iterator, bool> insert(value_type const& x);
    iterator insert(iterator const& hint, value_type const& x);
    void insert(iterator const& first, iterator const& last);
    void insert(value_type const* first, value_type const* last);

    void erase(iterator position);
    size_type erase(key_type const& x);
    void erase(iterator first, iterator last);

    void swap(map<Key, T, Compare>& x);

    void clear();

    iterator find(key_type const& x);

    iterator lower_bound(key_type const& x);
    iterator upper_bound(key_type const& x);
    pair<iterator, iterator> equal_range(key_type const& x);

  private:

    Compare key_cmp_;
    assoc_base tree_;

#   undef map_type
#   undef key_type
#   undef mapped_type
#   undef value_type
#   undef reference
#   undef const_reference
#   undef iterator
#   undef const_iterator
#   undef rev_iterator
#   undef const_rev_iterator
#   undef size_type
#   undef difference_type
};


template<class Key, class T, class Compare>
bool operator==(map<Key, T, Compare> const& lhs, map<Key, T, Compare> const& rhs);

template<class Key, class T, class Compare>
bool operator< (map<Key, T, Compare> const& lhs, map<Key, T, Compare> const& rhs);


// CFront has trouble using pair<Key const, T> directly

template<class Key, class T>
struct map_value_type : public pair<Key const, T>
{
  map_value_type()
    {}

  map_value_type(Key const& k, T const& t)
    : pair<Key const, T>(k, t)
    {}

  map_value_type(const pair<Key const, T> p)
    : pair<Key const, T>(p)
    {}

  bool operator==(const map_value_type<Key, T>& rhs)
    {
      return REF_reinterpret_cast(Key, first) == REF_reinterpret_cast(Key, rhs.first) &&
             REF_reinterpret_cast(T, second) == REF_reinterpret_cast(T, rhs.second);
    }

  bool operator<(const map_value_type<Key, T>& rhs)
    {
      return REF_reinterpret_cast(Key, first) < REF_reinterpret_cast(Key, rhs.first) ||
             (!(REF_reinterpret_cast(Key, rhs.first) < REF_reinterpret_cast(Key, first)) &&
                REF_reinterpret_cast(T, second) < REF_reinterpret_cast(T, rhs.second));
    }
};


// class multimap<Key, T, Compare>

#define multimap_iterator            map_iterator
#define multimap_const_iterator      map_const_iterator
#define multimap_value_type          map_value_type


template<class Key, class T, class Compare>
class multimap
{
  friend bool operator==(multimap<Key, T, Compare> const& x, multimap<Key, T, Compare> const& y);
  friend bool operator< (multimap<Key, T, Compare> const& x, multimap<Key, T, Compare> const& y);

  public:

#   define multimap_type             multimap<Key, T, Compare>
#   define key_type                  Key
#   define mapped_type               T
#   define value_type                map_value_type<Key, T>
#   define reference                 T&
#   define const_reference           T const&
#   define iterator                  multimap_iterator<Key, T, Compare>
#   define const_iterator            multimap_const_iterator<Key, T, Compare>
#   define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type&>
#   define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#   define size_type                 size_t
#   define difference_type           ptrdiff_t

    // constructors
    multimap();
    multimap(Compare const& cmp);
    multimap(iterator const& first, iterator const& last);
    multimap(iterator const& first, iterator const& last, Compare const& cmp);
    multimap(value_type const* first, value_type const* last);
    multimap(value_type const* first, value_type const* last, Compare const& cmp);
    multimap(multimap<Key, T, Compare> const& rhs);
    ~multimap();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    const_rev_iterator rbegin() const;
    const_rev_iterator rend() const;

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

    const_iterator find(key_type const& x) const;

    size_type count(key_type const& x) const;

    const_iterator lower_bound(key_type const& x) const;
    const_iterator upper_bound(key_type const& x) const;
    pair<const_iterator, const_iterator> equal_range(key_type const& x) const;

    Compare key_compare() const;

    // mutators
    multimap<Key, T, Compare>& operator=(multimap<Key, T, Compare> const& rhs);

    iterator begin();
    iterator end();

    rev_iterator rbegin();
    rev_iterator rend();

    pair<iterator, bool> insert(value_type const& x);
    iterator insert(iterator const& hint, value_type const& x);
    void insert(iterator const& first, iterator const& last);
    void insert(value_type const* first, value_type const* last);

    void erase(iterator position);
    size_type erase(key_type const& x);
    void erase(iterator first, iterator last);

    void swap(multimap<Key, T, Compare>& x);

    void clear();

    iterator find(key_type const& x);

    iterator lower_bound(key_type const& x);
    iterator upper_bound(key_type const& x);
    pair<iterator, iterator> equal_range(key_type const& x);

  private:

    Compare key_cmp_;
    assoc_base tree_;

#   undef multimap_type
#   undef key_type
#   undef mapped_type
#   undef value_type
#   undef reference
#   undef const_reference
#   undef iterator
#   undef const_iterator
#   undef rev_iterator
#   undef const_rev_iterator
#   undef size_type
#   undef difference_type
};


template<class Key, class T, class Compare>
bool operator==(multimap<Key, T, Compare> const& lhs, multimap<Key, T, Compare> const& rhs);

template<class Key, class T, class Compare>
bool operator< (multimap<Key, T, Compare> const& lhs, multimap<Key, T, Compare> const& rhs);


// map_iterator

template<class Key, class T, class Compare>
class map_iterator : public bidirectional_iterator<map_value_type<Key, T> >
{
  friend class map<Key, T, Compare>;
  friend class multimap<Key, T, Compare>;

  public:

    // constructors
    map_iterator()
      {}
    map_iterator(map_iterator<Key, T, Compare> const& rhs);

    // accessors
    bool operator==(map_iterator<Key, T, Compare> const& rhs) const
      { return node_ == rhs.node_; }

    map_value_type<Key, T>& operator*() const
      { return *reinterpret_cast(map_value_type<Key _ T>*, node_+1); }

    // mutators
    map_iterator<Key, T, Compare>& operator=(map_iterator<Key, T, Compare> const& rhs);

    map_iterator<Key, T, Compare>& operator++();
    map_iterator<Key, T, Compare> operator++(int);

    map_iterator<Key, T, Compare>& operator--();
    map_iterator<Key, T, Compare> operator--(int);

  private:

    map_iterator(assoc_base* tree, assoc_base_node* node)
      : tree_(tree),
        node_(node)
      {}

    assoc_base* tree_;
    assoc_base_node* node_;
};


// map_const_iterator

template<class Key, class T, class Compare>
class map_const_iterator : public bidirectional_iterator<map_value_type<Key, T> >
{
  friend class map<Key, T, Compare>;
  friend class multimap<Key, T, Compare>;

  public:

    // constructors
    map_const_iterator()
      {}
    map_const_iterator(map_const_iterator<Key, T, Compare> const& rhs);

    // accessors
    bool operator==(map_const_iterator<Key, T, Compare> const& rhs) const
      { return node_ == rhs.node_; }

    map_value_type<Key, T> const& operator*() const
      { return *reinterpret_cast(map_value_type<Key _ T>*, node_+1); }

    // mutators
    map_const_iterator<Key, T, Compare>& operator=(map_const_iterator<Key, T, Compare> const& rhs);

    map_const_iterator<Key, T, Compare>& operator++();
    map_const_iterator<Key, T, Compare> operator++(int);

    map_const_iterator<Key, T, Compare>& operator--();
    map_const_iterator<Key, T, Compare> operator--(int);

  private:

    map_const_iterator(assoc_base const* tree, assoc_base_node const* node)
      : tree_(tree),
        node_(node)
      {}

    assoc_base const* tree_;
    assoc_base_node const* node_;
};

#endif
