/* ------------------------------------------------------------------------- */

/*
 * Copyright (c) 1999
 *      GMRS Software GmbH, Innsbrucker Ring 159, 81669 Munich, Germany.
 *      http://www.gmrs.de
 *      All rights reserved.
 *      Author: Arno Unkrig (arno.unkrig@gmrs.de)
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by GMRS Software GmbH.
 * 4. The name of GMRS Software GmbH may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY GMRS SOFTWARE GMBH ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GMRS SOFTWARE GMBH BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

/* ------------------------------------------------------------------------- */

#ifndef __map_INCLUDED__ /* { */
#define __map_INCLUDED__

/* ------------------------------------------------------------------------- */

#ident "$Id: map,v 1.2 1999/11/09 19:54:44 arno Exp $"

#include "../rb_tree.h"

/* ------------------------------------------------------------------------- */

template <class key_type, class mapped_type> class map__node;
template <class key_type, class mapped_type> class map__iterator;
template <class key_type, class mapped_type> class map__const_iterator;
template <class key_type, class mapped_type> class map;
template <class key_type, class mapped_type> class multimap;

template <class key_type, class mapped_type>
struct map__node : public rb_tree::node_type {
  map__node(const pair<const key_type, mapped_type> &v) : value(v) {
  }
//~map__node() {
//}
  pair<const key_type, mapped_type> value;
};

template <class key_type, class mapped_type>
class map__iterator {
public:
  map__iterator() {
  }
  map__iterator(const map__iterator<key_type, mapped_type> &x) : node(x.node) {
  }
  pair<const key_type, mapped_type> &operator*() const {
    return ((map__node<key_type, mapped_type> *) node)->value;
  }
  pair<const key_type, mapped_type> *operator->() const {
    return &((map__node<key_type, mapped_type> *) node)->value;
  }
  bool operator==(const map__iterator<key_type, mapped_type> &x) const {
    return node == x.node;
  }
  bool operator!=(const map__iterator<key_type, mapped_type> &x) const {
    return node != x.node;
  }
  const map__iterator<key_type, mapped_type> &operator++() {  // pre-increment
    node = rb_tree::successor(node); return *this;
  }
private:
  map__iterator(rb_tree::node_type *n) : node(n) {
  }
  rb_tree::node_type *node;
  friend map<key_type, mapped_type>;
  friend multimap<key_type, mapped_type>;
  friend map__const_iterator<key_type, mapped_type>;
};

template <class key_type, class mapped_type>
class map__const_iterator {
public:
  map__const_iterator() {
  }
  map__const_iterator(const map__const_iterator<key_type, mapped_type> &x) :
    node(x.node) {
  }
  map__const_iterator(const map__iterator<key_type, mapped_type> &x) :
    node(x.node) {
  }
  const pair<const key_type, mapped_type> &operator*() const {
    return ((const map__node<key_type, mapped_type> *) node)->value;
  }
  const pair<const key_type, mapped_type> *operator->() const {
    return &((const map__node<key_type, mapped_type> *) node)->value;
  }
  bool operator==(const map__const_iterator<key_type, mapped_type> &x) const {
    return node == x.node;
  }
  bool operator!=(const map__const_iterator<key_type, mapped_type> &x) const {
    return node != x.node;
  }
  const map__const_iterator<key_type, mapped_type> &operator++() { // pre-incr
    node = rb_tree::successor(node); return *this;
  }
private:
  map__const_iterator(const rb_tree::node_type *n) : node(n) {
  }
  const rb_tree::node_type *node;

  friend map<key_type, mapped_type>;
  friend multimap<key_type, mapped_type>;
};

/* ------------------------------------------------------------------------- */

template <class key_type, class mapped_type>
class map : public rb_tree {

  // Public types

public:
  typedef pair<const key_type, mapped_type>          value_type;
  typedef map__iterator<key_type, mapped_type>       iterator;
  typedef map__const_iterator<key_type, mapped_type> const_iterator;

  // Private types

private:
  typedef map__node<key_type, mapped_type> node_type;

  // Construct/Copy/Destroy

public:
  explicit map() : rb_tree() {
  }
  map(const_iterator i1, const_iterator i2) :
    rb_tree(i1.node, i2.node, copy_node2) {
  }
  map(const map<key_type, mapped_type> &x) : rb_tree(x) {
  }
  const map<key_type, mapped_type> &operator=(
    const map<key_type, mapped_type> &x
  ) {
    rb_tree::operator=(x); return *this;
  }
  ~map() {
    clear(delete_node2);
  }

