traversal 0.1.1

Generic and lazy tree traversal algorithms
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

# traversal


[![Build Status](https://travis-ci.org/vallentin/traversal.svg?branch=master)](https://travis-ci.org/vallentin/traversal)
[![Latest Version](https://img.shields.io/crates/v/traversal.svg)](https://crates.io/crates/traversal)
[![Docs](https://docs.rs/traversal/badge.svg)](https://docs.rs/traversal)
[![License](https://img.shields.io/github/license/vallentin/traversal.svg)](https://github.com/vallentin/traversal)

Traversal implements generic and lazy tree traversal algorithms.

Includes:
- [Breadth-First Traversal] ([`Bft`])
- [Depth-First Traversal] in Pre-Order ([`DftPre`])
- [Depth-First Traversal] in Post-Order ([`DftPost`])
- Reverse [Depth-First Traversal] in Pre-Order ([`DftPreRev`])
- Reverse [Depth-First Traversal] in Post-Order ([`DftPostRev`])
<!---->
- All Paths ([`DftPaths`])
- Longest Paths ([`DftLongestPaths`])
- All Cycles (Paths) ([`DftCycles`])

[Breadth-First Traversal]: https://en.wikipedia.org/wiki/Tree_traversal
[Depth-First Traversal]: https://en.wikipedia.org/wiki/Tree_traversal

### Generic


Traversal uses [generics] (or [type parameters]) to be
flexible to use, and easy to implement and fit into existing
architecture.

[generics]: https://doc.rust-lang.org/rust-by-example/generics.html
[type parameters]: https://doc.rust-lang.org/reference/types/parameters.html

### Laziness


Laziness or [lazy evaluation] refers to evaluation being delayed
until needed.

Traversal delays processing `Node`s and fetching child `Node`s
until [`Iterator::next`][`next`] is called.
When [`next`] is called, then traversal only processes the
`Node`s required for this iteration.

[lazy evaluation]: https://en.wikipedia.org/wiki/Lazy_evaluation

*From Rust's docs:*

> *Iterators (and iterator [adapters]) are lazy. This means that just
> creating an iterator doesn't do a whole lot. Nothing really happens
> until you call [`next`].*
>
> &mdash; [`Iterator`] - [Laziness]

[`Iterator`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html
[`next`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#tymethod.next

[Laziness]: https://doc.rust-lang.org/std/iter/index.html#laziness
[adapters]: https://doc.rust-lang.org/std/iter/index.html#adapters

## Usage


Add this to your `Cargo.toml`:

```toml
[dependencies]
every-range = "0.1"
```

## Algorithms


```text
     A
    / \
   B   C
  / \ / \
 D  E F  G
```

Given the above tree, then the following are the orders,
that each individual iterator / traversal algorithm produces.

| Algorithm | Order |
|-----------|-------|
| [`Bft`]        (Breadth-First Traversal)                     | A, B, C, D, E, F, G |
| [`DftPre`]     (Depth-First Traversal in Pre-Order)          | A, B, D, E, C, F, G |
| [`DftPost`]    (Depth-First Traversal in Post-Order)         | D, E, B, F, G, C, A |
| [`DftPreRev`]  (Reverse Depth-First Traversal in Pre-Order)  | G, F, C, E, D, B, A |
| [`DftPostRev`] (Reverse Depth-First Traversal in Post-Order) | A, C, G, F, B, E, D |

*See each individual algorithm for code examples.*

[`Bft`]: https://docs.rs/traversal/*/traversal/struct.Bft.html
[`DftPre`]: https://docs.rs/traversal/*/traversal/struct.DftPre.html
[`DftPost`]: https://docs.rs/traversal/*/traversal/struct.DftPost.html
[`DftPreRev`]: https://docs.rs/traversal/*/traversal/struct.DftPreRev.html
[`DftPostRev`]: https://docs.rs/traversal/*/traversal/struct.DftPostRev.html

### All Paths and Longest Paths


[`DftPaths`] and [`DftLongestPaths`] are utilities for
iterating all paths and the longest paths in a tree.

*Given the same tree as the previous examples, then
[`DftPaths`] and [`DftLongestPaths`] produce the
following paths.*

[`DftPaths`]:
- A, B
- A, B, D
- A, B, E
- A, C
- A, C, F
- A, C, G

[`DftLongestPaths`]:
- A, B, D
- A, B, E
- A, C, F
- A, C, G

*See each individual algorithm for code examples.*

[`DftPaths`]: https://docs.rs/traversal/*/traversal/struct.DftPaths.html
[`DftLongestPaths`]: https://docs.rs/traversal/*/traversal/struct.DftLongestPaths.html

## Cycles


```text
  A <---+
 / \    |
B   D >-+
|   |   |
C   E >-+
```

[`DftCycles`]:
- A -> D (*implies D is connected with A*)
- A -> D -> E

*See each individual algorithm for code examples.*

[`DftCycles`]: https://docs.rs/traversal/*/traversal/struct.DftCycles.html