Best match search on on object with required and optional fields

Question

Assume I have a key/value that has the following structure.

@Value.Immutable
public interface Key {
  EnumFoo required_enum_one;
  EnumBar required_enum_two;
  Optional<boolean> optional_boolean_one;
  Optional<EnumBaz> optional_enum_two; 
} 

@Value.Immutable
public interface Value {
  Message message; 
} 

Assume that I have a key/value mapping, where I have a message value for all the combinations of the required fields, and some combinations of optional fields. For example:

{foo1, bar1, true, baz1 } => msg1
{foo1, bar1, true, <any value except baz1> } => msg2
{foo1, bar2, <any value>, <any value> } => msg3
{foo2, bar2, <any value>, <any value> } => msg4
If I do a look up of {foo1, bar2, false, baz1}, it should resolve to msg3

What would be the best way to implement this? I was thinking of adding a custom @equals to the key where it skips optional matching when it isnt present in mapping collection. As for the mapping collection, I was thinking of a list of key/value tuples which is ordered based on the presence of the optional fields(similar to above code block), so that the first key which matches all required fields and most optional fields is selected and the corresponding value is returned?

Is there a better approach? As a bonus, I find myself repeating this pattern for different types. Is there a way to have a reusable solution?

Answer 1

I have solved this problem in the past by considering the "key of the map" (a java.util.Map) to be a separate concern from the "Key type" (the interface you've defined in your q).

I've done this using a StringListMapKey that looks something like:

final class StringListMapKey {
    private List<String> keyParts;

    public StringListMapKey(List<String> keyParts) {
        this.keyParts = keyParts;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null || !(obj instanceof StringListMapKey)) {
            return false;
        }

        return this.keyParts.equals(((StringListMapKey) obj).keyParts);
    }

    @Override
    public int hashCode() {
        return keyParts.hashCode();
    }
}

Then you can take an instance of the Key type (the one in your question) and transform it to a StringListMapKey using something like this - where you can put in your well-known/static mappings:

final class MapKeyFactory {
    private static final String ANY = "$ANY";

    public StringListMapKey createFrom(Key key) {
        List<String> keyParts = new ArrayList<>();

        keyParts.add(key.getEnumFoo()
                        .toString());
        keyParts.add(key.getEnumBar()
                        .toString());

        keyParts.add(deriveMaybeBooleanOneKeyPart(key.isMaybeBooleanOne()));
        keyParts.add(derviceMaybeEnumBazKeyPart(key.getMaybeEnumBaz()));

        return new StringListMapKey(keyParts);
    }

    private String derviceMaybeEnumBazKeyPart(Optional<EnumBaz> maybeEnumBaz) {
        if (!maybeEnumBaz.isPresent()) {
            return ANY;
        }

        EnumBaz enumBaz = maybeEnumBaz.get();

        switch (enumBaz) {
        case BAZ1:
            return "ONE";
        default:
            return ANY;
        }
    }

    private String deriveMaybeBooleanOneKeyPart(Optional<Boolean> maybeBooleanOne) {
        if (!maybeBooleanOne.isPresent()) {
            return ANY;
        }

        Boolean booleanOne = maybeBooleanOne.get();

        if (booleanOne) {
            return "TRUE";
        }

        return ANY;
    }
}

The only issue with doing this is that you lose type information in the actual map key (as it's a List<String> under the hood). For that reason, I have made the value the equivalent of Pair<Key, Message>, in case I need to get to the underlying data in the actual key.

Rationale here is that your type Key really (or: probably!) should check its actual field values for equality - and not derived values.

So you eventually have a Map that looks like this: Map<StringListMapKey, Pair<Key, Message>>.

It's not big and it's not clever, but it has served me well and is generic enough to use for other complex criteria that you might want to cache and do quick lookups on.

If performance becomes a consideration (that's a lot of hashing/equals'ing), you can consider a "DelimitiedStringMapKey" that turns your Key instance into a plain old String like "foo1:bar1:$ANY:$ANY".

Answer 2

I suggest you use 'Chain of responsibility design pattern'. You can think of creating a Key criteria to be a node in the chain. Each node has its way of evaluating a given criteria.

https://sourcemaking.com/design_patterns/chain_of_responsibility