PowTrees.LINQPad 0.0.48

PowTrees

Table of content

• Introduction
• Usage
• License

Introduction

Tree structure with algorithms

Usage

FoldL

Map a tree recursively. For each node, we use the node and the mapped parent as input

Signature:

static TNod<U> FoldL<T, U>(
	this TNod<T> root,
	Func<TNod<T>, U, U> fun,
	U seed
);

Example:

record Rec(int Val, int Ofs); // where Ofs is an offset we want to apply to Val

// root =
//                 ┌►(30,0)        
//                 │               
// (10,0)──►(20,3)─┤        ┌►(50,0)
//                 └►(40,6)─┤      
//                          └►(60,1)

// 1. Apply Ofs on the node and its descendents:
// ---------------------------------------------
root.FoldL((nod, acc) => acc + nod.V.Ofs, 0)
      ┌►3    
      │      
0──►3─┤   ┌►9
      └►9─┤  
          └►10

// 2. Apply Ofs on the node descendents only:
// ------------------------------------------
root.FoldL((nod, acc) => acc + nod.ParentOr(e => e.Ofs, 0), 0)
      ┌►3   
      │     
0──►0─┤   ┌►9
      └►3─┤ 
          └►9

// 3. Create a dictionary from the nodes to their accumulators
// -----------------------------------------------------------
root.Zip(root.FoldL(fun))
	.ToDictionary(
		e => e.First.V,
		e => e.Second.V
	);

As these cases are quite common, there are some utility functions to implement them easily:

static TNod<U> FoldL_Parent<T, U>(
	this TNod<T> root,
	Func<T, U> get,
	Func<U, U, U> fun,
	U seed
);

static IReadOnlyDictionary<T, U> FoldL_Dict<T, U>(
	this TNod<T> root,
	Func<T, U, U> fun,
	U seed
) where T : notnull;

static IReadOnlyDictionary<T, U> FoldL_Parent_Dict<T, U>(
	this TNod<T> root,
	Func<T, U> get,
	Func<U, U, U> fun,
	U seed
) where T : notnull;

Build a node lookup map

If you transform a tree (A) into tree (B) without changing its shape (just changing the node content, not children). Very often, you then need to map the nodes of B back to A. For this use:

static IReadOnlyDictionary<TNod<T>, TNod<U>> BuildNodeLookup<T, U>(TNod<T> rootSrc, TNod<U> rootDst);

var lookupMap = TreeUtils.BuildNodeLookup(B, A);

License

MIT