Commits

Peter Arrenbrecht committed b6e2bbc

drop java stuff

Comments (0)

Files changed (15)

java/.classpath

-<?xml version="1.0" encoding="UTF-8"?>
-<classpath>
-	<classpathentry kind="src" path="src"/>
-	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6"/>
-	<classpathentry kind="lib" path="lib/commons-io-1.4.jar" sourcepath="lib/commons-io-1.4-sources.jar">
-		<attributes>
-			<attribute name="javadoc_location" value="jar:platform:/resource/dagdiscovery-java/lib/commons-io-1.4-javadoc.jar!/"/>
-		</attributes>
-	</classpathentry>
-	<classpathentry kind="output" path="bin"/>
-</classpath>

java/.project

-<?xml version="1.0" encoding="UTF-8"?>
-<projectDescription>
-	<name>dagdiscovery-java</name>
-	<comment></comment>
-	<projects>
-	</projects>
-	<buildSpec>
-		<buildCommand>
-			<name>org.eclipse.jdt.core.javabuilder</name>
-			<arguments>
-			</arguments>
-		</buildCommand>
-	</buildSpec>
-	<natures>
-		<nature>org.eclipse.jdt.core.javanature</nature>
-	</natures>
-</projectDescription>

java/.settings/org.eclipse.jdt.core.prefs

-#Tue Oct 06 17:30:18 CEST 2009
-eclipse.preferences.version=1
-org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
-org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
-org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
-org.eclipse.jdt.core.compiler.compliance=1.6
-org.eclipse.jdt.core.compiler.debug.lineNumber=generate
-org.eclipse.jdt.core.compiler.debug.localVariable=generate
-org.eclipse.jdt.core.compiler.debug.sourceFile=generate
-org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
-org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
-org.eclipse.jdt.core.compiler.source=1.6

java/lib/commons-io-1.4-javadoc.jar

Binary file removed.

java/lib/commons-io-1.4-sources.jar

Binary file removed.

java/lib/commons-io-1.4.jar

Binary file removed.

java/src/ch/arrenbrecht/dags/AbstractDAG.java

-package ch.arrenbrecht.dags;
-
-public abstract class AbstractDAG implements DAG {
-	protected static final int[] NONE = new int[0];
-	private int tip;
-
-	protected AbstractDAG(int tip) {
-		this.tip = tip;
-	}
-
-	public final int tip() {
-		return this.tip;
-	}
-
-	abstract public int[] heads();
-	abstract public int[] parents(int id);
-
-	public final void walk(int[] heads, int[] stops, int limit, Visitor visitor) {
-		final IntStack pending = new IntStack();
-		for (int id : heads)
-			pending.push(id);
-		final HeadsFirstIntSet seen = new HeadsFirstIntSet(tip());
-		for (int id : stops)
-			seen.add(id);
-		while (!pending.isEmpty()) {
-			int id = pending.pop();
-			Integer ID = id;
-			while (!seen.contains(ID)) {
-				seen.add(ID);
-				if (!visitor.visit(id))
-					break;
-				final int[] ps = parents(id);
-				if (ps.length == 0)
-					break;
-				id = ps[0];
-				for (int i = 1; i < ps.length; i++)
-					pending.push(ps[i]);
-			}
-		}
-	}
-
-}

java/src/ch/arrenbrecht/dags/BoundedSkipSampler.java

