forked from HeliumProject/Foundation
-
Notifications
You must be signed in to change notification settings - Fork 1
/
SortedMap.h
64 lines (53 loc) · 2.43 KB
/
SortedMap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#pragma once
#include "Foundation/RedBlackTree.h"
namespace Helium
{
/// Key-sorted map.
///
/// SortedMap stores elements using a red-black tree data structure. Lookups, insertions, and deletions are
/// performed in a worst-case of O(log n) time. When iterating, values are guaranteed to be sorted by their keys.
template< typename Key, typename Data, typename CompareKey = Less< Key >, typename Allocator = DefaultAllocator >
class SortedMap : public RedBlackTree< KeyValue< Key, Data >, Key, SelectKey< KeyValue< Key, Data > >, CompareKey, Allocator, Pair< Key, Data > >
{
public:
/// Parent class type.
typedef RedBlackTree< KeyValue< Key, Data >, Key, SelectKey< KeyValue< Key, Data > >, CompareKey, Allocator, Pair< Key, Data > > Base;
/// Type for map keys.
typedef typename Base::KeyType KeyType;
/// Type for map data.
typedef Data DataType;
/// Type for map entries.
typedef typename Base::ValueType ValueType;
/// Type for comparing two keys.
typedef typename Base::KeyCompareType KeyCompareType;
/// Allocator type.
typedef typename Base::AllocatorType AllocatorType;
/// @name Construction/Destruction
//@{
SortedMap();
SortedMap( const SortedMap& rSource );
template< typename OtherAllocator > SortedMap(
const SortedMap< Key, Data, CompareKey, OtherAllocator >& rSource );
//@}
/// @name Overloaded Operators
//@{
SortedMap& operator=( const SortedMap& rSource );
template< typename OtherAllocator > SortedMap& operator=(
const SortedMap< Key, Data, CompareKey, OtherAllocator >& rSource );
Data& operator[]( const Key& rKey );
bool operator==( const SortedMap& rOther ) const;
template< typename OtherAllocator > bool operator==(
const SortedMap< Key, Data, CompareKey, OtherAllocator >& rOther ) const;
bool operator!=( const SortedMap& rOther ) const;
template< typename OtherAllocator > bool operator!=(
const SortedMap< Key, Data, CompareKey, OtherAllocator >& rOther ) const;
//@}
private:
/// @name Private Utility Functions
//@{
template< typename OtherAllocator > bool Equals(
const SortedMap< Key, Data, CompareKey, OtherAllocator >& rOther ) const;
//@}
};
}
#include "Foundation/SortedMap.inl"