Skip to content

Commit 7fef5e4

Browse files
iluwatariluwatar
authored
Merge pull request iluwatar#696 from besok/master
iluwatar#677 add pattern Trampoline.
2 parents d78434f + 9667878 commit 7fef5e4

File tree

7 files changed

+290
-1
lines changed

7 files changed

+290
-1
lines changed

‎pom.xml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -147,13 +147,13 @@
147147
<module>event-sourcing</module>
148148
<module>data-transfer-object</module>
149149
<module>throttling</module>
150-
151150
<module>unit-of-work</module>
152151
<module>partial-response</module>
153152
<module>eip-wire-tap</module>
154153
<module>eip-splitter</module>
155154
<module>eip-aggregator</module>
156155
<module>retry</module>
156+
<module>trampoline</module>
157157
</modules>
158158

159159
<repositories>

‎trampoline/.gitignore

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
/target/
2+
.idea/

‎trampoline/README.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
---
2+
layout: pattern
3+
title: Trampoline
4+
folder: trampoline
5+
permalink: /patterns/trampoline/
6+
categories: Behavior
7+
tags:
8+
- Java
9+
- Difficulty-Intermediate
10+
- Performance
11+
- Recursion
12+
---
13+
14+
## Intent
15+
Trampoline pattern is used for implementing algorithms recursively in Java without blowing the stack
16+
and to interleave the execution of functions without hard coding them together
17+
It is possible by representing a computation in one of 2 states : done | more
18+
(completed with result, or a reference to the reminder of the computation,
19+
something like the way a java.util.Supplier does).
20+
21+
22+
## Explanation
23+
Trampoline pattern allows to define recursive algorithms by iterative loop.
24+
25+
26+
## Applicability
27+
Use the Trampoline pattern when
28+
29+
* For implementing tail recursive function. This pattern allows to switch on a stackless operation.
30+
* For interleaving the execution of two or more functions on the same thread.
31+
32+
## Known uses(real world examples)
33+
* Trampoline refers to using reflection to avoid using inner classes, for example in event listeners.
34+
The time overhead of a reflection call is traded for the space overhead of an inner class.
35+
Trampolines in Java usually involve the creation of a GenericListener to pass events to an outer class.
36+
37+
38+
## Tutorials
39+
* [Trampolining: a practical guide for awesome Java Developers](https://medium.com/@johnmcclean/trampolining-a-practical-guide-for-awesome-java-developers-4b657d9c3076)
40+
* [Trampoline in java ](http://mindprod.com/jgloss/trampoline.html)
41+
42+
## Credits
43+
* [library 'cyclops-react' uses the pattern](https://github.com/aol/cyclops-react)
44+
45+

‎trampoline/pom.xml

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
<?xml version="1.0"?>
2+
<!--
3+
4+
The MIT License
5+
Copyright (c) 2014-2016 Ilkka Seppälä
6+
7+
Permission is hereby granted, free of charge, to any person obtaining a copy
8+
of this software and associated documentation files (the "Software"), to deal
9+
in the Software without restriction, including without limitation the rights
10+
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11+
copies of the Software, and to permit persons to whom the Software is
12+
furnished to do so, subject to the following conditions:
13+
14+
The above copyright notice and this permission notice shall be included in
15+
all copies or substantial portions of the Software.
16+
17+
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18+
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19+
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20+
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21+
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22+
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23+
THE SOFTWARE.
24+
25+
-->
26+
<project xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"
27+
xmlns="http://maven.apache.org/POM/4.0.0"
28+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
29+
<modelVersion>4.0.0</modelVersion>
30+
<parent>
31+
<groupId>com.iluwatar</groupId>
32+
<artifactId>java-design-patterns</artifactId>
33+
<version>1.19.0-SNAPSHOT</version>
34+
35+
</parent>
36+
<artifactId>trampoline</artifactId>
37+
<dependencies>
38+
<dependency>
39+
<groupId>junit</groupId>
40+
<artifactId>junit</artifactId>
41+
<version>4.12</version>
42+
<scope>test</scope>
43+
</dependency>
44+
45+
<dependency>
46+
<groupId>org.junit.jupiter</groupId>
47+
<artifactId>junit-jupiter-api</artifactId>
48+
<scope>test</scope>
49+
</dependency>
50+
<dependency>
51+
<groupId>org.junit.jupiter</groupId>
52+
<artifactId>junit-jupiter-engine</artifactId>
53+
<scope>test</scope>
54+
</dependency>
55+
56+
<dependency>
57+
<groupId>org.projectlombok</groupId>
58+
<artifactId>lombok</artifactId>
59+
<version>1.16.18</version>
60+
</dependency>
61+
62+
63+
</dependencies>
64+
65+
<build>
66+
<plugins>
67+
<plugin>
68+
<groupId>org.apache.maven.plugins</groupId>
69+
<artifactId>maven-surefire-plugin</artifactId>
70+
<version>2.19</version>
71+
<configuration>
72+
<skipTests>false</skipTests>
73+
</configuration>
74+
</plugin>
75+
</plugins>
76+
</build>
77+
</project>

‎trampoline/src/main/java/com/iluwatar/trampoline/Trampoline.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.iluwatar.trampoline;
2+
3+
import java.util.stream.Stream;
4+
5+
/**
6+
* <p>Trampoline pattern allows to define recursive algorithms by iterative loop </p>
7+
* <p>When get is called on the returned Trampoline, internally it will iterate calling ‘jump’
8+
* on the returned Trampoline as long as the concrete instance returned is {@link #more(Trampoline)},
9+
* stopping once the returned instance is {@link #done(Object)}.</p>
10+
* <p>Essential we convert looping via recursion into iteration,
11+
* the key enabling mechanism is the fact that {@link #more(Trampoline)} is a lazy operation.</p>
12+
*
13+
* @param <T> is type for returning result.
14+
*/
15+
public interface Trampoline<T> {
16+
T get();
17+
18+
19+
/**
20+
* @return next stage
21+
*/
22+
default Trampoline<T> jump() {
23+
return this;
24+
}
25+
26+
27+
default T result() {
28+
return get();
29+
}
30+
31+
/**
32+
* @return true if complete
33+
*/
34+
default boolean complete() {
35+
return true;
36+
}
37+
38+
/**
39+
* Created a completed Trampoline
40+
*
41+
* @param result Completed result
42+
* @return Completed Trampoline
43+
*/
44+
static <T> Trampoline<T> done(final T result) {
45+
return () -> result;
46+
}
47+
48+
49+
/**
50+
* Create a Trampoline that has more work to do
51+
*
52+
* @param trampoline Next stage in Trampoline
53+
* @return Trampoline with more work
54+
*/
55+
static <T> Trampoline<T> more(final Trampoline<Trampoline<T>> trampoline) {
56+
return new Trampoline<T>() {
57+
@Override
58+
public boolean complete() {
59+
return false;
60+
}
61+
62+
@Override
63+
public Trampoline<T> jump() {
64+
return trampoline.result();
65+
}
66+
67+
@Override
68+
public T get() {
69+
return trampoline(this);
70+
}
71+
72+
T trampoline(final Trampoline<T> trampoline) {
73+
74+
return Stream.iterate(trampoline, Trampoline::jump)
75+
.filter(Trampoline::complete)
76+
.findFirst()
77+
.get()
78+
.result();
79+
80+
}
81+
};
82+
}
83+
84+
85+
}

‎trampoline/src/main/java/com/iluwatar/trampoline/TrampolineApp.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
/**
2+
* The MIT License
3+
* Copyright (c) 2014-2016 Ilkka Seppälä
4+
* <p>
5+
* Permission is hereby granted, free of charge, to any person obtaining a copy
6+
* of this software and associated documentation files (the "Software"), to deal
7+
* in the Software without restriction, including without limitation the rights
8+
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9+
* copies of the Software, and to permit persons to whom the Software is
10+
* furnished to do so, subject to the following conditions:
11+
* <p>
12+
* The above copyright notice and this permission notice shall be included in
13+
* all copies or substantial portions of the Software.
14+
* <p>
15+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16+
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17+
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18+
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19+
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20+
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21+
* THE SOFTWARE.
22+
*/
23+
24+
package com.iluwatar.trampoline;
25+
26+
27+
import lombok.extern.slf4j.Slf4j;
28+
29+
/**
30+
* <p>Trampoline pattern allows to define recursive algorithms by iterative loop </p>
31+
* <p>it is possible to implement algorithms recursively in Java without blowing the stack
32+
* and to interleave the execution of functions without hard coding them together or even using threads.</p>
33+
*/
34+
@Slf4j
35+
public class TrampolineApp {
36+
37+
/**
38+
* Main program for showing pattern. It does loop with factorial function.
39+
* */
40+
public static void main(String[] args) {
41+
log.info("start pattern");
42+
Integer result = loop(10, 1).result();
43+
log.info("result {}", result);
44+
45+
}
46+
47+
/**
48+
* Manager for pattern. Define it with a factorial function.
49+
*/
50+
public static Trampoline<Integer> loop(int times, int prod) {
51+
if (times == 0) {
52+
return Trampoline.done(prod);
53+
} else {
54+
return Trampoline.more(() -> loop(times - 1, prod * times));
55+
}
56+
}
57+
58+
}

‎trampoline/src/test/java/com/iluwatar/trampoline/TrampolineAppTest.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.iluwatar.trampoline;
2+
3+
import org.junit.Test;
4+
5+
import java.io.IOException;
6+
7+
import static org.junit.Assert.*;
8+
9+
10+
/**
11+
* Test for trampoline pattern.
12+
* */
13+
public class TrampolineAppTest {
14+
15+
16+
@Test
17+
public void testTrampolineWithFactorialFunction() throws IOException {
18+
int result = TrampolineApp.loop(10, 1).result();
19+
assertEquals("Be equal", 3628800, result);
20+
}
21+
22+
}

0 commit comments

Comments
 (0)