-package ch.arrenbrecht.dags;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.List;
-import java.util.PriorityQueue;
-import java.util.Queue;
-
-public final class BoundedSkipSampler {
-	private final DAG dag;
-	private final int maxskip;
-	private final int maxjoinskip;
-	private final HeadsFirstIntMap<SkipInfo> nodeskips;
-	private Head nextHead;
-
-	public BoundedSkipSampler(DAG dag, int maxskip, int maxjoinskip) {
-		this.dag = dag;
-		this.maxskip = maxskip;
-		this.maxjoinskip = maxjoinskip;
-		this.nodeskips = new HeadsFirstIntMap<SkipInfo>(dag.tip());
-		for (Integer h : dag.heads())
-			for (Integer p : dag.parents(h))
-				addHead(new Head(p));
-	}
-
-	public final List<Sample> sampleSet(int size) {
-		System.out.println("Sampling...");
-		final List<Sample> set = unboundedSampleSet(size);
-		System.out.println("Fixing...");
-		bound(set);
-		return set;
-	}
-
-	private final List<Sample> unboundedSampleSet(int size) {
-		final List<Sample> set = new ArrayList<Sample>();
-		for (int i = 0; i < size; i++) {
-			final Sample s = nextSample();
-			if (null == s)
-				break;
-			set.add(s);
-		}
-		return set;
-	}
-
-	private final void bound(Collection<Sample> set) {
-		final HeadsFirstIntMap<Sample> samples = new HeadsFirstIntMap<Sample>(dag.tip());
-		int limit = Integer.MAX_VALUE;
-		for (Sample s : set) {
-			final int id = s.id;
-			samples.put(id, s);
-			if (id < limit)
-				limit = id;
-		}
-
-		if (null != nextHead) {
-
-			final class Pending implements Comparable<Pending> {
-				final int id;
-				final int skip;
-				Pending(int id, int skip) {
-					this.id = id;
-					this.skip = skip;
-				}
-				@Override
-				public int compareTo(Pending o) {
-					return o.id - id; // sort higher ids first
-				}
-			}
-
-			final Queue<Pending> pending = new PriorityQueue<Pending>();
-			{
-				final Head first = nextHead;
-				Head h = first;
-				do {
-					pending.add(new Pending(h.id, h.skip));
-				} while ((h = h.next) != first);
-			}
-			final HeadsFirstIntMap<Integer> nodeskips = new HeadsFirstIntMap<Integer>(dag.tip());
-			for (HeadsFirstIntMap.Entry<SkipInfo> e : this.nodeskips.entries())
-				nodeskips.put(e.key, e.value.skip);
-
-			if (pending.size() > 0)
-				System.out.println("fixup down to " + limit + " from " + pending.peek().id + "...");
-
-			int fixed = 0;
-			while (pending.size() > 0) {
-				final Pending pend = pending.poll();
-				int id = pend.id;
-				int skip = pend.skip;
-				while (id > limit) {
-					final Integer seenatskip = nodeskips.get(id);
-					final int atskip = (null == seenatskip) ? -1 : seenatskip;
-					if (atskip >= skip)
-						break;
-					nodeskips.put(id, skip);
-
-					final Sample s = samples.get(id);
-					if (null != s) {
-						if (skip > s.skip) {
-							s.skip = skip;
-							fixed++;
-						}
-						break;
-					}
-
-					skip++;
-					final int[] ps = dag.parents(id);
-					if (ps.length == 0)
-						break;
-					id = ps[0];
-					for (int i = 1; i < ps.length; i++)
-						pending.add(new Pending(ps[i], skip));
-					if (pending.size() > 0 && id < pending.peek().id) {
-						pending.add(new Pending(id, skip));
-						break;
-					}
-				}
-			}
-			System.out.println(fixed);
-		}
-	}
-
-	private final Sample nextSample() {
-		Sample sample = null;
-		while (null == sample) {
-			final Head hd = nextHead;
-			if (null == hd)
-				break;
-			final int id = hd.id;
-			final int skip = hd.skip;
-			final SkipInfo info = nodeskips.get(id);
-			if (null == info) {
-				/*
-				 * Seeing this for the first time.
-				 */
-				nodeskips.put(id, new SkipInfo(skip, false));
-				/*
-				 * Place a sample if necessary.
-				 */
-				if (skip >= maxskip)
-					sample = hd.takeSample();
-				/*
-				 * Setup next iteration.
-				 */
-				hd.skipping.add(id);
-				hd.skip++;
-				final int[] ps = dag.parents(id);
-				if (0 == ps.length) {
-					hd.assumeSkipped();
-					removeHead(hd);
-				} else {
-					/*
-					 * Follow parents, adding new paths at merges.
-					 */
-					hd.id = ps[0];
-					for (int i = 1; i < ps.length; i++) {
-						final Head hd2 = new Head(hd, ps[i]);
-						hd2.next = hd;
-						hd2.prev = hd.prev;
-						hd.prev.next = hd2;
-						hd.prev = hd2;
-					}
-					nextHead = hd.next;
-				}
-			} else {
-				/*
-				 * We've seen the node before, so we abandon this head once
-				 * we've either joined the heads that have been here before, or
-				 * else placed a forced sample.
-				 */
-				final int atskip = info.skip;
-				if (atskip >= skip) {
-					/*
-					 * We join a path that is already at a larger, or the same,
-					 * skip. So we can just rely on samples placed by that path.
-					 */
-					final Collection<Head> hs = findOtherHeadsSkipping(hd, id);
-					if (hs.size() > 0) {
-						/*
-						 * Path is still being skipped. We need to make sure our
-						 * nodes are finalized along with those on the other
-						 * path(s).
-						 */
-						for (Head h : hs)
-							h.skipping.addAll(hd.skipping);
-					} else {
-						/*
-						 * We must assume our nodes to be finalized since all
-						 * other paths from here are, too.
-						 */
-						hd.assumeSkipped();
-					}
-
-				} else {
-					/*
-					 * The other heads will place or have placed samples on the
-					 * paths further down too far away for my path to be
-					 * properly bounded as well. We try to join our path to
-					 * these heads.
-					 */
-					boolean canJoin = false;
-					if (!info.skipped) {
-						/*
-						 * All heads from this node still have their next sample
-						 * pending. Let's find them.
-						 */
-						final Collection<Head> hs = findOtherHeadsSkipping(hd, id);
-						/*
-						 * See if they are still close enough so we can just
-						 * inform them about the bigger skip we cause (so they
-						 * will place their next sample a bit closer than they
-						 * would have).
-						 */
-						canJoin = true;
-						final int skipinc = skip - atskip;
-						for (Head h : hs)
-							if (h.skip + skipinc >= maxjoinskip) {
-								canJoin = false;
-								break;
-							}
-						if (canJoin) {
-							/*
-							 * We can join the other heads. This increases their
-							 * skip...
-							 */
-							final int[] stops = new int[hs.size()];
-							int i = 0;
-							for (Head h : hs) {
-								h.skip += skipinc;
-								h.skipping.addAll(hd.skipping);
-								stops[i++] = h.id;
-							}
-							/*
-							 * ...and also the skip of all the nodes from here
-							 * to these heads' positions.
-							 */
-							dag.walk(new int[] { id }, stops, -1, new DAG.Visitor() {
-								@Override
-								public boolean visit(int id2) {
-									// FIXME use max(skip+depth, skip+skipinc)
-									// to handle prior joins better
-									nodeskips.get(id2).skip += skipinc;
-									return false;
-								}
-							});
-						}
-					}
-					if (!canJoin)
-						/*
-						 * All other heads are already past the point where we'd
-						 * need our next sample. So we take a forced sample
-						 * here.
-						 */
-						sample = hd.takeSample();
-				}
-				/*
-				 * We're done following this path.
-				 */
-				removeHead(hd);
-			}
-		}
-		return sample;
-	}
-
-	private final void addHead(Head h) {
-		if (null == nextHead) {
-			h.next = h;
-			h.prev = h;
-			nextHead = h;
-		} else {
-			h.next = nextHead;
-			h.prev = nextHead.prev;
-			nextHead.prev = h;
-		}
-	}
-
-	private void removeHead(Head hd) {
-		if (hd.next == hd)
-			nextHead = null;
-		else {
-			nextHead = hd.next;
-			hd.prev.next = hd.next;
-			hd.next.prev = hd.prev;
-		}
-	}
-
-	private Collection<Head> findOtherHeadsSkipping(Head hd, int id) {
-		final Collection<Head> hs = new ArrayList<Head>();
-		Head h = hd.next;
-		while (h != hd) {
-			if (h.skipping.contains(id))
-				hs.add(h);
-			h = h.next;
-		}
-		return hs;
-	}
-
-	private final class Head {
-		Integer id;
-		int skip;
-		final HeadsFirstIntSet skipping;
-		Head prev, next;
-
-		public Head(Integer id) {
-			this.id = id;
-			this.skipping = new HeadsFirstIntSet(dag.tip());
-		}
-
-		public Head(Head template, int id) {
-			this.id = id;
-			this.skip = template.skip;
-			this.skipping = new HeadsFirstIntSet(template.skipping);
-		}
-
-		public final Sample takeSample() {
-			final Sample res = new Sample(id, skip);
-			skipping.walk(new HeadsFirstIntSet.Visitor() {
-				@Override
-				public void visit(int v) {
-					nodeskips.get(v).skipped = true;
-				}
-			});
-			skipping.clear();
-			skip = 0;
-			return res;
-		}
-
-		public void assumeSkipped() {
-			skipping.walk(new HeadsFirstIntSet.Visitor() {
-				public void visit(int id) {
-					final SkipInfo info = nodeskips.get(id);
-					if (null == info)
-						nodeskips.put(id, new SkipInfo(0, true));
-					else
-						info.skipped = true;
-				}
-			});
-		}
-	}
-
-	private final class SkipInfo {
-		int skip;
-		boolean skipped;
-		public SkipInfo(int skip, boolean skipped) {
-			this.skip = skip;
-			this.skipped = skipped;
-		}
-	}
-
-	public static final class Sample {
-		public final Integer id;
-		public int skip;
-
-		public Sample(Integer id, int skip) {
-			this.id = id;
-			this.skip = skip;
-		}
-	}
-
-	public final List<SampleError> sampleErrors(Iterable<Sample> sampleSet) {
-		final List<SampleError> errors = new ArrayList<SampleError>();
-		final HeadsFirstIntMap<Sample> lookup = new HeadsFirstIntMap<Sample>(dag.tip());
-		int limit = Integer.MAX_VALUE;
-		for (Sample s : sampleSet) {
-			lookup.put(s.id, s);
-			if (limit > s.id)
-				limit = s.id;
-		}
-		final HeadsFirstIntMap<Integer> seenAtDepth = new HeadsFirstIntMap<Integer>(dag.tip());
-		class Pending {
-			int id, depth;
-			final List<Integer> path = new ArrayList<Integer>();
-			public Pending(int id) {
-				this.id = id;
-			}
-			public Pending(int id, int depth, Collection<Integer> path) {
-				this.id = id;
-				this.depth = depth;
-				this.path.addAll(path);
-			}
-		}
-		final List<Pending> pending = new ArrayList<Pending>();
-		for (int h : dag.heads())
-			for (int p : dag.parents(h))
-				pending.add(new Pending(p));
-
-		while (pending.size() > 0) {
-			final Pending pend = pending.remove(pending.size() - 1);
-			int id = pend.id;
-			int depth = pend.depth;
-			List<Integer> path = pend.path;
-			while (id >= limit) {
-				final Integer sad = seenAtDepth.get(id);
-				if (null != sad && sad >= depth)
-					break;
-				seenAtDepth.put(id, depth);
-
-				final Sample s = lookup.get(id);
-				if (null == s)
-					path.add(id);
-				else {
-					final int skip = path.size();
-					if (skip > s.skip)
-						errors.add(new SampleError(s, skip, path));
-					path.clear();
-					path.add(id);
-				}
-
-				final int[] ps = dag.parents(id);
-				if (0 == ps.length)
-					break;
-				else {
-					depth++;
-					id = ps[0];
-					for (int i = 1; i < ps.length; i++) {
-						pending.add(new Pending(ps[i], depth, path));
-					}
-				}
-			}
-		}
-		return errors;
-	}
-
-	public static final class SampleError {
-		public final Sample sample;
-		public final int actualSkip;
-
-		public SampleError(Sample sample, int actualSkip, Iterable<Integer> path) {
-			this.sample = sample;
-			this.actualSkip = actualSkip;
-		}
-	}
-
-}

