lib/src/union_set.dart

// Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

import 'dart:collection';

import 'unmodifiable_wrappers.dart';

/// A single set that provides a view of the union over a set of sets.
///
/// Since this is just a view, it reflects all changes in the underlying sets.
///
/// If an element is in multiple sets and the outer set is ordered, the version
/// in the earliest inner set is preferred. Component sets are assumed to use
/// `==` and `hashCode` for equality.
class UnionSet<E> extends SetBase<E> with UnmodifiableSetMixin<E> {
  /// The set of sets that this provides a view of.
  final Set<Set<E>> _sets;

  /// Whether the sets in [_sets] are guaranteed to be disjoint.
  final bool _disjoint;

  /// Creates a new set that's a view of the union of all sets in [sets].
  ///
  /// If any sets in [sets] change, this [UnionSet] reflects that change. If a
  /// new set is added to [sets], this [UnionSet] reflects that as well.
  ///
  /// If [disjoint] is `true`, then all component sets must be disjoint. That
  /// is, that they contain no elements in common. This makes many operations
  /// including [length] more efficient. If the component sets turn out not to
  /// be disjoint, some operations may behave inconsistently.
  UnionSet(this._sets, {bool disjoint: false}) : _disjoint = disjoint;

  /// Creates a new set that's a view of the union of all sets in [sets].
  ///
  /// If any sets in [sets] change, this [UnionSet] reflects that change.
  /// However, unlike [new UnionSet], this creates a copy of its parameter, so
  /// changes in [sets] aren't reflected in this [UnionSet].
  ///
  /// If [disjoint] is `true`, then all component sets must be disjoint. That
  /// is, that they contain no elements in common. This makes many operations
  /// including [length] more efficient. If the component sets turn out not to
  /// be disjoint, some operations may behave inconsistently.
  UnionSet.from(Iterable<Set<E>> sets, {bool disjoint: false})
      : this(sets.toSet(), disjoint: disjoint);

  int get length => _disjoint
      ? _sets.fold(0, (length, set) => length + set.length)
      : _iterable.length;

  Iterator<E> get iterator => _iterable.iterator;

  /// Returns an iterable over the contents of all the sets in [this].
  Iterable<E> get _iterable =>
      _disjoint ? _sets.expand((set) => set) : _dedupIterable;

  /// Returns an iterable over the contents of all the sets in [this] that
  /// de-duplicates elements.
  ///
  /// If the sets aren't guaranteed to be disjoint, this keeps track of the
  /// elements we've already emitted so that we can de-duplicate them.
  Iterable<E> get _dedupIterable {
    var seen = new Set<E>();
    return _sets.expand((set) => set).where((element) {
      if (seen.contains(element)) return false;
      seen.add(element);
      return true;
    });
  }

  bool contains(Object element) => _sets.any((set) => set.contains(element));

  E lookup(Object element) {
    if (element == null) return null;

    return _sets
        .map((set) => set.lookup(element))
        .firstWhere((result) => result != null, orElse: () => null);
  }

  Set<E> toSet() {
    var result = new Set<E>();
    for (var set in _sets) {
      result.addAll(set);
    }
    return result;
  }
}