data/grass_footsteps.png

/*
Minetest-c55
Copyright (C) 2010-2012 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#ifndef UTIL_CONTAINER_HEADER
#define UTIL_CONTAINER_HEADER

#include "../irrlichttypes.h"
#include <jmutex.h>
#include <jmutexautolock.h>
#include "../porting.h" // For sleep_ms

/*
	Queue with unique values with fast checking of value existence
*/

template<typename Value>
class UniqueQueue
{
public:
	
	/*
		Does nothing if value is already queued.
		Return value:
			true: value added
			false: value already exists
	*/
	bool push_back(Value value)
	{
		// Check if already exists
		if(m_map.find(value) != NULL)
			return false;

		// Add
		m_map.insert(value, 0);
		m_list.push_back(value);
		
		return true;
	}

	Value pop_front()
	{
		typename core::list<Value>::Iterator i = m_list.begin();
		Value value = *i;
		m_map.remove(value);
		m_list.erase(i);
		return value;
	}

	u32 size()
	{
		assert(m_list.size() == m_map.size());
		return m_list.size();
	}

private:
	core::map<Value, u8> m_map;
	core::list<Value> m_list;
};

#if 1
template<typename Key, typename Value>
class MutexedMap
{
public:
	MutexedMap()
	{
		m_mutex.Init();
		assert(m_mutex.IsInitialized());
	}
	
	void set(const Key &name, const Value &value)
	{
		JMutexAutoLock lock(m_mutex);

		m_values[name] = value;
	}
	
	bool get(const Key &name, Value *result)
	{
		JMutexAutoLock lock(m_mutex);

		typename core::map<Key, Value>::Node *n;
		n = m_values.find(name);

		if(n == NULL)
			return false;
		
		if(result != NULL)
			*result = n->getValue();
			
		return true;
	}

	core::list<Value> getValues()
	{
		core::list<Value> result;
		for(typename core::map<Key, Value>::Iterator
				i = m_values.getIterator();
				i.atEnd() == false; i++){
			result.push_back(i.getNode()->getValue());
		}
		return result;
	}

private:
	core::map<Key, Value> m_values;
	JMutex m_mutex;
};
#endif

/*
	Generates ids for comparable values.
	Id=0 is reserved for "no value".

	Is fast at:
	- Returning value by id (very fast)
	- Returning id by value
	- Generating a new id for a value

	Is not able to:
	- Remove an id/value pair (is possible to implement but slow)
*/
template<typename T>
class MutexedIdGenerator
{
public:
	MutexedIdGenerator()
	{
		m_mutex.Init();
		assert(m_mutex.IsInitialized());
	}
	
	// Returns true if found
	bool getValue(u32 id, T &value)
	{
		if(id == 0)
			return false;
		JMutexAutoLock lock(m_mutex);
		if(m_id_to_value.size() < id)
			return false;
		value = m_id_to_value[id-1];
		return true;
	}
	
	// If id exists for value, returns the id.
	// Otherwise generates an id for the value.
	u32 getId(const T &value)
	{
		JMutexAutoLock lock(m_mutex);
		typename core::map<T, u32>::Node *n;
		n = m_value_to_id.find(value);
		if(n != NULL)
			return n->getValue();
		m_id_to_value.push_back(value);
		u32 new_id = m_id_to_value.size();
		m_value_to_id.insert(value, new_id);
		return new_id;
	}

private:
	JMutex m_mutex;
	// Values are stored here at id-1 position (id 1 = [0])
	core::array<T> m_id_to_value;
	core::map<T, u32> m_value_to_id;
};

/*
	FIFO queue (well, actually a FILO also)
*/
template<typename T>
class Queue
{
public:
	void push_back(T t)
	{
		m_list.push_back(t);
	}
	
