// Test of closest pair algorithms
// David Eppstein, UC Irvine, 19 Apr 1997
//
// Sorted array subroutine for conga line data structure subset sizes
// Since there are few (O(log n)) subsets, we are best off avoiding
// complicated binary search trees etc, and just using a sorted array.
//
// This is an object that acts like a normal array, except that
// after changing an array entry you are supposed to call Update(),
// and it will allow you to look up the min. array element or the
// pair of elements having sizes with the smallest ratio.
// For technical reasons involving the constructor of CongaLine,
// the SortedArray constructor does little; instead call Allocate later.

#ifndef SORTED_ARRAY_H
#define SORTED_ARRAY_H

class SortedArray {
	unsigned long * values;
	unsigned long * where_are_the_values;
	unsigned long * sorted_indices;
	unsigned long array_size;
	void Swap(unsigned long i);
	double SizeRatio(unsigned long i);

 public:
 	unsigned long & operator[] (unsigned long i);
 	void Update(unsigned long i);
 	unsigned long MinValue();
 	void MinRatio(unsigned long &, unsigned long &);

 	void Allocate(unsigned long arraysize);
 	SortedArray() { array_size = 0; }
 	~SortedArray() { Allocate(0); }
};

#endif