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 | */
|
---|
12 | template<typename T> class EntityMap
|
---|
13 | {
|
---|
14 | public:
|
---|
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 |
|
---|
24 | private:
|
---|
25 | std::vector<value_type> m_Data;
|
---|
26 |
|
---|
27 | public:
|
---|
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
|
---|