java/src/ch/arrenbrecht/dags/DAG.java

-package ch.arrenbrecht.dags;
-
-public interface DAG {
-
-	int tip();
-	int[] heads();
-	int[] parents(int id);
-
-	static interface Visitor {
-		boolean visit(int id);
-	}
-	void walk(int[] heads, int[] stops, int limit, Visitor visitor);
-
-}

java/src/ch/arrenbrecht/dags/HeadsFirstIntMap.java

-package ch.arrenbrecht.dags;
-
-import java.util.Iterator;
-import java.util.NoSuchElementException;
-
-public final class HeadsFirstIntMap<V> {
-	private final int size;
-	private Object[] data;
-	private int used;
-
-	public HeadsFirstIntMap(int size) {
-		this.size = size;
-	}
-
-	public HeadsFirstIntMap(HeadsFirstIntMap<V> template) {
-		this(template.size);
-		if (template.used > 0) {
-			data = new Object[template.data.length];
-			System.arraycopy(template.data, 0, data, 0, template.used);
-			used = template.used;
-		}
-	}
-
-	@SuppressWarnings("unchecked")
-	public final V get(int k) {
-		k = size - k;
-		if (k >= used)
-			return null;
-		return (V) data[k];
-	}
-
-	public final void put(int k, V v) {
-		assert k < size;
-		k = size - k;
-		if (null == data)
-			data = new Object[k + 1];
-		else if (k >= data.length) {
-			int n = data.length * 2;
-			if (n < k + 1)
-				n = k + 1;
-			if (n > size)
-				n = size;
-			Object[] more = new Object[n];
-			System.arraycopy(data, 0, more, 0, used);
-			data = more;
-		}
-		if (used <= k)
-			used = k + 1;
-		data[k] = v;
-	}
-
-	public Iterable<Entry<V>> entries() {
-		return new Iterable<Entry<V>>() {
-			@Override
-			public Iterator<Entry<V>> iterator() {
-				return new EntryIterator();
-			}
-		};
-	}
-
-	public static final class Entry<V> {
-		public int key;
-		public V value;
-	}
-
-	private final class EntryIterator implements Iterator<Entry<V>> {
-		private final Entry<V> e = new Entry<V>();
-		private int next = -1;
-
-		public EntryIterator() {
-			scanNext();
-		}
-
-		@Override
-		public boolean hasNext() {
-			return next < used;
-		}
-
-		@SuppressWarnings("unchecked")
-		@Override
-		public Entry<V> next() {
-			if (next >= used)
-				throw new NoSuchElementException();
-			e.key = next;
-			e.value = (V) data[next];
-			scanNext();
-			return e;
-		}
-
-		@Override
-		public void remove() {
-			throw new UnsupportedOperationException();
-		}
-
-		private void scanNext() {
-			while (++next < used)
-				if (null != data[next])
-					break;
-		}
-	}
-
-}

