//#####################################################################
// Copyright 2004, Ronald Fedkiw.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class LIST_ARRAY
//#####################################################################
#ifndef __LIST_ARRAY__
#define __LIST_ARRAY__

#include <assert.h>
#include "ARRAY.h"
namespace PhysBAM
{

template<class T>
class LIST_ARRAY
{
public:
	typedef T ELEMENT;

	ARRAY<T> array;
	int m; // the current size of the array (array.m may be larger for elbow room)

	LIST_ARRAY()
		: m (0)
	{}

	explicit LIST_ARRAY (const int m_input, const bool initialize_using_default_constructor = true)
		: array (m_input, initialize_using_default_constructor), m (m_input)
	{}

	explicit LIST_ARRAY (const ARRAY<T>& array_input)
		: array (array_input), m (array_input.m)
	{}

	LIST_ARRAY (std::istream& input_stream)
		: array (input_stream)
	{
		m = array.m;
	}

	~LIST_ARRAY()
	{}

	LIST_ARRAY<T>& operator= (const ARRAY<T>& source)
	{
		array = source;
		m = source.m;
		return *this;
	}

	LIST_ARRAY<T>& operator= (const LIST_ARRAY<T>& source)
	{
		array = source.array;
		m = source.m;
		return *this;
	}

	T& operator() (const int i)
	{
		assert (i <= m);
		return array (i);
	}

	const T& operator() (const int i) const
	{
		assert (i <= m);
		return array (i);
	}

	ARRAY_RANGE<LIST_ARRAY> Range (const VECTOR_2D<int>& range)
	{
		return ARRAY_RANGE<LIST_ARRAY> (*this, range);
	}

	ARRAY_RANGE<const LIST_ARRAY> Range (const VECTOR_2D<int>& range) const
	{
		return ARRAY_RANGE<const LIST_ARRAY> (*this, range);
	}

	T& Last_Element()
	{
		return (*this) (m);
	}

	const T& Last_Element() const
	{
		return (*this) (m);
	}

	void Get (const int i, T& element) const
	{
		assert (i <= m);
		array.Get (i, element);
	}

	void Set (const int i, const T& element1)
	{
		assert (i <= m);
		array.Set (i, element1);
	}

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

	void Compact()
	{
		if (m < array.m) Exact_Resize_Array (m);
	}

private:
	void Ensure_Enough_Space (const int m_new, const bool copy_existing_elements = true)
	{
		if (array.m < m_new) array.Resize_Array (4 * m_new / 3 + 2, false, copy_existing_elements);
	}

public:
	void Preallocate (const int max_size)
	{
		if (array.m < max_size) array.Resize_Array (max_size, false);
	}

	void Resize_Array (const int m_new, const bool initialize_new_elements = true, const bool copy_existing_elements = true)
	{
		Ensure_Enough_Space (m_new, copy_existing_elements);

		if (initialize_new_elements && m_new > m) for (int i = m + 1; i <= m_new; i++) array (i) = T();

		m = m_new;
	}

	void Exact_Resize_Array (const int m_new, const bool initialize_new_elements = true) // zero elbow room
	{
		array.Resize_Array (m_new, initialize_new_elements);
		m = array.m;
	}

	void Exact_Resize_Array2 (const int m_new, const bool initialize_new_elements = true) // zero elbow room
	{
		m = m_new;
	}

	void Append_Element (const T& element)
	{
		m++;
		Ensure_Enough_Space (m);
		array (m) = element;
	}

	void Append_Elements (const ARRAY<T>& append_array)
	{
		m += append_array.m;
		Ensure_Enough_Space (m);

		for (int i = 1; i <= append_array.m; i++) array (m - append_array.m + i) = append_array (i);
	}

	void Append_Elements (const LIST_ARRAY<T>& append_list)
	{
		m += append_list.m;
		Ensure_Enough_Space (m);

		for (int i = 1; i <= append_list.m; i++) array (m - append_list.m + i) = append_list.array (i);
	}

	void Append_Unique_Element (const T& element)
	{
		for (int i = 1; i <= m; i++) if (array (i) == element) return;

		Append_Element (element);
	}

	void Append_Unique_Elements (const ARRAY<T>& append_array)
	{
		for (int i = 1; i <= append_array.m; i++) Append_Unique_Element (append_array (i));
	}

	void Append_Unique_Elements (const LIST_ARRAY<T>& append_list)
	{
		for (int i = 1; i <= append_list.m; i++) Append_Unique_Element (append_list (i));
	}

	void Remove_End()
	{
		if (m)
		{
			array (m) = T();
			m--;
		}
	}

	void Remove_End_Without_Clearing_Value()
	{
		assert (m > 0);
		m--;
	}

	void Remove_Index (const int index) // preserves ordering of remaining elements
	{
		assert (1 <= index && index <= m);

		for (int i = index; i < m; i++) array (i) = array (i + 1);

		Remove_End();
	}

	void Remove_Indices (const ARRAY<int>& index)
	{
		if (index.m == 0) return;

		for (int kk = 1; kk <= index.m - 1; kk++)
		{
			assert (1 <= index (kk) && index (kk) <= m);

			for (int i = index (kk) + 1 - kk; i <= index (kk + 1) - 1 - kk; i++) (*this) (i) = (*this) (i + kk);
		}

		for (int i = index (index.m) + 1 - index.m; i <= m - index.m; i++) (*this) (i) = (*this) (i + index.m);

		m -= index.m;
	}

