/*********************************************************
** Copyright (c) 2005
** University of Washington
** Licensed under the terms set forth by University of
** Washington. If you did not sign such a license, you
** are using this software/code illegally and you do not
** have permission to use, modify, or redistribute
** this or any files in this software package.
**
** File: CongaLine.h
**
**********************************************************/
#if 0
#ifndef CONGALINE_H
#define CONGALINE_H
// Test of closest pair algorithms
// David Eppstein, UC Irvine, 19 Apr 1997
//
// Modifications by Eva Monsen
//
// Conga line closest pair algorithm
//
// Keeps a partition of the points into subsets, with a graph
// for each subset computed as described in my paper.  Each graph is initially
// computed using a nearest-neighbor insertion process alternating between
// points in the subset and points in the whole database.
//
// Constructor takes as arg number of subsets to make; if omitted, uses
// ceil(log_2(n)).
//
// Total space: 42n + O(k) bytes (where k=number of subsets, normally O(log n)).
// Time per insertion: O(n log(n/k)) amortized
// Time per deletion: O(n log(n/k)) expected, O(nk log(n/k)) worst case amortized
//
// Time per closest pair: O(n).

#include "Cluster.h"

// how many subsets can we have? need to leave one for scratch, one for inactive
#define MaxCongaSubsets 65534L

class CCongaLine {
 	CDistanceFunction & dist;				// how to compare two points
 	unsigned long max_points;
 	
 	typedef unsigned short CongaSubset;
	// 	SortedArray subset_sizes;		// list of subset sizes
 	int* subset_sizes;		// list of subset sizes
	CongaSubset how_many_subsets;

 	typedef CClusterNode* point;

 	typedef struct { point in, out; double d; CongaSubset s; } CongaEdge;
 	CongaEdge * edges;				// list of all edges in graph
 	unsigned long how_many_edges;

	CongaSubset * subsets;			// which subset is each point in?
	point * scratch;
	
	void FixWhat(point);			// update subset_sizes prior to removing pt
	void AddEdge(point, point, double, CongaSubset); // add an edge to the graph
	void RemoveEdge(unsigned long);			// remove edge w/given index
	void MoveToSubset(point, CongaSubset);	// move point to new subset
	void CleanAllGraphs();					// remove non-inter-subset edges
	
	unsigned long NeighborInList(point pt, point * ptlist, unsigned long listlen,
		double & d); // return dist & list pos of nearest nbr in list to pt
	void FindSubsetEdges(CongaSubset);	// recompute edges in subset
	void MergeSubsets(CongaSubset,CongaSubset);	// combine subsets
	CongaSubset FindFreeSubset();	// where can I put this newly inserted pt?
	void MadeNewSubset(CongaSubset, unsigned long);	// make edges etc

	int gInsertions;
	int gDeletions;
	int gPairs;

 public:
 	~CCongaLine();
 	CCongaLine(long np, long mp, CDistanceFunction & d, long how_many_subs = 0);
 	void InsertPoint(point);
 	void DeletePoint(point);
 	double GetClosestPair(point & a, point & b);
	// 	void UpdatePoint(point);
	// 	void UpdateDistance(point,point);
};
#endif
#endif