java/src/ch/arrenbrecht/dags/HeadsFirstIntSet.java

-package ch.arrenbrecht.dags;
-
-import java.util.BitSet;
-
-/**
- * Wrapper for BitSet with a more {@link java.util.Set} like interface.
- * Internally reverses the order of the bits if a fixed size is given. Since we
- * normally operate on the dags from the heads downwards.
- */
-public final class HeadsFirstIntSet {
-	private final BitSet bs;
-	private final int nbits;
-	private int size;
-
-	public HeadsFirstIntSet(int nbits) {
-		this.bs = new BitSet(); // don't pass size as it preallocates
-		this.nbits = nbits;
-	}
-
-	public HeadsFirstIntSet(HeadsFirstIntSet template) {
-		this(template.nbits);
-		addAll(template);
-	}
-
-	public final void add(int v) {
-		v = nbits - v;
-		if (bs.get(v))
-			return;
-		bs.set(v);
-		size++;
-	}
-
-	public void addAll(HeadsFirstIntSet other) {
-		int i = 0;
-		while ((i = other.bs.nextSetBit(i)) >= 0)
-			bs.set(i++);
-	}
-
-	public final void remove(int v) {
-		v = nbits - v;
-		if (!bs.get(v))
-			return;
-		bs.clear(v);
-		size--;
-	}
-
-	public final boolean contains(int v) {
-		v = nbits - v;
-		return bs.get(v);
-	}
-
-	public final int size() {
-		return size;
-	}
-
-	public void clear() {
-		bs.clear();
-	}
-
-	public final void walk(Visitor v) {
-		int i = 0;
-		while ((i = bs.nextSetBit(i)) >= 0)
-			v.visit(nbits - (i++));
-	}
-
-	public static interface Visitor {
-		void visit(int v);
-	}
-
-}

