Skip to content

v0.3.0

Choose a tag to compare

View all tags
@github-actions github-actions released this 05 Aug 10:43
· 17 commits to main since this release
v0.3.0
42e08aa

What's Changed

Added

  • Added TopologicalSort::items() and TopologicalSort::into_items() to iterate over all remaining items, including ones that are still blocked by unresolved dependencies or cycles. (#70 by @gifnksm)
  • Implemented Extend<DependencyLink<T>> for TopologicalSort<T>, allowing dependency links to be appended with extend(). (#63 by @gifnksm)
  • Added TopologicalSort::pop_iter(), which returns a PopIter<'_, T> that repeatedly calls pop(). (#64 by @gifnksm)
  • Added TopologicalSort::pop_batch(), which removes and returns the current batch of ready items and can collect into any collection implementing Default + Extend<T>. (#66, #71 by @gifnksm)
  • Added TopologicalSort::peek_batch(), which iterates over the current batch of ready items. (#66, #71 by @gifnksm)
  • Added TopologicalSort::remove(), which removes a specified item only when it has no remaining dependencies. (#68 by @gifnksm)
  • Added CHANGELOG.md. (#51 by @gifnksm)

Changed

  • (Breaking Change) TopologicalSort::add_dependency() and TopologicalSort::add_link() now return true when they add a new dependency link and false when that link already existed. (#39 by @szabgab)
  • Raised the minimum supported Rust version to Rust 1.88.0. (#29 by @gifnksm)
  • Adjusted TopologicalSort<T> debug output to use a more collection-like representation of dependency relationships. (#58 by @gifnksm)
  • Added #[must_use] to TopologicalSort::new(), len(), is_empty(), peek(), and peek_batch(), which may produce new warnings when their return values are ignored.

Deprecated

  • Deprecated TopologicalSort::pop_all() in favor of TopologicalSort::pop_batch(). (#66, #72 by @gifnksm)

    • Rationale:
      The old name could be taken to mean that the method would keep popping items until no more progress was possible.
      However, it only removed the current batch of items that had no remaining dependencies at the time of the call.
      The new name makes that batch-oriented behavior explicit and helps avoid using a single pop_all() call as a cycle check.

      pop_batch() also avoids unnecessary intermediate collection work.
      Callers can now collect directly into their chosen container instead of always receiving a Vec.

    • Migration notes:

      • Replace ts.pop_all() with ts.pop_batch::<Vec<_>>() when you still want a Vec.
      • If you intended to keep popping until no more progress is possible, use ts.pop_iter() instead, for example let items: Vec<_> = ts.pop_iter().collect();.
  • Deprecated TopologicalSort::peek_all() in favor of TopologicalSort::peek_batch(). (#66, #72 by @gifnksm)

    • Rationale:
      The old name could be taken to mean that the method would inspect every item that would become ready as popping progressed.
      However, it only inspected the current batch of items that had no remaining dependencies at the time of the call.
      The new name makes that batch-oriented behavior explicit.

      peek_batch() also avoids unnecessary allocation when callers only need to inspect or stream the ready items.

    • Migration notes:

      • Replace ts.peek_all() with ts.peek_batch().collect::<Vec<_>>() when you still want Vec<&T>.
      • If you want owned copied values from peek_batch(), use ts.peek_batch().copied().collect::<Vec<_>>() for Copy types or ts.peek_batch().cloned().collect::<Vec<_>>() for Clone types.

Removed

  • (Breaking Change) Removed impl From<(T, T)> for DependencyLink<T>. (#57 by @gifnksm)
    • Rationale:
      The tuple order was the inverse of TopologicalSort::add_dependency(prec, succ) and DependencyLink { prec, succ }, which made it easy to invert a dependency link by mistake.
    • Migration notes:
      • Replace ts.add_link((succ, prec).into()) with ts.add_link(DependencyLink { prec, succ }).
      • Replace DependencyLink::from((succ, prec)) with DependencyLink { prec, succ }.
      • Replace .map(DependencyLink::from) on (succ, prec) tuples with .map(|(succ, prec)| DependencyLink { prec, succ }).
  • (Breaking Change) Removed impl FromIterator<T> for TopologicalSort<T>. (#61 by @ginksm)
    • Rationale:
      TopologicalSort::from_iter(iter) or iter.collect::<TopologicalSort<T>>() compared each item with all previously seen items using partial_cmp() and inferred dependency links from every comparable pair.
      That behavior was not intuitive for from_iter(), which readers could reasonably expect to just gather items or to derive relationships only from something more local such as adjacent pairs.
      It also made from_iter() unexpectedly O(n^2) instead of the O(n) work that a collection-style operation usually suggests.
    • Migration notes:
      • There is no direct replacement for items.into_iter().collect::<TopologicalSort<_>>().
      • If partial_cmp() defines a total order for your values and you only needed to iterate them in order, collect them into a Vec and sort it directly instead of using TopologicalSort.
      • If you intended to model dependency links, construct the graph explicitly with TopologicalSort::new() plus insert(), add_dependency(), and/or add_link().
  • (Breaking Change) Removed impl Iterator for TopologicalSort<T>. (#64 by @gifnksm)
    Destructive iteration now requires an explicit TopologicalSort::pop_iter() call.
    • Rationale:
      Iterating TopologicalSort removes items from the sort.
      Implementing Iterator for TopologicalSort exposed methods such as count(), find(), and filter() directly on the sort itself.
      On TopologicalSort, those methods look like inspection or search operations, even though calling them could destructively advance or consume the sort.
      Requiring pop_iter() makes that destructive step explicit.
    • Migration notes:
      • Replace ts.next() with ts.pop() when consuming one item at a time.
      • Replace iteration through TopologicalSort itself with ts.pop_iter().
      • Replace direct iterator adapter calls on TopologicalSort with calls on ts.pop_iter() instead.

Other Changes

New Contributors

  • @dependabot[bot] made their first contribution in #28
  • @vladh made their first contribution in #33
  • @gifnksm with @Copilot made their first contribution in #44
  • @szabgab made their first contribution in #37
  • @gifnksm-update-bot[bot] made their first contribution in #53

Full Changelog: v0.2.2...v0.3.0

Contributors

szabgab, gifnksm, and 2 other contributors
Assets 2
Loading