Strategy Pattern
Strategy is a behavioral design pattern that turns a set of behaviors into objects and makes them interchangeable inside original context object.
The original object, called context, holds a reference to a strategy object. The context delegates executing the behavior to the linked strategy object. In order to change the way the context performs its work, other objects may replace the currently linked strategy object with another one.
Golang Implementation
Example: Cache eviction strategy
Suppose you are building an In-Memory-Cache. Since it’s in memory, it has a limited size. Whenever it reaches its maximum size, some entries have to be evicted to free-up space. This can happen via several algorithms. Some of the popular algorithms are:
- Least Recently Used (LRU): remove an entry that has been used least recently.
- First In, First Out (FIFO): remove an entry that was created first.
- Least Frequently Used (LFU): remove an entry that was least frequently used.
The problem is how to decouple our cache class from these algorithms so that we can change the algorithm at run time. Also, the cache class should not change when a new algorithm is being added.
This is where Strategy pattern comes into the picture. It suggests creating a family of the algorithm with each algorithm having its own class. Each of these classes follows the same interface, and this makes the algorithm interchangeable within the family. Let’s say the common interface name is evictionAlgo.
Now our main cache class will embed the evictionAlgo interface. Instead of implementing all types of eviction algorithms in itself, our cache class will delegate the execution to the evictionAlgo interface. Since evictionAlgo is an interface, we can change the algorithm in run time to either LRU, FIFO, LFU without changing the cache class.
evictionAlgo.go
package main
type EvictionAlgo interface {
evict(c *Cache)
}
fifo.go
package main
import "fmt"
type Fifo struct {
}
func (l *Fifo) evict(c *Cache) {
fmt.Println("Evicting by fifo strategy")
}
lru.go
package main
import "fmt"
type Lru struct {
}
func (l *Lru) evict(c *Cache) {
fmt.Println("Evicting by lru strategy")
}
lfu.go
package main
import "fmt"
type Lfu struct {
}
func (l *Lfu) evict(c *Cache) {
fmt.Println("Evicting by lfu strategy")
}
cache.go
package main
type Cache struct {
storage map[string]string
evictionAlgo EvictionAlgo
capacity int
maxCapacity int
}
func initCache(e EvictionAlgo) *Cache {
storage := make(map[string]string)
return &Cache{
storage: storage,
evictionAlgo: e,
capacity: 0,
maxCapacity: 2,
}
}
func (c *Cache) setEvictionAlgo(e EvictionAlgo) {
c.evictionAlgo = e
}
func (c *Cache) add(key, value string) {
if c.capacity == c.maxCapacity {
c.evict()
}
c.capacity++
c.storage[key] = value
}
func (c *Cache) get(key string) {
delete(c.storage, key)
}
func (c *Cache) evict() {
c.evictionAlgo.evict(c)
c.capacity--
}
main.go
package main
func main() {
lfu := &Lfu{}
cache := initCache(lfu)
cache.add("a", "1")
cache.add("b", "2")
cache.add("c", "3")
lru := &Lru{}
cache.setEvictionAlgo(lru)
cache.add("d", "4")
fifo := &Fifo{}
cache.setEvictionAlgo(fifo)
cache.add("e", "5")
}
// Evicting by lfu strategy
// Evicting by lru strategy
// Evicting by fifo strategy
Rust Implementation
Example 1: A conceptual Strategy example via traits
main.rs
/// Defines an injectable strategy for building routes.
trait RouteStrategy {
fn build_route(&self, from: &str, to: &str);
}
struct WalkingStrategy;
impl RouteStrategy for WalkingStrategy {
fn build_route(&self, from: &str, to: &str) {
println!("Walking route from {} to {}: 4 km, 30 min", from, to);
}
}
struct PublicTransportStrategy;
impl RouteStrategy for PublicTransportStrategy {
fn build_route(&self, from: &str, to: &str) {
println!(
"Public transport route from {} to {}: 3 km, 5 min",
from, to
);
}
}
struct Navigator<T: RouteStrategy> {
route_strategy: T,
}
impl<T: RouteStrategy> Navigator<T> {
pub fn new(route_strategy: T) -> Self {
Self { route_strategy }
}
pub fn route(&self, from: &str, to: &str) {
self.route_strategy.build_route(from, to);
}
}
fn main() {
let navigator = Navigator::new(WalkingStrategy);
navigator.route("Home", "Club");
navigator.route("Club", "Work");
let navigator = Navigator::new(PublicTransportStrategy);
navigator.route("Home", "Club");
navigator.route("Club", "Work");
}
// Walking route from Home to Club: 4 km, 30 min
// Walking route from Club to Work: 4 km, 30 min
// Public transport route from Home to Club: 3 km, 5 min
// Public transport route from Club to Work: 3 km, 5 min
Example 2: Functional approach
Functions and closures simplify Strategy implementation as you can inject behavior right into the object without complex interface definition.
It seems that Strategy is often implicitly and widely used in the modern development with Rust, e.g. it’s just like iterators work:
let a = [0i32, 1, 2];
let mut iter = a.iter().filter(|x| x.is_positive());
main.rs
type RouteStrategy = fn(from: &str, to: &str);
fn walking_strategy(from: &str, to: &str) {
println!("Walking route from {} to {}: 4 km, 30 min", from, to);
}
fn public_transport_strategy(from: &str, to: &str) {
println!(
"Public transport route from {} to {}: 3 km, 5 min",
from, to
);
}
struct Navigator {
route_strategy: RouteStrategy,
}
impl Navigator {
pub fn new(route_strategy: RouteStrategy) -> Self {
Self { route_strategy }
}
pub fn route(&self, from: &str, to: &str) {
(self.route_strategy)(from, to);
}
}
fn main() {
let navigator = Navigator::new(walking_strategy);
navigator.route("Home", "Club");
navigator.route("Club", "Work");
let navigator = Navigator::new(public_transport_strategy);
navigator.route("Home", "Club");
navigator.route("Club", "Work");
let navigator = Navigator::new(|from, to| println!("Specific route from {} to {}", from, to));
navigator.route("Home", "Club");
navigator.route("Club", "Work");
}
// Walking route from Home to Club: 4 km, 30 min
// Walking route from Club to Work: 4 km, 30 min
// Public transport route from Home to Club: 3 km, 5 min
// Public transport route from Club to Work: 3 km, 5 min
// Specific route from Home to Club
// Specific route from Club to Work