Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / Java

Set membership and cycle detection

Test, add, and remove members of a `Set`. Use the result of `add` to detect a type already on the active path, and use `finally` to remove its entry when the call exits.

Version: Java SE 21

Syntax

Java SE 21 — instance methods of java.util.Set<E>:
boolean add(E e);
boolean contains(Object o);
boolean remove(Object o);

In java.util.Set<E>, membership is based on element equality as defined by Objects.equals, not on position. Set.contains (contains(Object o)) returns true if an equal element is present, without changing the set. Set.add (add(E e)) returns true when it inserts the element; a duplicate returns false and leaves the set unchanged. Set.remove (remove(Object o)) returns true when it removes an equal element and false when none is present. The Object parameter means lookup and removal do not require an argument of type E; removal is by value, not by index.

Insertion and removal are optional operations: a set created with Set.of rejects them with UnsupportedOperationException. Depending on the implementation, add can reject null, an incompatible type, or an invalid element property with NullPointerException, ClassCastException, or IllegalArgumentException, respectively. When testing or removing a disallowed null or an incompatible type, an implementation may return false or throw the corresponding exception. Use a mutable HashSet with keys whose equals and hashCode stay stable while stored.

When recursively traversing type dependencies, keep only the types on the current path in the set. !active.add(type) detects a cycle without a preliminary contains call. Do not remove the entry in the cycle branch: it belongs to an earlier call. Enter try only after a successful insertion and remove the entry in finally, which runs on normal exit, on return, and when an exception propagates. The set records neither stack order nor every type ever visited; another branch can visit the same type again.

Examples

import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class SetMembershipDemo {
    private static final class A {}
    private static final class B {}
    private static final class C {}

    private static final Map<Class<?>, List<Class<?>>> DEPENDENCIES = Map.of(
        A.class, List.of(B.class, C.class),
        B.class, List.of(A.class, C.class)
    );

    public static void main(String[] args) {
        Set<Class<?>> active = new HashSet<>();
        visit(A.class, active);
        System.out.println("A active after traversal: " + active.contains(A.class));
    }

    private static void visit(Class<?> type, Set<Class<?>> active) {
        if (!active.add(type)) {
            System.out.println("cycle: " + type.getSimpleName());
            return;
        }

        try {
            System.out.println("visit: " + type.getSimpleName());
            for (Class<?> dependency : DEPENDENCIES.getOrDefault(type, List.of())) {
                visit(dependency, active);
            }
        } finally {
            active.remove(type);
        }
    }
}

Result

visit: A
visit: B
cycle: A
visit: C
visit: C
A active after traversal: false

`B` detects the return to active `A`. `C` is visited separately through `B` and through `A`. The final `false` confirms that `A` is no longer on the active path.

Related lessons

  • Java · Lesson 59 · Advanced · Version: 2

Sources