sdk/lib/internal/linked_list.dart - Issue 2974073002: Revert "Don't use `LinkedList` in the core libraries anymore."

Side by Side Diff: sdk/lib/internal/linked_list.dart

Issue 2974073002: Revert "Don't use `LinkedList` in the core libraries anymore." (Closed)

Patch Set: Created 3 years, 5 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 // Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file

2 // for details. All rights reserved. Use of this source code is governed by a

3 // BSD-style license that can be found in the LICENSE file.

4

5 part of dart._internal;

6

7 /// A rudimentary linked list.

8 class LinkedList<T extends LinkedListEntry<T>> extends IterableBase<T> {

9 T first;

10 T last;

11 int length = 0;

12

13 bool get isEmpty => length == 0;

14

15 /**

16 * Adds [newLast] to the end of this linked list.

17 */

18 void add(T newLast) {

19 assert(newLast._next == null && newLast._previous == null);

20 if (last != null) {

21 assert(last._next == null);

22 last._next = newLast;

23 } else {

24 first = newLast;

25 }

26 newLast._previous = last;

27 last = newLast;

28 last._list = this;

29 length++;

30 }

31

32 /**

33 * Adds [newFirst] to the beginning of this linked list.

34 */

35 void addFirst(T newFirst) {

36 if (first != null) {

37 assert(first._previous == null);

38 first._previous = newFirst;

39 } else {

40 last = newFirst;

41 }

42 newFirst._next = first;

43 first = newFirst;

44 first._list = this;

45 length++;

46 }

47

48 /**

49 * Removes the given [node] from this list.

50 *

51 * The entry must be in this linked list when this method is called. Also see

52 * [LinkedListEntry.unlink].

53 */

54 void remove(T node) {

55 assert(node._previous != null \|\| node._next != null \|\| length == 1);

56 length--;

57 if (node._previous == null) {

58 assert(identical(node, first));

59 first = node._next;

60 } else {

61 node._previous._next = node._next;

62 }

63 if (node._next == null) {

64 assert(identical(node, last));

65 last = node._previous;

66 } else {

67 node._next._previous = node._previous;

68 }

69 node._next = node._previous = null;

70 }

71

72 Iterator<T> get iterator => new _LinkedListIterator<T>(this);

73 }

74

75 class LinkedListEntry<T extends LinkedListEntry<T>> {

76 T _next;

77 T _previous;

78 LinkedList<T> _list;

79

80 /**

81 * Unlinks the element from its linked list.

82 *

83 * The entry must be in a linked list when this method is called.

84 * This is equivalent to calling [LinkedList.remove] on the list this entry

85 * is currently in.

86 */

87 void unlink() {

88 _list.remove(this);

89 }

90 }

91

92 class _LinkedListIterator<T extends LinkedListEntry<T>> implements Iterator<T> {

93 /// The current element of the iterator.

94 // This field is writeable, but should only read by users of this class.

95 T current;

96

97 /// The list the iterator iterates over.

98 ///

99 /// Set to [null] if the provided list was empty (indicating that there were

100 /// no entries to iterate over).

101 ///

102 /// Set to [null] as soon as [moveNext] was invoked (indicating that the

103 /// iterator has to work with [current] from now on.

104 LinkedList<T> _list;

105

106 _LinkedListIterator(this._list) {

107 if (_list.length == 0) _list = null;

108 }

109

110 bool moveNext() {

111 // current is null if the iterator hasn't started iterating, or if the

112 // iteration is finished. In the first case, the [_list] field is not null.

113 if (current == null) {

114 if (_list == null) return false;

115 assert(_list.length > 0);

116 current = _list.first;

117 _list = null;

118 return true;

119 }

120 current = current._next;

121 return current != null;

122 }

123 }

OLD	NEW

« no previous file with comments | « sdk/lib/internal/internal_sources.gypi ('k') | sdk/lib/io/io.dart » ('j') | no next file with comments »