Code:
// Author: Piotr Tarsa
// License: Public Domain
//#define NDEBUG
#include <assert.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int32_t max(int32_t const a, int32_t const b) {
return a < b ? b : a;
}
bool equal(int32_t const a, int32_t const b, int32_t const c) {
return a == b && b == c;
}
void makeLogTable(uint8_t * const table, int32_t const length) {
assert(table != NULL);
assert(length >= 0);
if (length == 0)
return;
table[0] = 0;
for (int32_t i = 1; i < length; i++)
table[i] = 1 + table[i >> 1];
}
uint8_t computeLog(uint8_t(* const table)[256], uint32_t const value) {
if (value < 0x10000ul) {
if (value < 0x100ul)
return (*table)[value];
else
return (*table)[value >> 8] + 8;
} else {
if (value < 0x1000000ul)
return (*table)[value >> 16 & 0xff] + 16;
else
return (*table)[value >> 24 & 0xff] + 24;
}
}
typedef struct {
int32_t items;
int32_t *at;
} frequencies_t;
frequencies_t makeFrequencies(int32_t const items) {
frequencies_t frequencies;
frequencies.items = items;
frequencies.at = malloc(sizeof (int32_t) * items);
memset(frequencies.at, 0, sizeof (int32_t) * items);
return frequencies;
}
bool isNonDecreasing1(frequencies_t const * const frequencies) {
for (int32_t i = 0; i < frequencies->items; i++)
if (frequencies->at[i] < 0)
return false;
return true;
}
int32_t getFrequency1(frequencies_t const * const frequencies,
int32_t const item) {
assert(item >= 0);
assert(item < frequencies->items);
return frequencies->at[item];
}
void adjustFrequency1(frequencies_t * const frequencies,
int32_t const item, int32_t const value) {
assert(item >= 0);
assert(item < frequencies->items);
frequencies->at[item] += value;
}
int32_t getCumulativeInclusive1(frequencies_t const * const frequencies,
int32_t const item) {
assert(item >= 0);
assert(item < frequencies->items);
int32_t result = 0;
for (int32_t i = 0; i <= item; i++)
result += frequencies->at[i];
return result;
}
int32_t getTotal1(frequencies_t const * const frequencies) {
return getCumulativeInclusive1(frequencies, frequencies->items - 1);
}
int32_t getCumulativeExclusive1(frequencies_t const * const frequencies,
int32_t const item) {
assert(item >= 0);
assert(item < frequencies->items);
int32_t result = 0;
for (int32_t i = 0; i < item; i++)
result += frequencies->at[i];
return result;
}
void adjustRangeByValue1(frequencies_t * const frequencies,
int32_t const from, int32_t const to, int32_t const value) {
assert(from >= 0);
assert(from <= to);
assert(to < frequencies->items);
for (int32_t i = from; i <= to; i++)
frequencies->at[i] += value;
}
void rescale1(frequencies_t * const frequencies) {
for (int32_t i = 0; i < frequencies->items; i++)
frequencies->at[i] -= frequencies->at[i] >> 1;
}
int32_t findFirstInterval1(frequencies_t const * const frequencies,
int32_t const value) {
assert(value >= 0);
assert(value < getTotal1(frequencies));
assert(isNonDecreasing1(frequencies));
int32_t sum = 0;
for (int32_t i = 0; i < frequencies->items; i++)
if (frequencies->at[i] + sum > value)
return i;
else
sum += frequencies->at[i];
return frequencies->items - 1;
}
typedef struct {
int32_t items;
int32_t *at;
} cumulative_t;
cumulative_t makeCumulative(int32_t const items) {
cumulative_t cumulative;
cumulative.items = items;
cumulative.at = malloc(sizeof (int32_t) * items);
memset(cumulative.at, 0, sizeof (int32_t) * items);
return cumulative;
}
bool isNonDecreasing2(cumulative_t const * const cumulative) {
for (int32_t i = 1; i < cumulative->items; i++)
if (cumulative->at[i - 1] > cumulative->at[i])
return false;
return true;
}
int32_t getFrequency2(cumulative_t const * const cumulative,
int32_t const item) {
assert(item >= 0);
assert(item < cumulative->items);
return item == 0 ? cumulative->at[0] :
cumulative->at[item] - cumulative->at[item - 1];
}
void adjustFrequency2(cumulative_t * const cumulative,
int32_t const item, int32_t const value) {
assert(item >= 0);
assert(item < cumulative->items);
for (int32_t i = item; i < cumulative->items; i++)
cumulative->at[i] += value;
}
int32_t getCumulativeInclusive2(
cumulative_t const * const cumulative,
int32_t const item) {
assert(item >= 0);
assert(item < cumulative->items);
return cumulative->at[item];
}
int32_t getTotal2(
cumulative_t const * const cumulative) {
return getCumulativeInclusive2(cumulative, cumulative->items - 1);
}
int32_t getCumulativeExclusive2(
cumulative_t const * const cumulative,
int32_t const item) {
assert(item >= 0);
assert(item < cumulative->items);
return item == 0 ? 0 : cumulative->at[item - 1];
}
void adjustRangeByValue2(cumulative_t * const cumulative,
int32_t const from, int32_t const to, int32_t const value) {
assert(from >= 0);
assert(from <= to);
assert(to < cumulative->items);
for (int32_t i = from; i <= to; i++)
cumulative->at[i] += (i - from + 1) * value;
for (int32_t i = to + 1; i < cumulative->items; i++)
cumulative->at[i] += (to - from + 1) * value;
}
void rescale2(cumulative_t * const cumulative) {
int32_t prev = 0;
int32_t error = 0;
for (int32_t i = 0; i < cumulative->items; i++) {
error += (cumulative->at[i] - prev) & 1;
prev = cumulative->at[i];
cumulative->at[i] -= cumulative->at[i] - error >> 1;
}
}
int32_t findFirstInterval2(cumulative_t const * const cumulative,
int32_t const value) {
assert(value >= 0);
assert(value < getTotal2(cumulative));
assert(isNonDecreasing2(cumulative));
int32_t left = 0;
int32_t right = cumulative->items - 1;
while (left < right) {
int32_t const mid = left + right >> 1;
if (cumulative->at[mid] > value)
right = mid;
else
left = mid + 1;
}
return left;
}
typedef struct {
int32_t items;
int32_t *at;
} tree_t;
tree_t makeTree(int32_t const items) {
tree_t tree;
tree.items = items;
tree.at = malloc(sizeof (int32_t) * items);
memset(tree.at, 0, sizeof (int32_t) * items);
return tree;
}
bool isNonDecreasing3(tree_t const * const tree,
uint8_t(* const table)[256]) {
if (tree->items == 0)
return true;
int32_t const items = tree->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackValues[ilog];
int32_t next = 0;
for (int32_t i = 0; i < items; i++)
if (i % 2 == 0) {
if (tree->at[i] < 0)
return false;
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackValues[next] = tree->at[i];
next++;
} else
stackValues[next - 1] += tree->at[i];
} else {
if (tree->at[i] - stackValues[next - 1] < 0)
return false;
stackValues[next - 1] = tree->at[i];
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackValues[next - 2] += stackValues[next - 1];
next--;
}
}
return true;
}
int32_t getCumulativeInclusive3(tree_t const * const tree,
int32_t const item) {
assert(item >= 0);
assert(item < tree->items);
int32_t result = 0;
int32_t p = item + 1;
do {
result += tree->at[p - 1];
p &= p - 1;
} while (p > 0);
return result;
}
int32_t getTotal3(tree_t const * const tree) {
return getCumulativeInclusive3(tree, tree->items - 1);
}
int32_t getCumulativeExclusive3(tree_t const * const tree,
int32_t const item) {
assert(item >= 0);
assert(item < tree->items);
int32_t result = 0;
int32_t p = item;
while (p > 0) {
result += tree->at[p - 1];
p &= p - 1;
}
return result;
}
int32_t getFrequency3(tree_t const * const tree,
int32_t const item) {
assert(item >= 0);
assert(item < tree->items);
int32_t result = tree->at[item];
int32_t p = 1;
while ((item & p) > 0) {
result -= tree->at[item - p];
p <<= 1;
}
return result;
}
void adjustFrequency3(tree_t * const tree,
int32_t const item, int32_t const value) {
assert(item >= 0);
assert(item < tree->items);
int32_t p = item;
do {
tree->at[p] += value;
p |= p + 1;
} while (p < tree->items);
}
void adjustRangeByValue3(tree_t * const tree,
int32_t const from, int32_t const to, int32_t const value) {
assert(from >= 0);
assert(from <= to);
assert(to < tree->items);
for (int32_t i = from; i < to; i++)
tree->at[i] += (i - max(from, i & i + 1) + 1) * value;
int32_t p = to;
do {
tree->at[p] += (to - max(from, p & p + 1) + 1) * value;
p |= p + 1;
} while (p < tree->items);
}
void rescale3(tree_t * const tree,
uint8_t(* const table)[256]) {
int32_t const items = tree->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackOldValues[ilog];
int32_t stackNewValues[ilog];
int32_t next = 0;
for (int32_t i = 0; i < items; i++)
if (i % 2 == 0) {
int32_t const oldValue = tree->at[i];
/** Rescale function. */
int32_t const newValue = oldValue - oldValue / 2;
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackOldValues[next] = oldValue;
stackNewValues[next] = newValue;
next++;
} else {
stackOldValues[next - 1] += oldValue;
stackNewValues[next - 1] += newValue;
}
tree->at[i] = newValue;
} else {
int32_t const oldValue = tree->at[i] - stackOldValues[next - 1];
/** Rescale function. */
int32_t const newValue = oldValue - oldValue / 2;
tree->at[i] = stackNewValues[next - 1] + newValue;
stackOldValues[next - 1] += oldValue;
stackNewValues[next - 1] += newValue;
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackOldValues[next - 2] += stackOldValues[next - 1];
stackNewValues[next - 2] += stackNewValues[next - 1];
next--;
}
}
}
int32_t findFirstInterval3(tree_t const * const tree,
int32_t const value,
uint8_t(* const table)[256]) {
assert(value >= 0);
assert(value < getTotal3(tree));
assert(isNonDecreasing3(tree, table));
int32_t const items = tree->items;
int32_t result = 0;
int32_t sum = 0;
int32_t interval = items - 1;
while ((interval & interval - 1) > 0)
interval &= interval - 1;
while (interval > 0) {
if (result + interval < items &&
sum + tree->at[result + interval - 1] <= value) {
sum += tree->at[result + interval - 1];
result += interval;
}
interval >>= 1;
}
return result;
}
bool compare1(frequencies_t const * const frequencies,
cumulative_t const * const cumulatives) {
if (frequencies->items != cumulatives->items)
return false;
int32_t const items = frequencies->items;
int32_t sum = 0;
for (int32_t i = 0; i < items; i++) {
sum += frequencies->at[i];
if (sum != cumulatives->at[i])
return false;
}
return true;
}
bool compare2(frequencies_t const * const frequencies,
tree_t const * const tree,
uint8_t(* const table)[256]) {
if (frequencies->items != tree->items)
return false;
int32_t const items = frequencies->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackValues[ilog];
int32_t next = 0;
for (int32_t i = 0; i < items; i++)
if (i % 2 == 0) {
if (frequencies->at[i] != tree->at[i])
return false;
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackValues[next] = frequencies->at[i];
next++;
} else
stackValues[next - 1] += frequencies->at[i];
} else {
if (frequencies->at[i] + stackValues[next - 1] != tree->at[i])
return false;
stackValues[next - 1] += frequencies->at[i];
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackValues[next - 2] += stackValues[next - 1];
next--;
}
}
return true;
}
bool compare3(cumulative_t const * const cumulative,
tree_t const * const tree,
uint8_t(* const table)[256]) {
if (cumulative->items != tree->items)
return false;
int32_t const items = cumulative->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackValues[ilog];
int32_t prevCumulative = 0;
int32_t next = 0;
for (int32_t i = 0; i < items; i++) {
if (i % 2 == 0) {
if (cumulative->at[i] - prevCumulative != tree->at[i])
return false;
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackValues[next] = cumulative->at[i] - prevCumulative;
next++;
} else
stackValues[next - 1] += cumulative->at[i] - prevCumulative;
} else {
if (cumulative->at[i] - prevCumulative + stackValues[next - 1] !=
tree->at[i])
return false;
stackValues[next - 1] += cumulative->at[i] - prevCumulative;
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackValues[next - 2] += stackValues[next - 1];
next--;
}
}
prevCumulative = cumulative->at[i];
}
return true;
}
bool convertFrequenciesToCumulative(
frequencies_t const * const frequencies,
cumulative_t * const cumulative) {
if (frequencies->items != cumulative->items)
return false;
int32_t sum = 0;
for (int32_t i = 0; i < frequencies->items; i++) {
sum += frequencies->at[i];
cumulative->at[i] = sum;
}
return true;
}
bool convertFrequenciesToTree(
frequencies_t const * const frequencies,
tree_t * const tree,
uint8_t(* const table)[256]) {
if (frequencies->items != tree->items)
return false;
int32_t const items = frequencies->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackValues[ilog];
int32_t next = 0;
for (int32_t i = 0; i < items; i++)
if (i % 2 == 0) {
tree->at[i] = frequencies->at[i];
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackValues[next] = frequencies->at[i];
next++;
} else
stackValues[next - 1] += frequencies->at[i];
} else {
int32_t const newValue = frequencies->at[i] + stackValues[next - 1];
stackValues[next - 1] += frequencies->at[i];
tree->at[i] = newValue;
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackValues[next - 2] += stackValues[next - 1];
next--;
}
}
return true;
}
bool convertCumulativeToFrequencies(
cumulative_t const * const cumulative,
frequencies_t * const frequencies) {
if (frequencies->items != cumulative->items)
return false;
int32_t prev = 0;
for (int32_t i = 0; i < cumulative->items; i++) {
int32_t const current = cumulative->at[i];
frequencies->at[i] = current - prev;
prev = current;
}
return true;
}
bool convertCumulativeToTree(
cumulative_t const * const cumulative,
tree_t * const tree,
uint8_t(* const table)[256]) {
if (cumulative->items != tree->items)
return false;
int32_t const items = cumulative->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackValues[ilog];
int32_t prevCumulative = 0;
int32_t next = 0;
for (int32_t i = 0; i < items; i++) {
if (i % 2 == 0) {
int32_t const frequency = cumulative->at[i] - prevCumulative;
prevCumulative = cumulative->at[i];
tree->at[i] = frequency;
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackValues[next] = frequency;
next++;
} else
stackValues[next - 1] += frequency;
} else {
int32_t const frequency = cumulative->at[i] - prevCumulative;
prevCumulative = cumulative->at[i];
tree->at[i] = frequency + stackValues[next - 1];
stackValues[next - 1] += frequency;
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackValues[next - 2] += stackValues[next - 1];
next--;
}
}
}
return true;
}
bool convertTreeToFrequencies(
tree_t const * const tree,
frequencies_t * const frequencies,
uint8_t(* const table)[256]) {
if (tree->items != frequencies->items)
return false;
int32_t const items = tree->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackValues[ilog];
int32_t next = 0;
for (int32_t i = 0; i < items; i++)
if (i % 2 == 0) {
frequencies->at[i] = tree->at[i];
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackValues[next] = frequencies->at[i];
next++;
} else
stackValues[next - 1] += frequencies->at[i];
} else {
frequencies->at[i] = tree->at[i] - stackValues[next - 1];
stackValues[next - 1] += frequencies->at[i];
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackValues[next - 2] += stackValues[next - 1];
next--;
}
}
return true;
}
bool convertTreeToCumulative(
tree_t const * const tree,
cumulative_t * const cumulative,
uint8_t(* const table)[256]) {
if (tree->items != cumulative->items)
return false;
int32_t const items = tree->items;
int32_t const ilog = computeLog(table, items);
int32_t stackItems[ilog];
int32_t stackValues[ilog];
int32_t sum = 0;
int32_t next = 0;
for (int32_t i = 0; i < items; i++)
if (i % 2 == 0) {
int32_t const frequency = tree->at[i];
sum += frequency;
cumulative->at[i] = sum;
if (next == 0 || stackItems[next - 1] != i + 1) {
stackItems[next] = i + 1;
stackValues[next] = frequency;
next++;
} else
stackValues[next - 1] += frequency;
} else {
int32_t const frequency = tree->at[i] - stackValues[next - 1];
sum += frequency;
cumulative->at[i] = sum;
stackValues[next - 1] += frequency;
stackItems[next - 1] |= stackItems[next - 1] + 1;
if (next - 1 != 0 && stackItems[next - 2] == stackItems[next - 1]) {
stackValues[next - 2] += stackValues[next - 1];
next--;
}
}
return true;
}
int main(int argc, char const * * const argv) {
uint8_t logTable[256];
makeLogTable(logTable, 256);
srand(0);
for (int32_t length = 1; length < 1000; length++) {
frequencies_t frequencies = makeFrequencies(length);
cumulative_t cumulatives = makeCumulative(length);
tree_t tree = makeTree(length);
for (int32_t i = 0; i < 1000; i++) {
int32_t const key = rand() % length;
int32_t const value1 = rand() % 1000;
assert(equal(
getFrequency1(&frequencies, key),
getFrequency2(&cumulatives, key),
getFrequency3(&tree, key)));
adjustFrequency1(&frequencies, key, value1);
adjustFrequency2(&cumulatives, key, value1);
adjustFrequency3(&tree, key, value1);
assert(equal(
getCumulativeInclusive1(&frequencies, key),
getCumulativeInclusive2(&cumulatives, key),
getCumulativeInclusive3(&tree, key)));
int32_t const from = rand() % length;
int32_t const to = from + rand() % (length - from);
int32_t const value2 = rand() % 10;
adjustRangeByValue1(&frequencies, from, to, value2);
adjustRangeByValue2(&cumulatives, from, to, value2);
adjustRangeByValue3(&tree, from, to, value2);
assert(compare1(&frequencies, &cumulatives));
assert(compare2(&frequencies, &tree, &logTable));
assert(compare3(&cumulatives, &tree, &logTable));
if (value1 < value2) {
rescale1(&frequencies);
rescale2(&cumulatives);
rescale3(&tree, &logTable);
}
assert(equal(
getCumulativeExclusive1(&frequencies, key),
getCumulativeExclusive2(&cumulatives, key),
getCumulativeExclusive3(&tree, key)));
assert(equal(
getTotal1(&frequencies),
getTotal2(&cumulatives),
getTotal3(&tree)));
assert(isNonDecreasing1(&frequencies) ==
isNonDecreasing2(&cumulatives));
assert(isNonDecreasing2(&cumulatives) ==
isNonDecreasing3(&tree, &logTable));
int32_t const toFind = rand() % getTotal2(&cumulatives);
assert(findFirstInterval1(&frequencies, toFind) ==
findFirstInterval2(&cumulatives, toFind));
assert(findFirstInterval2(&cumulatives, toFind) ==
findFirstInterval3(&tree, toFind, &logTable));
switch (rand() % 100) {
case 0:
assert(convertFrequenciesToCumulative(&frequencies,
&cumulatives));
break;
case 1:
assert(convertFrequenciesToTree(&frequencies,
&tree, &logTable));
break;
case 2:
assert(convertCumulativeToFrequencies(&cumulatives,
&frequencies));
break;
case 3:
assert(convertCumulativeToTree(&cumulatives,
&tree, &logTable));
break;
case 4:
assert(convertTreeToFrequencies(&tree,
&frequencies, &logTable));
break;
case 5:
assert(convertTreeToCumulative(&tree,
&cumulatives, &logTable));
break;
case 6:
{
cumulative_t fakeCumulatives;
fakeCumulatives.items = frequencies.items;
fakeCumulatives.at = frequencies.at;
tree_t fakeTree;
fakeTree.items = frequencies.items;
fakeTree.at = frequencies.at;
assert(convertFrequenciesToCumulative(&frequencies,
&fakeCumulatives));
assert(convertCumulativeToTree(&fakeCumulatives,
&fakeTree, &logTable));
assert(convertTreeToFrequencies(&fakeTree,
&frequencies, &logTable));
}
break;
case 7:
{
tree_t fakeTree;
fakeTree.items = frequencies.items;
fakeTree.at = frequencies.at;
cumulative_t fakeCumulatives;
fakeCumulatives.items = frequencies.items;
fakeCumulatives.at = frequencies.at;
assert(convertFrequenciesToTree(&frequencies,
&fakeTree, &logTable));
assert(convertTreeToCumulative(&fakeTree,
&fakeCumulatives, &logTable));
assert(convertCumulativeToFrequencies(&fakeCumulatives,
&frequencies));
}
break;
}
}
}
puts("Assertions passed.");
return EXIT_SUCCESS;
}