A Java utility class that caches the resulting value of (expensively?) computing a function taking a single argument

org.public_domain.java.utils.Memoizer.java

package org.public_domain.java.utils;

import java.util.*;
import java.util.Map.Entry;
import java.util.function.Function;
import java.util.function.Supplier;

/**
 * File: org.public_domain.java.utils.Memoizer.java
 * <p>
 * Version: v2023.12.18
 * <p>
 * -
 * <p>
 * A {@link Memoizer} is a utility class that caches the resulting value of (expensively?) computing a function taking a
 * single argument.
 * <p>
 * By storing the result (the value) of a call to the defining function for a particular input value (the key), all
 * subsequent calls with the same input value (i.e. key) return the previously computed (cached) value as opposed to
 * recomputing the function. This can significantly improve the performance of computationally expensive functions,
 * especially those that are called repeatedly with the same inputs.
 * <p>
 * -
 * <p>
 * Memoization is particularly useful for a function with the following profile:
 * <p>
 * <ul>
 * <li>Likely to be time-consuming to execute
 * <li>Likely to be repeatedly called with the same inputs
 * <li>Deterministic; i.e. always returns the same output for a given input
 * </ul>
 * <p>
 * -
 * <p>
 * <b>CAUTION:</b> Because this design eliminates multi-thread race conditions, and this
 * implementation allows a compute function to be defined within the {@link
 * #from(Function, MethodOverride, InsertionOrder)} factory method, as well as allowing a compute function to be
 * provided with the {@link #get(K, Function)} method, it is important to note that when a computed
 * result (the value) is associated with the input parameter (the key), the association is made
 * permanent and immutable in a thread-safe manner.
 * <p>
 * -
 * <p>
 * Said another way, the {@link #get(K, Function)} method is unable to "update" an existing
 * association. Once an association is generated, it remains permanent and immutable.
 *
 * @param <K> type of the input value (the key) permanently associated with the computed, and subsequently cached,
 *            value
 * @param <V> type of the cached computed value
 **/
public final class Memoizer<K, V> {

  /**
   * Creates a lazy {@link Supplier<T>} that delays the creating of an instance of {@code t} until the first time it is
   * requested. Upon request, the generated instance of {@code t} is, in a thread-safe way, cached and returned. And
   * then for all future requests, the cached value of {@code t} is returned, as opposed to recomputing it.
   * <p>
   * -
   * <p>
   * <b>CAUTION:</b> If {@link Supplier#get()} throws an {@link Exception}, the exception is
   * captured, suppressed, and the returned instance of {@link Supplier<T>} is defined to short-circuit by having
   * {@link Supplier#get()} hardcoded to return <code>null</code>.
   *
   * @param executeExactlyOnceSupplierT The {@link Supplier#get()} used to create the {@code t} instance exactly once
   * @param <T>                         type of computed function's resulting value instance of {@code t}
   * @return lazy {@link Supplier<T>} that creates the instance of {@code t} upon the first call to
   *     {@link Supplier#get()}.
   */
  public static <T> Supplier<T> lazyInstantiation(Supplier<T> executeExactlyOnceSupplierT) {
    Objects.requireNonNull(executeExactlyOnceSupplierT);

    return new Supplier<T>() {
      private boolean isInitialized;
      private Supplier<T> supplierT = this::executeExactlyOnce;

      private synchronized T executeExactlyOnce() {
        if (!isInitialized) {
          try {
            var t = executeExactlyOnceSupplierT.get();
            supplierT = () -> t;
          } catch (Exception exception) {
            supplierT = () -> null;
          }
          isInitialized = true;
        }

        return supplierT.get();
      }

      public T get() {
        return supplierT.get();
      }
    };
  }

  public enum InsertionOrder {
    NONE,
    RETAIN
  }

  public enum MethodOverride {
    INHIBITED,
    ALLOWED
  }

  private final Optional<Entry<Function<K, V>, MethodOverride>> optionalDefaultDeriveVFromKAndMethodOverride;
  private final InsertionOrder insertionOrder;
  private final Map<K, V> vByK;

