#ifndef PARTICLE_ID_HASH
#define PARTICLE_ID_HASH

//-
// ==========================================================================
// Copyright (C) 1995 - 2006 Autodesk, Inc. and/or its licensors.  All 
// rights reserved.
//
// The coded instructions, statements, computer programs, and/or related 
// material (collectively the "Data") in these files contain unpublished 
// information proprietary to Autodesk, Inc. ("Autodesk") and/or its 
// licensors, which is protected by U.S. and Canadian federal copyright 
// law and by international treaties.
//
// The Data is provided for use exclusively by You. You have the right 
// to use, modify, and incorporate this Data into other products for 
// purposes authorized by the Autodesk software license agreement, 
// without fee.
//
// The copyright notices in the Software and this entire statement, 
// including the above license grant, this restriction and the 
// following disclaimer, must be included in all copies of the 
// Software, in whole or in part, and all derivative works of 
// the Software, unless such copies or derivative works are solely 
// in the form of machine-executable object code generated by a 
// source language processor.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND. 
// AUTODESK DOES NOT MAKE AND HEREBY DISCLAIMS ANY EXPRESS OR IMPLIED 
// WARRANTIES INCLUDING, BUT NOT LIMITED TO, THE WARRANTIES OF 
// NON-INFRINGEMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR 
// PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE, OR 
// TRADE PRACTICE. IN NO EVENT WILL AUTODESK AND/OR ITS LICENSORS 
// BE LIABLE FOR ANY LOST REVENUES, DATA, OR PROFITS, OR SPECIAL, 
// DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES, EVEN IF AUTODESK 
// AND/OR ITS LICENSORS HAS BEEN ADVISED OF THE POSSIBILITY 
// OR PROBABILITY OF SUCH DAMAGES.
//
// ==========================================================================
//+

/*

	Separate chained hash table for mapping particle ids to sample points in 
	an efficient manner.  Since particle ID's may not be contiguous, an array 
	may need to be arbitrarily large to index on particle ID.  The hash table
	overcomes this limitation by allowing multiple ID's to match a single hash
	key.

*/

#include <maya/MPointArray.h>

class ParticleIdHash
{
private:

	// Element class for the hash table
	class ParticleSample
	{
	public:
		ParticleSample(int inId, MPoint& inPosition, ParticleSample* inNext) : 
			id(inId), position(inPosition), next(inNext) {}
		int id;					// Particle id
		MPoint position;		// Particle position
		ParticleSample* next;	// Next pointer for hash table
	};

public:
	// Constructor / Destructor
	ParticleIdHash(int inSize) : size(inSize) {
		if (size <= 0)
		{
			size = 1;	// Cannot have hash tables with 0 or less elements
		}
		data = new ParticleSample*[size];
		for (int i = 0; i < size; i++)
		{
			data[i] = NULL;
		}
	}
	~ParticleIdHash() {
		for (int i = 0; i < size; i++)
		{
			ParticleSample* sample = data[i];
			ParticleSample* prev = NULL;
			while (sample != NULL)
			{
				prev = sample;
				sample = sample->next;
				delete prev;
			}
		}
		delete [] data;
	}

	// Add the point to the head of the list at its hash value
	void insert(int id, MPoint& pt) {
		ParticleSample* sample = new ParticleSample(id,pt,data[id%size]);
		data[id%size] = sample;
	}
	// Get the list of points for the given id
	MPointArray getPoints(int id) {
		MPointArray result;
		ParticleSample* sample = data[id%size];
		while (sample != NULL)
		{
			if (sample->id == id)
			{
				result.append(sample->position);
			}
			sample = sample->next;
		}
		return result;
	}

private:
	ParticleSample** data;
	int size;
};

#endif