/*
 * Copyright (c) 2012-2020 Daniele Bartolini and individual contributors.
 * License: https://github.com/dbartolini/crown/blob/master/LICENSE
 */

using Gee;

namespace Crown
{
	public class Database
	{
		private enum Action
		{
			CREATE,
			DESTROY,
			SET_PROPERTY_NULL,
			SET_PROPERTY_BOOL,
			SET_PROPERTY_DOUBLE,
			SET_PROPERTY_STRING,
			SET_PROPERTY_GUID,
			SET_PROPERTY_VECTOR3,
			SET_PROPERTY_QUATERNION,
			ADD_TO_SET,
			REMOVE_FROM_SET,
			RESTORE_POINT
		}

		private struct RestorePoint
		{
			public int id;
			public uint32 size;
			public Guid[] data;
		}

		private class Stack
		{
			private uint8[] _data;
			private uint32 _read;

			public Stack()
			{
				_data = new uint8[1024*1024];
				_read = 0;
			}

			public void clear()
			{
				_read = 0;
			}

			public uint32 size()
			{
				return _read;
			}

			public void write_data(void* data, ulong len)
			{
				uint8* buf = (uint8*)data;
				for (ulong i = 0; i < len; ++i, ++_read)
					_data[_read] = buf[i];
			}

			public void write_bool(bool a)
			{
				write_data(&a, sizeof(bool));
			}

			public void write_int(int a)
			{
				write_data(&a, sizeof(int));
			}

			public void write_uint32(uint32 a)
			{
				write_data(&a, sizeof(uint32));
			}

			public void write_double(double a)
			{
				write_data(&a, sizeof(double));
			}

			public void write_string(string str)
			{
				uint32 len = str.length;
				write_data(&str.data[0], len);
				write_data(&len, sizeof(uint32));
			}

			public void write_guid(Guid a)
			{
				write_data(&a, sizeof(Guid));
			}

			public void write_vector3(Vector3 a)
			{
				write_data(&a, sizeof(Vector3));
			}

			public void write_quaternion(Quaternion a)
			{
				write_data(&a, sizeof(Quaternion));
			}

			public void write_action(Action t)
			{
				write_uint32((uint32)t);
			}

			public Action read_action()
			{
				_read -= (uint32)sizeof(uint32);
				uint32 a = *(uint32*)(&_data[_read]);
				return (Action)a;
			}

			public bool read_bool()
			{
				_read -= (uint32)sizeof(bool);
				bool a = *(bool*)(&_data[_read]);
				return a;
			}

			public int read_int()
			{
				_read -= (uint32)sizeof(int);
				int a = *(int*)(&_data[_read]);
				return a;
			}

			public uint32 read_uint32()
			{
				_read -= (uint32)sizeof(uint32);
				uint32 a = *(uint32*)(&_data[_read]);
				return a;
			}

			public double read_double()
			{
				_read -= (uint32)sizeof(double);
				double a = *(double*)(&_data[_read]);
				return a;
			}

			public Guid read_guid()
			{
				_read -= (uint32)sizeof(Guid);
				Guid a = *(Guid*)(&_data[_read]);
				return a;
			}

			public Vector3 read_vector3()
			{
				_read -= (uint32)sizeof(Vector3);
				Vector3 a = *(Vector3*)(&_data[_read]);
				return a;
			}

			public Quaternion read_quaternion()
			{
				_read -= (uint32)sizeof(Quaternion);
				Quaternion a = *(Quaternion*)(&_data[_read]);
				return a;
			}

			public string read_string()
			{
				_read -= (uint32)sizeof(uint32);
				uint32 len = *(uint32*)(&_data[_read]);
				_read -= len;
				uint8[] str = new uint8[len + 1];
				for (uint32 i = 0; i < len; ++i)
					str[i] = *(uint8*)(&_data[_read + i]);
				str[len] = '\0';
				return (string)str;
			}

			public void write_create_action(Guid id)
			{
				write_guid(id);
				write_action(Action.CREATE);
			}

			public void write_destroy_action(Guid id)
			{
				write_guid(id);
				write_action(Action.DESTROY);
			}