  /**
   * Creates a {@link Memoizer} without a default {@code deriveVFromK} function and doesn't maintain insertion order of
   * the keys.
   * <p>
   * -
   * <p>
   * <b>CAUTION:</b> This requires all calls be routed through the {@link #get(K, Function)}.
   *
   * @return an instance of {@link Memoizer} without a default {@code deriveVFromK} function and doesn't maintain
   *     insertion order of the keys
   */
  public static <K, V> Memoizer<K, V> from() {
    return new Memoizer<>(
        Optional.empty(),
        InsertionOrder.NONE);
  }

  /**
   * Creates a {@link Memoizer} with a specified default {@code deriveVFromK} function, disallows the function to be
   * overridden by the {@link #get(K, Function)} method, and doesn't maintain insertion order of the keys.
   *
   * @param defaultDeriveVFromK function to use to derive {@link V} from {@link K}, if the association is not already
   *                            cached
   * @return an instance of {@link Memoizer} with a specified default {@code deriveVFromK} function, disallows the
   *     function to be overridden by the {@link #get(K, Function)} method, and doesn't maintain insertion order of the
   *     keys
   */
  public static <K, V> Memoizer<K, V> from(
      Function<K, V> defaultDeriveVFromK
  ) {
    return new Memoizer<>(
        Optional.of(Map.entry(Objects.requireNonNull(defaultDeriveVFromK), MethodOverride.INHIBITED)),
        InsertionOrder.NONE);
  }

  /**
   * Creates a new {@link Memoizer} with a specified default {@code deriveVFromK} function, optionally allows the
   * function to be overridden by the {@link #get(K, Function)} method, and doesn't maintain insertion order of the
   * keys.
   *
   * @param defaultDeriveVFromK function to use to derive {@link V} from {@link K}, if the association is not already
   *                            cached
   * @param methodOverride      when {@link MethodOverride#ALLOWED}, enables {@link #get(Object, Function)} to be
   *                            called, otherwise the {@link #get(Object, Function)} method will throw an
   *                            {@link UnsupportedOperationException}
   * @return an instance of {@link Memoizer} with a specified default {@code deriveVFromK} function, optionally allows
   *     the function to be overridden by the {@link #get(K, Function)} method, and doesn't maintain insertion order of
   *     the keys
   */
  public static <K, V> Memoizer<K, V> from(
      Function<K, V> defaultDeriveVFromK,
      MethodOverride methodOverride
  ) {
    return new Memoizer<>(
        Optional.of(Map.entry(Objects.requireNonNull(defaultDeriveVFromK), methodOverride)),
        InsertionOrder.NONE);
  }

  /**
   * Creates a {@link Memoizer} without a default {@code deriveVFromK} function, and optionally maintain insertion order
   * of the keys.
   * <p>
   * -
   * <p>
   * <b>CAUTION:</b> This requires all calls be routed through the {@link #get(K, Function)}.
   *
   * @param insertionOrder when {@link InsertionOrder#RETAIN}, retains the insertion order of the keys
   * @return an instance of {@link Memoizer} without a default {@code deriveVFromK} function, and optionally maintain
   *     insertion order of the keys
   */
  public static <K, V> Memoizer<K, V> from(
      InsertionOrder insertionOrder
  ) {
    return new Memoizer<>(
        Optional.empty(),
        insertionOrder);
  }

  /**
   * Creates a {@link Memoizer} with a specified default {@code deriveVFromK} function, optionally allowing this default
   * function to be overridden by the {@link #get(K, Function)} method, and optionally maintaining the insertion order
   * of the keys.
   *
   * @param defaultDeriveVFromK function to use to derive V from K, if the association is not already cached
   * @param methodOverride      when {@link MethodOverride#ALLOWED}, enables {@link #get(Object, Function)} to be
   *                            called, otherwise the {@link #get(Object, Function)} method will throw an
   *                            {@link UnsupportedOperationException}
   * @param insertionOrder      when {@link InsertionOrder#RETAIN}, retains the insertion order of the keys
   * @return an instance of {@link Memoizer} with a specified default {@code deriveVFromK} function, optionally allowing
   *     this default function * to be overridden by the {@link #get(K, Function)} method, and optionally maintaining
   *     the insertion order of the keys.
   */
  public static <K, V> Memoizer<K, V> from(
      Function<K, V> defaultDeriveVFromK,
      MethodOverride methodOverride,
      InsertionOrder insertionOrder
  ) {
    return new Memoizer<>(
        Optional.of(Map.entry(Objects.requireNonNull(defaultDeriveVFromK), methodOverride)),
        insertionOrder);
  }