  // Iterators

  iterator begin() {
    return iterator(rb_tree::begin());
  }
  const_iterator begin() const {
    return const_iterator(rb_tree::begin());
  }
  iterator end() {
    return iterator(rb_tree::end());
  }
  const_iterator end() const {
    return const_iterator(rb_tree::end());
  }
//reverse_iterator rbegin();
//const_reverse_iterator rbegin() const;
//reverse_iterator rend();
//const_reverse_iterator rend() const;

  // Capacity

//bool      empty()    const;  // Inherited from "rb_tree".
//size_type size()     const;  // Inherited from "rb_tree".
//size_type max_size() const;  // Inherited from "rb_tree".

  // Element access

  mapped_type &operator[](const key_type &x) {
    rb_tree::node_type *n = rb_tree::find_any((value_pointer) &x);
    if (n == rb_tree::end()) {
      n = rb_tree::insert(new node_type(value_type(x, mapped_type())));
    }
    return ((node_type *) n)->value.second;
  }

  // Modifiers

  // Must not use "iterator", else CFRONT fails.
  pair<map__iterator<key_type, mapped_type>, bool> insert(const value_type &x) {
    if (rb_tree::find_any((value_pointer) &x.first) != rb_tree::end()) {
      return pair<iterator, bool>(end(), false);
    }
    return pair<iterator, bool>(
      iterator(rb_tree::insert(new node_type(x))),
      true
    );
  }
  iterator insert(iterator, const value_type &);
  void insert(const_iterator from, const_iterator to) {
    rb_tree::insert(from.node, to.node);
  }
  size_type erase(const key_type &x) {
    return rb_tree::erase_one((value_pointer) &x);
  }
  iterator erase(iterator i) {
    return iterator(rb_tree::erase(i.node));
  }
  iterator erase(iterator i1, iterator i2) {
    return iterator(rb_tree::erase(i1.node, i2.node));
  }
  void swap(map<key_type, mapped_type> &x) {
    rb_tree::swap((rb_tree &) x);
  }
//void clear();                // Inherited from "rb_tree".

  // Map operations

  iterator find(const key_type &x) {
    return iterator(rb_tree::find_any((value_pointer) &x));
  }
  const_iterator find(const key_type &x) const {
    return const_iterator(rb_tree::find_any((value_pointer) &x));
  }
  size_type count(const key_type &x) const {
    return find_any((value_pointer) &x) != rb_tree::end();
  }
  iterator lower_bound(const key_type &x) {
    return iterator(rb_tree::lower_bound((value_pointer) &x));
  }
  const_iterator lower_bound(const key_type &x) const {
    return const_iterator(rb_tree::lower_bound((value_pointer) &x));
  }
  iterator upper_bound(const key_type &x) {
    return iterator(rb_tree::upper_bound((value_pointer) &x));
  }
  const_iterator upper_bound(const key_type &x) const {
    return const_iterator(rb_tree::upper_bound((value_pointer) &x));
  }
  // Must not use "pair<iterator, iterator>", else CFRONT fails
  pair<
    map__iterator<key_type, mapped_type>,
    map__iterator<key_type, mapped_type>
  > equal_range(const key_type &x) {
    return pair<iterator, iterator>(lower_bound(x), upper_bound(x));
  }
  // Must not use "pair<const_iterator, const_iterator>", else CFRONT fails
  pair<
    map__const_iterator<key_type, mapped_type>,
    map__const_iterator<key_type, mapped_type>
  > equal_range(const key_type &x) const {
    return pair<const_iterator, const_iterator>(
      lower_bound(x),
      upper_bound(x)
    );
  }

  bool operator==(const map<key_type, mapped_type> &x) const {
    return rb_tree::operator==((const rb_tree &) x);
  }
  bool operator<(const map<key_type, mapped_type> &x) const {
    return rb_tree::operator<((const rb_tree &) x);
  }

  // Implementation of "rb_tree"'s virtual methods.

private:
  /*virtual*/ bool node_less_than(
    const rb_tree::node_type *x,
    const rb_tree::node_type *y
  ) const {
    return (
      ((const node_type *) x)->value.first <
      ((const node_type *) y)->value.first
    );
  }
  /*virtual*/ bool node_less_than(
    value_pointer            x,
    const rb_tree::node_type *y
  ) const {
    return *(const key_type *) x < ((const node_type *) y)->value.first;
  }
  /*virtual*/ bool node_less_than(
    const rb_tree::node_type *x,
    value_pointer            y
  ) const {
    return ((const node_type *) x)->value.first < *(const key_type *) y;
  }