java/src/ch/arrenbrecht/dags/IntSet.java

-package ch.arrenbrecht.dags;
-
-import java.util.BitSet;
-
-/**
- * Wrapper for BitSet with a more {@link java.util.Set} like interface.
- * Internally reverses the order of the bits if a fixed size is given. Since we
- * normally operate on the dags from the heads downwards.
- */
-public final class IntSet {
-	private final BitSet bs;
-	private int size;
-
-	public IntSet() {
-		this.bs = new BitSet();
-	}
-
-	public final void add(int v) {
-		if (bs.get(v))
-			return;
-		bs.set(v);
-		size++;
-	}
-
-	public final void remove(int v) {
-		if (!bs.get(v))
-			return;
-		bs.clear(v);
-		size--;
-	}
-
-	public final boolean contains(int v) {
-		return bs.get(v);
-	}
-
-	public final int size() {
-		return size;
-	}
-
-	public final int[] toArray(int[] arr) {
-		int next = 0;
-		for (int i = 0; i < arr.length; i++) {
-			next = bs.nextSetBit(next);
-			arr[i] = next++;
-		}
-		return arr;
-	}
-
-}

java/src/ch/arrenbrecht/dags/IntStack.java

-package ch.arrenbrecht.dags;
-
-import java.util.NoSuchElementException;
-
-public final class IntStack {
-	private int[] data = null;
-	private int next = 0;
-
-	public boolean isEmpty() {
-		return next == 0;
-	}
-
-	public void push(int v) {
-		if (null == data)
-			data = new int[16];
-		else if (next >= data.length) {
-			int[] more = new int[data.length * 2];
-			System.arraycopy(data, 0, more, 0, data.length);
-			data = more;
-		}
-		data[next++] = v;
-	}
-
-	public int pop() {
-		if (next == 0)
-			throw new NoSuchElementException();
-		return data[--next];
-	}
-
-}

