Ticket #1707: EntityMap.3.h

File EntityMap.3.h, 3.9 KB (added by wraitii, 9 years ago)
Line 
1#ifndef INCLUDED_ENTITYMAP
2#define INCLUDED_ENTITYMAP
3
4/**
5 * A fast replacement for map<entity_id_t, T>.
6 * We make the following assumptions:
7 * - entity id's (keys) are unique and are inserted in increasing order
8 * - an entity id that was removed is never added again
9 * - modifications (add / delete) are far less frequent then look-ups
10 * - preformance for iteration is important
11 */
12template<typename T> class EntityMap
13{
14public:
15 // Map interface:
16 // Member types
17 typedef entity_id_t key_type;
18 typedef T mapped_type;
19 typedef std::pair<entity_id_t, T> value_type;
20
21 typedef typename std::vector<value_type>::difference_type difference_type;
22 typedef typename std::vector<value_type>::size_type size_type;
23
24private:
25 std::vector<value_type> m_Data;
26 size_t m_Size;
27
28public:
29 inline EntityMap() : m_Data(), m_Size(0)
30 {
31 }
32
33 inline EntityMap(const EntityMap& m) : m_Data(m.m_Data), m_Size(m.m_Size)
34 {
35 }
36
37 // Iterators
38 template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
39 {
40 U* val;
41 inline _iter(U* init) : val(init) { }
42 inline U& operator *( ) { return *val; }
43 inline U* operator ->( ) { return val; }
44 inline _iter& operator++( )
45 {
46 while ((val++)->first == INVALID_ENTITY) {}
47 return *this;
48 }
49 inline _iter& operator++(int)
50 {
51 U* ptr = val;
52 ++val;
53 return ptr;
54 }
55 inline bool operator != ( _iter other ) { return val != other.val; }
56 inline bool operator == ( _iter other ) { return val == other.val; }
57 inline operator _iter<U const>() const { return _iter<U const>(val); }
58 };
59
60 typedef _iter<value_type> iterator;
61 typedef _iter<value_type const> const_iterator;
62
63 inline iterator begin()
64 {
65 iterator it(&*m_Data.begin());
66 if (size() != 0 && it->first == INVALID_ENTITY)
67 ++it;
68 return it;
69 }
70 inline iterator end()
71 {
72 if (size() == 0) return begin();
73 return iterator(&*m_Data.end());
74 }
75 inline const_iterator begin() const
76 {
77 const_iterator it(&*m_Data.begin());
78 if (size() != 0 && it->first == INVALID_ENTITY)
79 ++it;
80 return it;
81 }
82 inline const_iterator end() const
83 {
84 if (size() == 0) return begin();
85 return const_iterator(&*m_Data.end());
86 }
87
88 // Capacity
89 inline bool empty() const { return m_Size == 0; }
90 inline size_type size() const { return m_Size; }
91
92 // Modification
93 std::pair<iterator, bool> insert(const value_type& val)
94 {
95 difference_type index = val.first;
96 bool new_index = false; // was a new element created?
97 if (index >= (int)m_Data.size())
98 {
99 m_Data.resize(index + 1);
100 new_index = true;
101 ++m_Size;
102 }
103 m_Data[index] = val;
104 return std::make_pair(iterator(&m_Data[index]), new_index); // false: element existed
105 }
106
107 void erase(iterator it)
108 {
109 // only reliable way right now? or we could try ~T() and memset null?
110 it->first = INVALID_ENTITY; // mark it as 'invalid entity_id'
111 it->second.~T(); // call dtor
112 new (&it->second) T(); // call placement new
113 if (it == (&m_Data.back()))
114 m_Data.pop_back();
115 --m_Size;
116 }
117
118 size_type erase(const key_type& key)
119 {
120 iterator it = find(key);
121 if (it != end())
122 erase(it);
123 return 1;
124 }
125
126 inline void swap(EntityMap &map)
127 {
128 m_Data.swap(map.m_Data);
129 }
130
131 inline void clear()
132 {
133 m_Size = 0;
134 m_Data.clear();
135 }
136
137 // Operations
138 inline iterator find(const key_type& key)
139 {
140 if (key < m_Data.size())
141 {
142 const value_type& val = m_Data[key];
143 if (val.first != INVALID_ENTITY) // is this a valid element?
144 return iterator(&m_Data[key]);
145 }
146 return end(); // not found
147 }
148
149 inline const_iterator find(const key_type& key) const
150 {
151 if (key < m_Data.size())
152 {
153 const value_type& val = m_Data[key];
154 if (val.first != INVALID_ENTITY) // is this a valid element?
155 return const_iterator(&m_Data[key]);
156 }
157 return end(); // not found
158 }
159
160 inline size_type count(const key_type& key) const
161 {
162 return find(key) == end() ? 0 : 1;
163 }
164};
165#endif