			public void write_set_property_null_action(Guid id, string key)
			{
				// No value to push
				write_string(key);
				write_guid(id);
				write_action(Action.SET_PROPERTY_NULL);
			}

			public void write_set_property_bool_action(Guid id, string key, bool val)
			{
				write_bool(val);
				write_string(key);
				write_guid(id);
				write_action(Action.SET_PROPERTY_BOOL);
			}

			public void write_set_property_double_action(Guid id, string key, double val)
			{
				write_double(val);
				write_string(key);
				write_guid(id);
				write_action(Action.SET_PROPERTY_DOUBLE);
			}

			public void write_set_property_string_action(Guid id, string key, string val)
			{
				write_string(val);
				write_string(key);
				write_guid(id);
				write_action(Action.SET_PROPERTY_STRING);
			}

			public void write_set_property_guid_action(Guid id, string key, Guid val)
			{
				write_guid(val);
				write_string(key);
				write_guid(id);
				write_action(Action.SET_PROPERTY_GUID);
			}

			public void write_set_property_vector3_action(Guid id, string key, Vector3 val)
			{
				write_vector3(val);
				write_string(key);
				write_guid(id);
				write_action(Action.SET_PROPERTY_VECTOR3);
			}

			public void write_set_property_quaternion_action(Guid id, string key, Quaternion val)
			{
				write_quaternion(val);
				write_string(key);
				write_guid(id);
				write_action(Action.SET_PROPERTY_QUATERNION);
			}

			public void write_add_to_set_action(Guid id, string key, Guid item_id)
			{
				write_guid(item_id);
				write_string(key);
				write_guid(id);
				write_action(Action.ADD_TO_SET);
			}

			public void write_remove_from_set_action(Guid id, string key, Guid item_id)
			{
				write_guid(item_id);
				write_string(key);
				write_guid(id);
				write_action(Action.REMOVE_FROM_SET);
			}

			public void write_restore_point(int id, uint32 size, Guid[] data)
			{
				uint32 num_guids = data.length;
				for (uint32 i = 0; i < num_guids; ++i)
					write_guid(data[i]);
				write_uint32(num_guids);
				write_uint32(size);
				write_int(id);
				write_action(Action.RESTORE_POINT);
			}

			public uint32 peek_type()
			{
				return *(uint32*)(&_data[_read - (uint32)sizeof(uint32)]);
			}

			public RestorePoint read_restore_point()
			{
				Action t = read_action();
				assert(t == Action.RESTORE_POINT);
				int id = read_int();
				uint32 size = read_uint32();
				uint32 num_guids = read_uint32();
				Guid[] ids = new Guid[num_guids];
				for (uint32 i = 0; i < num_guids; ++i)
					ids[i] = read_guid();
				return { id, size, ids };
			}
		}

		// Data
		private HashMap<string, Value?> _data;
		private Stack _undo;
		private Stack _redo;
		private Stack _undo_points;
		private Stack _redo_points;
		private bool _changed;

		// Signals
		public signal void key_changed(Guid id, string key);
		public signal void undo_redo(bool undo, int id, Guid[] data);

		public Database()
		{
			_data = new HashMap<string, Value?>();
			_undo = new Stack();
			_redo = new Stack();
			_undo_points = new Stack();
			_redo_points = new Stack();

			reset();
		}

		/// Resets database to clean state.
		public void reset()
		{
			_data.clear();
			_undo.clear();
			_redo.clear();
			_undo_points.clear();
			_redo_points.clear();

			_changed = false;

			// This is a special field which stores all objects
			_data.set("_objects", new HashMap<string, Value?>());
		}

		/// Returns whether the database has been changed since last call to Save().
		public bool changed()
		{
			return _changed;
		}

		/// Saves database to path without marking it as not changed.
		public void dump(string path)
		{
			Hashtable json = encode();
			SJSON.save(json, path);
		}

		/// Saves database to path.
		public void save(string path)
		{
			dump(path);
			_changed = false;
		}

		/// Loads database from path.
		public void load(string path)
		{
			Hashtable json = SJSON.load(path);
			decode(json);
			_changed = false;
		}

		private Hashtable encode()
		{
			return encode_object(GUID_ZERO, _data);
		}

