#ifndef PARTICLE_ID_HASH
#define PARTICLE_ID_HASH

//-
// ==========================================================================
// Copyright (C) 1995 - 2005 Alias Systems Corp. and/or its licensors.  All 
// rights reserved. 
// 
// The coded instructions, statements, computer programs, and/or related 
// material (collectively the "Data") in these files are provided by Alias 
// Systems Corp. ("Alias") and/or its licensors for the exclusive use of the 
// Customer (as defined in the Alias Software License Agreement that 
// accompanies this Alias software). Such Customer has the right to use, 
// modify, and incorporate the Data into other products and to distribute such 
// products for use by end-users.
//  
// THE DATA IS PROVIDED "AS IS".  ALIAS HEREBY DISCLAIMS ALL WARRANTIES 
// RELATING TO THE DATA, INCLUDING, WITHOUT LIMITATION, ANY AND ALL EXPRESS OR 
// IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND/OR FITNESS FOR A 
// PARTICULAR PURPOSE. IN NO EVENT SHALL ALIAS BE LIABLE FOR ANY DAMAGES 
// WHATSOEVER, WHETHER DIRECT, INDIRECT, SPECIAL, OR PUNITIVE, WHETHER IN AN 
// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, OR IN EQUITY, 
// ARISING OUT OF ACCESS TO, USE OF, OR RELIANCE UPON THE DATA.
// ==========================================================================
//+

/*

	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