  /*virtual*/ rb_tree::node_type *copy_node(const rb_tree::node_type *n) const {
    return new node_type(((const node_type *) n)->value);
  }
  /*virtual*/ void delete_node(rb_tree::node_type *n) const {
    delete (node_type *) n;
  }

  typedef void (*key_mapped_printer)(
    ostream           &,
    const key_type    &,
    const mapped_type &
  );
  /*virtual*/ void print_node_value(
    const rb_tree::node_type &n,
    ostream                  &os,
    void                     *closure
  ) const {
    (*(key_mapped_printer *) closure)(
      os,
      ((const node_type &) n).value.first,
      ((const node_type &) n).value.second
    );
  }
  void print(ostream &os, key_mapped_printer np) const {
    rb_tree::print(os, (void *) &np);
  }
  friend ostream &operator<<(
    ostream                          &,
    const map<key_type, mapped_type> &
  );

  // Needed by "map(iter, iter)".
  static rb_tree::node_type *copy_node2(const rb_tree::node_type *n) {
    return new node_type(((const node_type *) n)->value);
  }
  // Needed by "~map()".
  static void delete_node2(rb_tree::node_type *n) {
    delete (node_type *) n;
  }

  friend map__iterator<key_type, mapped_type>;
  friend map__const_iterator<key_type, mapped_type>;
};

/* ------------------------------------------------------------------------- */

template <class key_type, class mapped_type>
class multimap : public rb_tree {

  // Public types

public:
  typedef pair<const key_type, mapped_type>          value_type;
  typedef map__iterator<key_type, mapped_type>       iterator;
  typedef map__const_iterator<key_type, mapped_type> const_iterator;

  // Private types

private:
  typedef map__node<key_type, mapped_type> node_type;

  // Construct/Copy/Destroy

public:
  explicit multimap() : rb_tree() {
  }
  multimap(const_iterator i1, const_iterator i2) :
    rb_tree(i1.node, i2.node, copy_node2) {
  }
  multimap(const multimap<key_type, mapped_type> &x) : rb_tree(x) {
  }
  const multimap<key_type, mapped_type> &operator=(
    const multimap<key_type, mapped_type> &x
  ) {
    rb_tree::operator=(x); return *this;
  }
  ~multimap() {
    clear(delete_node2);
  }

  // Iterators

  iterator begin() {
    return iterator((node_type *) rb_tree::begin());
  }
  const_iterator begin() const {
    return const_iterator((const node_type *) rb_tree::begin());
  }
  iterator end() {
    return iterator((node_type *) rb_tree::end());
  }
  const_iterator end() const {
    return const_iterator((const node_type *) rb_tree::end());
  }
//reverse_iterator rbegin();
//const_reverse_iterator rbegin() const;
//reverse_iterator rend();
//const_reverse_iterator rend() const;

  // Capacity

//bool      empty()    const;  // Inherited from "rb_tree".
//size_type size()     const;  // Inherited from "rb_tree".
//size_type max_size() const;  // Inherited from "rb_tree".

  // Modifiers

  iterator insert(const value_type &x) {
    return iterator((node_type *) rb_tree::insert(new node_type(x)));
  }
//iterator insert(iterator, const value_type &);
  void insert(const_iterator from, const_iterator to) {
    rb_tree::insert(from.node, to.node);
  }
  size_type erase(const key_type &x) {
    return rb_tree::erase_all((value_pointer) &x);
  }
  iterator erase(iterator i) {
    return iterator(rb_tree::erase(i.node));
  }
  iterator erase(iterator i1, iterator i2) {
    return iterator(rb_tree::erase(i1.node, i2.node));
  }
  void swap(multimap<key_type, mapped_type> &x) {
    rb_tree::swap((rb_tree &) x);
  }
//void clear();                // Inherited from "rb_tree".

  // Multimap operations