	T pop_front()
	{
		if(m_list.size() == 0)
			throw ItemNotFoundException("Queue: queue is empty");

		typename core::list<T>::Iterator begin = m_list.begin();
		T t = *begin;
		m_list.erase(begin);
		return t;
	}
	T pop_back()
	{
		if(m_list.size() == 0)
			throw ItemNotFoundException("Queue: queue is empty");

		typename core::list<T>::Iterator last = m_list.getLast();
		T t = *last;
		m_list.erase(last);
		return t;
	}
ofs	hex dump	ascii
0000	89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 00 00 00 10 00 00 00 10 08 02 00 00 00 90 91 68	.PNG........IHDR...............h
0020	36 00 00 00 03 73 42 49 54 08 08 08 db e1 4f e0 00 00 00 09 70 48 59 73 00 00 0e c4 00 00 0e c4	6....sBIT.....O.....pHYs........
0040	01 95 2b 0e 1b 00 00 02 fb 49 44 41 54 28 91 3d c7 4b 6f 12 79 00 00 f0 61 fe f3 66 06 06 86 f7	..+......IDAT(.=.Ko.y...a..f....
0060	50 2c b6 94 d2 16 82 69 6d 34 a9 bb 4b d6 66 b3 4d 76 ad c6 c4 c4 78 f0 64 e2 c9 8f e0 cd 93 c9	P,.....im4..K.f.Mv....x.d.......
0080	7e 8a bd ec d1 dd 35 7a 31 8d b5 a2 b6 4a 7d d0 02 a5 e5 35 14 3a 30 0c 94 19 60 18 06 bc f9 bb	~.....5z1....J}....5.:0...`.....
00a0	fd 4c b7 1e 3a ed 0e 1b c9 c1 03 c3 a4 d4 7b 34 41 d5 1a cd f5 8d 78 b1 24 f1 56 6b c7 80 4e 4a	.L..:.........{4A.....x.$.Vk..NJ
00c0	05 1a 43 56 22 ab 47 c2 d7 62 f6 0c f6 46 58 55 d7 20 92 88 4f cf aa 65 e5 da 9a d7 41 5b 92 ef	..CV".G..b...FXU....O..e....A[..
00e0	0f ec 04 b9 ff be 54 3d e9 28 6a 3f 30 eb 4d 15 de 96 85 c6 18 f6 82 5b 0f e2 72 4b 6c 09 20 e0	......T=.(j?0.M........[..rKl...
0100	72 fb 17 83 62 a1 56 6f 4b de b9 c0 8b 7f d2 77 ef 5f 51 f4 ea de 4e 9b a4 26 f1 d5 79 dc 6c 43	r...b.VoK......w._Q...N..&..y.lC
0120	11 18 5c 4d 04 27 c4 c0 50 3b ef 76 0e 78 12 1d 42 00 57 24 ce e1 82 f5 b1 d0 d4 08 3b 31 13 46	..\M.'..P;.v.x..B.W$........;1.F
0140	26 26 42 16 95 fc be 5c 2e 9e c1 a7 dd 5c 21 27 43 93 36 83 f5 54 ad ea 63 e5 63 e1 fc cd eb 9d	&&B....\.....\!'C.6..T..c.c.....
0160	f5 3f 62 9c 47 f9 96 aa da 48 5b a5 28 c6 a2 4e 3b da f9 fd 66 04 90 01 94 33 93 c5 7c 8b 61 20	.?b.G....H[.(..N;...f....3..\|.a.
0180	ce c3 36 4b dd 7a 5b e1 e7 bc 66 d6 da d5 a1 5a 43 1e 18 06 45 8e 2d da ec 56 ea e8 b4 2d 81 c4	..6K.z[...f....ZC...E.-..V...-..
01a0	a6 e7 f2 a5 0b 95 aa 4a 23 c3 72 a9 93 4c f7 56 96 79 55 1a 75 cc 5d 74 d2 77 e0 56 08 37 1c 16	.......J#.r..L.V.yU.u.]t.w.V.7..
01c0	a2 ae ab 6b e1 65 bb c3 05 42 ab b8 a8 9c c7 23 31 d4 6e ea 89 4a 2c cc 97 fa da 66 e2 76 b7 af	...k.e...B.....#1.n..J,....f.v..
01e0	1c 66 ce c2 53 76 7f d8 b7 9b ac a5 de d6 64 55 40 98 11 f0 cd 10 8c 19 eb e9 03 ac 0f 4c 08 49	.f..Sv........dU@............L.I
0200	39 b9 51 5f ff b0 fd 89 40 b4 c5 28 fd cb 4f bf 3d 7d fc 5f 34 4e c2 b0 dd 3f 43 51 0c 09 6b 8a	9.Q_....@..(..O.=}._4N...?CQ..k.
0220	41 bb 1d 56 53 b8 d7 1b d9 82 96 e4 6e 8d 61 a8 e8 72 e8 28 2f 4d ea 96 97 cf b6 d7 16 50 5f c8	A..VS.......n.a..r.(/M.......P_.
0240	cf 4f 43 65 a1 85 52 1c 78 f4 24 96 de 13 f7 4f 72 53 8b 2e a7 99 88 47 79 8a 69 0b d5 a3 b1 da	.OCe..R.x.$....OrS.....Gy.i.....
0260	b7 b2 93 29 d7 78 77 5f 3c ce 95 c4 b3 c9 7c 64 16 c3 da 48 a5 26 5e e0 69 d7 34 4a 52 06 a2 b1	...).xw_<.....\|d...H.&^.i.4JR...
0280	1f 33 e9 9e 69 d8 c8 0d 5c 36 08 22 90 fc a1 ac 8d 75 3e e8 0d fa 3c 4c 90 7e f5 bf 00 67 33 aa	.3..i...\6.".....u>...<L.~...g3.
02a0	83 25 16 96 82 f9 cf 52 2a 97 71 fa b0 4e cb b8 b6 b1 82 23 c8 97 54 f5 59 52 ba 18 e2 8f 85 e1	.%.....R*.q..N.....#..T.YR......
02c0	cf 89 c4 df 7f ed 4e 4f c1 b0 21 1a 3f b2 78 89 4f 6d 0d 97 02 96 f2 a1 7c e3 ee 3d 0a c7 d6 af	......NO..!.?.x.Om......\|..=....
02e0	06 5e ed 9d 73 94 ed df e7 6f 7e dd 74 fb 42 7e 70 fd 8e b7 58 6a ce 44 81 2c e1 ac 0d 5f ba 6c	.^..s....o~.t.B~p...Xj.D.,..._.l
0300	31 61 48 a7 62 88 6a d3 c7 46 11 37 a7 9f 8b 3a 31 cc 1e 34 46 00 25 09 00 5c 21 90 c9 36 46 00	1aH.b.j..F.7...:1..4F.%..\!..6F.
0320	f5 07 e9 5a 51 2d 7e 69 e8 ba ee 74 f3 16 ab ba 97 ce 09 f5 d6 9f 9b f3 b9 6c 3b b6 e2 f4 30 9e	...ZQ-~i...t.............l;...0.
0340	42 a5 f2 1d 47 08 6d fc f5 a6 9d ec 00 00 00 00 49 45 4e 44 ae 42 60 82	B...G.m.........IEND.B`.