FenwickTree.java

packagecom.jwetherell.algorithms.data_structures;

importjava.math.BigDecimal;
importjava.math.BigInteger;
importjava.util.ArrayList;
importjava.util.List;

/**
 * A Fenwick tree or binary indexed tree is a data structure providing efficient methods 
 * for calculation and manipulation of the prefix sums of a table of values. Fenwick trees 
 * primarily solve the problem of balancing prefix sum calculation efficiency with element 
 * modification efficiency. 
 * <p>
 * This class is meant to be somewhat generic, all you'd have to do is extend
 * the Data abstract class to store your custom data. I've included a range sum
 * implementations.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Fenwick_tree">Fenwick Tree (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
@SuppressWarnings("unchecked")
publicclassFenwickTree<DextendsFenwickTree.Data> {

privateObject[] array;

publicFenwickTree(List<D> data) {
// Find the largest index
intn = 0;
for (Datad : data)
if (d.index > n)
n = d.index;
n = next(n+1);
array = newObject[n];

// Add the data
for (Dd : data)
update(d.index, d);
 }

/**
 * Stabbing query
 * 
 * @param index
 * index for query
 * @return data at index.
 */
publicDquery(intindex) {
returnquery(index, index);
 }

/**
 * Range query
 * 
 * @param start
 * start of range (inclusive)
 * @param end
 * end of range (inclusive)
 * @return data for range.
 */
publicDquery(intstart, intend) {
finalDe = lookup(end);
finalDs = lookup(start-1);
finalDc = (D) e.copy();
if (s != null)
c.separate(s);
returnc;
 }

privateDlookup(intindex) {
index++; // tree index is 1 based
index = Math.min(array.length - 1, index);
if (index <= 0)
returnnull;

Dres = null;
while (index > 0) {
if (res == null) {
finalDdata = (D) array[index];
if (data != null)
res = (D) data.copy();
 } else{ 
res.combined((D) array[index]);
 }
index = prev(index);
 }
returnres;
 }

privatevoidupdate(intindex, Dvalue) {
index++; // tree index is 1 based
while (index < array.length) {
Ddata = (D) array[index];
if (data == null) {
data = (D) value.copy();
data.index = index;
array[index] = data;
 } else {
data.combined(value);
 }
index = next(index);
 }
 }

privatestaticfinalintprev(intx) {
returnx & (x - 1);
 }

privatestaticfinalintnext(intx) {
return2 * x - prev(x);
 }

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
finalStringBuilderbuilder = newStringBuilder();
builder.append(FenwickTreePrinter.getString(this));
returnbuilder.toString();
 }

protectedstaticclassFenwickTreePrinter {

publicstatic <DextendsFenwickTree.Data> StringgetString(FenwickTree<D> tree) {
if (tree.array.length == 0)
return"Tree has no nodes.";

finalDfirst = (D) tree.array[1];
if (first == null)
return"Tree has no nodes.";

finalStringBuilderbuilder = newStringBuilder();
builder.append("└── dummy \n");
builder.append(getString(tree, 0, tree.array.length, "", true));
returnbuilder.toString();
 }

privatestatic <DextendsFenwickTree.Data> StringgetString(FenwickTree<D> tree, intstart, intend, Stringprefix, booleanisTail) {
if (end > tree.array.length || (end - start == 0))
return"";

finalStringBuilderbuilder = newStringBuilder();

finalDvalue = (D) tree.array[start];
if (value != null)
builder.append(prefix + (isTail ? "└── " : "├── ") + value + "\n");

intnext = start + 1;
finalList<Integer> children = newArrayList<Integer>(2);
while (next < end) {
children.add(next);
next = next(next);
 }
for (inti = 0; i < children.size() - 1; i++)
builder.append(getString(tree, children.get(i), children.get(i+1), prefix + (isTail ? " " : "│ "), false));
if (children.size() >= 1)
builder.append(getString(tree, children.get(children.size()-1), end, prefix + (isTail ? " " : "│ "), true));

returnbuilder.toString();
 }
 }

publicabstractstaticclassDataimplementsComparable<Data> {

protectedintindex = Integer.MIN_VALUE;

/**
 * Constructor for data at index.
 * 
 * @param index
 * of data.
 */
protectedData(intindex) {
this.index = index;
 }

/**
 * Clear the indices.
 */
publicvoidclear() {
index = Integer.MIN_VALUE;
 }

/**
 * Combined this data with the Data parameter.
 * 
 * @param data
 * to combined with.
 * @return Data which represents the combination.
 */
publicabstractDatacombined(Datadata);

/**
 * Separate this data with the Data parameter.
 * 
 * @param data
 * to separate with.
 * @return Data which represents the combination.
 */
publicabstractDataseparate(Datadata);

/**
 * Deep copy of data.
 * 
 * @return deep copy.
 */
publicabstractDatacopy();

/**
 * Query inside this data object.
 * 
 * @param startOfRange
 * of range to query for.
 * @param endOfRange
 * of range to query for.
 * @return Data queried for or NULL if it doesn't match the query.
 */
publicabstractDataquery(longstartOfRange, longendOfRange);

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
finalStringBuilderbuilder = newStringBuilder();
builder.append("[").append(index).append("]");
returnbuilder.toString();
 }

