July 2012, revised October 2013 and May 2014

The latest release is May 2014.

Feel free to contact me if you have any questions.

“Dynamic tree” refers to one of a family of abstract data types that specify operations for querying and updating a collection of trees (a forest). These operations typically include `Link`

, which joins two trees into one, and `Cut`

, which splits one tree into two. The forest is often node- or edge-weighted, with operations to update many weights at a time or aggregate them.

Dynamic trees were introduced in the early 1980s by Sleator and Tarjan, who used them to obtain the then-fastest algorithm for maximum flow. It is the case for many graph problems that the solutions with the best known asymptotic running time use dynamic trees.

Most dynamic-tree operations can be implemented in (amortized) logarithmic time. For `dtree`

, the few exceptions are noted individually. In theory, amortization is not necessary, but it has led to simpler data structures that perform better in practice. The worst-case time per operation is linear.

Please let me know if you find `dtree`

useful.

`dtree`

?**Efficient**`dtree`

adheres to the pay-for-what-you-use philosophy of C++, and I have spent a lot of time tuning it. In particular, the internal operation`Expose`

makes one pass. Some other implementations, including every possible generic implementation of top trees, make three.**Flexible**`dtree`

provides operations with tree scope as well as path scope. Many dynamic tree operations described in the literature are implemented, as are dynamic sequences based on splay trees.**Open source**`dtree`

is available under a permissive MIT license.**Portable**- The
`dtree`

header files are intended to conform to the C++98 standard.`dtree`

is known to work on Linux and OS X with recent versions of the GNU Compiler Collection (GCC), Clang, and Intel C++ Compiler. Unfortunately,`dtree`

is incompatible with Microsoft Visual C++ 2010, due to a compiler bug involving shadowed names (see the reduced test case in`msvc_bug.cpp`

). There seems to be no reasonable workaround. **Well tested**`dtree`

comes with an extensive test suite. For many tree/sequence configurations, the results of random operations are compared against the ground truth computed by a simpler implementation. Between operations, all data-structural invariants are verified.

Copy the header files in `standalone/`

into your project.

Building the example programs and tests requires a POSIX environment and C99 functionality. Run `make`

to build the examples with GCC and `make check`

to build and run the tests. To use Clang, for example, instead of GCC, run `make CXX=clang++`

. To fix errors involving `__attribute__`

, run the script `tool/remove_attribute.sh`

and try again.

`flow/`

- Implements the push-relabel algorithm for maximum (pre)flow due to Goldberg and Tarjan, with global and gap relabeling, with and without dynamic trees. Please note that, while the core algorithm is competitive with Goldberg’s implementation, the input and initialization steps could be made significantly more efficient.
`maze/`

- Samples and displays random spanning trees of a grid graph.
`tsp/`

- Implements a 2-opt local search for the traveling salesman problem in the 2D unit square, with dynamic sequences.

The July 2012 version was the first public release. The October 2013 version excised the hack previously required to support index predicates. The May 2014 version fixed a bug that prevented the naive versions of `seq-inl.h`

and `tree-inl.h`

from being included in the same file. As part of the fix, the function template `Connected`

was deprecated in favor of `SameSeq`

and `SameTree`

.

May 2014 also changed the usage of `WithReverseBy`

and `WithEvertBy`

and introduced the transformers `WithAncDescValue`

and `WithAncDescAggr`

, the method `SetNonDescValue`

, and the preprocessor symbol `DTREE_VERSION`

(currently `201405L`

).

Unless another bug is found, May 2014 likely will be the last version of `dtree`

.

`dtree`

never would have been written without the vision, encouragement, and support of my PhD coadvisor Philip N. Klein. I would like to thank Sarah Eisenstat and Daniel Patterson for reading early drafts of this manual. Any errors or omissions that remain are my own.

The development of `dtree`

was funded in part by NSF grant CCF-0964037.

The following MIT-licensed code demonstrates the operations of the dynamic tree described in the 1985 paper “Self-Adjusting Binary Search Trees” by Sleator and Tarjan.

```
#include "dtree/tree.h"
#include "dtree/tree-inl.h"
class Forest {
public:
// don't change Cost to an unsigned type; that breaks the Min aggregate
// read the appendix before changing Cost to a floating-point type
typedef int Cost;
private:
typedef dtree::WithAncAggr<dtree::Min<Cost>,
dtree::WithAncValue<dtree::Add<Cost>,
dtree::Begin<> > > C;
typedef dtree::WithEvert<C> E;
typedef dtree::EndTree<E> Node;
public:
typedef size_t NodeId;
Forest();
~Forest();
// creates a forest with node ids 0..size-1
void Initialize(size_t size);
// as in [ST85]
Cost FindCost(NodeId v) { return C::Value(&node_[v]); }
NodeId FindRoot(NodeId v) { return Root(&node_[v]) - node_; }
NodeId FindMin(NodeId v);
void AddCost(NodeId v, Cost x) { C::AddToAnc(&node_[v], x); }
void Link(NodeId v, NodeId w) { dtree::Link(&node_[v], &node_[w]); }
void Cut(NodeId v) { dtree::Cut(&node_[v]); }
void Evert(NodeId v) { E::Evert(&node_[v]); }
private:
Node* node_;
// disallows the copy constructor and the assignment operator
Forest(const Forest&);
void operator=(const Forest&);
};
Forest::Forest() : node_(NULL) {
}
Forest::~Forest() {
delete[] node_;
}
void Forest::Initialize(size_t size) {
Node* old_node = node_;
// avoids a double delete[] if new[] throws
node_ = NULL;
delete[] old_node;
node_ = new Node[size];
}
Forest::NodeId Forest::FindMin(NodeId v) {
return C::FindRootmostAnc(&node_[v],
dtree::LessEqual(C::AggrAnc(&node_[v]))) - node_;
}
```

Round brackets (like this) delimit parenthetical remarks. Square brackets [like this] resolve syntactic ambiguity.

For us, trees always are **rooted** and **unordered**. All of the terms defined below are standard except for “leafmost” and “rootmost”, whose meanings should be clear. Every node is its own ancestor and descendant.

