/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_MAP_H
#define _POLYMAKE_MAP_H "$Project: polymake $$Id: Map.h 7402 2006-07-27 23:44:14Z gawrilow $"

#ifndef _POLYMAKE_AVL_H
#  include <AVL.h>
#endif
#ifndef _POLYMAKE_TREE_CONTAINERS_H
#  include <tree_containers.h>
#endif
#ifndef _POLYMAKE_SHARED_OBJECT_H
#  include <shared_object.h>
#endif
#ifndef _POLYMAKE_ASSOC_H
#  include <assoc.h>
#endif

namespace pm {

template <typename K, typename D, typename Comparator=operations::cmp<> >
class Map
   : public modified_tree< Map<K,D,Comparator>,
			   list( Container< AVL::tree< AVL::traits<K,D,Comparator> > >,
				 Operation< BuildUnary<AVL::node_accessor> > ) > {
   typedef modified_tree<Map> _super;
protected:
   typedef AVL::tree< AVL::traits<K,D,Comparator> > tree_type;
   shared_object<tree_type> tree;

public:
   typedef K key_type;
   typedef D data_type;
   typedef Comparator key_comparator_type;

   tree_type& get_container() { return *tree; }
   const tree_type& get_container() const { return *tree; }
   using _super::get_comparator_object;

   Map() { }

   explicit Map(const Comparator& cmp_arg)
      : tree( make_constructor(cmp_arg, (tree_type*)0) ) { }

   template <typename Iterator>
   Map(Iterator src, Iterator src_end)
      : tree( make_constructor(src, src_end, (tree_type*)0) ) { }

   template <typename Iterator>
   explicit Map(Iterator src, typename enable_if_iterator<Iterator,end_sensitive>::type=0)
      : tree( make_constructor(src, (tree_type*)0) ) { }

   void clear() { tree.clear(); }

   void swap(Map& m) { tree.swap(m.tree); }

   friend void relocate(Map* from, Map* to)
   {
      pm::relocate(&from->tree, &to->tree);
   }

   /** Associative search.
       Creates new element if it did not exist, initializes it with the copy of the key
       and the default constructor of the value.
   */
   template <typename Key>
   typename assoc_helper<Map,Key>::type operator[] (const Key& k)
   {
      return assoc_helper<Map,Key>::_do(*this,k);
   }

   template <typename Key>
   typename assoc_helper<Map,Key>::const_type operator[] (const Key& k) const
   {
      return assoc_helper<Map,Key>::_do(*this,k);
   }

#ifdef POLY_DEBUG
   void check(const char* label) const { tree->check(label); }
   void dump() const { tree->dump(); }
#endif
};

template <typename K, typename D, typename Comparator>
struct spec_object_traits< Map<K,D,Comparator> >
   : spec_object_traits<is_container> {
   static const IO_separator_kind IO_separator=IO_sep_inherit;
};

} // end namespace pm

namespace polymake {
   using pm::Map;
}

namespace std {
   template <typename K, typename D, typename Comparator> inline
   void swap(pm::Map<K,D,Comparator>& m1, pm::Map<K,D,Comparator>& m2) { m1.swap(m2); }
}

#endif // _POLYMAKE_MAP_H

// Local Variables:
// mode:C++
// End:
