#ifndef FlexiMap_h_included
#define FlexiMap_h_included

static const char FlexiMap_h_RcsId[] = "$Id: FlexiMap.h,v 1.2 2002/09/21 23:56:56 neutron Exp $";

//
// FlexiMap.h:
//	A map-like container that has different space characteristics.
//
// Design:
//      FlexiMap is intended as a replacement for the STL map template
//      class.  It's implemented as a FlexiSet of pairs.
//
// Differences:
//      With a map, iterators are not invalidated when you insert or
//      erase an element.  With FlexiMap, iterators may be invalidated
//      if the FlexiSet is in the vector state.  It is best to assume
//      that iterators will always become invalidated.
//
//		       C O N F I D E N T I A L
//
// Copyright 2002 Hewlett-Packard
//
// No part of this file may be reproduced, stored in a retrieval system,
// or transmitted in any form or by any means--electronic, mechanical,
// photocopying, recording, or otherwise--without prior written permission
// of Hewlett-Packard.
//

#include "FlexiSet.h"

template <class _Key, class _TypeT, class _Compare = std::less<_Key> >
class FlexiMap
{
  public:
    typedef _Key                                key_type;
    typedef _TypeT                              mapped_type;
    // Consider making key_type const here
    typedef std::pair<key_type, mapped_type>	value_type;
    typedef _Compare                            key_compare;

  private:
    class pair_compare {
        public:
	    bool operator()(const value_type &a, const value_type &b) const {
		return key_compare()(a.first, b.first);
	    }
    };
    typedef FlexiSet<value_type, pair_compare> set_t;
    set_t fs;

  public:
    //
    // types
    //
    typedef typename set_t::reference                reference;
    typedef typename set_t::const_reference          const_reference;
    typedef typename set_t::iterator                 iterator;
    typedef typename set_t::const_iterator           const_iterator;
    typedef typename set_t::size_type                size_type;
    typedef typename set_t::difference_type          difference_type;
    typedef typename set_t::pointer                  pointer;
    typedef typename set_t::const_pointer            const_pointer;

    //
    // construct/copy/destroy
    //
    FlexiMap () {}


    template<class InputIterator>
    FlexiMap (InputIterator first, InputIterator last)
      : fs(first, last) {}

    // Default copy ctor, operator=, and dtor are fine.

    //
    // iterators
    //

    iterator               begin  ()       { return fs.begin();  }
    const_iterator         begin  () const { return fs.begin();  }
    iterator               end    ()       { return fs.end();    }
    const_iterator         end    () const { return fs.end();    }

    //
    // capacity
    //
    bool      empty    () const { return fs.empty();    }
    size_type size     () const { return fs.size();     }
    size_type max_size () const { return fs.max_size(); }

    //
    // element access
    //
    mapped_type& operator[](const key_type& k) {
      value_type tmp(k,_TypeT());
      iterator i = insert(tmp).first;
      return const_cast<mapped_type &>(i->second);
    }


    std::pair<iterator,bool> insert(const_reference __x) {
        return fs.insert (__x);
    }

    iterator insert(iterator position, const value_type& x) {
      return fs.insert(position, x);
    }

    template<class InputIterator>
    void insert(InputIterator first, InputIterator last) {
      fs.insert(first, last);
    }

    iterator erase(iterator position) {
    	return fs.erase(position);
    }
    size_type erase (const key_type& x) {
    	return fs.erase(value_type(x, mapped_type()));
    }
    void erase(iterator first, iterator last) {
    	fs.erase(first,last);
    }
    void clear() {
    	fs.clear();
    }

    //
    // FlexiMap operations
    //
    iterator     find (const key_type& x)        {
    	return fs.find(value_type(x, mapped_type()));
    }
    const_iterator find (const key_type& x)  const {
    	return fs.find(value_type(x, mapped_type()));
    }
    size_type    count (const key_type& x) const {
	return fs.count(value_type(x, mapped_type()));
    }
    iterator     lower_bound (const key_type& x) {
	return fs.lower_bound(value_type(x, mapped_type()));
    }
    iterator     upper_bound (const key_type& x) {
	return fs.upper_bound(value_type(x, mapped_type()));
    }
    const_iterator lower_bound (const key_type& x) const
    {
	return fs.lower_bound(value_type(x, mapped_type()));
    }
    const_iterator upper_bound (const key_type& x) const
    {
	return fs.upper_bound(value_type(x, mapped_type()));
    }
    std::pair<iterator,iterator> equal_range (const key_type& x)
    {
	return fs.equal_range(value_type(x, mapped_type()));
    }
    std::pair<const_iterator, const_iterator>
    equal_range (const key_type& x) const
    {
	return fs.equal_range(value_type(x, mapped_type()));
    }

  };

#endif   // FlexiMap_h_included