		private static bool is_valid_value(Value? value)
		{
			return value == null
				|| value.holds(typeof(bool))
				|| value.holds(typeof(double))
				|| value.holds(typeof(string))
				|| value.holds(typeof(Guid))
				|| value.holds(typeof(Vector3))
				|| value.holds(typeof(Quaternion))
				;
		}

		private static bool is_valid_key(string key)
		{
			return key.length > 0
				&& key != "_objects"
				&& !key.has_prefix(".")
				&& !key.has_suffix(".")
				;
		}

#if 0
		private static string value_to_string(Value? value)
		{
			if (value == null)
				return "null";
			if (value.holds(typeof(bool)))
				return ((bool)value).to_string();
			if (value.holds(typeof(double)))
				return ((double)value).to_string();
			if (value.holds(typeof(string)))
				return ((string)value).to_string();
			if (value.holds(typeof(Guid)))
				return ((Guid)value).to_string();
			if (value.holds(typeof(Vector3)))
				return ((Vector3)value).to_string();
			if (value.holds(typeof(Quaternion)))
				return ((Quaternion)value).to_string();
			if (value.holds(typeof(HashSet)))
				return "Set<Guid>";

			return "<invalid>";
		}
#endif // CROWN_DEBUG

		public void decode(Hashtable json)
		{
			reset();
			decode_object(GUID_ZERO, "", json);
		}

		private void decode_object(Guid id, string db_key, Hashtable json)
		{
			string old_db = db_key;
			string k = db_key;

			string[] keys = json.keys.to_array();
			foreach (string key in keys)
			{
				assert(key != "_objects");
				if (key == "id")
					continue;

				Value? val = json[key];

				k += k == "" ? key : ("." + key);

				if (val.holds(typeof(Hashtable)))
				{
					Hashtable ht = (Hashtable)val;
					decode_object(id, k, ht);
				}
				else if (val.holds(typeof(ArrayList)))
				{
					ArrayList<Value?> arr = (ArrayList<Value?>)val;
					if (arr.size > 0 && arr[0].holds(typeof(double)))
						set_property_internal(id, k, decode_value(val));
					else
						decode_set(id, key, arr);
				}
				else
				{
					set_property_internal(id, k, decode_value(val));
				}

				k = old_db;
			}
		}

		private void decode_set(Guid id, string key, ArrayList<Value?> json)
		{
			// Set should be created even if it is empty.
			create_empty_set(id, key);

			for (int i = 0; i < json.size; ++i)
			{
				Hashtable obj = (Hashtable)json[i];
				Guid item_id = Guid.parse((string)obj["id"]);
				create_internal(item_id);
				decode_object(item_id, "", obj);
				add_to_set_internal(id, key, item_id);
			}
		}

		private Value? decode_value(Value? value)
		{
			if (value.holds(typeof(ArrayList)))
			{
				ArrayList<Value?> al = (ArrayList<Value?>)value;
				if (al.size == 3)
					return Vector3((double)al[0], (double)al[1], (double)al[2]);
				else if (al.size == 4)
					return Quaternion((double)al[0], (double)al[1], (double)al[2], (double)al[3]);
				else
					assert(false);
			}
			else if (value.holds(typeof(string)))
			{
				Guid id;
				if (Guid.try_parse((string)value, out id))
					return id;
				return value;
			}
			else if (value == null || value.holds(typeof(bool)) || value.holds(typeof(double)))
			{
				return value;
			}
			else
			{
				assert(false);
			}

			return null;
		}

		private Hashtable encode_object(Guid id, HashMap<string, Value?> db)
		{
			Hashtable obj = new Hashtable();
			if (id != GUID_ZERO)
				obj["id"] = id.to_string();

			string[] keys = db.keys.to_array();
			foreach (string key in keys)
			{
				if (key == "_objects")
					continue;

				// Since null-key is equivalent to non-existent key, skip serialization.
				if (db[key] == null)
					continue;

				string[] foo = key.split(".");
				Hashtable x = obj;
				if (foo.length > 1)
				{
					for (int i = 0; i < foo.length - 1; ++i)
					{
						string f = foo[i];

						if (x.has_key(f))
						{
							x = (Hashtable)x[f];
							continue;
						}

						Hashtable y = new Hashtable();
						x.set(f, y);
						x = y;
					}
				}
				x.set(foo[foo.length-1], encode_value(db[key]));
			}

			return obj;
		}

