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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
/**
\file G3D/SmallArray.h
\created 2009-04-26
\edited 2012-07-23
Copyright 2000-2012, Morgan McGuire, http://graphics.cs.williams.edu
All rights reserved.
*/
#ifndef G3D_SmallArray_h
#define G3D_SmallArray_h
#include "G3D/platform.h"
#include "G3D/Array.h"
#include "G3D/MemoryManager.h"
namespace G3D {
/** Embeds \a N elements to reduce allocation time and increase
memory coherence when working with arrays of arrays.
Offers a limited subset of the functionality of G3D::Array.*/
template<class T, int N>
class SmallArray {
private:
int m_size;
/** First N elements */
T m_embedded[N];
/** Remaining elements */
Array<T> m_rest;
public:
SmallArray() : m_size(0) {}
inline int size() const {
return m_size;
}
void resize(int n, bool shrinkIfNecessary = true) {
m_rest.resize(std::max(0, n - N), shrinkIfNecessary);
m_size = n;
}
void clear(bool shrinkIfNecessary = true) {
resize(0, shrinkIfNecessary);
}
void clearAndSetMemoryManager(MemoryManager::Ref& m) {
clear();
m_rest.clearAndSetMemoryManager(m);
}
inline T& operator[](int i) {
debugAssert(i < m_size && i >= 0);
if (i < N) {
return m_embedded[i];
} else {
return m_rest[i - N];
}
}
inline const T& operator[](int i) const {
debugAssert(i < m_size && i >= 0);
if (i < N) {
return m_embedded[i];
} else {
return m_rest[i - N];
}
}
inline void push(const T& v) {
++m_size;
if (m_size <= N) {
m_embedded[m_size - 1] = v;
} else {
m_rest.append(v);
}
}
inline void append(const T& v) {
push(v);
}
inline void append(const T& v, const T& v2) {
push(v);
push(v2);
}
inline void append(const T& v, const T& v2, const T& v3) {
push(v);
push(v2);
push(v3);
}
inline void append(const T& v, const T& v2, const T& v3, const T& v4) {
push(v);
push(v2);
push(v3);
push(v4);
}
/** Find the index of \a v or -1 if not found */
int findIndex(const T& v) {
for (int i = 0; i < N; ++i) {
if (m_embedded[i] == v) {
return i;
}
}
return m_rest.findIndex(v) + N;
}
void fastRemove(int i, bool shrinkIfNecessary = false) {
debugAssert(i < m_size && i >= 0);
if (i < N) {
if (m_size <= N) {
// Exclusively embedded
m_embedded[i] = m_embedded[m_size - 1];
} else {
// Move one down from the rest array
m_embedded[i] = m_rest.pop();
}
} else {
// Removing from the rest array
m_rest.fastRemove(i - N, shrinkIfNecessary);
}
--m_size;
}
T pop() {
debugAssert(m_size > 0);
if (m_size <= N) {
// Popping from embedded, don't need a temporary
--m_size;
return m_embedded[m_size];
} else {
// Popping from rest
--m_size;
return m_rest.pop();
}
}
inline void popDiscard() {
debugAssert(m_size > 0);
if (m_size > N) {
m_rest.popDiscard();
}
--m_size;
}
inline T& next() {
++m_size;
if (m_size <= N) {
return m_embedded[m_size - 1];
} else {
return m_rest.next();
}
}
bool contains(const T& value) const {
for (int i = std::min(m_size, N) - 1; i >= 0; --i) {
if (m_embedded[i] == value) {
return true;
}
}
return m_rest.contains(value);
}
template<int MIN_ELEMENTS>
SmallArray<T, N>& operator=(const Array<T, MIN_ELEMENTS>& src) {
resize(src.size());
for (int i = 0; i < src.size(); ++i) {
(*this)[i] = src[i];
}
return *this;
}
inline const T& last() const {
return (*this)[size() - 1];
}
inline T& last() {
return (*this)[size() - 1];
}
};
}
#endif
|