  private Memoizer(
      Optional<Entry<Function<K, V>, MethodOverride>> optionalDefaultDeriveVFromKAndMethodOverride,
      InsertionOrder insertionOrder
  ) {
    this.optionalDefaultDeriveVFromKAndMethodOverride = optionalDefaultDeriveVFromKAndMethodOverride;
    this.insertionOrder = insertionOrder;
    this.vByK = insertionOrder == InsertionOrder.RETAIN
        ? new LinkedHashMap<>()
        : new HashMap<>();
  }

  /**
   * Returns whether the {@link #get(K, Function)} method is allowed to provide an {@code overrideDeriveVFromK}
   * function. If {@link MethodOverride#INHIBITED}, the {@link #get(K, Function)} method call will throw an
   * {@link UnsupportedOperationException}.
   *
   * @return if {@code true}, indicates the {@link #get(K, Function)} method is allowed to provide an
   *     {@code overrideDeriveVFromK} function, otherwise the same method call will throw an
   *     {@link UnsupportedOperationException}
   */
  public MethodOverride getMethodOverride() {
    return this.optionalDefaultDeriveVFromKAndMethodOverride
        .map(Entry::getValue)
        .orElse(MethodOverride.ALLOWED);
  }

  /**
   * Returns whether {@link #keySet()} returns a {@link Set<K>} of keys currently managed, and in temporal (insertion)
   * order, otherwise encounter order is unspecified.
   *
   * @return if {@link InsertionOrder#RETAIN}, indicates {@link #keySet} returns a {@link Set} of the keys currently
   *     managed, and in temporal (insertion) order, otherwise encounter order is unspecified
   */
  public InsertionOrder getInsertionOrder() {
    return this.insertionOrder;
  }

  private V get(
      K k,
      Optional<Function<K, V>> optionalOverrideDeriveVFromK
  ) {
    return Optional.ofNullable(this.vByK.get(Objects.requireNonNull(k, "k must not be null")))
        .orElseGet(() -> {
          synchronized (this.vByK) {
            return Optional.ofNullable(this.vByK.get(k))
                .orElseGet(() -> {
                  var lambda = optionalOverrideDeriveVFromK
                      .or(() -> this.optionalDefaultDeriveVFromKAndMethodOverride.map(Entry::getKey))
                      .orElseThrow(() -> new IllegalArgumentException(
                          "when calling the get() method without providing an overrideDeriveVFromK function, defaultDeriveVFromK must be provided in the from() factory method"));
                  var v = Objects.requireNonNull(lambda.apply(k),
                      "v returned from the %sDeriveVFromK function, provided by the %s, must not be null".formatted(
                          optionalOverrideDeriveVFromK.isEmpty()
                              ? "default"
                              : "override",
                          optionalOverrideDeriveVFromK.isEmpty()
                              ? "from() factory method"
                              : "get() method"));
                  this.vByK.put(k, v);

                  return v;
                });
          }
        });
  }

  /**
   * Retrieves the cached value for the specified key, first computing the value using the {@code defaultDeriveVFromK}
   * function provided by the {@link #from(Function, MethodOverride, InsertionOrder)} factory method, if this is the first request for
   * this input value.
   *
   * @param k key to use to retrieve the value
   * @return cached (computed) value for the specified key
   * @throws IllegalArgumentException if no value has been associated with {@code k}
   * @throws NullPointerException     if the value returned by the *DeriveVFromF function is {@code null}
   */
  public V get(K k) {
    return get(k, Optional.empty());
  }