Formally, the topology of a forest on a set of nodes *V* is specified by a partial map *p* : *V* → *V* such that, for every integer *k* > 0, the iterated map *p*^{k} has no fixed point (∀*k* > 0. ∄*u* ∈ *V*. *p*^{k}(*u*) = *u*). The **parent** of a node *u* ∈ *V* is *p*(*u*). There is an **edge** from *u* to *p*(*u*). The **ancestors** of *u* comprise the set {*p*^{k}(*u*) : *k* ≥ 0}. The **proper ancestors** of *u* are the ancestors of *u* except for *u* itself. With respect to a set of nodes *U* ⊆ *V*, a node *u* ∈ *U* is **rootmost** if and only if *U* contains no proper ancestor of *u*. The **root** of *u*’s tree is the rootmost ancestor of *u*. Nodes *u* and *v* **belong to the same tree** if and only if the roots of their trees are the same node. The nodes belonging to the same tree as *u* comprise *u*’s tree.

Most of these terms have an analog describing the reverse relationship. The **children** of a node *u* are the nodes with parent *u*. The **descendants** of *u* are the nodes with ancestor *u*. The **proper descendants** of *u* are the descendants of *u* except for *u* itself. With respect to a set of nodes, a member *u* is **leafmost** if and only if the set contains no proper descendant of *u*. A **leaf** is a node without proper descendants.

Sequences are ordered from left to right. The topology of a collection of sequences on a set of nodes *V* is specified by partial maps *l*, *r* : *V* → *V* such that, for every node *u* ∈ *V*, if *l*(*u*) is defined, then *r*(*l*(*u*)) = *u*, and if *r*(*u*) is defined, then *l*(*r*(*u*)) = *u*. The **node immediately to the left** of a node *u* is *l*(*u*). The **node immediately to the right** of a node *u* is *r*(*u*). A node *u* is **properly to the left of** a node *v* if and only if there exists an integer *k* > 0 such that *l*^{k}(*v*) = *u*. A node *u* is **properly to the right of** a node *v* if and only if there exists an integer *k* > 0 such that *r*^{k}(*v*) = *u*. With respect to a set of nodes *U* ⊆ *V*, a node *u* ∈ *U* is **leftmost** if and only if *U* contains no node properly to the left of *u*. Node *u* is **rightmost** if and only if *U* contains no node properly to the right of *u*. Nodes *u* and *v* **belong to the same sequence** if and only if there exists an integer *k* ≥ 0 such that *u* ∈ {*l*^{k}(*v*), *r*^{k}(*v*)}. The nodes belonging to the same sequence as *u* comprise *u*’s sequence.

We use the term “transformer” to mean a template class that derives from its last template argument. Below is an example of a transformer.

```
template<typename Base>
class Transformer : public Base {
/* ... */
};
```

Node types are constructed by applying the transformer `dtree::Begin<Base>`

, whose sole argument defaults to the empty class `dtree::Empty`

, followed by transformers specifying the features desired, followed by an end transformer. The simplest tree node, for example, has type `dtree::EndTree<dtree::Begin<> >`

.

Other than the base class, transformers in `dtree`

accept template arguments of three kinds: groups, semigroups, and predicates.

Groups specify how values are updated. `dtree`

defines several groups. For more information, see the appendix.

`dtree::Add<T>`

: updates by addition and subtraction; read the appendix before choosing`T`

to be an unsigned or floating-point type`dtree::Nop<T>`

: no updates`dtree::Xor<T>`

: updates by bitwise exclusive or

Semigroups specify how aggregates are computed. `dtree`

defines several semigroups. For more information, see the appendix.

`dtree::Count<T>`

: the number of nodes in scope, compatible with`dtree::Nop<dtree::NoValue>`

`dtree::CountAndSum<C, S>`

: the number of nodes in scope and the sum of their values, compatible with`dtree::Add<S>`

and`dtree::Nop<S>`

`dtree::Max<T>`

: the maximum of the values of the nodes in scope, compatible with`dtree::Add<T>`

and`dtree::Nop<T>`

`dtree::Min<T>`

: the minimum of the values of the nodes in scope, compatible with`dtree::Add<T>`

and`dtree::Nop<T>`

`dtree::Or<T>`

: the bitwise or of the values of the nodes in scope, compatible with`dtree::Nop<T>`

`dtree::Sum<T>`

: the sum of the values of the nodes in scope, compatible with`dtree::Nop<T>`

The aggregate type of `dtree::CountAndSum<C, S>`

is `dtree::CasAggr<C, S>`

, a structure with two fields: `count`

, of type `C`

; and `sum`

, of type `S`

.

Predicates specify search goals. `dtree`

defines several predicates. For more information, see the appendix.

`dtree::Greater(T b)`

: on argument`a`

, returns`a > b`

, compatible with`dtree::Max<T>`

`dtree::GreaterEqual(T b)`

: on argument`a`

, returns`a >= b`

, compatible with`dtree::Max<T>`

`dtree::Less(T b)`

: on argument`a`

, returns`a < b`

, compatible with`dtree::Min<T>`

`dtree::LessEqual(T b)`

: on argument`a`

, returns`a <= b`

, compatible with`dtree::Min<T>`

`dtree::Nonzero()`

: on argument`a`

, returns`bool(a)`

, compatible with`dtree::Or<T>`

`dtree::NonzeroAnd(T b)`

: on argument`a`

, returns`bool(a & b)`

, compatible with`dtree::Or<T>`

Three special predicates match the node at a specified index, which is asserted to be nonnegative. Formally, let the nodes in search scope be *u*_{1}, …, *u*_{n} from `dir`

most to `dir`

least. (In case the search has nonlinear scope, the ordering is topological and **inconsistent** across invocations.) For [`Index`

with `Count`

] or `IndexByCount`

, node *u*_{i} is matched by indexes in the interval [*i*-1, *i*). For [`Index`

with `Sum`

] or `IndexBySum`

, all node values in scope must be nonnegative, and node *u*_{i} is matched by indexes in the interval [*S*_{i-1}, *S*_{i}), where *S*_{j} = value(*u*_{1}) + … + value(*u*_{j}).

`dtree::Index(T)`

: compatible with`dtree::Count<T>`

and`dtree::Sum<T>`

`dtree::IndexByCount(C)`

: compatible with`dtree::CountAndSum<C, S>`

`dtree::IndexBySum(S)`

: compatible with`dtree::CountAndSum<C, S>`