	void Remove_Index_Lazy (const int index)
	{
		assert (1 <= index && index <= m);

		if (index < m)
		{
			array (index) = array (m);
			array (m) = T();
		}
		else array (m) = T();

		m--;
	}

	void Remove_All_Entries (const bool reinitialize_entries = true)
	{
		if (reinitialize_entries) ARRAY<T>::copy (T(), array);

		m = 0;
	}

	void Reset_Current_Size_To_Zero() // doesn't actually remove entries or set them to zero
	{
		m = 0;
	}

	void Clean_Up_Memory()
	{
		Exact_Resize_Array (0);
	}

	void Delete_Pointers_And_Clean_Memory() // only valid if T is a pointer type
	{
		for (int i = 1; i <= m; i++) delete array (i);

		Clean_Up_Memory();
	}

	int Find (const T& element) const
	{
		for (int i = 1; i <= m; i++) if (array (i) == element) return i;

		return 0;
	}

	bool Find (const T& element, int& index) const
	{
		return Find (element, 1, index);
	}

	bool Find (const T& element, const int start_index, int& index) const // returns first occurence at or after start_index
	{
		for (int i = start_index; i <= m; i++) if (array (i) == element)
			{
				index = i;
				return true;
			}

		return false;
	}

	void Insert_Element (const T& element, const int index)
	{
		m++;
		Ensure_Enough_Space (m);

		for (int i = m; i > index; i--) array (i) = array (i - 1);

		array (index) = element;
	}

	void Pop (T& last_element)
	{
		Get (m, last_element);
		Remove_End();
	}

	int Count_Matches (const T& value) const
	{
		int count = 0;

		for (int index = 1; index <= m; index++) if (array (index) == value) count++;

		return count;
	}

	int Number_True() const
	{
		return Count_Matches (true);
	}

	int Number_False() const
	{
		return Count_Matches (false);
	}

	static void copy (const T& constant, LIST_ARRAY<T>& new_copy)
	{
		for (int index = 1; index <= new_copy.m; index++) new_copy.array.base_pointer[index] = constant;
	}

	static void copy (const LIST_ARRAY<T>& old_copy, LIST_ARRAY<T>& new_copy)
	{
		assert (old_copy.m == new_copy.m);
		copy_up_to (old_copy, new_copy, old_copy.m);
	}

	static void copy_up_to (const LIST_ARRAY<T>& old_copy, LIST_ARRAY<T>& new_copy, const int up_to_index)
	{
		assert (up_to_index <= old_copy.array.m && up_to_index <= new_copy.array.m);

		for (int index = 1; index <= up_to_index; index++) new_copy (index) = old_copy (index);
	}

	static T max (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::max (a.array, a.m);
	}

	static T maxabs (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::maxabs (a.array, a.m);
	}

	static T maxmag (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::maxmag (a.array, a.m);
	}

	static int argmax (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::argmax (a.array, a.m);
	}

	static T min (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::min (a.array, a.m);
	}

	static T minmag (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::minmag (a.array, a.m);
	}

	static int argmin (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::argmin (a.array, a.m);
	}

	static T sum (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::sum (a.array, a.m);
	}

	static T sumabs (const LIST_ARRAY<T>& a)
	{
		return ARRAY<T>::sumabs (a.array, a.m);
	}

	static T Maximum_Pairwise_Distance (const LIST_ARRAY<T>& a, const LIST_ARRAY<T>& b)
	{
		assert (a.m == b.m);
		T result = (T) 0;

		for (int index = 1; index <= a.m; index++) result = PhysBAM::max (result, fabs (a (index) - b (index)));

		return result;
	}

	template<class TS>
	static TS Maximum_Pairwise_Vector_Distance (const LIST_ARRAY<T>& a, const LIST_ARRAY<T>& b)
	{
		assert (a.m == b.m);
		return ARRAY<T>::template Maximum_Pairwise_Vector_Distance<TS> (a.array, b.array, a.m);
	}

	static void find_common_elements (const LIST_ARRAY<T>& a, const LIST_ARRAY<T>& b, LIST_ARRAY<T>& result)
	{
		assert (a.array.base_pointer != result.array.base_pointer);
		assert (b.array.base_pointer != result.array.base_pointer);
		result.Remove_All_Entries();
		int j;

		for (int i = 1; i <= a.m; i++) if (b.Find (a (i), j)) result.Append_Element (a (i));
	}

	static void exchange_arrays (LIST_ARRAY<T>& a, LIST_ARRAY<T>& b)
	{
		ARRAY<T>::exchange_arrays (a.array, b.array);
		exchange (a.m, b.m);
	}

	static void sort (LIST_ARRAY<T>& a)
	{
		ARRAY<T>::sort (a.array, a.m);
	}

	template<class T2>
	static void sort (LIST_ARRAY<T>& a, LIST_ARRAY<T2>& aux)
	{
		ARRAY<T>::sort (a.array, aux.array, a.m);
	}

	static void permute (const LIST_ARRAY<T>& source, LIST_ARRAY<T>& destination, const ARRAY<int>& permutation)
	{
		ARRAY<T>::permute (source.array, destination.array, permutation);
	}

	static void unpermute (const LIST_ARRAY<T>& source, LIST_ARRAY<T>& destination, const ARRAY<int>& permutation)
	{
		unpermute (source.array, permutation);
	}

	template<class RW>
	void Read (std::istream& input_stream)
	{
		array.template Read<RW> (input_stream);
		m = array.m;
	}

	template<class RW>
	void Write (std::ostream& output_stream) const
	{
		array.template Write_Prefix<RW> (output_stream, m);
	}

//#####################################################################
};
}
#endif