java/src/ch/arrenbrecht/dags/Play.java

-package ch.arrenbrecht.dags;
-
-import java.io.File;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-
-import org.apache.commons.io.FileUtils;
-
-import ch.arrenbrecht.dags.BoundedSkipSampler.Sample;
-
-public class Play {
-
-	public static void main(String[] args) throws Exception {
-		final String desc = FileUtils.readFileToString(new File("../data/linux.dag"));
-		final TestDAG dag = TestDAG.fromDesc(desc);
-		final BoundedSkipSampler sampler = new BoundedSkipSampler(dag, 66, 100);
-		final List<Sample> sampleSet = sampler.sampleSet(200);
-
-		System.out.println("== Sample");
-		Collections.sort(sampleSet, new Comparator<Sample>() {
-			@Override
-			public int compare(Sample o1, Sample o2) {
-				final int i1 = o1.id;
-				final int i2 = o2.id;
-				return i1 == i2 ? 0 : i1 < i2 ? -1 : +1;
-			}
-		});
-//		for (Sample s : sampleSet)
-//			System.out.printf("%d: %d\n", s.id, s.skip);
-
-//		System.out.println("== Errors");
-//		final List<SampleError> errors = sampler.sampleErrors(sampleSet);
-//		for (SampleError e : errors)
-//			System.out.printf("%d: %d < %d\n", e.sample.id, e.sample.skip, e.actualSkip);
-	}
-
-}

