//#####################################################################
// Copyright 2004-2005, Eran Guendelman, Geoffrey Irving.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class DYNAMIC_LIST
//#####################################################################
// Elements in this list are identified by persistent id's (assigned sequentially as elements are added to the list).
// At any given time, the set of active elements is a subset of all of the elements previously allocated.
// One typically accesses elements by their unique id using Element(id), but it is also possible to acccess them using their index in the list of currently active elements using Active_Element(index).
// The latter is less preferrable since this index is not persistent.
// The state of the dynamic list can be read/written at any time using Read/Write.
// Elements are destroyed when they become inactive using the Destroy_Element callback (implemented in derived classes).
//#####################################################################
#ifndef __DYNAMIC_LIST__
#define __DYNAMIC_LIST__

#include "../Arrays/LIST_ARRAY.h"
#include "../Read_Write/FILE_UTILITIES.h"
namespace PhysBAM
{

template<class T>
class DYNAMIC_LIST
{
protected:
	LIST_ARRAY<T> array; // active elements
	LIST_ARRAY<int> index_to_id_map, id_to_index_map;
	mutable LIST_ARRAY<int> needs_write; // by id
	int last_unique_id;

public:
	DYNAMIC_LIST()
		: last_unique_id (0)
	{}

	virtual ~DYNAMIC_LIST()
	{}

	virtual void Clean_Up_Memory()
	{
		for (int i = 1; i <= array.m; i++)
		{
			Destroy_Element (array (i), index_to_id_map (i));
		}

		array.Clean_Up_Memory();
		needs_write.Clean_Up_Memory();
		index_to_id_map.Clean_Up_Memory();
		id_to_index_map.Clean_Up_Memory();
		last_unique_id = 0;
	}

	T& Element (const int id)
	{
		return array (id_to_index_map (id));
	}

	const T& Element (const int id) const
	{
		return array (id_to_index_map (id));
	}

	int Element_Index (const int id) const
	{
		return id_to_index_map (id);
	}

	int Number_Of_Elements() const // including inactive elements
	{
		return last_unique_id;
	}

	bool Is_Active (const int id) const
	{
		return id <= id_to_index_map.m && id_to_index_map (id);
	}

	T& Active_Element (const int index)
	{
		return array (index);
	}

	const T& Active_Element (const int index) const
	{
		return array (index);
	}

	int Active_Element_Id (const int index) const
	{
		return index_to_id_map (index);
	}

	int Number_Of_Active_Elements() const
	{
		return array.m;
	}

	// returns id
	virtual int Add_Element (const T& element)
	{
		last_unique_id++;
		array.Append_Element (element);
		needs_write.Append_Element (last_unique_id);
		index_to_id_map.Append_Element (last_unique_id);
		id_to_index_map.Append_Element (array.m);
		assert (id_to_index_map.m == last_unique_id);
		return last_unique_id;
	}

	void Remove_Element (const int id)
	{
		int index = id_to_index_map (id);
		assert (index);
		Destroy_Element (array (index), id);
		id_to_index_map (id) = 0;
		array.Remove_Index_Lazy (index);
		index_to_id_map.Remove_Index_Lazy (index);

		if (index <= array.m) id_to_index_map (index_to_id_map (index)) = index;
	}

//#####################################################################
	template<class RW> void Read (const std::string& prefix, const int frame, LIST_ARRAY<int>& needs_init);
	template<class RW> void Write (const std::string& prefix, const int frame) const;
	virtual void Destroy_Element (T& element, const int id) = 0;
//#####################################################################
};
//#####################################################################
// Function Read
//#####################################################################
// Reads the set of active id's and updates the index<->id maps.
// needs_init is filled with id's of those elements which have become newly active and need to be iniitalized.
template<class T> template<class RW> void DYNAMIC_LIST<T>::
Read (const std::string& prefix, const int frame, LIST_ARRAY<int>& needs_init)
{
	needs_init.Reset_Current_Size_To_Zero();
	LIST_ARRAY<int> active_ids;
	char version;
	FILE_UTILITIES::Read_From_File<RW> (STRING_UTILITIES::string_sprintf ("%sactive_ids.%d", prefix.c_str(), frame), version, last_unique_id, active_ids);
	assert (version == 1);
	LIST_ARRAY<T> new_array;
	ARRAY<bool> element_copied (array.m);
	id_to_index_map.Resize_Array (last_unique_id);

	for (int i = 1; i <= active_ids.m; i++)
	{
		int index = id_to_index_map (active_ids (i));

		if (index)
		{
			new_array.Append_Element (array (index));
			element_copied (index) = true;
		}
		else
		{
			new_array.Append_Element (T());
			needs_init.Append_Element (active_ids (i));
		}
	}

	for (int i = 1; i <= array.m; i++) if (!element_copied (i)) Destroy_Element (array (i), index_to_id_map (i));

	index_to_id_map.Resize_Array (active_ids.m);
	LIST_ARRAY<int>::copy (0, id_to_index_map);

	for (int i = 1; i <= new_array.m; i++)
	{
		index_to_id_map (i) = active_ids (i);
		id_to_index_map (active_ids (i)) = i;
	}

	LIST_ARRAY<T>::exchange_arrays (array, new_array);
}
//#####################################################################
// Function Write
//#####################################################################
// Writes the set of active id's.
// needs_write indicates which elements have not been written since their creation, so derived classes should write those out (and reset the needs_write list).
template<class T> template<class RW> void DYNAMIC_LIST<T>::
Write (const std::string& prefix, const int frame) const
{
	const char version = 1;
	FILE_UTILITIES::Write_To_File<RW> (STRING_UTILITIES::string_sprintf ("%sactive_ids.%d", prefix.c_str(), frame), version, last_unique_id, index_to_id_map);

	for (int i = needs_write.m; i >= 1; i--) if (!id_to_index_map (needs_write (i))) needs_write.Remove_Index_Lazy (i); // handle case of new element which was removed without being written
}
//#####################################################################
}
#endif