// 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