Skip to content

Java API, SimpleVisitor, and a generic Visitor

Latest

Choose a tag to compare

@rchillyard rchillyard released this 17 Nov 19:17
· 2 commits to main since this release
15638ab

Visitor 1.8.0 is on Maven Central.

libraryDependencies += "com.phasmidsoftware" %% "visitor" % "1.8.0"

Requires Scala 3.9 or later. This release breaks binary compatibility with 1.7.0 — under PVP the first two numbers form the major version. See Migrating to 1.8.0 in the README.

A Java API

com.phasmidsoftware.visitor.java makes the traversal engine usable from Java, which the Scala given-driven API could not be. Traversals.bfs / dfs / traverseTree, with NeighbourFunction and Evaluator as ordinary functional interfaces:

TraversalResult<String, String> r =
        Traversals.bfs("A", v -> graph.getOrDefault(v, List.of()));

r.visited();   // [A, B, C, D]
r.cameFrom();  // {B=A, C=A, D=B}

Javadoc is published beside the Scaladoc, at latest/javadoc.

Visitor is generic in its journal's element type

Visitor[V, R, J <: Appendable[Mapped[V, R]]] becomes Visitor[V, E, J <: Appendable[E, J]], where E is what the journal holds. This is what lets several kinds of visitor be ordinary Visitors that every Traversal entry point accepts:

records needs an Evaluable
JournaledVisitor Mapped[V, R] yes, bound when built
SimpleVisitor V no
ParentedVisitor Mapped[V, R], having consulted the predecessor an EvaluableFrom

visit no longer takes a using Evaluable — a visitor carries its own — so all seven Traversal entry points shed that implicit parameter.

Simpler traversals, in Scala as well as Java

SimpleVisitor records bare nodes, needs no Evaluable and allocates no pair per visit. Traverse wraps it for the common case:

Traverse.bfs("A")                 // List(A, B, C, D)
Traverse.dfs("A", DfsOrder.Post)
Traverse.tree(root)

Issues closed

  • #20 — EvaluableFrom and ParentedVisitor give an evaluator the node a node was reached from. No engine change was needed: the engine already calls discover(v, parent) before visit(v), a contract now pinned by VisitorOrderingSpec.
  • #21 — core.Zero and core.Monoid removed. They appeared in no signature in the public API: Visitor defined two type classes, published instances of them, and never consumed either. Consumers wanting a monoid should use cats-kernel, which supplies these through the implicit scope with no import.
  • #22 — Traversal.dfsTracking returns the VisitedSet it built, so a caller traversing each component in turn need not rebuild one; VisitedSet.from builds one from a Set in O(1).

Also

  • Appendable[X] is F-bounded as Appendable[X, A <: Appendable[X, A]], so append returns the journal's own type — removing four unchecked casts, two on the hot path of every visit
  • Mapped[V, R] alias for (V, Option[R])
  • versionScheme is now pvp, with MiMa checking every release
  • logback-classic moved to Test scope: a library should not publish a logging backend onto its consumers' classpath
  • -Werror enabled

Migration

The README's Migrating to 1.8.0 table covers each breaking change. In short: drop any Monoid as _ import exclusion; write Visitor[V, Mapped[V, R], J] where you wrote Visitor[V, R, J]; drop ev from explicit using lists; bring an Evaluable into scope where you build a JournaledVisitor; and if you implement Appendable yourself, add the second type parameter.