java/src/ch/arrenbrecht/dags/TestDAG.java

-package ch.arrenbrecht.dags;
-
-import java.util.ArrayList;
-import java.util.List;
-import java.util.regex.Pattern;
-
-public final class TestDAG extends AbstractDAG {
-	private final int[] heads;
-	private final int[][] parents;
-
-	public TestDAG(int[] heads, int[][] parents) {
-		super(max(heads));
-		this.heads = heads;
-		this.parents = parents;
-	}
-
-	private static int max(int[] heads) {
-		int m = 0;
-		for (int h : heads)
-			if (h > m)
-				m = h;
-		return m;
-	}
-
-	@Override
-	public int[] heads() {
-		return heads;
-	}
-
-	@Override
-	public int[] parents(int id) {
-		return parents[id];
-	}
-
-	public final void appendDesc(StringBuilder desc) {
-		int prev = -1;
-		int curr = 0;
-		for (int[] ps : parents) {
-			if (ps.length == 0)
-				desc.append("*,");
-			else if (ps.length == 1 && ps[0] == prev)
-				desc.append(',');
-			else {
-				for (int p : ps) {
-					if (p == prev)
-						desc.append('/');
-					else
-						desc.append(curr - p).append('/');
-				}
-				desc.setCharAt(desc.length() - 1, '\n');
-			}
-			prev = curr;
-			curr++;
-		}
-		desc.setLength(desc.length() - 1);
-	}
-
-	@Override
-	public String toString() {
-		final StringBuilder desc = new StringBuilder();
-		appendDesc(desc);
-		return desc.toString();
-	}
-
-	/**
-	 * Create test DAG from a description.
-	 *
-	 * Nodes are separated by a single \n or a single comma. A trailing \n is
-	 * ignored. Node number is node id. '' means single parent is previous node.
-	 * '*' means no parent. Otherwise parents are listed on the line, separated
-	 * by slashes. Ref to previous node is empty. Ref to other node is
-	 * difference between the referenced node number and the current one (so
-	 * positive numbers point towards earlier nodes).
-	 *
-	 * @param desc
-	 *            the description string.
-	 */
-	static public final TestDAG fromDesc(String desc) {
-		final IntSet heads = new IntSet();
-		final List<int[]> parents = new ArrayList<int[]>();
-		final String[] lines = desc.split("\n", -1);
-		int lastLine = lines.length - 1;
-		if (lastLine >= 0 && lines[lastLine].length() == 0)
-			lastLine--;
-		final Pattern eltSep = Pattern.compile(",");
-		final Pattern parSep = Pattern.compile("/");
-		int prev = -1;
-		int curr = 0;
-		for (String line : lines) {
-			final String[] elts = eltSep.split(line, -1);
-			for (String elt : elts) {
-				int[] ps;
-				if (elt.length() == 0)
-					ps = new int[] { prev };
-				else if (elt.charAt(0) == '*')
-					ps = NONE;
-				else {
-					final String[] pars = parSep.split(elt, -1);
-					ps = new int[pars.length];
-					int i = 0;
-					for (String par : pars)
-						if (par.length() == 0)
-							ps[i++] = prev;
-						else
-							ps[i++] = curr - Integer.parseInt(par);
-				}
-				parents.add(ps);
-				for (Integer p : ps)
-					heads.remove(p);
-				heads.add(curr);
-				prev = curr;
-				curr += 1;
-			}
-		}
-
-		return new TestDAG(heads.toArray(new int[heads.size()]), parents.toArray(new int[parents.size()][]));
-	}
-
-}