// A refinement of the average case n^2 log n sorted-slope maximum collinear
// subset problem. The sort that groups identical slopes is replaced by a hash
// table. The solution has O(n^4) behavior, but should have order n^2
// average-case behavior.
//
// CS 306 - Computer Algorithms II
// Fall '08
#include <list>
#include <cstdlib>
#include <cassert>
#include <numeric>
#include "mcp-hashed.h"
// The hash table used to store the slopes.
class hash_table {
public:
// Add the given value to this hash table.
void
add(unsigned v) {
// This terrible hash function relies in the quality of the
// client's hash function, which, in this closed environment,
// is reasonable.
bucket & b = scatter_table[v % scatter_table.size()]
b.collision = b.collision
or (not b.keys.empty() and (b.keys.front() ≠ v))
b.keys.push_front(v)
}
// Create a hash table having the given number of buckets.
explicit
hash_table(unsigned s)
: scatter_table(std::vector<bucket>(s)) {
assert(s > 0)
}
// Return the count of the most frequently occuring key stored in this
// hash table. This method may remove keys from the table.
unsigned
max_slope_group_size() {
return std::accumulate(scatter_table.begin(), scatter_table.end(),
0, maxer())
}
private:
typedef std::list<unsigned> chain
typedef chain::iterator chain_iter
// The scatter-table element.
struct bucket {
// The keys hashing to this bucket.
chain keys
// True iff this bucket has had collisions (that is, the chain
// contains different key values).
bool collision
// Return a new empty bucket.
bucket() : collision(false) { }
}
std::vector<bucket> scatter_table
// A functor that finds the size of the largest group of identical keys
// in a chain. This functor may remove elements from the chain.
class maxer {
public:
// Return the larger of the given value or the size of the
// largest group of identical keys in the given bucket.
unsigned operator () (unsigned mx, const bucket & b) {
return std::max(
mx, b.collision ? max_group_size(b.keys) : b.keys.size())
}
private:
unsigned max_group_size(chain keys) {
// Return the size of the largest group of identical keys in
// the given chain.
unsigned mx = 0
while (not keys.empty()) {
// The key to be counted in this iteration.
const unsigned key = keys.front()
// The key that has just been examined.
chain_iter cur = keys.begin()
// The number of times the key has occured so far in the
// chain.
unsigned m = 1
while (true) {
// the next key to examine in the chain, if it exists.
chain_iter next = cur
if (++next == keys.end())
break
if (*next == key) {
m++
keys.erase(next)
}
else
cur = next
}
mx = std::max(mx, m)
keys.erase(keys.begin())
}
return mx
}
}
}
// The byte permutation used by the client-side hash function.
typedef unsigned char byte
static byte bp[256] = {
176, 100, 80, 28, 62, 104, 130, 49, 239, 255, 128, 164, 32, 216,
65, 68, 234, 17, 112, 153, 16, 13, 67, 230, 76, 26, 194, 55,
225, 198, 3, 107, 150, 167, 119, 200, 193, 161, 180, 189, 56, 36,
202, 83, 31, 195, 69, 89, 175, 64, 34, 178, 8, 197, 46, 60,
163, 222, 241, 96, 172, 78, 110, 99, 71, 188, 120, 136, 108, 27,
240, 224, 63, 156, 254, 115, 82, 38, 102, 140, 0, 132, 30, 66,
109, 12, 86, 201, 139, 59, 158, 85, 72, 148, 252, 20, 187, 245,
203, 135, 236, 248, 134, 218, 97, 183, 131, 121, 70, 6, 15, 18,
37, 159, 111, 249, 91, 160, 123, 33, 154, 185, 226, 247, 92, 209,
4, 151, 199, 113, 117, 219, 2, 74, 177, 231, 7, 44, 186, 125,
41, 174, 114, 61, 118, 168, 53, 235, 19, 94, 124, 22, 122, 155,
217, 207, 142, 47, 173, 84, 215, 88, 98, 79, 206, 29, 81, 184,
138, 126, 103, 145, 137, 11, 144, 208, 21, 105, 182, 221, 253, 170,
133, 191, 146, 5, 1, 93, 58, 51, 45, 213, 211, 39, 223, 75,
242, 127, 238, 143, 232, 101, 227, 141, 50, 220, 40, 205, 212, 243,
196, 181, 229, 192, 95, 24, 35, 116, 244, 129, 106, 190, 52, 77,
9, 90, 152, 157, 10, 214, 147, 87, 165, 48, 171, 149, 23, 179,
251, 43, 54, 166, 169, 57, 233, 204, 14, 210, 228, 25, 162, 237,
250, 73, 246, 42
}
// Deja vu c++ style;
static inline unsigned hash(const slope &)
static unsigned
max_col_pts(const point &, points_citer, const points_citer &)
namespace mcp_hashed {
void
init() {
}
unsigned
answer(const point_set & points) {
unsigned mx = 0
const points_citer e = points.end()
for (points_citer i = points.begin(); i ≠ e; i++)
mx = std::max(mx, max_col_pts(*i, i + 1, e))
return mx
}
}
static hash_table
get_slopes(const point & pt, points_citer b, const points_citer & e) {
// Return a hash table containing the hash values of the slopes between the
// given point and all the points in the range [b, e).
hash_table ht(((e - b) + 1)*10)
while (b ≠ e)
ht.add(hash(get_slope(pt, *b++)))
return ht
}
static byte
hash(int i, unsigned offset) {
// Return the hash value for the sum of the given integer and the given
// offset.
byte h = 0
for (unsigned j = 0; j < sizeof(int); j++) {
h ^= bp[(i + offset) & 0xff]
i >>= 8
}
return h
}
static unsigned
hash(int i) {
// Return the hash value for the given integer.
unsigned h = 0
for (unsigned j = 0; j < sizeof(int); j++)
h = (h << j*8) + hash(i, j)
return h
}
static inline unsigned
hash(const slope & s) {
// Return the hash value of the given point.
return hash(s.first) ^ hash(s.second)
}
static unsigned
max_col_pts(const point & pt, points_citer b, const points_citer & e) {
return get_slopes(pt, b, e).max_slope_group_size()
}
#ifdef MCPHASHEDTESTING
// g++ -o mcphashedtesting -g -DMCPHASHEDTESTING -ansi -pedantic -Wall mcp-hashed.cc mcp-common.cc && ./mcphashedtesting
int main() {
hash_table ht(100)
assert(ht.max_slope_group_size() == 0)
ht.add(1)
assert(ht.max_slope_group_size() == 1)
// The next test assumes the previous call to max_slope_group_size() hasn't
// removed any keys from the hash table.
ht.add(1)
assert(ht.max_slope_group_size() == 2)
// The next test assumes the keys used hash to the same bucket.
ht = hash_table(2)
ht.add(1)
ht.add(1)
ht.add(3)
ht.add(3)
assert(ht.max_slope_group_size() == 2)
ht.add(3)
assert(ht.max_slope_group_size() == 3)
}
#endif
// $Log:$
syntax highlighted by Code2HTML, v. 0.9.1