  /**
   * Retrieves the cached value for the specified key, first computing the value using the provided
   * {@code overrideDeriveVFromK} function if this is the first request for this input value.
   * <p>
   * -
   * <p>
   * <b>CAUTION:</b> Because this design eliminates multi-thread race conditions, and this
   * implementation allows a compute function to be defined within the {@link #from(Function, MethodOverride, InsertionOrder)} factory
   * method, as well as allowing a compute function to be provided with this method, it is important to note that when a
   * computed result (the value) is associated with the input parameter (the key), the association is made permanent and
   * immutable in a thread-safe manner.
   * <p>
   * -
   * <p>
   * Said another way, this method is unable to "update" an existing association. Once an association has been
   * generated, it remains permanent and immutable.
   *
   * @param k key to use to retrieve the permanently associated computed value
   * @return cached (computed) value for the specified key
   * @throws UnsupportedOperationException if {@link #getMethodOverride()} method returns {@link MethodOverride#INHIBITED}
   * @throws NullPointerException          if the value returned by the {@code *DeriveVFromF} function is {@code null}
   */
  public V get(
      K k,
      Function<K, V> overrideDeriveVFromK
  ) {
    if (this.getMethodOverride() == MethodOverride.INHIBITED) {
      throw new UnsupportedOperationException("overrideDeriveVFromK is restricted from being provided by the from() factory method selected");
    }

    return get(k, Optional.of(overrideDeriveVFromK));
  }

  /**
   * Provides a {@link Set<K>} of keys currently managed, and is in temporal (insertion) order when
   * {@link #getInsertionOrder()} returns {@link InsertionOrder#RETAIN}.
   *
   * @return a {@link Set<K>} of keys currently managed, and is in temporal (insertion) order when
   *     {@link #getInsertionOrder()} returns {@link InsertionOrder#RETAIN}
   */
  public Set<K> keySet() {
    return Collections.unmodifiableSet(this.vByK.keySet());
  }
}

org.public_domain.java.utils.MemoizerTests.java

package org.public_domain.java.utils;

import java.util.List;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import org.junit.jupiter.api.Test;
import org.public_domain.java.utils.Memoizer.InsertionOrder;
import org.public_domain.java.utils.Memoizer.MethodOverride;

import static org.junit.jupiter.api.Assertions.*;

/**
 * File: org.public_domain.java.utils.MemoizerTests.java
 * <p>
 * Version: v2024.02.02
 **/
public class MemoizerTests {

  @Test
  public void testLazyInstantiation() {
    var threadSleepMillis = 1000;
    var memoizerValue = Integer.valueOf(10);
    var counter = new int[]{0};
    var isExceptionDetected = new boolean[1];
    var memoizer = Memoizer.lazyInstantiation(() -> {
      try {
        Thread.sleep(threadSleepMillis);
      } catch (InterruptedException e) {
        isExceptionDetected[0] = true;
        throw new RuntimeException(e);
      }
      ++counter[0];

      return memoizerValue + counter[0] - 1;
    });
    assertEquals(counter[0], 0);
    var threads = Stream.<Thread>generate(() ->
            new Thread(
                null,
                () -> {
                  var memoizerResultThreadSpawned = memoizer.get();
                  assertEquals(memoizerValue, memoizerResultThreadSpawned);
                }))
        .limit(10)
        .toList();
    assertEquals(counter[0], 0);
    assertFalse(isExceptionDetected[0]);
    var startMillis = System.currentTimeMillis();
    threads.forEach(Thread::start);
    assertEquals(counter[0], 0);
    var memoizerResultThreadMain = memoizer.get(); //thread blocks until timeout in memoizer elapses
    var totalMillis = System.currentTimeMillis() - startMillis;
    //System.out.println("totalMillis: " + totalMillis);
    assertEquals(counter[0], 1);
    assertFalse(isExceptionDetected[0]);
    assertTrue(totalMillis >= threadSleepMillis);
    assertEquals(memoizerValue, memoizerResultThreadMain);
    var memoizerResultThreadMain2 = memoizer.get(); //get the value again
    assertEquals(counter[0], 1); //ensure that the executeExactlyOnce is not re-executed
    assertFalse(isExceptionDetected[0]); //ensure that no exception was generated (which seems impossible if the prior statement confirmed the lambda was not re-executed
  }