  iterator find(const key_type &x) {
    return iterator(rb_tree::find_first((value_pointer) &x));
  }
  const_iterator find(const key_type &x) const {
    return const_iterator(rb_tree::find_first((value_pointer) &x));
  }
  size_type count(const key_type &x) const {
    return rb_tree::count((value_pointer) &x);
  }
  iterator lower_bound(const key_type &x) {
    return iterator(rb_tree::lower_bound((value_pointer) &x));
  }
  const_iterator lower_bound(const key_type &x) const {
    return const_iterator(rb_tree::lower_bound((value_pointer) &x));
  }
  iterator upper_bound(const key_type &x) {
    return iterator(rb_tree::upper_bound((value_pointer) &x));
  }
  const_iterator upper_bound(const key_type &x) const {
    return const_iterator(rb_tree::upper_bound((value_pointer) &x));
  }
  // Must not use "pair<iterator, iterator>", else CFRONT fails
  // G++ 2.7.2.1 cannot compile this ("field "first" has incomplete type")!?
//pair<
//  map__iterator<key_type, mapped_type>,
//  map__iterator<key_type, mapped_type>
//> equal_range(const key_type &x) {
//  return pair<iterator, iterator>(lower_bound(x), upper_bound(x));
//}
  // Must not use "pair<const_iterator, const_iterator>", else CFRONT fails
  pair<
    map__const_iterator<key_type, mapped_type>,
    map__const_iterator<key_type, mapped_type>
  > equal_range(const key_type &x) const {
    return pair<const_iterator, const_iterator>(lower_bound(x), upper_bound(x));
  }

  bool operator==(const multimap<key_type, mapped_type> &x) const {
    return rb_tree::operator==((const rb_tree &) x);
  }
  bool operator<(const multimap<key_type, mapped_type> &x) const {
    return rb_tree::operator<((const rb_tree &) x);
  }

  // Implementation of "rb_tree"'s virtual methods.

private:
  /*virtual*/ bool node_less_than(
    const rb_tree::node_type *x,
    const rb_tree::node_type *y
  ) const {
    return (
      ((const node_type *) x)->value.first <
      ((const node_type *) y)->value.first
    );
  }
  /*virtual*/ bool node_less_than(
    value_pointer            x,
    const rb_tree::node_type *y
  ) const {
    return *(const key_type *) x < ((const node_type *) y)->value.first;
  }
  /*virtual*/ bool node_less_than(
    const rb_tree::node_type *x,
    value_pointer            y
  ) const {
    return ((const node_type *) x)->value.first < *(const key_type *) y;
  }

  /*virtual*/ rb_tree::node_type *copy_node(const rb_tree::node_type *n) const {
    return new node_type(((const node_type *) n)->value);
  }
  /*virtual*/ void delete_node(rb_tree::node_type *n) const {
    delete (node_type *) n;
  }

  typedef void (*key_mapped_printer)(
    ostream           &,
    const key_type    &,
    const mapped_type &
  );
  /*virtual*/ void print_node_value(
    const rb_tree::node_type &n,
    ostream                  &os,
    void                     *closure
  ) const {
    (*(key_mapped_printer *) closure)(
      os,
      ((const node_type &) n).value.first,
      ((const node_type &) n).value.second
    );
  }
  void print(ostream &os, key_mapped_printer np) const {
    rb_tree::print(os, (void *) &np);
  }
  friend ostream &operator<<(
    ostream                               &,
    const multimap<key_type, mapped_type> &
  );

  // Needed by "multimap(iter, iter)".
  static rb_tree::node_type *copy_node2(const rb_tree::node_type *n) {
    return new node_type(((const node_type *) n)->value);
  }
  // Needed by "~multimap()".
  static void delete_node2(rb_tree::node_type *n) {
    delete (node_type *) n;
  }

  friend map__iterator<key_type, mapped_type>;
  friend map__const_iterator<key_type, mapped_type>;
};

/* ------------------------------------------------------------------------- */

/*
 * MUST DEFINE THESE HERE AT THE END OF THIS FILE; FOR ELSE STUPID CFRONT
 * INSTANTIATES IT OUT-OF-LINE!?
 */

template<class key_type, class mapped_type>
inline void map__print_key_mapped(
  ostream           &os,
  const key_type    &key,
  const mapped_type &mapped
)
{
  os << "(" << key << " => " << mapped << ")";
}

template<class key_type, class mapped_type>
inline ostream &
operator<<(ostream &os, const map<key_type, mapped_type> &x)
{
  x.print(os, map__print_key_mapped);
  return os;
}

template<class key_type, class mapped_type>
inline ostream &
operator<<(ostream &os, const multimap<key_type, mapped_type> &x)
{
  x.print(os, map__print_key_mapped);
  return os;
}

/* ------------------------------------------------------------------------- */

#endif /* } */

/* ------------------------------------------------------------------------- */