		private Value? encode_value(Value? value)
		{
			assert(is_valid_value(value) || value.holds(typeof(HashSet)));

			if (value.holds(typeof(Vector3)))
			{
				Vector3 v = (Vector3)value;
				ArrayList<Value?> arr = new Gee.ArrayList<Value?>();
				arr.add(v.x);
				arr.add(v.y);
				arr.add(v.z);
				return arr;
			}
			else if (value.holds(typeof(Quaternion)))
			{
				Quaternion q = (Quaternion)value;
				ArrayList<Value?> arr = new Gee.ArrayList<Value?>();
				arr.add(q.x);
				arr.add(q.y);
				arr.add(q.z);
				arr.add(q.w);
				return arr;
			}
			else if (value.holds(typeof(Guid)))
			{
				Guid id = (Guid)value;
				return id.to_string();
			}
			else if (value.holds(typeof(HashSet)))
			{
				HashSet<Guid?> hs = (HashSet<Guid?>)value;
				ArrayList<Value?> arr = new Gee.ArrayList<Value?>();
				foreach (Guid id in hs)
				{
					HashMap<string, Value?> objs = (HashMap<string, Value?>)_data["_objects"];
					arr.add(encode_object(id, (HashMap<string, Value?>)objs[id.to_string()]));
				}
				return arr;
			}
			else
			{
				return value;
			}
		}

		private HashMap<string, Value?> get_data(Guid id)
		{
			assert(has_object(id));

			return (HashMap<string, Value?>)(id == GUID_ZERO ? _data : ((HashMap<string, Value?>)_data["_objects"])[id.to_string()]);
		}

		private void create_internal(Guid id)
		{
			assert(id != GUID_ZERO);
#if 0
			stdout.printf("create %s\n", id.to_string());
#endif // CROWN_DEBUG
			((HashMap<string, Value?>)_data["_objects"]).set(id.to_string(), new HashMap<string, Value?>());

			_changed = true;
			key_changed(id, "_objects");
		}

		private void destroy_internal(Guid id)
		{
			assert(id != GUID_ZERO);
			assert(has_object(id));
#if 0
			stdout.printf("destroy %s\n", id.to_string());
#endif // CROWN_DEBUG
			((HashMap<string, Value?>)_data["_objects"]).unset(id.to_string());

			_changed = true;
			key_changed(id, "_objects");
		}

		private void set_property_internal(Guid id, string key, Value? value)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(value));
#if 0
			stdout.printf("set_property %s %s %s\n"
				, id.to_string()
				, key
				, (value == null) ? "null" : value_to_string(value)
				);
#endif // CROWN_DEBUG
			HashMap<string, Value?> ob = get_data(id);
			ob[key] = value;

			_changed = true;
			key_changed(id, key);
		}

		private void create_empty_set(Guid id, string key)
		{
			assert(has_object(id));
			assert(is_valid_key(key));

			HashMap<string, Value?> ob = get_data(id);
			assert(!ob.has_key(key));

			ob[key] = new HashSet<Guid?>(Guid.hash_func, Guid.equal_func);
		}

		private void add_to_set_internal(Guid id, string key, Guid item_id)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(item_id != GUID_ZERO);
			assert(has_object(item_id));
#if 0
			stdout.printf("add_to_set %s %s %s\n"
				, id.to_string()
				, key
				, item_id.to_string()
				);
#endif // CROWN_DEBUG
			HashMap<string, Value?> ob = get_data(id);

			if (!ob.has_key(key))
			{
				HashSet<Guid?> hs = new HashSet<Guid?>(Guid.hash_func, Guid.equal_func);
				hs.add(item_id);
				ob[key] = hs;
			}
			else
			{
				((HashSet<Guid?>)ob[key]).add(item_id);
			}

			_changed = true;
			key_changed(id, key);
		}

		private void remove_from_set_internal(Guid id, string key, Guid item_id)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(item_id != GUID_ZERO);
#if 0
			stdout.printf("remove_from_set %s %s %s\n"
				, id.to_string()
				, key
				, item_id.to_string()
				);