  @Test
  public void testLazyInstantiationSupplierException() {
    var memoizerValue = Integer.valueOf(10);
    var counter = new int[]{0};
    var memoizer = Memoizer.lazyInstantiation(() -> {
      ++counter[0];
      var oopsie = 999 / (counter[0] - 1);
      //should never get here as prior expression contains a divide by zero
      System.out.println("oopsie: " + oopsie);

      return memoizerValue + counter[0] - 1;
    });
    assertEquals(counter[0], 0);
    var thread = new Thread(
        null,
        () -> {
          var memoizerResultThreadSpawned = memoizer.get();
          // memoizer.get throws an exception which we swallow and return null
          assertNull(memoizerResultThreadSpawned);
        });
    var isExceptionDetected = new boolean[1];
    Thread.setDefaultUncaughtExceptionHandler(
        (t, e) -> {
          // memoizer.get exception is swallowed and thread's assert should pass
          LOGGER.error("Exception detected: ", e);
          isExceptionDetected[0] = true;
        });
    thread.start();
    assertNull(memoizer.get()); //block until the other thread gets out of the way and allows this one through
    assertEquals(counter[0], 1); //ensure the thread executed the executeExactlyOnce lambda exactly once, prior to the exception
    assertFalse(isExceptionDetected[0]); //ensure the exception was successfully caught and suppressed
    assertNull(memoizer.get()); //ensure null is consistently being returned
    assertEquals(counter[0], 1); //ensure we are not re-executing the executeExactlyOnce lambda
  }

  private void testFactoriesExhaustiveHelper(
      boolean isDefiningDefaultDeriveVFromK,
      MethodOverride methodOverride,
      InsertionOrder insertionOrder
  ) {
    Function<Integer, Integer> lambdaDefaultTimes2 = (integer) -> integer * 2;
    Function<Integer, Integer> lambdaOverrideMinus1 = (integer) -> integer - 1;
    Function<Integer, Integer> lambdaOverridePlus1 = (integer) -> integer + 1;
    Memoizer<Integer, Integer> memoizer =
        isDefiningDefaultDeriveVFromK
            ? methodOverride == MethodOverride.ALLOWED //isAllowingMethodOverride
            ? insertionOrder == InsertionOrder.RETAIN //isRetainingInsertionOrder
            ? Memoizer.from(lambdaDefaultTimes2, methodOverride, insertionOrder)
            : Memoizer.from(lambdaDefaultTimes2, methodOverride)
            : insertionOrder == InsertionOrder.RETAIN //isRetainingInsertionOrder
                ? Memoizer.from(lambdaDefaultTimes2, methodOverride, insertionOrder)
                : Memoizer.from(lambdaDefaultTimes2)
            : insertionOrder == InsertionOrder.RETAIN //isRetainingInsertionOrder
                ? Memoizer.from(insertionOrder)
                : Memoizer.from();
    assertTrue(memoizer.keySet().isEmpty());
    assertEquals(methodOverride, memoizer.getMethodOverride());
    assertEquals(insertionOrder, memoizer.getInsertionOrder());
    if (isDefiningDefaultDeriveVFromK) {
      if (methodOverride == MethodOverride.ALLOWED) {
        //get(k) should return a value
        assertEquals(50, memoizer.get(25)); //default lambda invoked
        //get(k, overrideDeriveVFromK) should return a value
        assertEquals(26, memoizer.get(27, lambdaOverrideMinus1)); //override lambda invoked with default lambda ignored
        assertFalse(memoizer.keySet().isEmpty());
        assertEquals(Set.of(25, 27), memoizer.keySet());
        assertEquals(50, memoizer.get(25)); //default lambda ignored
        assertEquals(52, memoizer.get(26)); //default lambda invoked
        assertEquals(Set.of(25, 27, 26), memoizer.keySet());
        if (insertionOrder == InsertionOrder.RETAIN) {
          var keys = IntStream.range(20, 30)
              .mapToObj(index -> {
                memoizer.get(index); //override lambda invoked for all but 25, 26, and 27

                return index;
              })
              .toList();
          assertNotEquals(keys, memoizer.keySet().stream().toList());
          assertEquals(List.of(25, 27, 26, 20, 21, 22, 23, 24, 28, 29), memoizer.keySet().stream().toList());
        }
      } else {
        //get(k, overrideDeriveVFromK) should throw an exception
        var unsupportedOperationException =
            assertThrows(
                UnsupportedOperationException.class,
                () -> memoizer.get(15, lambdaOverrideMinus1)
            );
        assertEquals(
            "overrideDeriveVFromK is restricted from being provided by the from() factory method selected",
            unsupportedOperationException.getMessage());
        assertTrue(memoizer.keySet().isEmpty());
        //get(k) should return a value
        assertEquals(30, memoizer.get(15)); //default lambda invoked
        assertFalse(memoizer.keySet().isEmpty());
        assertEquals(Set.of(15), memoizer.keySet());
        assertEquals(30, memoizer.get(15)); //default lambda ignored
        assertEquals(34, memoizer.get(17)); //default lambda invoked
        assertEquals(Set.of(15, 17), memoizer.keySet());
        if (insertionOrder == InsertionOrder.RETAIN) {
          var keys = IntStream.range(10, 20)
              .mapToObj(index -> {
                memoizer.get(index); //override lambda invoked for all but 15 and 17

                return index;
              })
              .toList();
          assertNotEquals(keys, memoizer.keySet().stream().toList());
          assertEquals(List.of(15, 17, 10, 11, 12, 13, 14, 16, 18, 19), memoizer.keySet().stream().toList());
        }
      }
    } else {
      assertEquals(MethodOverride.ALLOWED, methodOverride); //isAllowingMethodOverride);
      //get(k) should throw an exception
      var illegalArgumentException =
          assertThrows(
              IllegalArgumentException.class,
              () -> memoizer.get(5)
          );
      assertEquals(
          "when calling the get() method without providing an overrideDeriveVFromK function, defaultDeriveVFromK must be provided in the from() factory method",
          illegalArgumentException.getMessage());
      assertTrue(memoizer.keySet().isEmpty());
      //get(k, overrideDeriveVFromK) should return a value
      assertEquals(4, memoizer.get(5, lambdaOverrideMinus1)); //override lambda invoked
      assertFalse(memoizer.keySet().isEmpty());
      assertEquals(Set.of(5), memoizer.keySet());
      assertEquals(4, memoizer.get(5)); //should now work as the key is present
      assertEquals(4, memoizer.get(5, lambdaOverridePlus1)); //override lambda ignored
      assertEquals(Set.of(5), memoizer.keySet());
      assertEquals(8, memoizer.get(7, lambdaOverridePlus1)); //override lambda invoked
      assertEquals(Set.of(5, 7), memoizer.keySet());
      assertEquals(8, memoizer.get(7)); //should now work as the key is present
      assertEquals(8, memoizer.get(7, lambdaOverrideMinus1)); //override lambda ignored
      assertEquals(Set.of(5, 7), memoizer.keySet());
      if (insertionOrder == InsertionOrder.RETAIN) {
        var keys = IntStream.range(0, 10)
            .mapToObj(index -> {
              memoizer.get(index, lambdaOverrideMinus1); //override lambda invoked for all but 5 and 7

              return index;
            })
            .toList();
        assertNotEquals(keys, memoizer.keySet().stream().toList());
        assertEquals(List.of(5, 7, 0, 1, 2, 3, 4, 6, 8, 9), memoizer.keySet().stream().toList());
      }
    }
  }

