import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
public class NestedIntervals {
private static ExecutorService executor;
private final int base;
private NestedIntervals(int base) {
this.base = base;
}
public static NestedIntervals base(int base) {
return new NestedIntervals(base);
}
public static class Fraction {
private int denominator;
private int numerator;
public Fraction(int numerator, int denominator) {
super();
this.numerator = numerator;
this.denominator = denominator;
}
public int getDenominator() {
return denominator;
}
public void setDenominator(int denominator) {
this.denominator = denominator;
}
public int getNumerator() {
return numerator;
}
public void setNumerator(int numerator) {
this.numerator = numerator;
}
@Override
public String toString() {
return numerator + "/" + denominator;
}
}
private List<Fraction> getFarey(Fraction left, Fraction right) {
Fraction mediant = new Fraction(left.getNumerator()
+ right.getNumerator(), left.getDenominator()
+ right.getDenominator());
if (mediant.getDenominator() > base) {
return Collections.emptyList();
}
List<Fraction> result = new LinkedList<Fraction>();
result.addAll(getFarey(left, mediant));
result.add(mediant);
result.addAll(getFarey(mediant, right));
return result;
}
public List<Fraction> getFarey() {
List<Fraction> result = new LinkedList<Fraction>();
Fraction left = new Fraction(0, 1);
Fraction right = new Fraction(1, 1);
result.add(left);
result.addAll(getFarey(left, right));
result.add(right);
return result;
}
public List<Fraction> getFareyNonRecurcive() {
LinkedList<Fraction> result = new LinkedList<Fraction>();
Fraction left = new Fraction(0, 1);
Fraction right = new Fraction(1, 1);
Fraction mediant = null;
result.add(left);
result.add(right);
ListIterator<Fraction> iterator = result.listIterator();
left = iterator.next();
while (iterator.hasNext()) {
right = iterator.next();
int denominator = left.getDenominator() + right.getDenominator();
if (denominator <= base) {
mediant = new Fraction(left.getNumerator()
+ right.getNumerator(), denominator);
iterator.previous();
iterator.add(mediant);
iterator.previous();
} else {
left = right;
}
}
return result;
}
public List<Fraction> getFareyNonRecurciveMultiThread(int threads) {
List<Fraction> result = null;
if (threads <= 1) {
result = getFareyNonRecurcive();
} else {
LinkedList<Fraction> ret = new LinkedList<Fraction>();
List<Future<LinkedList<Fraction>>> futureList = new
ArrayList<Future<LinkedList<Fraction>>>();
// fill params
LinkedList<Fraction> params = fillParams(threads);
ListIterator<Fraction> listIterator = params.listIterator();
Fraction first = listIterator.next();
while (listIterator.hasNext()) {
Fraction second = (Fraction) listIterator.next();
Future<LinkedList<Fraction>> future = executor
.submit(new FareyCallable(first, second, base));
futureList.add(future);
first = second;
}
try {
for (int i = 0; i < futureList.size(); i++) {
if (i == 0) {
ret.addAll(futureList.get(i).get());
} else {
LinkedList<Fraction> linkedList = futureList.get(i)
.get();
linkedList.pollFirst();
ret.addAll(linkedList);
}
}
} catch (Exception e) {
e.printStackTrace();
}
result = ret;
}
return result;
}
private LinkedList<Fraction> fillParams(int threads) {
LinkedList<Fraction> params = new LinkedList<Fraction>();
params.add(new Fraction(0, 1));
params.add(new Fraction(1, 1));
Fraction left = null;
Fraction right = null;
Fraction mediant = null;
for (int j = 0; j < base; j++) {
ListIterator<Fraction> listIterator = params.listIterator();
left = listIterator.next();
while (listIterator.hasNext()) {
if (params.size() - 1 == threads) {
return params;
}
right = listIterator.next();
int denominator = left.getDenominator()
+ right.getDenominator();
if (denominator <= base) {
mediant = new Fraction(left.getNumerator()
+ right.getNumerator(), denominator);
listIterator.previous();
listIterator.add(mediant);
left = listIterator.next();
} else {
left = right;
}
}
}
throw new RuntimeException();
}
public static class FareyCallable implements Callable<LinkedList<Fraction>> {
private Fraction first;
private Fraction last;
private int base;
public FareyCallable(Fraction first, Fraction last, int base) {
super();
this.first = first;
this.last = last;
this.base = base;
}
@Override
public LinkedList<Fraction> call() throws Exception {
LinkedList<Fraction> result = new LinkedList<Fraction>();
Fraction left = first;
Fraction right = last;
Fraction mediant = null;
result.add(left);
result.add(right);
ListIterator<Fraction> iterator = result.listIterator();
left = iterator.next();
while (iterator.hasNext()) {
right = iterator.next();
int denominator = left.getDenominator()
+ right.getDenominator();
if (denominator <= base) {
mediant = new Fraction(left.getNumerator()
+ right.getNumerator(), denominator);
iterator.previous();
iterator.add(mediant);
iterator.previous();
} else {
left = right;
}
}
return result;
}
}
public static void main(String[] args) {
int threads = 20;
int base = 5000;
executor = Executors.newFixedThreadPool(threads);
for (int i = 0; i < 1; i++) {
long time = System.currentTimeMillis();
List<Fraction> farey = NestedIntervals.base(base).getFarey();
System.out.printf("Total %dms ", System.currentTimeMillis() - time);
System.out.println(farey.size());
farey = null;
System.gc();
time = System.currentTimeMillis();
farey = NestedIntervals.base(base).getFareyNonRecurcive();
System.out.printf("n Total %dms ", System.currentTimeMillis()
- time);
System.out.println(farey.size());
farey = null;
System.gc();
time = System.currentTimeMillis();
farey = NestedIntervals.base(base).getFareyNonRecurciveMultiThread(threads);
System.out.printf("m Total %dms ",
System.currentTimeMillis() - time);
System.out.println(farey.size());
farey = null;
System.gc();
}
executor.shutdownNow();
}
}
