continued with localization

7 files changed, 835 insertions, 0 deletions

diff --git a/src/base/tl/algorithms.hpp b/src/base/tl/algorithms.hpp
new file mode 100644
index 00000000..15e8e8a9
--- /dev/null
+++ b/src/base/tl/algorithms.hpp
@@ -0,0 +1,135 @@
+#ifndef TL_FILE_ALGORITHMS_HPP
+#define TL_FILE_ALGORITHMS_HPP
+
+#include "range.hpp"
+
+
+/*
+	insert 4
+	      v
+	1 2 3 4 5 6
+
+*/
+
+
+template<class R, class T>
+R partition_linear(R range, T value)
+{
+	concept_empty::check(range);
+	concept_forwarditeration::check(range);
+	concept_sorted::check(range);
+
+	for(; !range.empty(); range.pop_front())
+	{
+		if(!(range.front() < value))
+			return range;
+	}
+	return range;
+}
+
+
+template<class R, class T>
+R partition_binary(R range, T value)
+{
+	concept_empty::check(range);
+	concept_index::check(range);
+	concept_size::check(range);
+	concept_slice::check(range);
+	concept_sorted::check(range);
+	
+	if(range.empty())
+		return range;
+	if(range.back() < value)
+		return R();
+	
+	while(range.size() > 1)
+	{
+		unsigned pivot = (range.size()-1)/2;
+		if(range.index(pivot) < value)
+			range = range.slice(pivot+1, range.size()-1);
+		else
+			range = range.slice(0, pivot+1);
+	}
+	return range;
+}
+
+template<class R, class T>
+R find_linear(R range, T value)
+{
+	concept_empty::check(range);
+	concept_forwarditeration::check(range);
+	for(; !range.empty(); range.pop_front())
+		if(value < range.front())
+			break;
+	return range;
+}
+
+template<class R, class T>
+R find_binary(R range, T value)
+{
+	range = partition_linear(range, value);
+	if(range.empty()) return range;
+	if(range.front() == value) return range;
+	return R();
+}
+
+
+template<class R>
+void sort_bubble(R range)
+{
+	concept_empty::check(range);
+	concept_forwarditeration::check(range);
+	concept_backwarditeration::check(range);
+	
+	// slow bubblesort :/
+	for(; !range.empty(); range.pop_back())
+	{
+		R section = range;
+		typename R::type *prev = &section.front();
+		section.pop_front();
+		for(; !section.empty(); section.pop_front())
+		{
+			typename R::type *cur = &section.front();
+			if(*cur < *prev)
+				swap(*cur, *prev);
+			prev = cur;
+		}
+	}
+}
+
+/*
+template<class R>
+void sort_quick(R range)
+{
+	concept_index::check(range);
+}*/
+
+
+template<class R>
+void sort(R range)
+{
+	sort_bubble(range);
+}
+
+
+template<class R>
+bool sort_verify(R range)
+{
+	concept_empty::check(range);
+	concept_forwarditeration::check(range);
+	
+	typename R::type *prev = &range.front();
+	range.pop_front();
+	for(; !range.empty(); range.pop_front())
+	{
+		typename R::type *cur = &range.front();
+		
+		if(*cur < *prev)
+			return false;
+		prev = cur;
+	}
+	
+	return true;
+}
+
+#endif // TL_FILE_ALGORITHMS_HPP
diff --git a/src/base/tl/allocator.hpp b/src/base/tl/allocator.hpp
new file mode 100644
index 00000000..3baa1c19
--- /dev/null
+++ b/src/base/tl/allocator.hpp
@@ -0,0 +1,15 @@
+#ifndef TL_FILE_ALLOCATOR_HPP
+#define TL_FILE_ALLOCATOR_HPP
+
+template <class T>
+class allocator_default
+{
+public:
+	static T *alloc() { return new T; }
+	static void free(T *p) { delete p; }
+
+	static T *alloc_array(int size) { return new T [size]; }
+	static void free_array(T *p) { delete [] p; }
+};
+
+#endif // TL_FILE_ALLOCATOR_HPP
diff --git a/src/base/tl/array.hpp b/src/base/tl/array.hpp
new file mode 100644
index 00000000..7fa4ab1b
--- /dev/null
+++ b/src/base/tl/array.hpp
@@ -0,0 +1,341 @@
+#ifndef TL_FILE_ARRAY_HPP
+#define TL_FILE_ARRAY_HPP
+
+#include "range.hpp"
+#include "allocator.hpp"
+
+
+/*
+	Class: array
+		Normal dynamic array class
+	
+	Remarks:
+		- Grows 50% each time it needs to fit new items
+		- Use set_size() if you know how many elements 
+		- Use optimize() to reduce the needed space.
+*/
+template <class T, class ALLOCATOR = allocator_default<T> >
+class array : private ALLOCATOR
+{
+	void init()
+	{
+		list = 0x0;
+		clear();
+	}
+	
+public:
+	typedef plain_range<T> range;
+
+	/*
+		Function: array constructor
+	*/
+	array()
+	{
+		init();
+	}
+	
+	/*
+		Function: array copy constructor
+	*/
+	array(const array &other)
+	{
+		init();
+		set_size(other.size());
+		for(int i = 0; i < size(); i++)
+			(*this)[i] = other[i];
+	}
+
+
+	/*
+		Function: array destructor
+	*/
+	~array()
+	{
+		ALLOCATOR::free_array(list);
+		list = 0x0;
+	}
+
+
+	/*
+		Function: delete_all
+		
+		Remarks:
+			- Invalidates ranges
+	*/
+	void delete_all()
+	{
+		for(int i = 0; i < size(); i++)
+			delete list[i];
+		clear();
+	}
+
+
+	/*
+		Function: clear
+	
+		Remarks:
+			- Invalidates ranges
+	*/
+	void clear()
+	{
+		ALLOCATOR::free_array(list);
+		list_size = 1;
+		list = ALLOCATOR::alloc_array(list_size);
+		num_elements = 0;
+	}
+
+	/*
+		Function: size
+	*/
+	int size() const
+	{
+		return num_elements;
+	}
+
+	/*
+		Function: remove_index_fast
+
+		Remarks:
+			- Invalidates ranges
+	*/
+	void remove_index_fast(int index)
+	{
+		list[index] = list[num_elements-1];
+		set_size(size()-1);
+	}
+
+	/*
+		Function: remove_fast
+
+		Remarks:
+			- Invalidates ranges
+	*/
+	void remove_fast(const T& item)
+	{
+		for(int i = 0; i < size(); i++)
+			if(list[i] == item)
+			{
+				remove_index_fast(i);
+				return;
+			}
+	}
+
+	/*
+		Function: remove_index
+		
+		Remarks:
+			- Invalidates ranges
+	*/
+	void remove_index(int index)
+	{
+		for(int i = index+1; i < num_elements; i++)
+			list[i-1] = list[i];
+		
+		set_size(size()-1);
+	}
+
+	/*
+		Function: remove
+
+		Remarks:
+			- Invalidates ranges
+	*/
+	bool remove(const T& item)
+	{
+		for(int i = 0; i < size(); i++)
+			if(list[i] == item)
+			{
+				remove_index(i);
+				return true;
+			}
+		return false;
+	}
+
+	/*
+		Function: add
+			Adds an item to the array.
+		
+		Arguments:
+			item - Item to add.
+			
+		Remarks:
+			- Invalidates ranges
+			- See remarks about <array> how the array grows.
+	*/
+	int add(const T& item)
+	{
+		incsize();
+		set_size(size()+1);
+		list[num_elements-1] = item;
+		return num_elements-1;
+	}
+
+	/*
+		Function: insert
+			Inserts an item into the array at a specified location.
+			
+		Arguments:
+			item - Item to insert.		
+			r - Range where to insert the item
+
+		Remarks:
+			- Invalidates ranges
+			- See remarks about <array> how the array grows.
+	*/
+	int insert(const T& item, range r)
+	{
+		if(r.empty())
+			return add(item);
+			
+		int index = (int)(&r.front()-list);
+		incsize();
+		set_size(size()+1);
+		
+		for(int i = num_elements-1; i > index; i--)
+			list[i] = list[i-1];
+
+		list[index] = item;
+		
+		return num_elements-1;
+	}
+
+	/*
+		Function: operator[]
+	*/
+	T& operator[] (int index)
+	{
+		return list[index];
+	}
+
+	/*
+		Function: const operator[]
+	*/
+	const T& operator[] (int index) const
+	{
+		return list[index];
+	}
+
+	/*
+		Function: base_ptr
+	*/
+	T *base_ptr()
+	{
+		return list;
+	}
+
+	/*
+		Function: base_ptr
+	*/
+	const T *base_ptr() const
+	{
+		return list;
+	}
+
+	/*
+		Function: set_size
+			Resizes the array to the specified size.
+			
+		Arguments:
+			new_size - The new size for the array.
+	*/
+	void set_size(int new_size)
+	{
+		alloc(new_size);
+		num_elements = new_size;
+	}
+
+	/*
+		Function: hint_size
+			Allocates the number of elements wanted but
+			does not increase the list size.
+			
+		Arguments:
+			hint - Size to allocate.
+			
+		Remarks:
+			- If the hint is smaller then the number of elements, nothing will be done.
+			- Invalidates ranges
+	*/
+	void hint_size(int hint)
+	{
+		if(num_elements < hint)
+			alloc(hint);
+	}
+
+
+	/*
+		Function: optimize
+			Removes unnessasary data, returns how many bytes was earned.
+
+		Remarks:
+			- Invalidates ranges
+	*/
+	int optimize()
+	{
+		int before = memusage();
+		alloc(num_elements);
+		return before - memusage();
+	}
+
+	/*
+		Function: memusage
+			Returns how much memory this dynamic array is using
+	*/
+	int memusage()
+	{
+		return sizeof(array) + sizeof(T)*size;
+	}
+
+	/*
+		Function: operator=(array)
+
+		Remarks:
+			- Invalidates ranges
+	*/
+	array &operator = (const array &other)
+	{
+		set_size(other.size());
+		for(int i = 0; i < size(); i++)
+			(*this)[i] = other[i];
+		return *this;
+	}
+	
+	/*
+		Function: all
+			Returns a range that contains the whole array.
+	*/
+	range all() { return range(list, list+num_elements); }
+protected:
+
+	void incsize()
+	{
+		if(num_elements == list_size)
+		{
+			if(list_size < 2)
+				alloc(list_size+1);
+			else
+				alloc(list_size+list_size/2);
+		}		
+	}
+
+	void alloc(int new_len)
+	{
+		list_size = new_len;
+		T *new_list = ALLOCATOR::alloc_array(list_size);
+		
+		int end = num_elements < list_size ? num_elements : list_size;
+		for(int i = 0; i < end; i++)
+			new_list[i] = list[i];
+		
+		ALLOCATOR::free_array(list);
+
+		num_elements = num_elements < list_size ? num_elements : list_size;
+		list = new_list;
+	}
+
+	T *list;
+	int list_size;
+	int num_elements;
+};
+
+#endif // TL_FILE_ARRAY_HPP
diff --git a/src/base/tl/base.hpp b/src/base/tl/base.hpp
new file mode 100644
index 00000000..238cfaea
--- /dev/null
+++ b/src/base/tl/base.hpp
@@ -0,0 +1,15 @@
+
+#include <base/system.h>
+
+inline void assert(bool statement)
+{
+	dbg_assert(statement, "assert!");
+}
+
+template<class T>
+inline void swap(T &a, T &b)
+{
+	T c = b;
+	b = a;
+	a = c;
+}
diff --git a/src/base/tl/range.hpp b/src/base/tl/range.hpp
new file mode 100644
index 00000000..b55f235e
--- /dev/null
+++ b/src/base/tl/range.hpp
@@ -0,0 +1,230 @@
+#ifndef __RANGE_H
+#define __RANGE_H
+
+/*
+	Group: Range concepts
+*/
+
+/*
+	Concept: concept_empty
+		
+		template<class T>
+		struct range
+		{
+			bool empty() const;
+		};
+*/
+struct concept_empty
+{
+	template<typename T> static void check(T &t) { if(0) t.empty(); };
+};
+
+/*
+	Concept: concept_index
+		
+		template<class T>
+		struct range
+		{
+			T &index(size_t);
+		};
+*/
+struct concept_index
+{
+	template<typename T> static void check(T &t) { if(0) t.index(0); };
+};
+
+/*
+	Concept: concept_size
+		
+		template<class T>
+		struct range
+		{
+			size_t size();
+		};
+*/
+struct concept_size
+{
+	template<typename T> static void check(T &t) { if(0) t.size(); };
+};
+
+/*
+	Concept: concept_slice
+		
+		template<class T>
+		struct range
+		{
+			range slice(size_t start, size_t count);
+		};
+*/
+struct concept_slice
+{
+	template<typename T> static void check(T &t) { if(0) t.slice(0, 0); };
+};
+
+/*
+	Concept: concept_sorted
+		
+		template<class T>
+		struct range
+		{
+			void sorted();
+		};
+*/
+struct concept_sorted
+{
+	template<typename T> static void check(T &t) { if(0) t.sorted(); };
+};
+
+/*
+	Concept: concept_forwarditeration
+		Checks for the front and pop_front methods
+		
+		template<class T>
+		struct range
+		{
+			void pop_front();
+			T &front() const;
+		};		
+*/
+struct concept_forwarditeration
+{
+	template<typename T> static void check(T &t) { if(0) { t.front(); t.pop_front(); } };
+};
+
+/*
+	Concept: concept_backwarditeration
+		Checks for the back and pop_back methods
+		
+		template<class T>
+		struct range
+		{
+			void pop_back();
+			T &back() const;
+		};			
+*/
+struct concept_backwarditeration
+{
+	template<typename T> static void check(T &t) { if(0) { t.back(); t.pop_back(); } };
+};
+
+
+/*
+	Group: Range classes
+*/
+
+
+/*
+	Class: plain_range
+	
+	Concepts:
+		<concept_empty>
+		<concept_index>
+		<concept_slice>
+		<concept_forwardinteration>
+		<concept_backwardinteration>
+*/
+template<class T>
+class plain_range
+{
+public:
+	typedef T type;
+	plain_range()
+	{
+		begin = 0x0;
+		end = 0x0;
+	}
+
+	plain_range(const plain_range &r)
+	{
+		*this = r;
+	}
+		
+	plain_range(T *b, T *e)
+	{
+		begin = b;
+		end = e;
+	}
+	
+	bool empty() const { return begin >= end; }
+	void pop_front() { assert(!empty()); begin++; }
+	void pop_back() { assert(!empty()); end--; }
+	T& front() { assert(!empty()); return *begin; }
+	T& back() { assert(!empty()); return *(end-1); }
+	T& index(unsigned i) { assert(i >= 0 && i < (unsigned)(end-begin)); return begin[i]; }
+	unsigned size() const { return (unsigned)(end-begin); }
+	plain_range slice(unsigned startindex, unsigned endindex)
+	{
+		return plain_range(begin+startindex, begin+endindex);
+	}
+	
+protected:
+	T *begin;
+	T *end;
+};
+
+/*
+	Class: plain_range_sorted
+	
+	Concepts:
+		Same as <plain_range> but with these additions:
+		<concept_sorted>
+*/
+template<class T>
+class plain_range_sorted : public plain_range<T>
+{
+	typedef plain_range<T> parent;
+public:
+	/* sorted concept */
+	void sorted() const { }
+	
+	plain_range_sorted()
+	{}
+
+	plain_range_sorted(const plain_range_sorted &r)
+	{
+		*this = r;
+	}
+		
+	plain_range_sorted(T *b, T *e)
+	: parent(b, e)
+	{}
+	
+	plain_range_sorted slice(unsigned start, unsigned count)
+	{
+		return plain_range_sorted(parent::begin+start, parent::begin+start+count);
+	}
+};
+
+template<class R>
+class reverse_range
+{
+private:
+	reverse_range() {}
+public:
+	typedef typename R::type type;
+	
+	reverse_range(R r)
+	{
+		range = r;
+	}
+	
+	reverse_range(const reverse_range &other) { range = other.range; }
+	
+
+	bool empty() const { return range.empty(); }
+	void pop_front() { range.pop_back(); }
+	void pop_back() { range.pop_front(); }
+	type& front() { return range.back(); }
+	type& back() { return range.front(); }
+	
+	R range;
+};
+
+template<class R> reverse_range<R> reverse(R range) {
+   return reverse_range<R>(range);
+}
+template<class R> R reverse(reverse_range<R> range) {
+   return range.range;
+}
+
+#endif
diff --git a/src/base/tl/sorted_array.hpp b/src/base/tl/sorted_array.hpp
new file mode 100644
index 00000000..bb09aba9
--- /dev/null
+++ b/src/base/tl/sorted_array.hpp
@@ -0,0 +1,31 @@
+#ifndef TL_FILE_SORTED_ARRAY_HPP
+#define TL_FILE_SORTED_ARRAY_HPP
+
+#include "algorithms.hpp"
+#include "array.hpp"
+
+template <class T, class ALLOCATOR = allocator_default<T> >
+class sorted_array : public array<T, ALLOCATOR>
+{
+	typedef array<T, ALLOCATOR> parent;
+	
+	// insert and size is not allowed
+	int insert(const T& item, typename parent::range r) { dbg_break(); return 0; }
+	int set_size(int new_size) { dbg_break(); return 0; }
+		
+public:
+	typedef plain_range_sorted<T> range;
+
+	int add(const T& item)
+	{
+		return parent::insert(item, partition_binary(all(), item));
+	}
+
+	/*
+		Function: all
+			Returns a sorted range that contains the whole array.
+	*/	
+	range all() { return range(parent::list, parent::list+parent::num_elements); }
+};
+
+#endif // TL_FILE_SORTED_ARRAY_HPP
diff --git a/src/base/tl/string.hpp b/src/base/tl/string.hpp
new file mode 100644
index 00000000..2b164091
--- /dev/null
+++ b/src/base/tl/string.hpp
@@ -0,0 +1,68 @@
+#ifndef TL_FILE_STRING_HPP
+#define TL_FILE_STRING_HPP
+
+#include "base.hpp"
+#include "allocator.hpp"
+
+template<class ALLOCATOR >
+class string_base : private ALLOCATOR
+{
+	char *str;
+	int length;
+	
+	void reset()
+	{
+		str = 0; length = 0;
+	}
+	
+	void free()
+	{
+		ALLOCATOR::free_array(str);
+		reset();
+	}	
+	
+	void copy(const char *other_str, int other_length)
+	{
+		length = other_length;
+		str = ALLOCATOR::alloc_array(length+1);
+		mem_copy(str, other_str, length+1);
+	}
+		
+	void copy(const string_base &other)
+	{
+		if(!other.str)
+			return;
+		copy(other.str, other.length);
+	}
+	
+public:
+	string_base() { reset(); }
+	string_base(const char *other_str) { copy(other_str, str_length(other_str)); }
+	string_base(const string_base &other) { reset(); copy(other); }
+	~string_base() { free(); }
+	
+	string_base &operator = (const char *other)
+	{
+		free();
+		if(other)
+			copy(other, str_length(other));
+		return *this;
+	}
+	
+	string_base &operator = (const string_base &other)
+	{
+		free();
+		copy(other);
+		return *this;
+	}
+		
+	bool operator < (const char *other_str) const { return str_comp(str, other_str) < 0; }
+	operator const char *() const { return str; }
+	
+	const char *cstr() const { return str; }
+};
+
+/* normal allocated string */
+typedef string_base<allocator_default<char> > string;
+
+#endif // TL_FILE_STRING_HPP