  @Test
  public void testFactoriesExhaustive() {
    //test all variations of from()
    //  from()
    //      equivalent: from(null, true, false)
    //  from(Function<K, V> defaultDeriveVFromK)
    //      equivalent: from(defaultDeriveVFromK, false, false)
    //  from(Function<K, V> defaultDeriveVFromK, boolean isAllowingMethodOverride)
    //      equivalent: from(defaultDeriveVFromK, isAllowingMethodOverride, false)
    //  from(boolean isRetainingInsertionOrder)
    //      equivalent: from(null, true, isRetainingInsertionOrder)
    //  from(Function<K, V> defaultDeriveVFromK, boolean isAllowingMethodOverride, boolean isRetainingInsertionOrder)
    Stream.of(false, true)
        .forEach(isDefiningDefaultDeriveVFromK ->
            (isDefiningDefaultDeriveVFromK
                ? Stream.of(MethodOverride.INHIBITED, MethodOverride.ALLOWED)
                : Stream.of(MethodOverride.ALLOWED))
                .forEach(methodOverride ->
                    Stream.of(InsertionOrder.NONE, InsertionOrder.RETAIN)
                        .forEach(insertionOrder ->
                            testFactoriesExhaustiveHelper(
                                isDefiningDefaultDeriveVFromK,
                                methodOverride,
                                insertionOrder))));
  }
}