/**
 * {@inheritDoc}
 */
@Override
publicintcompareTo(Datad) {
if (this.index < d.index)
return -1;
if (d.index < this.index)
return1;
return0;
 }

/**
 * Data structure representing sum of the range.
 */
publicstaticfinalclassRangeSumData<NextendsNumber> extendsData {

publicNsum = null;

publicRangeSumData(intindex, Nnumber) {
super(index);

this.sum = number;
 }

/**
 * {@inheritDoc}
 */
@Override
publicvoidclear() {
super.clear();

sum = null;
 }

/**
 * {@inheritDoc}
 */
@Override
publicDatacombined(Datadata) {
RangeSumData<N> q = null;
if (datainstanceofRangeSumData) {
q = (RangeSumData<N>) data;
this.combined(q);
 }
returnthis;
 }

/**
 * {@inheritDoc}
 */
@Override
publicDataseparate(Datadata) {
RangeSumData<N> q = null;
if (datainstanceofRangeSumData) {
q = (RangeSumData<N>) data;
this.separate(q);
 }
returnthis;
 }

/**
 * Combined range sum data.
 * 
 * @param data
 * resulted from combination.
 */
privatevoidcombined(RangeSumData<N> data) {
if (this.sum == null && data.sum == null)
return;
elseif (this.sum != null && data.sum == null)
return;
elseif (this.sum == null && data.sum != null)
this.sum = data.sum;
else {
/* TODO: This is ugly and how to handle number overflow? */
if (this.suminstanceofBigDecimal || data.suminstanceofBigDecimal) {
BigDecimalresult = ((BigDecimal)this.sum).add((BigDecimal)data.sum);
this.sum = (N)result;
 } elseif (this.suminstanceofBigInteger || data.suminstanceofBigInteger) {
BigIntegerresult = ((BigInteger)this.sum).add((BigInteger)data.sum);
this.sum = (N)result;
 } elseif (this.suminstanceofLong || data.suminstanceofLong) {
Longresult = (this.sum.longValue() + data.sum.longValue());
this.sum = (N)result;
 } elseif (this.suminstanceofDouble || data.suminstanceofDouble) {
Doubleresult = (this.sum.doubleValue() + data.sum.doubleValue());
this.sum = (N)result;
 } elseif (this.suminstanceofFloat || data.suminstanceofFloat) {
Floatresult = (this.sum.floatValue() + data.sum.floatValue());
this.sum = (N)result;
 } else {
// Integer
Integerresult = (this.sum.intValue() + data.sum.intValue());
this.sum = (N)result;
 }
 }
 }

/**
 * Separate range sum data.
 * 
 * @param data
 * resulted from combination.
 */
privatevoidseparate(RangeSumData<N> data) {
if (this.sum == null && data.sum == null)
return;
elseif (this.sum != null && data.sum == null)
return;
elseif (this.sum == null && data.sum != null)
this.sum = data.sum;
else {
/* TODO: This is ugly and how to handle number overflow? */
if (this.suminstanceofBigDecimal || data.suminstanceofBigDecimal) {
BigDecimalresult = ((BigDecimal)this.sum).subtract((BigDecimal)data.sum);
this.sum = (N)result;
 } elseif (this.suminstanceofBigInteger || data.suminstanceofBigInteger) {
BigIntegerresult = ((BigInteger)this.sum).subtract((BigInteger)data.sum);
this.sum = (N)result;
 } elseif (this.suminstanceofLong || data.suminstanceofLong) {
Longresult = (this.sum.longValue() - data.sum.longValue());
this.sum = (N)result;
 } elseif (this.suminstanceofDouble || data.suminstanceofDouble) {
Doubleresult = (this.sum.doubleValue() - data.sum.doubleValue());
this.sum = (N)result;
 } elseif (this.suminstanceofFloat || data.suminstanceofFloat) {
Floatresult = (this.sum.floatValue() - data.sum.floatValue());
this.sum = (N)result;
 } else {
// Integer
Integerresult = (this.sum.intValue() - data.sum.intValue());
this.sum = (N)result;
 }
 }
 }

/**
 * {@inheritDoc}
 */
@Override
publicDatacopy() {
returnnewRangeSumData<N>(index, sum);
 }

/**
 * {@inheritDoc}
 */
@Override
publicDataquery(longstartOfQuery, longendOfQuery) {
if (endOfQuery < this.index || startOfQuery > this.index)
returnnull;

returncopy();
 }

/**
 * {@inheritDoc}
 */
@Override
publicinthashCode() {
return31 * (int)(this.index + this.sum.hashCode());
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanequals(Objectobj) {
if (!(objinstanceofRangeSumData))
returnfalse;

RangeSumData<N> data = (RangeSumData<N>) obj;
if (this.index == data.index && this.sum.equals(data.sum))
returntrue;

returnfalse;
 }

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
StringBuilderbuilder = newStringBuilder();
builder.append(super.toString()).append(" ");
builder.append("sum=").append(sum);
returnbuilder.toString();
 }
 }
 }
}