Created memoization decoration.

5 files changed, 64 insertions, 8 deletions

diff --git a/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala b/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala
index 96cf142..1200926 100755
--- a/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala
+++ b/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala
@@ -1,6 +1,7 @@
 package com.rockymadden.stringmetric
 
 object Algorithm {
+	import scala.collection.immutable.Map
 	import Transform.StringTransform
 
 
@@ -34,13 +35,28 @@ object Algorithm {
 
 
 	final class StringAlgorithmDecorator(val sa: StringAlgorithm) {
+		val withMemoization: StringAlgorithm = new StringAlgorithm {
+			private val base: StringAlgorithm = sa
+			private var memo: Map[String, Option[String]] = Map()
+
+			override def compute(a: Array[Char]): Option[Array[Char]] =
+				compute(a.toString).map(_.toCharArray)
+
+			override def compute(a: String): Option[String] =
+				if (memo.contains(a)) memo(a)
+				else {
+					memo = memo + (a -> base.compute(a))
+					memo(a)
+				}
+		}
+
 		val withTransform: (StringTransform => StringAlgorithm) = (st) => new StringAlgorithm {
 			private val base: StringAlgorithm = sa
 			private val transform: StringTransform = st
 
 			override def compute(a: Array[Char]): Option[Array[Char]] = base.compute(transform(a))
 
-			override def compute(a: String): Option[String] = base.compute(transform(a.toCharArray)).map(_.mkString)
+			override def compute(a: String): Option[String] = compute(a.toCharArray).map(_.mkString)
 		}
 	}
 }
diff --git a/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala b/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala
index 03a0425..f217f52 100755
--- a/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala
+++ b/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala
@@ -63,15 +63,30 @@ object Metric {
 	}
 
 	final class StringMetricDecorator[A](val sm: StringMetric[A]) {
+		val withMemoization: StringMetric[A] = new StringMetric[A] {
+			private val base: StringMetric[A] = sm
+			private var memo: Map[(String, String), Option[A]] = Map()
+
+			override def compare(a: Array[Char], b: Array[Char]): Option[A] =  compare(a.toString, b.toString)
+
+			override def compare(a: String, b: String): Option[A] = {
+				val t = (a, b)
+
+				if (memo.contains(t)) memo(t)
+				else {
+					memo = memo + (t -> base.compare(a, b))
+					memo(t)
+				}
+			}
+		}
+
 		val withTransform: (StringTransform => StringMetric[A]) = (st) => new StringMetric[A] {
 			private val base: StringMetric[A] = sm
 			private val transform: StringTransform = st
 
-			override def compare(a: Array[Char], b: Array[Char]): Option[A] =
-				base.compare(transform(a), transform(b))
+			override def compare(a: Array[Char], b: Array[Char]): Option[A] = base.compare(transform(a), transform(b))
 
-			override def compare(a: String, b: String): Option[A] =
-				base.compare(transform(a.toCharArray), transform(b.toCharArray))
+			override def compare(a: String, b: String): Option[A] = compare(a.toCharArray, b.toCharArray)
 		}
 	}
 }
diff --git a/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala b/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala
index d727145..b95046d 100644
--- a/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala
+++ b/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala
@@ -7,7 +7,7 @@ import org.scalatest.junit.JUnitRunner
 final class AlgorithmSpec extends ScalaTest {
 	import phonetic._
 	import Algorithm._
-	import Transform.StringTransform
+	import Transform._
 
 	"StringAlgorithm" should provide {
 		"compute method and companion object pass through" in {
@@ -25,6 +25,15 @@ final class AlgorithmSpec extends ScalaTest {
 	}
 
 	"StringAlgorithmDecorator" should provide {
+		"withMemoization()" in {
+			val memo = MetaphoneAlgorithm withMemoization
+
+			(0 until 1000000) foreach { i =>
+				memo.compute("abc123")
+				memo.compute("abc456")
+			}
+		}
+
 		"withTransform()" in {
 			(MetaphoneAlgorithm withTransform StringTransform.filterAlpha).compute("abc123").get should
 				equal (MetaphoneAlgorithm.compute("abc").get)
diff --git a/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala b/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala
index 3b9021d..538976d 100644
--- a/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala
+++ b/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala
@@ -44,6 +44,15 @@ final class MetricSpec extends ScalaTest {
 	}
 
 	"StringMetricDecorator" should provide {
+		"withMemoization()" in {
+			val memo = MetaphoneMetric withMemoization
+
+			(0 until 1000000) foreach { i =>
+				memo.compare("abc123", "abc456")
+				memo.compare("abc456", "abc123")
+			}
+		}
+
 		"withTransform()" in {
 			(MetaphoneMetric withTransform StringTransform.filterAlpha).compare("abc123", "abc456").get should
 				equal (true)
diff --git a/readme.md b/readme.md
index 7621f81..4637d35 100755
--- a/readme.md
+++ b/readme.md
@@ -244,11 +244,11 @@ SoundexAlgorithm.compute("lukasiewicz") // l222
 ---
 
 ## Decorating
-It is possible to decorate algorithms and metrics with additional functionality, this is provided by rich wrapping via implicits. Decorations include:
+It is possible to decorate algorithms and metrics with additional functionality, this is provided by rich wrapping via implicits. Decorations include (you can mix and match):
 
 * __withTransform:__ Transform arguments prior to computation/comparison. A handful of pre-built transforms are located in the [transform module](https://github.com/rockymadden/stringmetric/blob/master/core/src/main/scala/com/rockymadden/stringmetric/Transform.scala).
 
-* __withMemoization:__ Queued.
+* __[withMemoization](https://en.wikipedia.org/wiki/Memoization):__ All computations/comparisons are cached. Any further calls made with identical arguments will be looked up, rather than computed/compared.
 
 ---
 
@@ -260,6 +260,13 @@ MetaphoneMetric.compare("abc123", "abc456")
 
 ---
 
+Memoized:
+```scala
+(MetaphoneAlgorithm withMemoization).compute("abc123")
+```
+
+---
+
 Single filter, so that we only examine alphabetical characters:
 ```scala
 (MetaphoneAlgorithm withTransform StringTransform.filterAlpha).compute("abc123")