Nodes cannot be copied and thus cannot be stored directly in Standard Template Library containers. Store smart pointers to nodes instead or use a lightweight container such as Boost’s `scoped_array`

. Alternatively, one hook method to support a custom node container is provided.

`void Node::CopyFrom(const Node& node, Forwarder forward);`

Argument

`forward`

is a [function or function object] with prototype`Node* forward(Node* lhs, const Node* rhs, Node* ptr)`

. Copies the data in`node`

, mapping the pointer members with`forward(this, &node, ptr)`

. Excluding the cost of copying the base object and calling`forward`

, the running time is*O*(1).

Except for `Assemble`

, an operation described in the appendix, every operation

- uses constant stack space
- does not allocate or deallocate memory
- reads and writes only [the stack] and nodes belonging to the same tree/sequence of one its arguments; does not read or write global variables.

`dtree`

thus can be used in a multithreaded program if accesses to the same tree/sequence are properly synchronized.

Include `"dtree/tree.h"`

for the types and `"dtree/tree-inl.h"`

for the functions. The transformer `dtree::EndTree<Base>`

yields a node type for trees without descendant pointers. The transformer `dtree::EndTreeWithDesc<Base>`

yields a node type for trees with descendant pointers. Descendant pointers consume time and space and should be requested only if required. Each of these transformers must be the **last** to be applied (most derived).

`bool SameTree(Node* u, Node* v);`

`bool Connected(Node* u, Node* v); // deprecated`

Arguments

`u`

and`v`

each may be null. Returns whether [`u`

and`v`

are both nonnull and belong to the same tree] or [`u`

and`v`

are both null].*Remark:*`SameTree`

