Ticket #1707: EntityMap.2.h

File EntityMap.2.h, 3.9 KB (added by wraitii, 9 years ago)

Updated EntityMap with custom iterator that skips invalid entities.

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
27public:
28 inline EntityMap() : m_Data()
29 {
30 }
31
32 inline EntityMap(const EntityMap& m) : m_Data(m.m_Data)
33 {
34 }
35
36 // Iterators
37 template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
38 {
39 U* val;
40 inline _iter(U* init) : val(init) { }
41 inline U& operator *( ) { return *val; }
42 inline U* operator ->( ) { return val; }
43 inline _iter& operator++( )
44 {
45 while ((val++)->first == INVALID_ENTITY) {}
46 return *this;
47 }
48 inline _iter& operator++(int)
49 {
50 U* ptr = val;
51 ++val;
52 return ptr;
53 }
54 inline bool operator != ( _iter other ) { return val != other.val; }
55 inline bool operator == ( _iter other ) { return val == other.val; }
56 inline operator _iter<U const>() const { return _iter<U const>(val); }
57 };
58
59 typedef _iter<value_type> iterator;
60 typedef _iter<value_type const> const_iterator;
61
62 inline iterator begin()
63 {
64 return iterator(&*m_Data.begin());
65 }
66 inline iterator end()
67 {
68 if (size() == 0)
69 return iterator(&*m_Data.begin()); // return the same as begin()
70 return iterator(&*m_Data.end());
71 }
72 inline const_iterator begin() const
73 {
74 return const_iterator(&*m_Data.begin());
75 }
76 inline const_iterator end() const
77 {
78 if (size() == 0)
79 return const_iterator(&*m_Data.begin());
80 return const_iterator(&*m_Data.end());
81 }
82
83 // Capacity
84 inline bool empty() const { return m_Data.empty(); }
85 inline size_type size() const { return m_Data.size(); }
86 inline size_type max_size() const { return m_Data.max_size(); }
87
88 // Modification
89 std::pair<iterator, bool> insert(const value_type& val)
90 {
91 difference_type index = val.first;
92 bool new_index = false; // was a new element created?
93 if (index >= (int)m_Data.size())
94 {
95 m_Data.resize(index + 1);
96 new_index = true;
97 }
98 m_Data[index] = val;
99 return std::make_pair(iterator(&m_Data[index]), new_index); // false: element existed
100 }
101
102 void erase(iterator it)
103 {
104 // only reliable way right now? or we could try ~T() and memset null?
105 it->first = INVALID_ENTITY; // mark it as 'invalid entity_id'
106 it->second.~T(); // call dtor
107 new (&it->second) T(); // call placement new
108 }
109
110 size_type erase(const key_type& key)
111 {
112 size_type count = 0;
113 iterator it = find(key);
114 if (it != end())
115 {
116 erase(it);
117 count = 1;
118 }
119 return count;
120 }
121
122 inline void swap(EntityMap &map)
123 {
124 m_Data.swap(map.m_Data);
125 }
126
127 inline void clear()
128 {
129 m_Data.clear();
130 }
131
132 // Operations
133 inline iterator find(const key_type& key)
134 {
135 if (key < m_Data.size())
136 {
137 const value_type& val = m_Data[key];
138 if (val.first != INVALID_ENTITY) // is this a valid element?
139 return iterator(&m_Data[key]);
140 }
141 return end(); // not found
142 }
143
144 inline const_iterator find(const key_type& key) const
145 {
146 if (key < m_Data.size())
147 {
148 const value_type& val = m_Data[key];
149 if (val.first != INVALID_ENTITY) // is this a valid element?
150 return const_iterator(&m_Data[key]);
151 }
152 return end(); // not found
153 }
154
155 inline size_type count(const key_type& key) const
156 {
157 return find(key) == end() ? 0 : 1;
158 }
159};
160#endif