#endif // CROWN_DEBUG
			HashMap<string, Value?> ob = get_data(id);
			((HashSet<Guid?>)ob[key]).remove(item_id);

			_changed = true;
			key_changed(id, key);
		}

		public void create(Guid id)
		{
			assert(id != GUID_ZERO);
			assert(!has_object(id));

			_undo.write_destroy_action(id);
			_redo.clear();
			_redo_points.clear();

			create_internal(id);
		}

		public void destroy(Guid id)
		{
			assert(id != GUID_ZERO);
			assert(has_object(id));


			HashMap<string, Value?> o = get_data(id);
			string[] keys = o.keys.to_array();

			foreach (string key in keys)
			{
				Value? value = o[key];
				if (value.holds(typeof(HashSet)))
				{
					HashSet<Guid?> hs = (HashSet<Guid?>)value;
					Guid?[] ids = hs.to_array();
					foreach (Guid item_id in ids)
					{
						remove_from_set(id, key, item_id);
						destroy(item_id);
					}
				}
				else
				{
					set_property_null(id, key);
				}
			}

			_undo.write_create_action(id);
			_redo.clear();
			_redo_points.clear();

			destroy_internal(id);
		}

		public void set_property_null(Guid id, string key)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(null));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key) && ob[key] != null)
			{
				if (ob[key].holds(typeof(bool)))
					_undo.write_set_property_bool_action(id, key, (bool)ob[key]);
				if (ob[key].holds(typeof(double)))
					_undo.write_set_property_double_action(id, key, (double)ob[key]);
				if (ob[key].holds(typeof(string)))
					_undo.write_set_property_string_action(id, key, (string)ob[key]);
				if (ob[key].holds(typeof(Guid)))
					_undo.write_set_property_guid_action(id, key, (Guid)ob[key]);
				if (ob[key].holds(typeof(Vector3)))
					_undo.write_set_property_vector3_action(id, key, (Vector3)ob[key]);
				if (ob[key].holds(typeof(Quaternion)))
					_undo.write_set_property_quaternion_action(id, key, (Quaternion)ob[key]);
			}
			else
			{
				_undo.write_set_property_null_action(id, key);
			}

			_redo.clear();
			_redo_points.clear();

			set_property_internal(id, key, null);
		}

		public void set_property_bool(Guid id, string key, bool val)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(val));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key) && ob[key] != null)
				_undo.write_set_property_bool_action(id, key, (bool)ob[key]);
			else
				_undo.write_set_property_null_action(id, key);

			_redo.clear();
			_redo_points.clear();

			set_property_internal(id, key, val);
		}

		public void set_property_double(Guid id, string key, double val)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(val));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key) && ob[key] != null)
				_undo.write_set_property_double_action(id, key, (double)ob[key]);
			else
				_undo.write_set_property_null_action(id, key);

			_redo.clear();
			_redo_points.clear();

			set_property_internal(id, key, val);
		}

		public void set_property_string(Guid id, string key, string val)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(val));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key) && ob[key] != null)
				_undo.write_set_property_string_action(id, key, (string)ob[key]);
			else
				_undo.write_set_property_null_action(id, key);

			_redo.clear();
			_redo_points.clear();

			set_property_internal(id, key, val);
		}

		public void set_property_guid(Guid id, string key, Guid val)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(val));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key) && ob[key] != null)
				_undo.write_set_property_guid_action(id, key, (Guid)ob[key]);
			else
				_undo.write_set_property_null_action(id, key);

			_redo.clear();
			_redo_points.clear();

			set_property_internal(id, key, val);
		}

		public void set_property_vector3(Guid id, string key, Vector3 val)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(val));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key) && ob[key] != null)
				_undo.write_set_property_vector3_action(id, key, (Vector3)ob[key]);
			else
				_undo.write_set_property_null_action(id, key);

			_redo.clear();
			_redo_points.clear();

			set_property_internal(id, key, val);
		}

		public void set_property_quaternion(Guid id, string key, Quaternion val)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(is_valid_value(val));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key) && ob[key] != null)
				_undo.write_set_property_quaternion_action(id, key, (Quaternion)ob[key]);
			else
				_undo.write_set_property_null_action(id, key);

			_redo.clear();
			_redo_points.clear();

			set_property_internal(id, key, val);
		}

		public void add_to_set(Guid id, string key, Guid item_id)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(item_id != GUID_ZERO);
			assert(has_object(item_id));

			_undo.write_remove_from_set_action(id, key, item_id);
			_redo.clear();
			_redo_points.clear();

			add_to_set_internal(id, key, item_id);
		}

		public void remove_from_set(Guid id, string key, Guid item_id)
		{
			assert(has_object(id));
			assert(is_valid_key(key));
			assert(item_id != GUID_ZERO);

			_undo.write_add_to_set_action(id, key, item_id);
			_redo.clear();
			_redo_points.clear();

			remove_from_set_internal(id, key, item_id);
		}

		public bool has_object(Guid id)
		{
			return id == GUID_ZERO || ((HashMap<string, Value?>)_data["_objects"]).has_key(id.to_string());
		}

		public bool has_property(Guid id, string key)
		{
			return get_property(id, key) != null;
		}

		public Value? get_property(Guid id, string key)
		{
			assert(has_object(id));
			assert(is_valid_key(key));

			HashMap<string, Value?> ob = get_data(id);
			Value? value = (ob.has_key(key) ? ob[key] : null);
#if 0
			stdout.printf("get_property %s %s %s\n"
				, id.to_string()
				, key
				, (value == null) ? "null" : value_to_string(value)
				);
#endif // CROWN_DEBUG
			return value;
		}

		public bool get_property_bool(Guid id, string key)
		{
			return (bool)get_property(id, key);
		}

		public double get_property_double(Guid id, string key)
		{
			return (double)get_property(id, key);
		}

		public string get_property_string(Guid id, string key)
		{
			return (string)get_property(id, key);
		}

		public Guid get_property_guid(Guid id, string key)
		{
			return (Guid)get_property(id, key);
		}

		public Vector3 get_property_vector3(Guid id, string key)
		{
			return (Vector3)get_property(id, key);
		}

		public Quaternion get_property_quaternion(Guid id, string key)
		{
			return (Quaternion)get_property(id, key);
		}

		public HashSet<Guid?> get_property_set(Guid id, string key, HashSet<Guid?> deffault)
		{
			assert(has_object(id));
			assert(is_valid_key(key));

			HashMap<string, Value?> ob = get_data(id);
			if (ob.has_key(key))
				return ob[key] as HashSet<Guid?>;
			else
				return deffault;
#if 0
			// stdout.printf("get_property %s %s %s\n"
			// 	, id.to_string()
			// 	, key
			// 	, (value == null) ? "null" : value_to_string(value)
			// 	);
#endif // CROWN_DEBUG
		}

		public HashMap<string, Value?> get_object(Guid id)
		{
			return (HashMap<string, Value?>)get_data(GUID_ZERO)[id.to_string()];
		}

		public string[] get_keys(Guid id)
		{
			HashMap<string, Value?> data = get_data(id);
			return data.keys.to_array();
		}

		public void add_restore_point(int id, Guid[] data)
		{
#if 0
			stdout.printf("add_restore_point %d, undo size = %u\n", id, _undo.size());
#endif // CROWN_DEBUG
			_undo_points.write_restore_point(id, _undo.size(), data);

			_redo.clear();
			_redo_points.clear();
		}

		/// Duplicates the object specified by id and assign new_id to the duplicated object.
		public void duplicate(Guid id, Guid new_id)
		{
			assert(id != GUID_ZERO);
			assert(new_id != GUID_ZERO);
			assert(id != new_id);
			assert(has_object(id));

			create(new_id);

			HashMap<string, Value?> ob = get_data(id);
			string[] keys = ob.keys.to_array();
			foreach (string key in keys)
			{
				Value? val = ob[key];
				if (val.holds(typeof(HashSet)))
				{
					HashSet<Guid?> hs = (HashSet<Guid?>)val;
					foreach (Guid j in hs)
					{
						Guid x = Guid.new_guid();
						duplicate(j, x);
						add_to_set(new_id, key, x);
					}
				}
				else
				{
					if (ob[key] == null)
						set_property_null(new_id, key);
					if (ob[key].holds(typeof(bool)))
						set_property_bool(new_id, key, (bool)ob[key]);
					if (ob[key].holds(typeof(double)))
						set_property_double(new_id, key, (double)ob[key]);
					if (ob[key].holds(typeof(string)))
						set_property_string(new_id, key, (string)ob[key]);
					if (ob[key].holds(typeof(Guid)))
						set_property_guid(new_id, key, (Guid)ob[key]);
					if (ob[key].holds(typeof(Vector3)))
						set_property_vector3(new_id, key, (Vector3)ob[key]);
					if (ob[key].holds(typeof(Quaternion)))
						set_property_quaternion(new_id, key, (Quaternion)ob[key]);
				}
			}
		}

		/// Copies the database to db under the given new_key.
		public void copy_to(Database db, string new_key)
		{
			assert(db != null);
			assert(is_valid_key(new_key));

			copy_deep(db, GUID_ZERO, new_key);
		}

		public void copy_deep(Database db, Guid id, string new_key)
		{
			HashMap<string, Value?> ob = get_data(id);
			string[] keys = ob.keys.to_array();
			foreach (string key in keys)
			{
				if (key == "_objects")
					continue;

				Value? value = ob[key];
				if (value.holds(typeof(HashSet)))
				{
					HashSet<Guid?> hs = (HashSet<Guid?>)value;
					foreach (Guid j in hs)
					{
						db.create(j);
						copy_deep(db, j, "");
						db.add_to_set(id, new_key + (new_key == "" ? "" : ".") + key, j);
					}
				}
				else
				{
					string kk = new_key + (new_key == "" ? "" : ".") + key;

					if (ob[key] == null)
						db.set_property_null(id, kk);
					if (ob[key].holds(typeof(bool)))
						db.set_property_bool(id, kk, (bool)ob[key]);
					if (ob[key].holds(typeof(double)))
						db.set_property_double(id, kk, (double)ob[key]);
					if (ob[key].holds(typeof(string)))
						db.set_property_string(id, kk, (string)ob[key]);
					if (ob[key].holds(typeof(Guid)))
						db.set_property_guid(id, kk, (Guid)ob[key]);
					if (ob[key].holds(typeof(Vector3)))
						db.set_property_vector3(id, kk, (Vector3)ob[key]);
					if (ob[key].holds(typeof(Quaternion)))
						db.set_property_quaternion(id, kk, (Quaternion)ob[key]);
				}
			}
		}

		// Un-does the last action and returns its ID, or -1 if there is no
		// action to undo.
		public int undo()
		{
			if (_undo_points.size() == 0)
				return -1;

			RestorePoint rp = _undo_points.read_restore_point();
			_redo_points.write_restore_point(rp.id, _redo.size(), rp.data);
			undo_until(rp.size);
			undo_redo(true, rp.id, rp.data);
			return rp.id;
		}

		// Re-does the last action and returns its ID, or -1 if there is no
		// action to redo.
		public int redo()
		{
			if (_redo_points.size() == 0)
				return -1;

			RestorePoint rp = _redo_points.read_restore_point();
			_undo_points.write_restore_point(rp.id, _undo.size(), rp.data);
			redo_until(rp.size);
			undo_redo(false, rp.id, rp.data);
			return rp.id;
		}

		private void undo_until(uint32 size)
		{
			undo_redo_until(size, _undo, _redo);
		}

		private void redo_until(uint32 size)
		{
			undo_redo_until(size, _redo, _undo);
		}

		private void undo_redo_until(uint32 size, Stack undo, Stack redo)
		{
			while (undo.size() != size)
			{
				uint32 type = undo.peek_type();
				if (type == Action.CREATE)
				{
					Action t = undo.read_action();
					assert(t == Action.CREATE);

					Guid id = undo.read_guid();

					redo.write_destroy_action(id);
					create_internal(id);
				}
				else if (type == Action.DESTROY)
				{
					Action t = undo.read_action();
					assert(t == Action.DESTROY);

					Guid id = undo.read_guid();

					redo.write_create_action(id);
					destroy_internal(id);
				}
				else if (type == Action.SET_PROPERTY_NULL)
				{
					Action t = undo.read_action();
					assert(t == Action.SET_PROPERTY_NULL);

					Guid id = undo.read_guid();
					string key = undo.read_string();

					if (has_property(id, key))
					{
						if (get_data(id)[key].holds(typeof(bool)))
							redo.write_set_property_bool_action(id, key, get_property_bool(id, key));
						if (get_data(id)[key].holds(typeof(double)))
							redo.write_set_property_double_action(id, key, get_property_double(id, key));
						if (get_data(id)[key].holds(typeof(string)))
							redo.write_set_property_string_action(id, key, get_property_string(id, key));
						if (get_data(id)[key].holds(typeof(Guid)))
							redo.write_set_property_guid_action(id, key, get_property_guid(id, key));
						if (get_data(id)[key].holds(typeof(Vector3)))
							redo.write_set_property_vector3_action(id, key, get_property_vector3(id, key));
						if (get_data(id)[key].holds(typeof(Quaternion)))
							redo.write_set_property_quaternion_action(id, key, get_property_quaternion(id, key));
					}
					else
					{
						redo.write_set_property_null_action(id, key);
					}
					set_property_internal(id, key, null);
				}
				else if (type == Action.SET_PROPERTY_BOOL)
				{
					Action t = undo.read_action();
					assert(t == Action.SET_PROPERTY_BOOL);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					bool val = undo.read_bool();

					if (has_property(id, key))
						redo.write_set_property_bool_action(id, key, get_property_bool(id, key));
					else
						redo.write_set_property_null_action(id, key);
					set_property_internal(id, key, val);
				}
				else if (type == Action.SET_PROPERTY_DOUBLE)
				{
					Action t = undo.read_action();
					assert(t == Action.SET_PROPERTY_DOUBLE);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					double val = undo.read_double();

					if (has_property(id, key))
						redo.write_set_property_double_action(id, key, get_property_double(id, key));
					else
						redo.write_set_property_null_action(id, key);
					set_property_internal(id, key, val);
				}
				else if (type == Action.SET_PROPERTY_STRING)
				{
					Action t = undo.read_action();
					assert(t == Action.SET_PROPERTY_STRING);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					string val = undo.read_string();

					if (has_property(id, key))
						redo.write_set_property_string_action(id, key, get_property_string(id, key));
					else
						redo.write_set_property_null_action(id, key);
					set_property_internal(id, key, val);
				}
				else if (type == Action.SET_PROPERTY_GUID)
				{
					Action t = undo.read_action();
					assert(t == Action.SET_PROPERTY_GUID);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					Guid val = undo.read_guid();

					if (has_property(id, key))
						redo.write_set_property_guid_action(id, key, get_property_guid(id, key));
					else
						redo.write_set_property_null_action(id, key);
					set_property_internal(id, key, val);
				}
				else if (type == Action.SET_PROPERTY_VECTOR3)
				{
					Action t = undo.read_action();
					assert(t == Action.SET_PROPERTY_VECTOR3);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					Vector3 val = undo.read_vector3();

					if (has_property(id, key))
						redo.write_set_property_vector3_action(id, key, get_property_vector3(id, key));
					else
						redo.write_set_property_null_action(id, key);
					set_property_internal(id, key, val);
				}
				else if (type == Action.SET_PROPERTY_QUATERNION)
				{
					Action t = undo.read_action();
					assert(t == Action.SET_PROPERTY_QUATERNION);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					Quaternion val = undo.read_quaternion();

					if (has_property(id, key))
						redo.write_set_property_quaternion_action(id, key, get_property_quaternion(id, key));
					else
						redo.write_set_property_null_action(id, key);
					set_property_internal(id, key, val);
				}
				else if (type == Action.ADD_TO_SET)
				{
					Action t = undo.read_action();
					assert(t == Action.ADD_TO_SET);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					Guid item_id = undo.read_guid();

					redo.write_remove_from_set_action(id, key, item_id);
					add_to_set_internal(id, key, item_id);
				}
				else if (type == Action.REMOVE_FROM_SET)
				{
					Action t = undo.read_action();
					assert(t == Action.REMOVE_FROM_SET);

					Guid id = undo.read_guid();
					string key = undo.read_string();
					Guid item_id = undo.read_guid();

					redo.write_add_to_set_action(id, key, item_id);
					remove_from_set_internal(id, key, item_id);
				}
			}
		}
	}
}