1731be7ddSAugustin Cavalier/*
2731be7ddSAugustin Cavalier * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
3731be7ddSAugustin Cavalier * All rights reserved. Distributed under the terms of the MIT license.
4731be7ddSAugustin Cavalier */
57e65f8ebSIngo Weinhold#ifndef _VECTOR_MAP_H
67e65f8ebSIngo Weinhold#define _VECTOR_MAP_H
77e65f8ebSIngo Weinhold
87e65f8ebSIngo Weinhold#include <stdlib.h>
97e65f8ebSIngo Weinhold#include <string.h>
107e65f8ebSIngo Weinhold
117e65f8ebSIngo Weinhold#include <SupportDefs.h>
127e65f8ebSIngo Weinhold
13960371b7SAxel Dörfler#include <util/kernel_cpp.h>
147e65f8ebSIngo Weinhold#include <KernelUtilsOrder.h>
157e65f8ebSIngo Weinhold#include <Vector.h>
167e65f8ebSIngo Weinhold
177e65f8ebSIngo Weinholdnamespace VectorMapEntryStrategy {
187e65f8ebSIngo Weinhold	// Pair
197e65f8ebSIngo Weinhold	template<typename Key, typename Value,
207e65f8ebSIngo Weinhold			 typename KeyOrder = KernelUtilsOrder::Ascending<Key> > class Pair;
2183744ac9SIngo Weinhold	// ImplicitKey
2283744ac9SIngo Weinhold	template<typename Key, typename Value, typename GetKey,
2383744ac9SIngo Weinhold			 typename KeyOrder = KernelUtilsOrder::Ascending<Key> >
2483744ac9SIngo Weinhold			 class ImplicitKey;
257e65f8ebSIngo Weinhold}
267e65f8ebSIngo Weinhold
277e65f8ebSIngo Weinholdtemplate<typename Entry, typename Parent, typename EntryIterator>
287e65f8ebSIngo Weinhold	class VectorMapIterator;
297e65f8ebSIngo Weinholdtemplate<typename _Key, typename _Value, typename Entry, typename Parent>
307e65f8ebSIngo Weinhold	class VectorMapEntry;
317e65f8ebSIngo Weinhold
327e65f8ebSIngo Weinhold// for convenience
337e65f8ebSIngo Weinhold#define _VECTOR_MAP_TEMPLATE_LIST template<typename Key, typename Value, \
347e65f8ebSIngo Weinhold										   typename EntryStrategy>
357e65f8ebSIngo Weinhold#define _VECTOR_MAP_CLASS_NAME VectorMap<Key, Value, EntryStrategy>
369eed5c27SAxel Dörfler#define _VECTOR_MAP_CLASS_TYPE typename VectorMap<Key, Value, EntryStrategy>
377e65f8ebSIngo Weinhold
387e65f8ebSIngo Weinhold/*!
397e65f8ebSIngo Weinhold	\class VectorMap
407e65f8ebSIngo Weinhold	\brief A generic vector-based map implementation.
417e65f8ebSIngo Weinhold
427e65f8ebSIngo Weinhold	The map entries are ordered according to the supplied
437e65f8ebSIngo Weinhold	compare function object. Default is ascending order.
447e65f8ebSIngo Weinhold
457e65f8ebSIngo Weinhold	Note that VectorMap::Entry is not the same class as EntryStrategy::Entry.
467e65f8ebSIngo Weinhold	It is light-weight class, an object of which is returned when a iterator
477e65f8ebSIngo Weinhold	is dereferenced. It features a Key() and a Value() method returning
487e65f8ebSIngo Weinhold	references to the entry's key/value. This allows EntryStrategy::Entry
497e65f8ebSIngo Weinhold	to be an arbitrary class, not needing to implement a certain interface.
507e65f8ebSIngo Weinhold*/
517e65f8ebSIngo Weinholdtemplate<typename Key, typename Value,
527e65f8ebSIngo Weinhold		 typename EntryStrategy = VectorMapEntryStrategy::Pair<Key, Value> >
537e65f8ebSIngo Weinholdclass VectorMap {
547e65f8ebSIngo Weinholdprivate:
557e65f8ebSIngo Weinhold	typedef _VECTOR_MAP_CLASS_NAME							Class;
567e65f8ebSIngo Weinhold	typedef typename EntryStrategy::Entry					_Entry;
5783744ac9SIngo Weinhold	typedef typename EntryStrategy::KeyReference			KeyReference;
587e65f8ebSIngo Weinhold	typedef Vector<_Entry>									ElementVector;
597e65f8ebSIngo Weinhold
607e65f8ebSIngo Weinholdpublic:
6183744ac9SIngo Weinhold	typedef VectorMapEntry<KeyReference, Value, _Entry, Class>
6283744ac9SIngo Weinhold															Entry;
6383744ac9SIngo Weinhold	typedef VectorMapEntry<KeyReference, const Value, const _Entry,
6483744ac9SIngo Weinhold						   const Class>						ConstEntry;
65731be7ddSAugustin Cavalier	typedef VectorMapIterator<Entry, Class, typename ElementVector::Iterator>
667e65f8ebSIngo Weinhold															Iterator;
67731be7ddSAugustin Cavalier	typedef VectorMapIterator<ConstEntry, const Class, typename ElementVector::ConstIterator>
689eed5c27SAxel Dörfler															ConstIterator;
697e65f8ebSIngo Weinhold
707e65f8ebSIngo Weinholdprivate:
717e65f8ebSIngo Weinhold	static const size_t				kDefaultChunkSize = 10;
727e65f8ebSIngo Weinhold	static const size_t				kMaximalChunkSize = 1024 * 1024;
737e65f8ebSIngo Weinhold
747e65f8ebSIngo Weinholdpublic:
757e65f8ebSIngo Weinhold	VectorMap(size_t chunkSize = kDefaultChunkSize);
767e65f8ebSIngo Weinhold// TODO: Copy constructor, assignment operator.
777e65f8ebSIngo Weinhold	~VectorMap();
787e65f8ebSIngo Weinhold
797e65f8ebSIngo Weinhold	status_t Insert(const Key &key, const Value &value);
807e65f8ebSIngo Weinhold	status_t Put(const Key &key, const Value &value);
817e65f8ebSIngo Weinhold	Value &Get(const Key &key);
827e65f8ebSIngo Weinhold	const Value &Get(const Key &key) const;
837e65f8ebSIngo Weinhold
847e65f8ebSIngo Weinhold	int32 Remove(const Key &key);
857e65f8ebSIngo Weinhold	Iterator Erase(const Iterator &iterator);
867e65f8ebSIngo Weinhold
877e65f8ebSIngo Weinhold	inline int32 Count() const;
887e65f8ebSIngo Weinhold	inline bool IsEmpty() const;
897e65f8ebSIngo Weinhold	void MakeEmpty();
907e65f8ebSIngo Weinhold
917e65f8ebSIngo Weinhold	inline Iterator Begin();
927e65f8ebSIngo Weinhold	inline ConstIterator Begin() const;
937e65f8ebSIngo Weinhold	inline Iterator End();
947e65f8ebSIngo Weinhold	inline ConstIterator End() const;
957e65f8ebSIngo Weinhold	inline Iterator Null();
967e65f8ebSIngo Weinhold	inline ConstIterator Null() const;
977e65f8ebSIngo Weinhold
987e65f8ebSIngo Weinhold	Iterator Find(const Key &key);
997e65f8ebSIngo Weinhold	ConstIterator Find(const Key &key) const;
1007e65f8ebSIngo Weinhold	Iterator FindClose(const Key &key, bool less);
1017e65f8ebSIngo Weinhold	ConstIterator FindClose(const Key &key, bool less) const;
1027e65f8ebSIngo Weinhold
1037e65f8ebSIngo Weinholdprivate:
1047e65f8ebSIngo Weinhold	int32 _FindInsertionIndex(const Key &key, bool &exists) const;
1057e65f8ebSIngo Weinhold
1067e65f8ebSIngo Weinholdprivate:
107758b1d0eSIngo Weinhold//	friend class Entry;
108758b1d0eSIngo Weinhold//	friend class ConstEntry;
109758b1d0eSIngo Weinhold	friend class VectorMapEntry<KeyReference, Value, _Entry, Class>;
110758b1d0eSIngo Weinhold	friend class VectorMapEntry<KeyReference, const Value, const _Entry,
111758b1d0eSIngo Weinhold		const Class>;
1127e65f8ebSIngo Weinhold
1137e65f8ebSIngo Weinhold	ElementVector	fElements;
1147e65f8ebSIngo Weinhold	EntryStrategy	fEntryStrategy;
1157e65f8ebSIngo Weinhold};
1167e65f8ebSIngo Weinhold
1177e65f8ebSIngo Weinhold
1187e65f8ebSIngo Weinhold// VectorMapEntry
11983744ac9SIngo Weinholdtemplate<typename KeyReference, typename _Value, typename Entry,
12083744ac9SIngo Weinhold		 typename Parent>
1217e65f8ebSIngo Weinholdclass VectorMapEntry {
1227e65f8ebSIngo Weinholdprivate:
12383744ac9SIngo Weinhold	typedef VectorMapEntry<KeyReference, _Value, Entry, Parent>	Class;
1247e65f8ebSIngo Weinhold
1257e65f8ebSIngo Weinholdpublic:
1267e65f8ebSIngo Weinhold	VectorMapEntry()
1277e65f8ebSIngo Weinhold		: fParent(NULL), fEntry(NULL) {}
1287e65f8ebSIngo Weinhold
12983744ac9SIngo Weinhold	inline KeyReference Key() const
1307e65f8ebSIngo Weinhold	{
1317e65f8ebSIngo Weinhold		return fParent->fEntryStrategy.GetKey(*fEntry);
1327e65f8ebSIngo Weinhold	}
1337e65f8ebSIngo Weinhold
1347e65f8ebSIngo Weinhold	inline _Value &Value() const
1357e65f8ebSIngo Weinhold	{
1367e65f8ebSIngo Weinhold		return fParent->fEntryStrategy.GetValue(*fEntry);
1377e65f8ebSIngo Weinhold	}
1387e65f8ebSIngo Weinhold
1397e65f8ebSIngo Weinhold	inline const Class *operator->() const
1407e65f8ebSIngo Weinhold	{
1417e65f8ebSIngo Weinhold		return this;
1427e65f8ebSIngo Weinhold	}
1437e65f8ebSIngo Weinhold
1447e65f8ebSIngo Weinhold// private
1457e65f8ebSIngo Weinholdpublic:
1467e65f8ebSIngo Weinhold	VectorMapEntry(Parent *parent, Entry *entry)
1477e65f8ebSIngo Weinhold		: fParent(parent), fEntry(entry) {}
1487e65f8ebSIngo Weinhold
1497e65f8ebSIngo Weinholdprivate:
1507e65f8ebSIngo Weinhold	const Parent	*fParent;
1517e65f8ebSIngo Weinhold	Entry			*fEntry;
1527e65f8ebSIngo Weinhold};
1537e65f8ebSIngo Weinhold
1547e65f8ebSIngo Weinhold
1557e65f8ebSIngo Weinhold// VectorMapIterator
1567e65f8ebSIngo Weinholdtemplate<typename Entry, typename Parent, typename EntryIterator>
1577e65f8ebSIngo Weinholdclass VectorMapIterator {
1587e65f8ebSIngo Weinholdprivate:
1597e65f8ebSIngo Weinhold	typedef VectorMapIterator<Entry, Parent, EntryIterator>	Iterator;
1607e65f8ebSIngo Weinhold
1617e65f8ebSIngo Weinholdpublic:
16283744ac9SIngo Weinhold	inline VectorMapIterator()
1637e65f8ebSIngo Weinhold		: fParent(NULL),
1647e65f8ebSIngo Weinhold		  fIterator()
1657e65f8ebSIngo Weinhold	{
1667e65f8ebSIngo Weinhold	}
1677e65f8ebSIngo Weinhold
16883744ac9SIngo Weinhold	inline VectorMapIterator(
1697e65f8ebSIngo Weinhold		const Iterator &other)
1707e65f8ebSIngo Weinhold		: fParent(other.fParent),
1717e65f8ebSIngo Weinhold		  fIterator(other.fIterator)
1727e65f8ebSIngo Weinhold	{
1737e65f8ebSIngo Weinhold	}
1747e65f8ebSIngo Weinhold
1757e65f8ebSIngo Weinhold	inline Iterator &operator++()
1767e65f8ebSIngo Weinhold	{
1777e65f8ebSIngo Weinhold		++fIterator;
1787e65f8ebSIngo Weinhold		return *this;
1797e65f8ebSIngo Weinhold	}
1807e65f8ebSIngo Weinhold
1817e65f8ebSIngo Weinhold	inline Iterator operator++(int)
1827e65f8ebSIngo Weinhold	{
1837e65f8ebSIngo Weinhold		Iterator it(*this);
1847e65f8ebSIngo Weinhold		++*this;
1857e65f8ebSIngo Weinhold		return it;
1867e65f8ebSIngo Weinhold	}
1877e65f8ebSIngo Weinhold
1887e65f8ebSIngo Weinhold	inline Iterator &operator--()
1897e65f8ebSIngo Weinhold	{
1907e65f8ebSIngo Weinhold		--fIterator;
1917e65f8ebSIngo Weinhold		return *this;
1927e65f8ebSIngo Weinhold	}
1937e65f8ebSIngo Weinhold
1947e65f8ebSIngo Weinhold	inline Iterator operator--(int)
1957e65f8ebSIngo Weinhold	{
1967e65f8ebSIngo Weinhold		Iterator it(*this);
1977e65f8ebSIngo Weinhold		--*this;
1987e65f8ebSIngo Weinhold		return it;
1997e65f8ebSIngo Weinhold	}
2007e65f8ebSIngo Weinhold
2017e65f8ebSIngo Weinhold	inline Iterator &operator=(const Iterator &other)
2027e65f8ebSIngo Weinhold	{
2037e65f8ebSIngo Weinhold		fParent = other.fParent;
2047e65f8ebSIngo Weinhold		fIterator = other.fIterator;
2057e65f8ebSIngo Weinhold		return *this;
2067e65f8ebSIngo Weinhold	}
2077e65f8ebSIngo Weinhold
2087e65f8ebSIngo Weinhold	inline bool operator==(const Iterator &other) const
2097e65f8ebSIngo Weinhold	{
2107e65f8ebSIngo Weinhold		return (fParent == other.fParent && fIterator == other.fIterator);
2117e65f8ebSIngo Weinhold	}
2127e65f8ebSIngo Weinhold
2137e65f8ebSIngo Weinhold	inline bool operator!=(const Iterator &other) const
2147e65f8ebSIngo Weinhold	{
2157e65f8ebSIngo Weinhold		return !(*this == other);
2167e65f8ebSIngo Weinhold	}
2177e65f8ebSIngo Weinhold
2187e65f8ebSIngo Weinhold	inline Entry operator*() const
2197e65f8ebSIngo Weinhold	{
2207e65f8ebSIngo Weinhold		return Entry(fParent, &*fIterator);
2217e65f8ebSIngo Weinhold	}
2227e65f8ebSIngo Weinhold
2237e65f8ebSIngo Weinhold	inline Entry operator->() const
2247e65f8ebSIngo Weinhold	{
2257e65f8ebSIngo Weinhold		return Entry(fParent, &*fIterator);
2267e65f8ebSIngo Weinhold	}
2277e65f8ebSIngo Weinhold
2287e65f8ebSIngo Weinhold	inline operator bool() const
2297e65f8ebSIngo Weinhold	{
2307e65f8ebSIngo Weinhold		return fIterator;
2317e65f8ebSIngo Weinhold	}
2327e65f8ebSIngo Weinhold
2337e65f8ebSIngo Weinhold// private
2347e65f8ebSIngo Weinholdpublic:
23583744ac9SIngo Weinhold	inline VectorMapIterator(Parent *parent, const EntryIterator &iterator)
2367e65f8ebSIngo Weinhold		: fParent(parent),
2377e65f8ebSIngo Weinhold		  fIterator(iterator)
2387e65f8ebSIngo Weinhold	{
2397e65f8ebSIngo Weinhold	}
2407e65f8ebSIngo Weinhold
2417e65f8ebSIngo Weinhold	inline EntryIterator &GetIterator()
2427e65f8ebSIngo Weinhold	{
2437e65f8ebSIngo Weinhold		return fIterator;
2447e65f8ebSIngo Weinhold	}
2457e65f8ebSIngo Weinhold
2467e65f8ebSIngo Weinhold	inline const EntryIterator &GetIterator() const
2477e65f8ebSIngo Weinhold	{
2487e65f8ebSIngo Weinhold		return fIterator;
2497e65f8ebSIngo Weinhold	}
2507e65f8ebSIngo Weinhold
2517e65f8ebSIngo Weinholdprotected:
2527e65f8ebSIngo Weinhold	Parent			*fParent;
2537e65f8ebSIngo Weinhold	EntryIterator	fIterator;
2547e65f8ebSIngo Weinhold};
2557e65f8ebSIngo Weinhold
2567e65f8ebSIngo Weinhold
2577e65f8ebSIngo Weinhold// VectorMap
2587e65f8ebSIngo Weinhold
2597e65f8ebSIngo Weinhold// constructor
2607e65f8ebSIngo Weinhold/*!	\brief Creates an empty map.
2617e65f8ebSIngo Weinhold	\param chunkSize The granularity for the underlying vector's capacity,
2627e65f8ebSIngo Weinhold		   i.e. the minimal number of elements the capacity grows or shrinks
2637e65f8ebSIngo Weinhold		   when necessary.
2647e65f8ebSIngo Weinhold*/
2657e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
2667e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::VectorMap(size_t chunkSize)
2677e65f8ebSIngo Weinhold	: fElements(chunkSize)
2687e65f8ebSIngo Weinhold{
2697e65f8ebSIngo Weinhold}
2707e65f8ebSIngo Weinhold
2717e65f8ebSIngo Weinhold// destructor
2727e65f8ebSIngo Weinhold/*!	\brief Frees all resources associated with the object.
2737e65f8ebSIngo Weinhold
2747e65f8ebSIngo Weinhold	The contained keys and values are destroyed. Note, that for pointer
2757e65f8ebSIngo Weinhold	types only the pointer is destroyed, not the object it points to.
2767e65f8ebSIngo Weinhold*/
2777e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
2787e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::~VectorMap()
2797e65f8ebSIngo Weinhold{
2807e65f8ebSIngo Weinhold}
2817e65f8ebSIngo Weinhold
2827e65f8ebSIngo Weinhold// Insert
2837e65f8ebSIngo Weinhold/*!	\brief Associates a key with a value.
2847e65f8ebSIngo Weinhold
2857e65f8ebSIngo Weinhold	If there is already a value associated with the key, the old entry
2867e65f8ebSIngo Weinhold	is replaced.
2877e65f8ebSIngo Weinhold
2887e65f8ebSIngo Weinhold	\param key The key to which a value shall be associated.
2897e65f8ebSIngo Weinhold	\param value The value to be associated with the key.
2907e65f8ebSIngo Weinhold	\return
2917e65f8ebSIngo Weinhold	- \c B_OK: Everything went fine.
2927e65f8ebSIngo Weinhold	- \c B_NO_MEMORY: Insufficient memory for this operation.
2937e65f8ebSIngo Weinhold	- \c B_BAD_VALUE: The map's EntryStrategy requires some special
2947e65f8ebSIngo Weinhold	  relationship between key and value, that \a key and \a value haven't
2957e65f8ebSIngo Weinhold	  (doesn't apply to the default strategy).
2967e65f8ebSIngo Weinhold*/
2977e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
2987e65f8ebSIngo Weinholdstatus_t
2997e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Insert(const Key &key, const Value &value)
3007e65f8ebSIngo Weinhold{
3017e65f8ebSIngo Weinhold	if (!fEntryStrategy.AreCompatible(key, value))
3027e65f8ebSIngo Weinhold		return B_BAD_VALUE;
3037e65f8ebSIngo Weinhold	bool exists = false;
3047e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
3057e65f8ebSIngo Weinhold	if (exists) {
3067e65f8ebSIngo Weinhold		fElements[index] = fEntryStrategy.MakeEntry(key, value);
3077e65f8ebSIngo Weinhold		return B_OK;
3087e65f8ebSIngo Weinhold	}
3097e65f8ebSIngo Weinhold	return fElements.Insert(fEntryStrategy.MakeEntry(key, value), index);
3107e65f8ebSIngo Weinhold}
3117e65f8ebSIngo Weinhold
3127e65f8ebSIngo Weinhold// Put
3137e65f8ebSIngo Weinhold/*!	\brief Equivalent to Insert().
3147e65f8ebSIngo Weinhold*/
3157e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
3167e65f8ebSIngo Weinholdinline
3177e65f8ebSIngo Weinholdstatus_t
3187e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Put(const Key &key, const Value &value)
3197e65f8ebSIngo Weinhold{
3207e65f8ebSIngo Weinhold	return Insert(key, value);
3217e65f8ebSIngo Weinhold}
3227e65f8ebSIngo Weinhold
3237e65f8ebSIngo Weinhold// Get
3247e65f8ebSIngo Weinhold/*!	\brief Returns the value associated with a given key.
3257e65f8ebSIngo Weinhold
3267e65f8ebSIngo Weinhold	\note Invoking this method for a key not know to the map is dangerous!
3277e65f8ebSIngo Weinhold		  The behavior is unspecified. It may even crash.
3287e65f8ebSIngo Weinhold
3297e65f8ebSIngo Weinhold	\param key The key to be looked up.
3307e65f8ebSIngo Weinhold	\return The value associated with \a key.
3317e65f8ebSIngo Weinhold*/
3327e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
3337e65f8ebSIngo WeinholdValue &
3347e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Get(const Key &key)
3357e65f8ebSIngo Weinhold{
3367e65f8ebSIngo Weinhold	bool exists = false;
3377e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
3387e65f8ebSIngo Weinhold	if (!exists)
3397e65f8ebSIngo Weinhold		return fEntryStrategy.GetValue(fElements[0]);
3407e65f8ebSIngo Weinhold	return fEntryStrategy.GetValue(fElements[index]);
3417e65f8ebSIngo Weinhold}
3427e65f8ebSIngo Weinhold
3437e65f8ebSIngo Weinhold// Get
3447e65f8ebSIngo Weinhold/*!	\brief Returns the value associated with a given key.
3457e65f8ebSIngo Weinhold
3467e65f8ebSIngo Weinhold	\note Invoking this method for a key not know to the map is dangerous!
3477e65f8ebSIngo Weinhold		  The behavior is unspecified. It may even crash.
3487e65f8ebSIngo Weinhold
3497e65f8ebSIngo Weinhold	\param key The key to be looked up.
3507e65f8ebSIngo Weinhold	\return The value associated with \a key.
3517e65f8ebSIngo Weinhold*/
3527e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
3537e65f8ebSIngo Weinholdconst Value &
3547e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Get(const Key &key) const
3557e65f8ebSIngo Weinhold{
3567e65f8ebSIngo Weinhold	bool exists = false;
3577e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
3587e65f8ebSIngo Weinhold	if (!exists)
3597e65f8ebSIngo Weinhold		return fEntryStrategy.GetValue(fElements[0]);
3607e65f8ebSIngo Weinhold	return fEntryStrategy.GetValue(fElements[index]);
3617e65f8ebSIngo Weinhold}
3627e65f8ebSIngo Weinhold
3637e65f8ebSIngo Weinhold// Remove
3647e65f8ebSIngo Weinhold/*!	\brief Removes the entry with the supplied key.
3657e65f8ebSIngo Weinhold	\param key The key to be removed.
3667e65f8ebSIngo Weinhold	\return The number of removed occurrences, i.e. \c 1, if the map
3677e65f8ebSIngo Weinhold			contained an entry with that key, \c 0 otherwise.
3687e65f8ebSIngo Weinhold*/
3697e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
3707e65f8ebSIngo Weinholdint32
3717e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Remove(const Key &key)
3727e65f8ebSIngo Weinhold{
3737e65f8ebSIngo Weinhold	bool exists = false;
3747e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
3757e65f8ebSIngo Weinhold	if (!exists)
3767e65f8ebSIngo Weinhold		return 0;
3777e65f8ebSIngo Weinhold	fElements.Erase(index);
3787e65f8ebSIngo Weinhold	return 1;
3797e65f8ebSIngo Weinhold}
3807e65f8ebSIngo Weinhold
3817e65f8ebSIngo Weinhold// Erase
3827e65f8ebSIngo Weinhold/*!	\brief Removes the entry at the given position.
3837e65f8ebSIngo Weinhold	\param iterator An iterator referring to the entry to be removed.
3847e65f8ebSIngo Weinhold	\return An iterator referring to the entry succeeding the removed
3857e65f8ebSIngo Weinhold			one (End(), if it was the last element that has been
3867e65f8ebSIngo Weinhold			removed), or Null(), if \a iterator was an invalid iterator
3877e65f8ebSIngo Weinhold			(in this case including End()).
3887e65f8ebSIngo Weinhold*/
3897e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
3909eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::Iterator
3917e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Erase(const Iterator &iterator)
3927e65f8ebSIngo Weinhold{
3937e65f8ebSIngo Weinhold	return Iterator(this, fElements.Erase(iterator.GetIterator()));
3947e65f8ebSIngo Weinhold}
3957e65f8ebSIngo Weinhold
3967e65f8ebSIngo Weinhold// Count
3977e65f8ebSIngo Weinhold/*!	\brief Returns the number of entry the map contains.
3987e65f8ebSIngo Weinhold	\return The number of entries the map contains.
3997e65f8ebSIngo Weinhold*/
4007e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
4017e65f8ebSIngo Weinholdinline
4027e65f8ebSIngo Weinholdint32
4037e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Count() const
4047e65f8ebSIngo Weinhold{
4057e65f8ebSIngo Weinhold	return fElements.Count();
4067e65f8ebSIngo Weinhold}
4077e65f8ebSIngo Weinhold
4087e65f8ebSIngo Weinhold// IsEmpty
4097e65f8ebSIngo Weinhold/*!	\brief Returns whether the map is empty.
4107e65f8ebSIngo Weinhold	\return \c true, if the map is empty, \c false otherwise.
4117e65f8ebSIngo Weinhold*/
4127e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
4137e65f8ebSIngo Weinholdinline
4147e65f8ebSIngo Weinholdbool
4157e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::IsEmpty() const
4167e65f8ebSIngo Weinhold{
4177e65f8ebSIngo Weinhold	return fElements.IsEmpty();
4187e65f8ebSIngo Weinhold}
4197e65f8ebSIngo Weinhold
4207e65f8ebSIngo Weinhold// MakeEmpty
4217e65f8ebSIngo Weinhold/*!	\brief Removes all entries from the map.
4227e65f8ebSIngo Weinhold*/
4237e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
4247e65f8ebSIngo Weinholdvoid
4257e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::MakeEmpty()
4267e65f8ebSIngo Weinhold{
4277e65f8ebSIngo Weinhold	fElements.MakeEmpty();
4287e65f8ebSIngo Weinhold}
4297e65f8ebSIngo Weinhold
4307e65f8ebSIngo Weinhold// Begin
4317e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the beginning of the map.
4327e65f8ebSIngo Weinhold
4337e65f8ebSIngo Weinhold	If the map is not empty, Begin() refers to its first entry,
4347e65f8ebSIngo Weinhold	otherwise it is equal to End() and must not be dereferenced!
4357e65f8ebSIngo Weinhold
4367e65f8ebSIngo Weinhold	\return An iterator referring to the beginning of the map.
4377e65f8ebSIngo Weinhold*/
4387e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
4397e65f8ebSIngo Weinholdinline
4409eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::Iterator
4417e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Begin()
4427e65f8ebSIngo Weinhold{
4437e65f8ebSIngo Weinhold	return Iterator(this, fElements.Begin());
4447e65f8ebSIngo Weinhold}
4457e65f8ebSIngo Weinhold
4467e65f8ebSIngo Weinhold// Begin
4477e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the beginning of the map.
4487e65f8ebSIngo Weinhold
4497e65f8ebSIngo Weinhold	If the map is not empty, Begin() refers to its first entry,
4507e65f8ebSIngo Weinhold	otherwise it is equal to End() and must not be dereferenced!
4517e65f8ebSIngo Weinhold
4527e65f8ebSIngo Weinhold	\return An iterator referring to the beginning of the map.
4537e65f8ebSIngo Weinhold*/
4547e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
4557e65f8ebSIngo Weinholdinline
4569eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::ConstIterator
4577e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Begin() const
4587e65f8ebSIngo Weinhold{
4597e65f8ebSIngo Weinhold	return ConstIterator(this, fElements.Begin());
4607e65f8ebSIngo Weinhold}
4617e65f8ebSIngo Weinhold
4627e65f8ebSIngo Weinhold// End
4637e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the end of the map.
4647e65f8ebSIngo Weinhold
4657e65f8ebSIngo Weinhold	The position identified by End() is the one succeeding the last
4667e65f8ebSIngo Weinhold	entry, i.e. it must not be dereferenced!
4677e65f8ebSIngo Weinhold
4687e65f8ebSIngo Weinhold	\return An iterator referring to the end of the map.
4697e65f8ebSIngo Weinhold*/
4707e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
4717e65f8ebSIngo Weinholdinline
4729eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::Iterator
4737e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::End()
4747e65f8ebSIngo Weinhold{
4757e65f8ebSIngo Weinhold	return Iterator(this, fElements.End());
4767e65f8ebSIngo Weinhold}
4777e65f8ebSIngo Weinhold
4787e65f8ebSIngo Weinhold// End
4797e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the end of the map.
4807e65f8ebSIngo Weinhold
4817e65f8ebSIngo Weinhold	The position identified by End() is the one succeeding the last
4827e65f8ebSIngo Weinhold	entry, i.e. it must not be dereferenced!
4837e65f8ebSIngo Weinhold
4847e65f8ebSIngo Weinhold	\return An iterator referring to the end of the map.
4857e65f8ebSIngo Weinhold*/
4867e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
4877e65f8ebSIngo Weinholdinline
4889eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::ConstIterator
4897e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::End() const
4907e65f8ebSIngo Weinhold{
4917e65f8ebSIngo Weinhold	return ConstIterator(this, fElements.End());
4927e65f8ebSIngo Weinhold}
4937e65f8ebSIngo Weinhold
4947e65f8ebSIngo Weinhold// Null
4957e65f8ebSIngo Weinhold/*!	\brief Returns an invalid iterator.
4967e65f8ebSIngo Weinhold
4977e65f8ebSIngo Weinhold	Null() is used as a return value, if something went wrong. It must
4987e65f8ebSIngo Weinhold	neither be incremented or decremented nor dereferenced!
4997e65f8ebSIngo Weinhold
5007e65f8ebSIngo Weinhold	\return An invalid iterator.
5017e65f8ebSIngo Weinhold*/
5027e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
5037e65f8ebSIngo Weinholdinline
5049eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::Iterator
5057e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Null()
5067e65f8ebSIngo Weinhold{
5077e65f8ebSIngo Weinhold	return Iterator(this, fElements.Null());
5087e65f8ebSIngo Weinhold}
5097e65f8ebSIngo Weinhold
5107e65f8ebSIngo Weinhold// Null
5117e65f8ebSIngo Weinhold/*!	\brief Returns an invalid iterator.
5127e65f8ebSIngo Weinhold
5137e65f8ebSIngo Weinhold	Null() is used as a return value, if something went wrong. It must
5147e65f8ebSIngo Weinhold	neither be incremented or decremented nor dereferenced!
5157e65f8ebSIngo Weinhold
5167e65f8ebSIngo Weinhold	\return An invalid iterator.
5177e65f8ebSIngo Weinhold*/
5187e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
5197e65f8ebSIngo Weinholdinline
5209eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::ConstIterator
5217e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Null() const
5227e65f8ebSIngo Weinhold{
5237e65f8ebSIngo Weinhold	return ConstIterator(this, fElements.Null());
5247e65f8ebSIngo Weinhold}
5257e65f8ebSIngo Weinhold
5267e65f8ebSIngo Weinhold// Find
5277e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the entry with the
5287e65f8ebSIngo Weinhold		   specified key.
5297e65f8ebSIngo Weinhold	\param key The key of the entry to be found.
5307e65f8ebSIngo Weinhold	\return An iterator referring to the found entry, or End(), if the
5317e65f8ebSIngo Weinhold			map doesn't contain any entry with the given value.
5327e65f8ebSIngo Weinhold*/
5337e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
5349eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::Iterator
5357e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Find(const Key &key)
5367e65f8ebSIngo Weinhold{
5377e65f8ebSIngo Weinhold	bool exists = false;
5387e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
5397e65f8ebSIngo Weinhold	if (!exists)
5407e65f8ebSIngo Weinhold		return End();
5417e65f8ebSIngo Weinhold	return Iterator(this, fElements.IteratorForIndex(index));
5427e65f8ebSIngo Weinhold}
5437e65f8ebSIngo Weinhold
5447e65f8ebSIngo Weinhold// Find
5457e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the entry with the
5467e65f8ebSIngo Weinhold		   specified key.
5477e65f8ebSIngo Weinhold	\param key The key of the entry to be found.
5487e65f8ebSIngo Weinhold	\return An iterator referring to the found entry, or End(), if the
5497e65f8ebSIngo Weinhold			map doesn't contain any entry with the given value.
5507e65f8ebSIngo Weinhold*/
5517e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
5529eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::ConstIterator
5537e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::Find(const Key &key) const
5547e65f8ebSIngo Weinhold{
5557e65f8ebSIngo Weinhold	bool exists = false;
5567e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
5577e65f8ebSIngo Weinhold	if (!exists)
5587e65f8ebSIngo Weinhold		return End();
5597e65f8ebSIngo Weinhold	return ConstIterator(this, fElements.IteratorForIndex(index));
5607e65f8ebSIngo Weinhold}
5617e65f8ebSIngo Weinhold
5627e65f8ebSIngo Weinhold// FindClose
5637e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the entry with a key closest
5647e65f8ebSIngo Weinhold		   to the specified one.
5657e65f8ebSIngo Weinhold
5667e65f8ebSIngo Weinhold	If the map contains an entry with the specified key, an iterator
5677e65f8ebSIngo Weinhold	to it is returned. Otherwise \a less indicates whether an iterator to
5687e65f8ebSIngo Weinhold	the entry with an directly smaller or greater key shall be returned.
5697e65f8ebSIngo Weinhold
5707e65f8ebSIngo Weinhold	If \a less is \c true and the first entry in the map has a greater
5717e65f8ebSIngo Weinhold	key than the specified one, End() is returned. Similarly, when \a less
5727e65f8ebSIngo Weinhold	is \c false and the last entry's key is smaller. Find() invoked on an
5737e65f8ebSIngo Weinhold	empty map always returns End().
5747e65f8ebSIngo Weinhold
5757e65f8ebSIngo Weinhold	Note, that the key order used for the set is specified as template
5767e65f8ebSIngo Weinhold	argument to the class. Default is ascending order. Descending order
5777e65f8ebSIngo Weinhold	inverts the meaning of \a less, i.e. if \c true, greater values will
5787e65f8ebSIngo Weinhold	be returned, since they are smaller ones according to the order.
5797e65f8ebSIngo Weinhold
5807e65f8ebSIngo Weinhold	\param value The key of the entry to be found.
5817e65f8ebSIngo Weinhold	\return An iterator referring to the found entry, or End(), if the
5827e65f8ebSIngo Weinhold			map doesn't contain any entry with the given key or a close
5837e65f8ebSIngo Weinhold			one according to \a less.
5847e65f8ebSIngo Weinhold*/
5857e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
5869eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::Iterator
5877e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::FindClose(const Key &key, bool less)
5887e65f8ebSIngo Weinhold{
5897e65f8ebSIngo Weinhold	bool exists = false;
5907e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
5917e65f8ebSIngo Weinhold	// If not found, the index _FindInsertionIndex() returns will point to
5927e65f8ebSIngo Weinhold	// an element with a greater value or to End(). So, no special handling
5937e65f8ebSIngo Weinhold	// is needed for !less.
5947e65f8ebSIngo Weinhold	if (exists || !less)
5957e65f8ebSIngo Weinhold		return Iterator(this, fElements.IteratorForIndex(index));
5967e65f8ebSIngo Weinhold	// An element with a smaller value is desired. The previous one (if any)
5977e65f8ebSIngo Weinhold	// will do.
5987e65f8ebSIngo Weinhold	if (index > 0)
5997e65f8ebSIngo Weinhold		return Iterator(this, fElements.IteratorForIndex(index - 1));
6007e65f8ebSIngo Weinhold	return End();
6017e65f8ebSIngo Weinhold}
6027e65f8ebSIngo Weinhold
6037e65f8ebSIngo Weinhold// FindClose
6047e65f8ebSIngo Weinhold/*!	\brief Returns an iterator referring to the entry with a key closest
6057e65f8ebSIngo Weinhold		   to the specified one.
6067e65f8ebSIngo Weinhold
6077e65f8ebSIngo Weinhold	If the map contains an entry with the specified key, an iterator
6087e65f8ebSIngo Weinhold	to it is returned. Otherwise \a less indicates whether an iterator to
6097e65f8ebSIngo Weinhold	the entry with an directly smaller or greater key shall be returned.
6107e65f8ebSIngo Weinhold
6117e65f8ebSIngo Weinhold	If \a less is \c true and the first entry in the map has a greater
6127e65f8ebSIngo Weinhold	key than the specified one, End() is returned. Similarly, when \a less
6137e65f8ebSIngo Weinhold	is \c false and the last entry's key is smaller. Find() invoked on an
6147e65f8ebSIngo Weinhold	empty map always returns End().
6157e65f8ebSIngo Weinhold
6167e65f8ebSIngo Weinhold	Note, that the key order used for the set is specified as template
6177e65f8ebSIngo Weinhold	argument to the class. Default is ascending order. Descending order
6187e65f8ebSIngo Weinhold	inverts the meaning of \a less, i.e. if \c true, greater values will
6197e65f8ebSIngo Weinhold	be returned, since they are smaller ones according to the order.
6207e65f8ebSIngo Weinhold
6217e65f8ebSIngo Weinhold	\param value The key of the entry to be found.
6227e65f8ebSIngo Weinhold	\return An iterator referring to the found entry, or End(), if the
6237e65f8ebSIngo Weinhold			map doesn't contain any entry with the given key or a close
6247e65f8ebSIngo Weinhold			one according to \a less.
6257e65f8ebSIngo Weinhold*/
6267e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
6279eed5c27SAxel Dörfler_VECTOR_MAP_CLASS_TYPE::ConstIterator
6287e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::FindClose(const Key &key, bool less) const
6297e65f8ebSIngo Weinhold{
6307e65f8ebSIngo Weinhold	bool exists = false;
6317e65f8ebSIngo Weinhold	int32 index = _FindInsertionIndex(key, exists);
6327e65f8ebSIngo Weinhold	// If not found, the index _FindInsertionIndex() returns will point to
6337e65f8ebSIngo Weinhold	// an element with a greater value or to End(). So, no special handling
6347e65f8ebSIngo Weinhold	// is needed for !less.
6357e65f8ebSIngo Weinhold	if (exists || !less)
6367e65f8ebSIngo Weinhold		return ConstIterator(this, fElements.IteratorForIndex(index));
6377e65f8ebSIngo Weinhold	// An element with a smaller value is desired. The previous one (if any)
6387e65f8ebSIngo Weinhold	// will do.
6397e65f8ebSIngo Weinhold	if (index > 0)
6407e65f8ebSIngo Weinhold		return ConstIterator(this, fElements.IteratorForIndex(index - 1));
6417e65f8ebSIngo Weinhold	return End();
6427e65f8ebSIngo Weinhold}
6437e65f8ebSIngo Weinhold
6447e65f8ebSIngo Weinhold// _FindInsertionIndex
6457e65f8ebSIngo Weinhold/*!	\brief Finds the index at which the entry with the supplied key is
6467e65f8ebSIngo Weinhold		   located or at which it would need to be inserted.
6477e65f8ebSIngo Weinhold	\param key The key.
6487e65f8ebSIngo Weinhold	\param exists Is set to \c true, if the map does already contain an
6497e65f8ebSIngo Weinhold		   entry with that key, to \c false otherwise.
6507e65f8ebSIngo Weinhold	\return The index at which the entry with the supplied key is
6517e65f8ebSIngo Weinhold			located or at which it would need to be inserted.
6527e65f8ebSIngo Weinhold*/
6537e65f8ebSIngo Weinhold_VECTOR_MAP_TEMPLATE_LIST
6547e65f8ebSIngo Weinholdint32
6557e65f8ebSIngo Weinhold_VECTOR_MAP_CLASS_NAME::_FindInsertionIndex(const Key &key,
6567e65f8ebSIngo Weinhold											bool &exists) const
6577e65f8ebSIngo Weinhold{
6587e65f8ebSIngo Weinhold	// binary search
6597e65f8ebSIngo Weinhold	int32 lower = 0;
6607e65f8ebSIngo Weinhold	int32 upper = Count();
6617e65f8ebSIngo Weinhold	while (lower < upper) {
6627e65f8ebSIngo Weinhold		int32 mid = (lower + upper) / 2;
6637e65f8ebSIngo Weinhold		int cmp = fEntryStrategy.Compare(fEntryStrategy.GetKey(fElements[mid]),
6647e65f8ebSIngo Weinhold															   key);
6657e65f8ebSIngo Weinhold		if (cmp < 0)
6667e65f8ebSIngo Weinhold			lower = mid + 1;
6677e65f8ebSIngo Weinhold		else
6687e65f8ebSIngo Weinhold			upper = mid;
6697e65f8ebSIngo Weinhold	}
6707e65f8ebSIngo Weinhold	exists = (lower < Count() && fEntryStrategy.Compare(key,
6717e65f8ebSIngo Weinhold		fEntryStrategy.GetKey(fElements[lower])) == 0);
6727e65f8ebSIngo Weinhold	return lower;
6737e65f8ebSIngo Weinhold}
6747e65f8ebSIngo Weinhold
6757e65f8ebSIngo Weinhold
6767e65f8ebSIngo Weinhold// entry strategies
6777e65f8ebSIngo Weinhold
6787e65f8ebSIngo Weinholdnamespace VectorMapEntryStrategy {
6797e65f8ebSIngo Weinhold
68083744ac9SIngo Weinhold// Pair
6817e65f8ebSIngo Weinholdtemplate<typename Key, typename Value, typename KeyOrder>
6827e65f8ebSIngo Weinholdclass Pair {
6837e65f8ebSIngo Weinholdpublic:
68483744ac9SIngo Weinhold	typedef const Key	&KeyReference;
68583744ac9SIngo Weinhold
6867e65f8ebSIngo Weinhold	class Entry {
6877e65f8ebSIngo Weinhold	public:
6887e65f8ebSIngo Weinhold		Entry(const Key &key, const Value &value)
6897e65f8ebSIngo Weinhold			: key(key), value(value) {}
6907e65f8ebSIngo Weinhold
6917e65f8ebSIngo Weinhold		Key		key;
6927e65f8ebSIngo Weinhold		Value	value;
6937e65f8ebSIngo Weinhold	};
6947e65f8ebSIngo Weinhold
69583744ac9SIngo Weinhold	inline KeyReference GetKey(const Entry &entry) const
6967e65f8ebSIngo Weinhold	{
6977e65f8ebSIngo Weinhold		return entry.key;
6987e65f8ebSIngo Weinhold	}
6997e65f8ebSIngo Weinhold
7007e65f8ebSIngo Weinhold	inline const Value &GetValue(const Entry &entry) const
7017e65f8ebSIngo Weinhold	{
7027e65f8ebSIngo Weinhold		return entry.value;
7037e65f8ebSIngo Weinhold	}
7047e65f8ebSIngo Weinhold
7057e65f8ebSIngo Weinhold	inline Value &GetValue(Entry &entry) const
7067e65f8ebSIngo Weinhold	{
7077e65f8ebSIngo Weinhold		return entry.value;
7087e65f8ebSIngo Weinhold	}
7097e65f8ebSIngo Weinhold
7107e65f8ebSIngo Weinhold	inline Entry MakeEntry(const Key &key, const Value &value) const
7117e65f8ebSIngo Weinhold	{
7127e65f8ebSIngo Weinhold		return Entry(key, value);
7137e65f8ebSIngo Weinhold	}
7147e65f8ebSIngo Weinhold
7157e65f8ebSIngo Weinhold	inline bool AreCompatible(const Key &, const Value &) const
7167e65f8ebSIngo Weinhold	{
7177e65f8ebSIngo Weinhold		return true;
7187e65f8ebSIngo Weinhold	}
7197e65f8ebSIngo Weinhold
7207e65f8ebSIngo Weinhold	inline int Compare(const Key &a, const Key &b) const
7217e65f8ebSIngo Weinhold	{
7227e65f8ebSIngo Weinhold		return fCompare(a, b);
7237e65f8ebSIngo Weinhold	}
7247e65f8ebSIngo Weinhold
7257e65f8ebSIngo Weinholdprivate:
7267e65f8ebSIngo Weinhold	KeyOrder	fCompare;
7277e65f8ebSIngo Weinhold};
7287e65f8ebSIngo Weinhold
72983744ac9SIngo Weinhold// ImplicitKey
73083744ac9SIngo Weinholdtemplate<typename Key, typename Value, typename _GetKey, typename KeyOrder>
73183744ac9SIngo Weinholdclass ImplicitKey {
73283744ac9SIngo Weinholdpublic:
73383744ac9SIngo Weinhold	typedef Key			KeyReference;
73483744ac9SIngo Weinhold	typedef Value		Entry;
73583744ac9SIngo Weinhold
73683744ac9SIngo Weinhold	inline KeyReference GetKey(const Entry &entry) const
73783744ac9SIngo Weinhold	{
73883744ac9SIngo Weinhold		return fGetKey(entry);
73983744ac9SIngo Weinhold	}
74083744ac9SIngo Weinhold
74183744ac9SIngo Weinhold	inline const Value &GetValue(const Entry &entry) const
74283744ac9SIngo Weinhold	{
74383744ac9SIngo Weinhold		return entry;
74483744ac9SIngo Weinhold	}
74583744ac9SIngo Weinhold
74683744ac9SIngo Weinhold	inline Value &GetValue(Entry &entry) const
74783744ac9SIngo Weinhold	{
74883744ac9SIngo Weinhold		return entry;
74983744ac9SIngo Weinhold	}
75083744ac9SIngo Weinhold
75183744ac9SIngo Weinhold	inline Entry MakeEntry(const Key &, const Value &value) const
75283744ac9SIngo Weinhold	{
75383744ac9SIngo Weinhold		return value;
75483744ac9SIngo Weinhold	}
75583744ac9SIngo Weinhold
75683744ac9SIngo Weinhold	inline bool AreCompatible(const Key &key, const Value &value) const
75783744ac9SIngo Weinhold	{
75883744ac9SIngo Weinhold		return (fGetKey(value) == key);
75983744ac9SIngo Weinhold	}
76083744ac9SIngo Weinhold
76183744ac9SIngo Weinhold	inline int Compare(const Key &a, const Key &b) const
76283744ac9SIngo Weinhold	{
76383744ac9SIngo Weinhold		return fCompare(a, b);
76483744ac9SIngo Weinhold	}
76583744ac9SIngo Weinhold
76683744ac9SIngo Weinholdprivate:
76783744ac9SIngo Weinhold	KeyOrder	fCompare;
76883744ac9SIngo Weinhold	_GetKey		fGetKey;
76983744ac9SIngo Weinhold};
77083744ac9SIngo Weinhold
7717e65f8ebSIngo Weinhold}	// VectorMapEntryStrategy
7727e65f8ebSIngo Weinhold
7737e65f8ebSIngo Weinhold#endif	// _VECTOR_MAP_H
774