1: # ifndef util_hpp |
2: # define util_hpp |
3: |
4: # include < algorithm > |
5: # include < cassert > |
6: # include < cstdint > |
7: # include < initializer_list > |
8: # include < random > |
9: # include < sstream > |
10: # include < string > |
11: # include < unordered_map > |
12: |
13: |
14: struct ident { |
15: public : |
16: constexpr explicit ident ( uint32_t i ) : i_ { i } { } |
17: |
18: operator bool ( ) { return i_ != 0 ; } |
19: |
20: bool operator == ( const ident & other ) const { return i_ == other . i_ ; } |
21: bool operator != ( const ident & other ) const { return ! ( * this == other ) ; } |
22: |
23: ident operator ++ ( int ) { |
24: uint32_t old = i_ ++ ; |
25: return ident { old } ; |
26: } |
27: |
28: protected : |
29: uint32_t i_ ; |
30: friend std : : hash < ident > ; |
31: friend std : : string to_string ( const ident & id ) ; |
32: } ; |
33: |
34: constexpr ident invalid_id { 0 } ; |
35: |
36: inline std : : string to_string ( const ident & id ) { return std : : string ( "#" ) + std : : to_string ( id . i_ ) ; } |
37: |
38: namespace std { |
39: |
40: template < > struct hash <: : ident > { |
41: size_t operator ( ) ( : : ident i ) const noexcept { return hash < uint32_t > ( ) ( i . i_ ) ; } |
42: } ; |
43: } ; |
44: |
45: |
46: template < typename T > class container { |
47: public : |
48: using key_type = ident ; |
49: using value_type = T ; |
50: |
51: container ( ) { |
52: const int initialElems = 4096 ; |
53: values_ . reserve ( initialElems ) ; |
54: } |
55: |
56: value_type & add ( value_type value = { } ) { |
57: key_type key = nextKey_ ++ ; |
58: size_t index = values_ . size ( ) ; |
59: values_ . push_back ( std : : move ( value ) ) ; |
60: values_ . back ( ) . id = key ; |
61: indices_ [ key ] = index ; |
62: return values_ . back ( ) ; |
63: } |
64: |
65: value_type & operator [ ] ( key_type key ) { |
66: auto it = indices_ . find ( key ) ; |
67: if ( it == indices_ . end ( ) ) |
68: return nullElement_ ; |
69: else |
70: return values_ [ it -> second ] ; |
71: } |
72: |
73: void remove ( key_type key ) { |
74: auto it = indices_ . find ( key ) ; |
75: assert ( it != indices_ . end ( ) ) ; |
76: size_t index = it -> second ; |
77: auto & back = values_ . back ( ) ; |
78: indices_ [ back . id ] = index ; |
79: values_ [ index ] = std : : move ( back ) ; |
80: values_ . pop_back ( ) ; |
81: indices_ . erase ( it ) ; |
82: } |
83: |
84: std : : vector < T > & values ( ) { return values_ ; } |
85: |
86: protected : |
87: std : : unordered_map < key_type , size_t > indices_ ; |
88: std : : vector < T > values_ ; |
89: key_type nextKey_ { 1 } ; |
90: T nullElement_ { } ; |
91: |
92: template < typename U > friend std : : string to_string ( const container < U > & container ) ; |
93: } ; |
94: |
95: template < typename T > std : : string to_string ( const container < T > & container ) { |
96: std : : ostringstream oss ; |
97: oss << "[" ; |
98: for ( const auto & v : container . values_ ) { |
99: oss << "(" << container . indices_ . at ( v . id ) << ":" << to_string ( v ) << ") " ; |
100: } |
101: oss << "]" ; |
102: return oss . str ( ) ; |
103: } |
104: |
105: |
106: |
107: template < typename T > class buffered_container : public container < T > { |
108: using super = container < T > ; |
109: |
110: public : |
111: using key_type = typename super : : key_type ; |
112: using value_type = typename super : : value_type ; |
113: |
114: buffered_container ( ) { |
115: add_ . reserve ( max_size ( ) ) ; |
116: remove_ . reserve ( max_size ( ) ) ; |
117: |
118: remove_ . clear ( ) ; |
119: add_ . clear ( ) ; |
120: } |
121: |
122: constexpr int max_size ( ) const { return 1024 ; } |
123: |
124: int size ( ) const { return ( int ) add_ . size ( ) ; } |
125: |
126: value_type & add ( value_type value = { } ) { |
127: if ( add_ . size ( ) >= max_size ( ) ) { |
128: throw std : : runtime_error ( "Exceeded buffer capacity" ) ; |
129: } |
130: |
131: buffered_ = true ; |
132: key_type key = super : : nextKey_ ++ ; |
133: add_ . push_back ( std : : move ( value ) ) ; |
134: add_ . back ( ) . id = key ; |
135: return add_ . back ( ) ; |
136: } |
137: |
138: void remove ( key_type key ) { |
139: bool inContainer = super : : indices_ . find ( key ) != super : : indices_ . end ( ) ; |
140: bool inBuffer = std : : find_if ( add_ . begin ( ) , add_ . end ( ) , |
141: [ key ] ( T & value ) { return value . id == key ; } ) != add_ . end ( ) ; |
142: assert (/* inContainer || */truefalse inContainer inBuffer ) ; |
143: |
144: buffered_ = true ; |
145: remove_ . push_back ( key ) ; |
146: } |
147: |
148: value_type & operator [ ] ( key_type key ) { |
149: if ( buffered_ ) { |
150: auto remove_it = std : : find ( remove_ . begin ( ) , remove_ . end ( ) , key ) ; |
151: if ( remove_it != remove_ . end ( ) ) |
152: return super : : nullElement_ ; |
153: |
154: if ( super : : indices_ . count ( key ) == 0 ) { |
155: auto add_it = std : : find_if ( add_ . begin ( ) , add_ . end ( ) , |
156: [ key ] ( const T & t ) { return t . id == key ; } ) ; |
157: if ( add_it != add_ . end ( ) ) |
158: return * add_it ; |
159: } |
160: } |
161: return super : : operator [ ] ( key ) ; |
162: } |
163: |
164: void sync ( ) { |
165: for ( auto & value : add_ ) { |
166: size_t index = super : : values_ . size ( ) ; |
167: super : : values_ . push_back ( std : : move ( value ) ) ; |
168: super : : indices_ [ value . id ] = index ; |
169: } |
170: |
171: for ( auto & id : remove_ ) { |
172: super : : remove ( id ) ; |
173: } |
174: |
175: add_ . clear ( ) ; |
176: remove_ . clear ( ) ; |
177: buffered_ = false ; |
178: } |
179: |
180: protected : |
181: bool buffered_ = false ; |
182: std : : vector < T > add_ { } ; |
183: std : : vector < ident > remove_ { } ; |
184: } ; |
185: |
186: |
187: |
188: template < typename T > struct vec2 { |
189: T x , y ; |
190: |
191: template < typename U > explicit operator vec2 < U > ( ) { |
192: return vec2 < U > { static_cast < U > ( x ) , static_cast < U > ( y ) } ; |
193: } |
194: } ; |
195: |
196: using vec2i = vec2 < int32_t > ; |
197: using vec2d = vec2 < double > ; |
198: |
199: template < typename T > inline vec2 < T > operator - ( vec2 < T > a ) { return { - a . x , - a . y } ; } |
200: template < typename T > inline vec2 < T > operator + ( vec2 < T > a , vec2 < T > b ) { |
201: return { a . x + b . x , a . y + b . y } ; |
202: } |
203: template < typename T > inline vec2 < T > operator - ( vec2 < T > a , vec2 < T > b ) { |
204: return { a . x - b . x , a . y - b . y } ; |
205: } |
206: template < typename T > inline vec2 < T > operator * ( vec2 < T > a , T m ) { return { a . x * m , a . y * m } ; } |
207: template < typename T > inline vec2 < T > operator / ( vec2 < T > a , T m ) { return { a . x / m , a . y / m } ; } |
208: template < typename T > inline vec2 < T > & operator += ( vec2 < T > & a , vec2 < T > b ) { return a = a + b ; } |
209: template < typename T > inline vec2 < T > & operator -= ( vec2 < T > & a , vec2 < T > b ) { return a = a + b ; } |
210: template < typename T > inline vec2 < T > & operator *= ( vec2 < T > & a , T b ) { return a = a * b ; } |
211: template < typename T > inline vec2 < T > & operator /= ( vec2 < T > & a , T b ) { return a = a / b ; } |
212: template < typename T > inline bool operator == ( vec2 < T > a , vec2 < T > b ) { |
213: return a/* a.x == b.x && */truefalse . x == b . x a . y == b . y ; |
214: } |
215: template < typename T > inline bool operator != ( vec2 < T > a , vec2 < T > b ) { |
216: return a/* a.x != b.x || */truefalse . x != b . x a . y != b . y ; |
217: } |
218: |
219: struct recti { |
220: int32_t left , top , width , height ; |
221: inline bool contains ( const vec2i & p ) const { |
222: return p/* p.x >= left && */truefalse/* p.x >= left && p.x < left + width && */truefalse/* p.x >= left && p.x < left + width && p.y <= top && */truefalse . x >= left &&||/* && p.x < left + width */ p . x < left + width p . y <= top &&||/* && p.y > top - height */ p . y > top - height ; |
223: } |
224: } ; |
225: |
226: template < typename T > inline std : : string to_string ( const vec2 < T > & vec ) { |
227: using namespace std : : string_literals ; |
228: return "{" s + std : : to_string ( vec . x ) + ", " s + std : : to_string ( vec . y ) + "}" s ; |
229: } |
230: |
231: template < typename T > T sign ( T t ) { |
232: if ( t > 0 ) |
233: return 1 ; |
234: else if ( t < 0 ) |
235: return - 1 ; |
236: else |
237: return 0 ; |
238: } |
239: |
240: |
241: |
242: template < typename T > struct Array2D { |
243: public : |
244: Array2D ( int width , int height , T nullVal = { } ) |
245: : nullVal_ ( nullVal ) , width_ ( width ) , height_ ( height ) , data_ ( width * height , nullVal ) { } |
246: |
247: void resize ( int newWidth , int newHeight ) { |
248: width_ = newWidth ; |
249: height_ = newHeight ; |
250: data_ . resize ( width_ * height_ , nullVal_ ) ; |
251: data_ . shrink_to_fit ( ) ; |
252: } |
253: |
254: int width ( ) const { return width_ ; } |
255: |
256: int height ( ) const { return height_ ; } |
257: |
258: void fill ( T val ) { std : : fill ( data_ . begin ( ) , data_ . end ( ) , val ) ; } |
259: |
260: T & operator ( ) ( int x , int y ) { return inBounds ( x , y ) ? data_ [ x + y * width_ ] : nullVal_ ; } |
261: |
262: T & operator ( ) ( vec2i p ) { return ( * this ) ( p . x , p . y ) ; } |
263: |
264: const T & operator ( ) ( int x , int y ) const { |
265: return inBounds ( x , y ) ? data_ [ x + y * width_ ] : nullVal_ ; |
266: } |
267: |
268: const T & operator ( ) ( vec2i p ) const { return ( * this ) ( p . x , p . y ) ; } |
269: |
270: bool inBounds ( int x , int y ) const { return x/* x >= 0 && */truefalse/* x >= 0 && x < width_ && */truefalse/* x >= 0 && x < width_ && y >= 0 && */truefalse >= 0 x < width_ y >= 0 y < height_ ; } |
271: |
272: bool inBounds ( vec2i p ) const { return p/* p.x >= 0 && */truefalse/* p.x >= 0 && p.x < width_ && */truefalse/* p.x >= 0 && p.x < width_ && p.y >= 0 && */truefalse . x >= 0 &&||/* && p.x < width_ */ p . x < width_ p . y >= 0 &&||/* && p.y < height_ */ p . y < height_ ; } |
273: |
274: |
275: std : : vector < T > & data ( ) { return data_ ; } |
276: |
277: private : |
278: T nullVal_ { } ; |
279: int width_ = 0 ; |
280: int height_ = 0 ; |
281: std : : vector < T > data_ ; |
282: } ; |
283: |
284: |
285: |
286: inline std : : default_random_engine & engine ( ) { |
287: static std : : default_random_engine engine_ ; |
288: return engine_ ; |
289: } |
290: |
291: inline int32_t randInt ( int32_t from , int32_t to ) { |
292: return std : : uniform_int_distribution < > ( from , to ) ( engine ( ) ) ; |
293: } |
294: |
295: inline double random ( double from = 0.0 , double to = 1.0 ) { |
296: return std : : uniform_real_distribution < > ( from , to ) ( engine ( ) ) ; |
297: } |
298: |
299: inline vec2i randVec2i ( vec2i from , vec2i to ) { |
300: return { randInt ( from . x , to . x ) , randInt ( from . y , to . y ) } ; |
301: } |
302: |
303: template < typename T > T choose ( const std : : vector < T > & values ) { |
304: return values [ randInt ( 0 , values . size ( ) - 1 ) ] ; |
305: } |
306: |
307: template < typename T > T choose ( std : : initializer_list < T > values ) { |
308: return * ( values . begin ( ) + randInt ( 0 , ( int ) values . size ( ) - 1 ) ) ; |
309: } |
310: |
311: # endif |