observer_list.dart 3.81 KB
Newer Older
Ian Hickson's avatar
Ian Hickson committed
1
// Copyright 2014 The Flutter Authors. All rights reserved.
2 3 4 5 6
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

import 'dart:collection';

7 8
/// A list optimized for the observer pattern when there are small numbers of
/// observers.
9 10 11
///
/// Consider using an [ObserverList] instead of a [List] when the number of
/// [contains] calls dominates the number of [add] and [remove] calls.
12 13 14 15 16 17 18 19 20 21 22 23 24
///
/// This class will include in the [iterator] each added item in the order it
/// was added, as many times as it was added.
///
/// If there will be a large number of observers, consider using
/// [HashedObserverList] instead. It has slightly different iteration semantics,
/// but serves a similar purpose, while being more efficient for large numbers
/// of observers.
///
/// See also:
///
///  * [HashedObserverList] for a list that is optimized for larger numbers of
///    observers.
25 26
// TODO(ianh): Use DelegatingIterable, possibly moving it from the collection
// package to foundation, or to dart:collection.
27
class ObserverList<T> extends Iterable<T> {
28
  final List<T> _list = <T>[];
29
  bool _isDirty = false;
30
  late final HashSet<T> _set = HashSet<T>();
31 32

  /// Adds an item to the end of this list.
33 34
  ///
  /// This operation has constant time complexity.
35 36 37 38 39 40 41
  void add(T item) {
    _isDirty = true;
    _list.add(item);
  }

  /// Removes an item from the list.
  ///
42 43
  /// This is O(N) in the number of items in the list.
  ///
44 45 46
  /// Returns whether the item was present in the list.
  bool remove(T item) {
    _isDirty = true;
47
    _set.clear(); // Clear the set so that we don't leak items.
48 49 50
    return _list.remove(item);
  }

51 52 53 54 55 56 57
  /// Removes all items from the list.
  void clear() {
    _isDirty = false;
    _list.clear();
    _set.clear();
  }

58
  @override
59
  bool contains(Object? element) {
60
    if (_list.length < 3) {
61
      return _list.contains(element);
62
    }
63 64

    if (_isDirty) {
65
      _set.addAll(_list);
66 67 68
      _isDirty = false;
    }

69
    return _set.contains(element);
70 71 72 73
  }

  @override
  Iterator<T> get iterator => _list.iterator;
74 75 76 77 78 79

  @override
  bool get isEmpty => _list.isEmpty;

  @override
  bool get isNotEmpty => _list.isNotEmpty;
80 81 82 83 84

  @override
  List<T> toList({bool growable = true}) {
    return _list.toList(growable: growable);
  }
85
}
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

/// A list optimized for the observer pattern, but for larger numbers of observers.
///
/// For small numbers of observers (e.g. less than 10), use [ObserverList] instead.
///
/// The iteration semantics of the this class are slightly different from
/// [ObserverList]. This class will only return an item once in the [iterator],
/// no matter how many times it was added, although it does require that an item
/// be removed as many times as it was added for it to stop appearing in the
/// [iterator]. It will return them in the order the first instance of an item
/// was originally added.
///
/// See also:
///
///  * [ObserverList] for a list that is fast for small numbers of observers.
class HashedObserverList<T> extends Iterable<T> {
  final LinkedHashMap<T, int> _map = LinkedHashMap<T, int>();

  /// Adds an item to the end of this list.
  ///
  /// This has constant time complexity.
  void add(T item) {
    _map[item] = (_map[item] ?? 0) + 1;
  }

  /// Removes an item from the list.
  ///
  /// This operation has constant time complexity.
  ///
  /// Returns whether the item was present in the list.
  bool remove(T item) {
117
    final int? value = _map[item];
118 119 120 121 122 123 124 125 126 127 128 129
    if (value == null) {
      return false;
    }
    if (value == 1) {
      _map.remove(item);
    } else {
      _map[item] = value - 1;
    }
    return true;
  }

  @override
130
  bool contains(Object? element) => _map.containsKey(element);
131 132 133 134 135 136 137 138 139 140

  @override
  Iterator<T> get iterator => _map.keys.iterator;

  @override
  bool get isEmpty => _map.isEmpty;

  @override
  bool get isNotEmpty => _map.isNotEmpty;
}