is an equivalence relation.`Node* Cut(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull and has a parent`p`

, removes the edge from`u`

to`p`

and returns an ancestor of`p`

; the root of`u`

’s new tree is`u`

, and the root of`p`

’s new tree is the root of the former tree. Otherwise, has no effect and returns null.`Node* LeafmostCommonAnc(Node* u, Node* v);`

Arguments

`u`

and`v`

each may be null. If`u`

and`v`

are both nonnull and belong to the same tree, returns the leafmost ancestor of`u`

that is an ancestor of`v`

also. Otherwise, returns null.*Remark:*`LeafmostCommonAnc`

is an idempotent, commutative, associative binary operation with absorbing element null.`Node* Link(Node* u, Node* p);`

Arguments

`u`

and`p`

each may be null. If`u`

and`p`

are both nonnull, asserts that`u`

and`p`

do not belong to the same tree and adds an edge from the root of`u`

’s tree to`p`

; the root of the new tree is the root of`p`

’s former tree. Otherwise, has no effect. Returns`p`

if`p`

is nonnull and`u`

otherwise.`Node* Parent(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull and has a parent`p`

, returns`p`

. Otherwise, returns null.`Node* Root(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, returns the root of`u`

’s tree. Otherwise, returns null.

`// EndTreeWithDesc only`

`Node* Child(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull and has a child, returns a child of`u`

. Otherwise, returns null.`// EndTreeWithDesc only`

`Node* Leaf(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, returns a leaf that is a descendant of`u`

. Otherwise, returns null.`// EndTreeWithDesc only`

`Node* ContractDirward(int dir, Node* u);`

`Node* ContractLeafward(Node* u);`

`Node* ContractRootward(Node* u);`

Argument

`u`

may be null. Argument`dir`

must be either`dtree::kLeaf`

or`dtree::kRoot`

. If`u`

is nonnull and has a parent`p`

, contracts`dir`

ward (respectively, leafward or rootward) the edge from`u`

to`p`

and returns`p`

. Otherwise, returns null. Rootward contraction means removing the edge from`u`

to`p`

and, for every child`c`

of`u`

, changing the parent of`c`

to`p`

. Leafward contraction means changing the root of`u`

’s tree from some node`r`

to`u`

, contracting rootward with the roles of`u`

and`p`

reversed, and, if`r`

is not`p`

, changing the root of`u`

’s tree back to`r`

.

The transformer `dtree::WithEvert<Base>`

extends its argument to support the `Evert`

operation.

`typedef dtree::WithEvert<Base> E;`

`static void E::Evert(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, changes the root of`u`

’s tree to`u`

.

The transformer `dtree::WithStaticValue<Type, Base>`

extends its second argument by a value field (`Type`

must be default-constructible, copyable, and assignable). The transformer `dtree::WithAncValue<Group, Base>`

extends its second argument by a value field supporting bulk addition and subtraction in `Group`

with ancestor (path) scope. The transformer `dtree::WithDescValue<Group, Base>`

extends its second argument by a value field supporting bulk addition and subtraction in `Group`

with descendant (tree) scope. The transformer `dtree::WithAncDescValue<Group, Base>`

extends its second argument by a value field supporting bulk addition and subtraction in `Group`

with ancestor and descendant scope. Descendant values do not require descendant pointers.

`typedef dtree::WithStaticValue<Type, Base> SV;`

`static Type SV::Value(Node* u);`

Argument

`u`

must be nonnull. Returns the value of`u`

’s`SV`

field.`typedef dtree::WithStaticValue<Type, Base> SV;`

`Type SV::value() const;`

Returns the value of implicit argument

`this`

’s`SV`

field.*Remark:*The invocation syntax is`u->SV::value()`

. This is negligibly more efficient than`SV::Value(u)`

and should be used only when necessary.`typedef dtree::WithStaticValue<Type, Base> SV;`

`static void SV::SetValue(Node* u, Type value);`

Argument

`u`

must be nonnull. Sets the value of`u`

’s`SV`

field to`value`

.`typedef dtree::WithStaticValue<Type, Base> SV;`

`void SV::set_value(Type value);`

Implicit argument

`this`

**must be the sole node in its tree**. Sets the value of`this`

’s`SV`

field to`value`

.*Remark:*The invocation syntax is`u->SV::set_value(value)`

. This is negligibly more efficient than`SV::SetValue(u, value)`

and should be used only when necessary.

`typedef dtree::WithAncValue<Group, Base> AV;`

`static Group::Type AV::Value(Node* u);`

Argument

`u`

must be nonnull. Returns the value of`u`

’s`AV`

field.`typedef dtree::WithAncValue<Group, Base> AV;`

`Group::Type AV::value() const;`

Implicit argument

`this`

**must be the sole node in its tree**. Returns the value of`this`

’s`AV`

field.*Remark:*The invocation syntax is`u->AV::value()`

. This is negligibly more efficient than`AV::Value(u)`

and should be used only when necessary.`typedef dtree::WithAncValue<Group, Base> AV;`

`static void AV::SetValue(Node* u, Group::Type value);`

Argument

`u`

must be nonnull. Sets the value of`u`

’s`AV`

field to`value`

.`typedef dtree::WithAncValue<Group, Base> AV;`

`void AV::set_value(Group::Type value);`

Implicit argument

`this`

**must be the sole node in its tree**. Sets the value of`this`

’s`AV`

field to`value`

.*Remark:*The invocation syntax is`u->AV::set_value(value)`

. This is negligibly more efficient than`AV::SetValue(u, value)`

and should be used only when necessary.`typedef dtree::WithAncValue<Group, Base> AV;`

`static void AV::AddToAnc(Node* u, Group::Type delta);`

`static void AV::AddToProperAnc(Node* u, Group::Type delta);`

Argument

`u`

may be null. If`u`

is nonnull, for every (proper) ancestor`v`

of`u`

, (right-)increments the value of`v`

’s`AV`

field by`delta`

.`typedef dtree::WithAncValue<Group, Base> AV;`

`static void AV::SubtractFromAnc(Node* u, Group::Type delta);`

`static void AV::SubtractFromProperAnc(Node* u, Group::Type delta);`

Argument

`u`

may be null. If`u`

is nonnull, for every (proper) ancestor`v`

of`u`

, (right-)decrements the value of`v`

’s`AV`

field by`delta`

.

`typedef dtree::WithDescValue<Group, Base> DV;`

`static Group::Type DV::Value(Node* u);`

Argument

`u`

must be nonnull. Returns the value of`u`

’s`DV`

field.`typedef dtree::WithDescValue<Group, Base> DV;`

`Group::Type DV::value() const;`

Implicit argument

`this`

**must be the sole node in its tree**. Returns the value of`this`

’s`DV`

field.*Remark:*The invocation syntax is`u->DV::value()`

. This is negligibly more efficient than`DV::Value(u)`

and should be used only when necessary.`typedef dtree::WithDescValue<Group, Base> DV;`

`// EndTreeWithDesc only`

`static void DV::SetValue(Node* u, Group::Type value);`

Argument

`u`

must be nonnull. Sets the value of`u`

’s`DV`

field to`value`

. See also`SetNonDescValue`

below.`typedef dtree::WithDescValue<Group, Base> DV;`

`static void DV::SetNonDescValue(Node* u, Group::Type value);`

Argument

`u`

must be nonnull. Sets the value of`u`

’s`DV`

field to`Group::Plus(Group::Minus(value, value), DV::Value(u))`

. See also`SetValue`

above.`typedef dtree::WithDescValue<Group, Base> DV;`

`void DV::set_value(Group::Type value);`

Implicit argument

`this`

**must be the sole node in its tree**. Sets the value of`this`

’s`DV`

field to`value`

.*Remark:*The invocation syntax is`u->DV::set_value(value)`

. This is negligibly more efficient than`DV::SetValue(u, value)`

and should be used only when necessary.`typedef dtree::WithDescValue<Group, Base> DV;`

`static void DV::AddToTree(Node* u, Group::Type delta);`

`static void DV::AddToDesc(Node* u, Group::Type delta);`

`// EndTreeWithDesc only`

`static void DV::AddToProperDesc(Node* u, Group::Type delta);`

Argument

`u`

may be null. If`u`

is nonnull, for every node`v`

in`u`

’s tree (respectively, every (proper) descendant`v`

of`u`

), (right-)increments the value of`v`

’s`DV`

field by`delta`

.`typedef dtree::WithDescValue<Group, Base> DV;`

`static void DV::SubtractFromTree(Node* u, Group::Type delta);`

`static void DV::SubtractFromDesc(Node* u, Group::Type delta);`

`// EndTreeWithDesc only`

`static void DV::SubtractFromProperDesc(Node* u, Group::Type delta);`

Argument

`u`

may be null. If`u`

is nonnull, for every node`v`

in`u`

’s tree (respectively, every (proper) descendant`v`

of`u`

), (right-)decrements the value of`v`

’s`DV`

field by`delta`

.

With three caveats, all of the methods for ancestor and descendant values described above are available for `WithAncDescValue`

. A custom group with `PlusFilter`

and `MinusFilter`

is required; see below for more details. Intuitively, the filter passes descendant updates only.

`SetValue`

is restricted to trees with descendant pointers. The `delta`

argument for the ancestor-value methods is filtered by `delta = Group::MinusFilter(delta, delta)`

. All of the operations with descendant scope use [`PlusFilter`

instead of `Plus`

] and [`MinusFilter`

instead of `Minus`

].

The transformer `dtree::WithAncAggr<Semigroup, Base>`

extends its second argument to maintain `Semigroup`

aggregates with ancestor (path) scope. The transformer `dtree::WithDescAggr<Semigroup, Base>`

extends its second argument to maintain `Semigroup`

aggregates with descendant (tree) scope. The transformer `dtree::WithAncDescAggr<Semigroup, Base>`

extends its second argument to maintain `Semigroup`

aggregates with both ancestor and descendant scope.

Aggregation uses the value field declared by second argument’s most derived transformer of type `Begin`

, `WithStaticValue`

, `WithAncValue`

, `WithDescValue`

, `WithAncDescValue`

, or maybe `WithEvert`

(don’t make any assumptions). The group implicitly associated with `dtree::Begin<>`

is `dtree::Nop<dtree::NoValue>`

. The group implicitly associated with `dtree::WithStaticValue<Type, Base>`

is `dtree::Nop<Type>`

.

Descendant aggregates require descendant pointers. Searches require an aggregate compatible with the search scope and predicate.

`typedef dtree::WithAncAggr<Semigroup, Base> AA;`

`static Semigroup::Type AA::AggrAnc(Node* u);`

`static Semigroup::Type AA::AggrProperAnc(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, returns the aggregate by`Semigroup`

of the (proper) ancestors of`u`

. Otherwise, returns`Semigroup::empty_aggr()`

.`typedef dtree::WithAncAggr<Semigroup, Base> AA;`

`static Node* AA::FindDirmostAnc(int dir, Node* u, const Predicate& predicate);`

`static Node* AA::FindLeafmostAnc(Node* u, const Predicate& predicate);`

`static Node* AA::FindRootmostAnc(Node* u, const Predicate& predicate);`

`static Node* AA::FindDirmostProperAnc(int dir, Node* u, const Predicate& predicate);`

`static Node* AA::FindLeafmostProperAnc(Node* u, const Predicate& predicate);`

`static Node* AA::FindRootmostProperAnc(Node* u, const Predicate& predicate);`

Argument

`dir`

must be either`dtree::kLeaf`

or`dtree::kRoot`

. Argument`u`

may be null. Argument`predicate`

must be [either a function or a function object] with prototype`bool predicate(Semigroup::Type a)`

and must be compatible with`Semigroup`

. If`u`

is nonnull, returns the`dir`

most (respectively, leafmost or rootmost) (proper) ancestor of`u`

matching`predicate`

. If`u`

is null or no (proper) ancestor of`u`

matches`predicate`

, returns null.Note for writers of custom predicates: as of October 2013, the support of

`predicate`

no longer is required to be a prime ideal. The nodes in scope implicitly are ordered from`dir`

most to`dir`

least, and`predicate`

matches a node if and only if it evaluates to true on the aggregate of the values of that node and all nodes before it in the order.

`// EndTreeWithDesc only`

`typedef dtree::WithDescAggr<Semigroup, Base> DA;`

`static Semigroup::Type DA::AggrTree(Node* u);`

`static Semigroup::Type DA::AggrDesc(Node* u);`

`static Semigroup::Type DA::AggrProperDesc(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, returns the aggregate by`Semigroup`

of the nodes in`u`

’s tree (respectively, the (proper) descendants of`u`

). Otherwise, returns`Semigroup::empty_aggr()`

.`// EndTreeWithDesc only`

`typedef dtree::WithDescAggr<Semigroup, Base> DA;`

`static Node* DA::FindDirmostTree(int dir, Node* u, const Predicate& predicate);`

`static Node* DA::FindLeafmostTree(Node* u, const Predicate& predicate);`

`static Node* DA::FindRootmostTree(Node* u, const Predicate& predicate);`

`static Node* DA::FindDirmostDesc(int dir, Node* u, const Predicate& predicate);`

`static Node* DA::FindLeafmostDesc(Node* u, const Predicate& predicate);`

`static Node* DA::FindRootmostDesc(Node* u, const Predicate& predicate);`

`static Node* DA::FindDirmostProperDesc(int dir, Node* u, const Predicate& predicate);`

`static Node* DA::FindLeafmostProperDesc(Node* u, const Predicate& predicate);`

`static Node* DA::FindRootmostProperDesc(Node* u, const Predicate& predicate);`

Argument

`dir`

must be either`dtree::kLeaf`

or`dtree::kRoot`

. Argument`u`

may be null. Argument`predicate`

must be [either a function or a function object] with prototype`bool predicate(Semigroup::Type a)`

and must be compatible with`Semigroup`

. If`u`

is nonnull, returns a`dir`

most (respectively, leafmost or rootmost) node in`u`

’s tree (respectively, (proper) descendant of`u`

) matching`predicate`

. If`u`

is null or no node in`u`

’s tree (respectively, (proper) descendant of`u`

) matches`predicate`

, returns null.Note for writers of custom predicates: as of October 2013, the support of

`predicate`

no longer is required to be a prime ideal. The nodes in scope implicitly are ordered from`dir`

most to`dir`

least, and`predicate`

matches a node if and only if it evaluates to true on the aggregate of the values of that node and all nodes before it in the order.

All of the methods for ancestor and descendant aggregates described above are available for `WithAncDescAggr`

.

Edges in `dtree`

are not first-class. If edge values are required, there are at least two solutions. The first, which applies if there is no eversion, is to store the value of each edge in its leafmost endpoint. The second is to subdivide each edge and store its value in the midpoint. Neither solution is provided by `dtree`

because both result in leaky abstractions.

Include `"dtree/seq.h"`

for the types and `"dtree/seq-inl.h"`

for the functions. The transformer `dtree::EndSeq<Base>`

yields a node type for sequences. This transformer must be the **last** to be applied (most derived).

`bool SameSeq(Node* u, Node* v);`

`bool Connected(Node* u, Node* v); // deprecated`

Arguments

`u`

and`v`

each may be null. Returns whether [`u`

and`v`

are both nonnull and belong to the same sequence] or [`u`

and`v`

are both null].*Remark:*`SameSeq`

is an equivalence relation.`Node* CutDirOf(int dir, Node* u);`

`Node* CutLeftOf(Node* u);`

`Node* CutRightOf(Node* u);`

Argument

`dir`

must be either`dtree::kLeft`

or`dtree::kRight`

. Argument`u`

may be null. If`u`

is nonnull and has a node`v`

immediately to the`dir`

(respectively, left or right), splits the sequence between`u`

and`v`

and returns a node in the same new sequence as`v`

. Otherwise, has no effect and returns null.`Node* Dir(int dir, Node* u);`

`Node* Left(Node* u);`

`Node* Right(Node* u);`

Argument

`dir`

must be either`dtree::kLeft`

or`dtree::kRight`

. Argument`u`

may be null. If`u`

is nonnull, returns the`dir`

most (respectively, leftmost or rightmost) node in`u`

’s sequence. Otherwise, returns null.`Node* Dirward(int dir, Node* u);`

`Node* Leftward(Node* u);`

`Node* Rightward(Node* u);`

Argument

`dir`

must be either`dtree::kLeft`

or`dtree::kRight`

. Argument`u`

may be null. If`u`

is nonnull, returns the node immediately to the`dir`

(respectively, left or right) of`u`

. If`u`

is null or is the`dir`

most (respectively, leftmost or rightmost) node in its sequence, returns null.`Node* LinkDirOf(int dir, Node* u, Node* v);`

`Node* LinkLeftOf(Node* u, Node* v);`

`Node* LinkRightOf(Node* u, Node* v);`

Argument

`dir`

must be either`dtree::kLeft`

or`dtree::kRight`

. Arguments`u`

and`v`

each may be null. If`u`

and`v`

are both nonnull, asserts that`u`

and`v`

do not belong to the same sequence, joins the sequences of`u`

and`v`

so that`u`

is to the`dir`

(respectively, left or right) of`v`

, and returns the`dir`

most (respectively, leftmost or rightmost) node in`v`

’s former sequence. If`u`

is null, returns`v`

. If`v`

is null, returns`u`

.

The template class `dtree::ScopedCutDirOf<Node>`

streamlines the idiom of cutting a sequence, operating on one of its parts, and linking the parts back together again. Analogous subclasses `dtree::ScopedCutLeftOf<Node>`

and `dtree::ScopedCutRightOf<Node>`

binding `dir`

to `dtree::kLeft`

or `dtree::kRight`

respectively also are provided.

`dtree::ScopedCutDirOf<Node> cut(dir, u);`

The constructor calls

`CutDirOf(dir, u)`

and stores the return value in a member variable that can be accessed by calling`cut.excl_part()`

. Argument`dir`

can be accessed by calling`cut.dir()`

, and argument`u`

can be accessed by calling`cut.incl_part()`

. The destructor calls`LinkDirOf(dir, cut.excl_part(), u)`

, which, absent other changes, restores`u`

’s former sequence.

The transformer `dtree::WithReverse<Base>`

extends its argument to support the `ReverseSeq`

operation.

`typedef dtree::WithReverse<Base> R;`

`static void R::ReverseSeq(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, reverses`u`

’s sequence.

The transformer `dtree::WithValue<Group, Base>`

extends its second argument by a value field supporting bulk addition and subtraction in `Group`

.

`typedef dtree::WithValue<Group, Base> V;`

`static Group::Type V::Value(Node* u);`

Argument

`u`

must be nonnull. Returns the value of`u`

’s`V`

field.`typedef dtree::WithValue<Group, Base> V;`

`Group::Type V::value() const;`

Implicit argument

`this`

**must be the sole node in its sequence**. Returns the value of`this`

’s`V`

field.*Remark:*The invocation syntax is`u->V::value()`

. This is negligibly more efficient than`V::Value(u)`

and should be used only when necessary.`typedef dtree::WithValue<Group, Base> V;`

`static void V::SetValue(Node* u, Group::Type value);`

Argument

`u`

must be nonnull. Sets the value of`u`

’s`V`

field to`value`

.`typedef dtree::WithValue<Group, Base> V;`

`void V::set_value(Group::Type value);`

Implicit argument

`this`

**must be the sole node in its sequence**. Sets the value of`this`

’s`V`

field to`value`

.*Remark:*The invocation syntax is`u->V::set_value(value)`

. This is negligibly more efficient than`V::SetValue(u, value)`

and should be used only when necessary.`typedef dtree::WithValue<Group, Base> V;`

`static void V::AddToSeq(Node* u, Group::Type delta);`

Argument

`u`

may be null. If`u`

is nonnull, for every node in`v`

in`u`

’s sequence, (right-)increments the value of`v`

’s`V`

field by`delta`

.`typedef dtree::WithValue<Group, Base> V;`

`static void V::SubtractFromSeq(Node* u, Group::Type delta);`

Argument

`u`

may be null. If`u`

is nonnull, for every node in`v`

in`u`

’s sequence, (right-)decrements the value of`v`

’s`V`

field by`delta`

.

The transformer `dtree::WithAggr<Semigroup, Base>`

extends its second argument to maintain `Semigroup`

aggregates. Aggregation uses the value field declared by second argument’s most derived transformer of type `Begin`

, `WithValue`

, or maybe `WithReverse`

(don’t make any assumptions). The group implicitly associated with `Begin`

is `dtree::Nop<dtree::NoValue>`

.

Searches require an aggregate compatible with the search predicate.

`typedef dtree::WithAggr<Semigroup, Base> A;`

`static Semigroup::Type A::AggrSeq(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, returns the aggregate by`Semigroup`

of the nodes in`u`

’s sequence. Otherwise, returns`Semigroup::empty_aggr()`

.`typedef dtree::WithAggr<Semigroup, Base> A;`

`static Node* A::FindDirmostSeq(int dir, Node* u, const Predicate& predicate);`

`static Node* A::FindLeftmostSeq(Node* u, const Predicate& predicate);`

`static Node* A::FindRightmostSeq(Node* u, const Predicate& predicate);`

Argument

`dir`

must be either`dtree::kLeft`

or`dtree::kRight`

. Argument`u`

may be null. Argument`predicate`

must be [either a function or a function object] with prototype`bool predicate(Semigroup::Type a)`

and must be compatible with`Semigroup`

. If`u`

is nonnull, returns the`dir`

most (respectively, leftmost or rightmost) node in`u`

’s sequence matching`predicate`

. If`u`

is null or no node in`u`

’s sequence matches`predicate`

, returns null.Note for writers of custom predicates: as of October 2013, the support of

`predicate`

no longer is required to be a prime ideal. The nodes in scope implicitly are ordered from`dir`

most to`dir`

least, and`predicate`

matches a node if and only if it evaluates to true on the aggregate of the values of that node and all nodes before it in the order.

The template group `dtree::DpAdd<T>`

provides pairs of values under componentwise addition that, when used with the proper transformers, respond to eversion or reversal. One element of the pair is denoted `lw`

, for leafward or leftward, and the other is denoted `rw`

, for rootward or rightward. The implementation of directed pairs uses the wreath product (`T`

, +) ≀ **Z**_{2}. Read the appendix before choosing `T`

to be an unsigned or floating-point type.

The value type for directed pairs is `dtree::DpValue<T>`

, with a zero-argument constructor that constructs zero and a two-argument constructor with arguments `lw`

and `rw`

. The aggregate type for directed pairs is `dtree::DpAggr<T>`

, with analogous constructors. These types are distinct because `DpValue`

also has a flip member. Both types have getters `.lw()`

and `.rw()`

and setters `.set_lw(T lw)`

and `.set_rw(T rw)`

. Additionally, getter `.dw(int dir)`

and setter `.set_dw(int dir, T dw)`

provide generic access to `lw`

and `rw`

by accepting a direction argument that is either `dtree::kLw`

or `dtree::kRw`

. For convenience, it is guaranteed that `dtree::kLw == dtree::kLeaf`

and `dtree::kRw == dtree::kRoot`

and `dtree::kLw == dtree::kLeft`

and `dtree::kRw == dtree::kRight`

.

Directed pairs are especially useful in combination with simulated edge values.

`typedef dtree::WithEvertBy<dtree::WithAncValue<dtree::DpAdd<T>, Base> > EB;`

`static void EB::Evert(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, changes the root of`u`

’s tree to`u`

and, for every former ancestor`v`

of`u`

, exchanges`v`

’s leafward value with`v`

’s rootward value.

`typedef dtree::WithReverseBy<WithValue<dtree::DpAdd<T>, Base> > RB;`

`static void RB::ReverseSeq(Node* u);`

Argument

`u`

may be null. If`u`

is nonnull, reverses`u`

’s sequence and, for every node`v`

in`u`

’s sequence, exchanges`v`

’s leftward value with`v`

’s rightward value.

Pass these to `WithAncAggr`

, `WithDescAggr`

, or `WithAggr`

.

`dtree::DpMax<T>`

: the maximum leaf/leftward value and the maximum root/rightward value of the nodes in scope, compatible with`dtree::DpAdd<T>`

`dtree::DpMin<T>`

: the minimum leaf/leftward value and the minimum root/rightward value of the nodes in scope, compatible with`dtree::DpAdd<T>`

Pass these to `Find*`

.

`dtree::DwGreater(int dir, T b)`

: on argument`a`

, returns`a.dw(dir) > b`

, compatible with`dtree::DpMax<T>`

`dtree::DwGreaterEqual(int dir, T b)`

: on argument`a`

, returns`a.dw(dir) >= b`

, compatible with`dtree::DpMax<T>`

`dtree::DwLess(int dir, T b)`

: on argument`a`

, returns`a.dw(dir) < b`

, compatible with`dtree::DpMin<T>`

`dtree::DwLessEqual(int dir, T b)`

: on argument`a`

, returns`a.dw(dir) <= b`

, compatible with`dtree::DpMin<T>`

`dtree::LwGreater(T b)`

: on argument`a`

, returns`a.lw() > b`

, compatible with`dtree::DpMax<T>`

`dtree::LwGreaterEqual(T b)`

: on argument`a`

, returns`a.lw() >= b`

, compatible with`dtree::DpMax<T>`

`dtree::LwLess(T b)`

: on argument`a`

, returns`a.lw() < b`

, compatible with`dtree::DpMin<T>`

`dtree::LwLessEqual(T b)`

: on argument`a`

, returns`a.lw() <= b`

, compatible with`dtree::DpMin<T>`

`dtree::RwGreater(T b)`

: on argument`a`

, returns`a.rw() > b`

, compatible with`dtree::DpMax<T>`

`dtree::RwGreaterEqual(T b)`

: on argument`a`

, returns`a.rw() >= b`

, compatible with`dtree::DpMax<T>`

`dtree::RwLess(T b)`

: on argument`a`

, returns`a.rw() < b`

, compatible with`dtree::DpMin<T>`

`dtree::RwLessEqual(T b)`

: on argument`a`

, returns`a.rw() <= b`

, compatible with`dtree::DpMin<T>`

The appendix describes `dtree`

in more detail than is necessary for most uses.

“Group”, `Plus`

, and `Minus`

are misnomers; see the nonstandard axioms below. Groups are specified by classes with three public members.

- a type
`Type`

for values (must be default-constructible, copyable, and assignable) - a static method
`Type Plus(Type x, Type y)`

- a static method
`Type Minus(Type x, Type y)`

An example of a group follows.

```
struct AddInt {
typedef int Type;
int Plus(int x, int y) { return x + y; }
int Minus(int x, int y) { return x - y; }
};
```

Groups must satisfy several axioms. `Plus`

and `Minus`

must be associative.

`Plus(x, Plus(y, z)) == Plus(Plus(x, y), z)`

`Plus(x, Minus(y, z)) == Minus(Plus(x, y), z)`

`Minus(x, Plus(y, z)) == Minus(Minus(x, z), y)`

`Minus(x, Minus(y, z)) == Minus(Plus(x, z), y)`

`Plus(·, y)`

and `Minus(·, y)`

must be inverses.

`Minus(Plus(x, y), y) == x`

`Plus(Minus(x, y), y) == x`

`WithEvertBy`

and `WithReverseBy`

To be used with `WithEvertBy`

or `WithReverseBy`

, a group must have two additional public members.

- a static method
`int FlippedFromValue(Type x)`

- a static method
`Type flip_delta()`

`FlippedFromValue`

must be a homomorphism from the group to **Z**_{2}.

`FlippedFromValue(x) == 0 || FlippedFromValue(x) == 1`

`FlippedFromValue(Plus(x, y)) == FlippedFromValue(x) ^ FlippedFromValue(y)`

`FlippedFromValue(Minus(x, y)) == FlippedFromValue(x) ^ FlippedFromValue(y)`

`flip_delta()`

must have an effect.

`FlippedFromValue(flip_delta()) == 1`

`WithAncDescValue`

To be used with `WithAncDescValue`

, a group must have two additional public members.

- a static method
`Type PlusFilter(Type x, Type y)`

- a static method
`Type MinusFilter(Type x, Type y)`

There are several more axioms. To specify them compactly, we stipulate the existence of a function `Type Filter(Type x)`

with the following properties.

`Filter(Plus(x, y)) == Plus(Filter(x), Filter(y))`

`Filter(Minus(x, y)) == Minus(Filter(x), Filter(y))`

`Filter(Filter(x)) == Filter(x)`

`PlusFilter(x, y) == Plus(x, Filter(y))`

`MinusFilter(x, y) == Minus(x, Filter(y))`

`FlippedFromValue(Filter(x)) == 0`

(if`FlippedFromValue`

is defined)

Semigroups are specified by classes with four public members.

- a type
`Type`

for aggregates (must be default-constructible, copyable, and assignable) - a static method
`Type AggrFromValue(Group::Type x)`

that converts a value into a singleton aggregate - a static method
`Type CombineAggrs(Type a, Type b)`

- a static method
`Type empty_aggr()`

An example of an semigroup follows.

```
struct MinInt {
typedef int Type;
int AggrFromValue(int x) { return x; }
int CombineAggrs(int a, int b) { return std::min(a, b); }
int empty_aggr() { return std::numeric_limits<int>::max(); }
};
```

The group must have a right action on aggregates consisting of two public members.

- a static method
`Type Group::Plus(Type a, Group::Type x)`

- a static method
`Type Group::Minus(Type a, Group::Type x)`

Right actions must satisfy several axioms analogous to the group axioms.

`Plus(a, Plus(x, y)) == Plus(Plus(a, x), y)`

`Plus(a, Minus(x, y)) == Minus(Plus(a, x), y)`

`Minus(a, Plus(x, y)) == Minus(Minus(a, y), x)`

`Minus(a, Minus(x, y)) == Minus(Plus(a, y), x)`

`Minus(Plus(a, x), x) == a`

`Plus(Minus(a, x), x) == a`

Semigroups must satisfy several axioms and be compatible with the group and its right action. `CombineAggrs`

must be commutative and associative.

`CombineAggrs(a, b) == CombineAggrs(b, a)`

`CombineAggrs(a, CombineAggrs(b, c)) == CombineAggrs(CombineAggrs(a, b), c)`

`empty_aggr()`

must be the identity element of `CombineAggrs`

.

`CombineAggrs(empty_aggr(), a) == a`

`CombineAggrs(a, empty_aggr()) == a`

`AggrFromValue`

must commute with `Plus(·, y)`

and `Minus(·, y)`

.

`AggrFromValue(Plus(x, y)) == Plus(AggrFromValue(x), y)`

`AggrFromValue(Minus(x, y)) == Minus(AggrFromValue(x), y)`

`Plus`

and `Minus`

must distribute over `CombineAggrs`

.

`CombineAggrs(Plus(a, x), Plus(b, x)) == Plus(CombineAggrs(a, b), x)`

`CombineAggrs(Minus(a, x), Minus(b, x)) == Minus(CombineAggrs(a, b), x)`

`WithAncDescValue`

The group must have a filtered right action on aggregates consisting of two public members.

- a static method
`Type Group::PlusFilter(Type a, Group::Type x)`

- a static method
`Type Group::MinusFilter(Type a, Group::Type x)`

This action must satisfy the following two axioms, where `Filter`

is the witness from before.

`PlusFilter(a, x) == Plus(a, Filter(x))`

`MinusFilter(a, x) == Minus(a, Filter(x))`

Predicates must satisfy the following three axioms. In algebraic terms, the support of a predicate must be a proper two-sided ideal of the semigroup.

`!predicate(a) || predicate(CombineAggrs(a, b))`

`!predicate(b) || predicate(CombineAggrs(a, b))`

`!predicate(empty_aggr())`

Technically, since the behavior of signed-integer overflow is undefined in C++, `dtree::Add<int>`

may not be a group. Even if overflow is resolved modulo `UINT_MAX + 1`

, the group `dtree::Add<int>`

is not compatible with the semigroup `dtree::Min<int>`

, as the distributive axiom `min(a + x, b + x) == min(a, b) + x`

is violated in some cases where exactly one of the additions on the left-hand side wraps around. Floating-point numbers are problematic as well; floating-point addition, for example, is not associative.

Fortunately, axiom violations that `dtree`

does not observe do not affect correctness. Since `dtree`

constructs values and aggregates in only a few ways, detailed below, careful use can keep all violations hidden. For integers, it suffices never to store negative values. For floating-point numbers, this means using a subset on which floating-point arithmetic behaves like fixed-point.

At all times, for every node `u`

and every value field, the value `x`

of `u`

may be constructed. Additionally, for every node `w`

in the same tree/sequence as `u`

, the value `Minus(x, y)`

may be constructed, where `y`

is the value of `w`

. For every [aggregate associated with the value field] and every nonempty set of nodes in the same tree/sequence, the aggregate `a`

of that set may be constructed, as may, for every node `u`

in the set, `Minus(a, x)`

, where `x`

is the value of `u`

. The identity element `empty_aggr()`

may be constructed. `WithAncDescAggr`

may construct `Minus(empty_aggr(), x)`

.

For the non-standalone headers, defining the preprocessor symbol `NAIVE_DTREE`

causes the implementations based on splay trees to be replaced by ones based on linked lists. The latter often are faster for small numbers of nodes. The naive tree omits descendant pointers, descendant values, and descendant aggregates. The naive sequence omits nothing.

Include `"dtree/tree-extra.h"`

.

`void EvertByTraversing(Node* u, Visitor* v);`

Argument

`u`

may be null. Argument`v`

must be a nonnull pointer to a [function or function object] with prototype`void (*v)(Node* w)`

. If`u`

is nonnull, changes root of`u`

’s tree from some node`r`

to`u`

. Calls the visitor`*v`

on every node of the path`u`

, …,`r`

in order. Values of`w`

are available via`.value`

methods. Ancestor values not providing eversion can be set via`.set_value`

methods. Other`dtree`

functions must not be called with arguments belonging to the same tree as`u`

. Excluding the cost of calling`*v`

, the running time for a node of depth*d*is*O*(*d*).*Remark:*the savings of not requesting`WithEvert`

may be larger than the added cost of`EvertByTraversing`

over`Evert`

.`void Assemble(Node node[], size_t num_nodes);`

Argument

`node`

must be a nonnull array with`num_nodes`

nodes.`Assemble`

must be called at the end of an**assembly interaction**, where the forest is first specified by calling the method`void Node::set_parent(Node* p)`

on every node in the array that will not be a root. Prior to the assembly interaction, every node in the array**must be the sole node in its tree**. The running time is*O*(`num_nodes`

). Temporarily allocates an array of`num_nodes`

node pointers and uses log-depth recursion.*Remark:*the forests created by`Assemble`

have linear potential (an upper bound on the amount of work in excess of log per operation), which, for some algorithms, is theoretically necessary to achieve linear running times. In practice,`Assemble`

always seems to be slower than just linking the forest despite the possibility of this naive approach creating a forest with linearithmic potential.`void CutOneOfMany(Node* u);`

Argument

`u`

must be nonnull.`CutOneOfMany`

must be called on each node in a tree. Afterward, each node on which`CutOneOfMany`

is called is the sole node in its tree.`CutOneOfMany`

and calls to`.value`

may be interleaved. The total running time for an*n*-node forest is*O*(*n*).*Remark:*`CutOneOfMany`

may be faster than [bulk cuts] or [bulk retrievals of final values].

© 2012–2014 David Eisenstat