dart-lang / collection Goto Github PK

How about adding an example of how to use the equality checker classes?

final bool contentsEqual = (const ListEquality<Type>()).equals(list1, list2);

@override
bool operator ==(Object other) =>
  (other is MyClass) &&
  foo == other.foo &&
  (const ListEquality<Bar>()).equals(bars, other.bars);

At src/algorithms.dart:177 there is a new List<T> that should probably be new List/*<T>*/

It currently links to https://www.dartdocs.org/documentation/collection/1.12.0/ which returns a 404 error.

<img src="https://avatars.githubusercontent.com/u/17034?v=3" align="left" width="96" height="96"hspace="10"> Issue by kevmoo
Originally opened as dart-lang/sdk#16842

Show content?

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="96" height="96"hspace="10"> Issue by nex3
Originally opened as dart-lang/sdk#17637

It's often useful to expose the keys of an internal map as a set. Currently to do so it's necessary to copy them into a Set, which can be expensive. It would be handy if the collections package exposed an unmodifiable set class that wraps a map and provides a view of its keys.

<img src="https://avatars.githubusercontent.com/u/6812044?v=3" align="left" width="96" height="96"hspace="10"> Issue by tfortes
Originally opened as dart-lang/sdk#20169

Looking at the code for UnmodifiableMapView, it seems there is room for improvement;

var map0 = {'foo': 42};
var map1 = new UnmodifiableMapView<String, int>(map0);
// Handed off to another component that also creates a read-only view:
var map2 = new UnmodifiableMapView<String, int>(map1);

map2.containsKey('foo'); // Calls map1 that calls map0, but should just call map0 directly...

Shouldn't the ctor be a factory that checks if the map arg is already an UnmodifiableMapView, and then avoid creating yet another layer?
[Or is the magic dart compiler perhaps already smart enough to unwrap it?]

Please fix all errors before compiling (warnings are okay).
Error compiling dartdevc module:collection|lib/lib__shared_3.js

[error] Missing field type for 'key'. (package:collection/src/equality.dart, line 268, col 9)
[error] Missing field type for 'value'. (package:collection/src/equality.dart, line 269, col 9)
[error] Missing type arguments for generic type 'Equality<dynamic>'. (package:collection/src/equality.dart, line 397, col 41)
[error] Missing type arguments for generic type 'DefaultEquality<dynamic>'. (package:collection/src/equality.dart, line 400, col 55)
[error] Missing type arguments for generic type 'DefaultEquality<dynamic>'. (package:collection/src/equality.dart, line 408, col 30)
[error] Missing parameter type for 'e1'. (package:collection/src/equality.dart, line 412, col 15)
[error] Missing parameter type for 'e2'. (package:collection/src/equality.dart, line 412, col 19)
[error] Missing type arguments for generic type 'SetEquality<dynamic>'. (package:collection/src/equality.dart, line 415, col 18)
[error] The argument type 'dynamic' can't be assigned to the parameter type 'Set'. (package:collection/src/equality.dart, line 415, col 47)
[error] Missing type arguments for generic type 'MapEquality<dynamic, dynamic>'. (package:collection/src/equality.dart, line 419, col 18)
[error] The argument type 'dynamic' can't be assigned to the parameter type 'Map'. (package:collection/src/equality.dart, line 419, col 67)
[error] Missing type arguments for generic type 'ListEquality<dynamic>'. (package:collection/src/equality.dart, line 424, col 20)
[error] The argument type 'dynamic' can't be assigned to the parameter type 'List'. (package:collection/src/equality.dart, line 424, col 50)
[error] Missing type arguments for generic type 'IterableEquality<dynamic>'. (package:collection/src/equality.dart, line 428, col 20)
[error] The argument type 'dynamic' can't be assigned to the parameter type 'Iterable'. (package:collection/src/equality.dart, line 428, col 54)
[error] Missing type arguments for generic type 'UnorderedIterableEquality<dynamic>'. (package:collection/src/equality.dart, line 433, col 18)
[error] The argument type 'dynamic' can't be assigned to the parameter type 'Iterable'. (package:collection/src/equality.dart, line 433, col 61)
[error] Missing type arguments for generic type 'SetEquality<dynamic>'. (package:collection/src/equality.dart, line 439, col 30)
[error] Missing type arguments for generic type 'MapEquality<dynamic, dynamic>'. (package:collection/src/equality.dart, line 440, col 30)
[error] Missing type arguments for generic type 'ListEquality<dynamic>'. (package:collection/src/equality.dart, line 442, col 33)
[error] Missing type arguments for generic type 'IterableEquality<dynamic>'. (package:collection/src/equality.dart, line 443, col 37)
[error] Missing type arguments for generic type 'UnorderedIterableEquality<dynamic>'. (package:collection/src/equality.dart, line 445, col 18)

with (not sure if this matters)

analyzer:

  strong-mode:
    implicit-casts: false
    implicit-dynamic: false

  errors:
    strong_mode_down_cast_composite: error

I know it's simple but it's quite often useful:

Something like this:

class Pair<T1,T2> {
    final T1 first;
    final T2 second;
    Pair(this.first, this.second);

    bool operator==(final Pair other) {
        return first == other.first && second == other.second;
    }
    int get hashCode => hash2(first.hashCode,second.hashCode);
}

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="96" height="96"hspace="10"> Issue by nex3
Originally opened as dart-lang/sdk#18708

Sometimes it's useful to have a map that canonicalizes its keys but still keeps the original representations around. This can be done with the [equals] and [hashCode] parameters to [new HashMap], but this is inefficient since any canonicalization must take place for each equality comparison. It would be useful to expose a more efficient canonicalized map, and the collection package seems like the place.

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="96" height="96"hspace="10"> Issue by nex3
Originally opened as dart-lang/sdk#18970

UnmodifiableMapMixin exists, so it seems strange that UnmodifiableListMixin doesn't as well.

See also issue dart-lang/sdk#11178.

This is the issue for discussion (I don't have a detailed proposal yet).
Index is similar to MapValueSet, it wants to address a couple of extra problems:

1. MapValueSet stores the keys as independent objects. However, the key (by its definition from MapValueSet) can always be reconstructed from the record. Keys pollute memory and increase load on allocator and GC.
2. By construction, MapValueSet assumes the Key to be a public type. Not sure this is necessary. It's hard even to find a good name for the Key class (e.g., XAndY key type for point?)
3. In reality, it all leads to a lot of boilerplate; it would be desirable to have more user-friendly apparatus..

One obvious approach would be:

1. Introduce Index class that accepts Equality as parameter. Due to equality, you can always compare 2 records directly, without creating Key object. Index constructor looks as new Index(Equality)
2. Since there are no "physical" keys, they are not stored anywhere.
3. To top it off, user is not supposed to write anything manually, b/c we can always define generator like in @davidmorgan's example:

part 'point.g.dart';
class Point {
  @Index(#x)
  static final Equality<Point> byX = _$byX;
  @Index(#x, #y)
  static final Equality<Point> byXandY = _$byXandY;

  int x;
  int y;
  // other stuff
}

Everything looks good, except that I can't figure out the syntax for search. There should be a method index.find(something).
But how to write this "something", if we, say, want to find a point (2, 2)?

There are several ways.

• We can create "partial point" (template) containing only fields that constitute the key: points.findByTemplate(new Point(2,2)).
• We can pass tuple: points.find([2, 2])
• We can include createKey() into Equality interface, and call index.find(myEquality.createKey(2,2)). In this case, we don't have to make type K public. And in fact, it might return "template" without defining special type for Key, even private one.
• As a variant, we can call it createTemplate instead of createKey, then it will return record type T.

Do you think the problem is worth solving? I had a couple of situations where it was critical. E.g. there are 3 tables, cross-referenced by composite "relations", - say, several million records each
Suppose you need to run complex (reporting) algo that with many joins (and self-joins) - over entire set. Database operation takes forever. In memory, everything is fast, but indexes (implemented as maps) are eating all memory.
I had to write something like Index in java, and it was not very easy.

Added later: if we have Index, we need also MultiIndex or something - for one-to-many relation

<img src="https://avatars.githubusercontent.com/u/8631949?v=3" align="left" width="96" height="96"hspace="10"> Issue by floitschG
Originally opened as dart-lang/sdk#16426

I just marked priority_queue_test as slow for IE9 in checked mode.

... given that Dart 2 does this out of the box?

Here's what public APIs package offers today:

• DelegatingIterable.typed
• DelegatingList.typed
• DelegatingMap.typed
• DelegatingQueue.typed
• DelegatingSet.typed

Here's an example of the implementation of those static methods:

I imagine to avoid churn, we could do the following:

• Add a package-internal field called isStrongMode:

final bool isStrongMode = (() {
  bool typeParamIsString<T>(T item) => T == String;
  return typeParamIsString('');
})();

• Change the .typed methods to be:

static List<E> typed<E>(List base) {
  if (isStrongMode) {
    return base.cast<E>();
  }
  return base is List<E> ? base : new TypeSafeList<E>(base);
}

• When Dart 2 is enabled by default everywhere (Dart2JS/VM/Flutter), remove the TypeSafeX wrapper classes, as they will never be used. This should not be a breaking change, strictly.

• At the same time of above, deprecate the .typed methods, because they no longer have value and are misleading, doing is and .cast is fine for all users at this point.

Thoughts? @lrhn @srawlins @kevmoo

If you guys are interested, I'll start on a PR.

As the ecosystem moves to strong mode, we'll no longer be able to treat collections without generic types as though they had those types—stuff like list as List<String> will fail at runtime if the reified generic type doesn't match up. This can be avoided by writing stuff like new List<String>.from(list), but that involves copying the list—it's not as efficient as it could be, and it won't work at all if the user is relying on being able to see changes in the underlying list.

To fix this, we should provide properly-typed wrapper classes that assert the types of all values they returns from the underlying object. These could either be seperate types (CoercingListView? AssertingListView?) or constructors on the existing delegating types (new DelegatingList.coerce()? new DelegatingList.assertType()?).

See #74.

I won't be writing tests for TypeSafeX or DelegatingX for Dart 2.0 collections, as it will be a huge time sink with little value. Perhaps this can be done in the future.

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="96" height="96"hspace="10"> Issue by nex3
Originally opened as dart-lang/sdk#18705

Suppose there's a collection of objects that are indexed by properties on the objects themselves. Normally this would be represented by a Map, but in some cases it may be more useful to treat it as a Set. This is possible since the key is determinable from each value, so for example "add" could be implemented as "super[keyForValue(value)] = value". It would be nice to add a class to support this to the collection package.

It looks like we will need to run the tests using DDC, and skip them for Dart2JS only until Dart2JS implements 2.0 semantics. Seems easy enough, we've done that in other places.

It would be really nice to have a const Unmodifiable{List/Map/Set}View.empty() constructor or Empty{List/Map/Set} classes with const constructor because only const values can be used as default arguments for optional parameters!
The is a const Iterable.empty() constructor in Dart:core, but the same for List/Map/Set is missing and the List/Map/Set.from{Iterable}(Iterable i) constructors don't help us because they aren't const.

Please?

@jmesserly @lrhn

The following list of strong-mode errors prevent code that depend on package:collection from being compiled with DDC.

(ran dartanalyzer --strong find lib -name '*.dart' | sort -u with SDK version 1.16.0-dev.0.0)

[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.expand (((E) → Iterable<dynamic>) → Iterable<dynamic>) is not a subtype of Iterable<E>.expand (<T>((E) → Iterable<T>) → Iterable<T>). (./lib/src/wrappers.dart, line 194, col 24)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.expand (((E) → Iterable<dynamic>) → Iterable<dynamic>) is not a subtype of Iterable<E>.expand (<T>((E) → Iterable<T>) → Iterable<T>). (./lib/src/wrappers.dart, line 245, col 26)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.expand (((E) → Iterable<dynamic>) → Iterable<dynamic>) is not a subtype of Iterable<E>.expand (<T>((E) → Iterable<T>) → Iterable<T>). (./lib/src/wrappers.dart, line 97, col 25)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.expand (((V) → Iterable<dynamic>) → Iterable<dynamic>) is not a subtype of Iterable<V>.expand (<T>((V) → Iterable<T>) → Iterable<T>). (./lib/src/wrappers.dart, line 414, col 25)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.fold ((dynamic, (dynamic, E) → dynamic) → dynamic) is not a subtype of Iterable<E>.fold (<T>(T, (T, E) → T) → T). (./lib/src/wrappers.dart, line 194, col 24)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.fold ((dynamic, (dynamic, E) → dynamic) → dynamic) is not a subtype of Iterable<E>.fold (<T>(T, (T, E) → T) → T). (./lib/src/wrappers.dart, line 245, col 26)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.fold ((dynamic, (dynamic, E) → dynamic) → dynamic) is not a subtype of Iterable<E>.fold (<T>(T, (T, E) → T) → T). (./lib/src/wrappers.dart, line 97, col 25)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.fold ((dynamic, (dynamic, V) → dynamic) → dynamic) is not a subtype of Iterable<V>.fold (<T>(T, (T, V) → T) → T). (./lib/src/wrappers.dart, line 414, col 25)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.map (((E) → dynamic) → Iterable<dynamic>) is not a subtype of Iterable<E>.map (<T>((E) → T) → Iterable<T>). (./lib/src/wrappers.dart, line 194, col 24)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.map (((E) → dynamic) → Iterable<dynamic>) is not a subtype of Iterable<E>.map (<T>((E) → T) → Iterable<T>). (./lib/src/wrappers.dart, line 245, col 26)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.map (((E) → dynamic) → Iterable<dynamic>) is not a subtype of Iterable<E>.map (<T>((E) → T) → Iterable<T>). (./lib/src/wrappers.dart, line 97, col 25)
[error] Base class introduces an invalid override. The type of _DelegatingIterableBase.map (((V) → dynamic) → Iterable<dynamic>) is not a subtype of Iterable<V>.map (<T>((V) → T) → Iterable<T>). (./lib/src/wrappers.dart, line 414, col 25)
[error] Invalid override. The type of _DelegatingIterableBase.expand (((E) → Iterable<dynamic>) → Iterable<dynamic>) is not a subtype of Iterable<E>.expand (<T>((E) → Iterable<T>) → Iterable<T>). (./lib/src/wrappers.dart, line 27, col 3)
[error] Invalid override. The type of _DelegatingIterableBase.fold ((dynamic, (dynamic, E) → dynamic) → dynamic) is not a subtype of Iterable<E>.fold (<T>(T, (T, E) → T) → T). (./lib/src/wrappers.dart, line 34, col 3)
[error] Invalid override. The type of _DelegatingIterableBase.map (((E) → dynamic) → Iterable<dynamic>) is not a subtype of Iterable<E>.map (<T>((E) → T) → Iterable<T>). (./lib/src/wrappers.dart, line 54, col 3)
[error] Type check failed: const DefaultEquality() (DefaultEquality) is not of type Equality<E> (./lib/src/equality.dart, line 182, col 38)
[error] Type check failed: const DefaultEquality() (DefaultEquality) is not of type Equality<E> (./lib/src/equality.dart, line 198, col 38)
[error] Type check failed: const DefaultEquality() (DefaultEquality) is not of type Equality<E> (./lib/src/equality.dart, line 56, col 31)
[error] Type check failed: const DefaultEquality() (DefaultEquality) is not of type Equality<E> (./lib/src/equality.dart, line 99, col 53)
[error] Type check failed: const DefaultEquality() (DefaultEquality) is not of type Equality<K> (./lib/src/equality.dart, line 234, col 42)
[error] Type check failed: const DefaultEquality() (DefaultEquality) is not of type Equality<V> (./lib/src/equality.dart, line 235, col 44)
[warning] Missing concrete implementation of 'Iterable.expand', 'Iterable.fold' and 'Iterable.map' (./lib/src/unmodifiable_wrappers.dart, line 20, col 7)
[warning] Missing concrete implementation of 'Iterable.expand', 'Iterable.fold' and 'Iterable.map' (./lib/src/unmodifiable_wrappers.dart, line 93, col 7)
[warning] Missing concrete implementation of 'Iterable.expand', 'Iterable.fold' and 'Iterable.map' (./lib/src/wrappers.dart, line 194, col 7)
[warning] Missing concrete implementation of 'Iterable.expand', 'Iterable.fold' and 'Iterable.map' (./lib/src/wrappers.dart, line 245, col 7)
[warning] Missing concrete implementation of 'Iterable.expand', 'Iterable.fold' and 'Iterable.map' (./lib/src/wrappers.dart, line 339, col 7)
[warning] Missing concrete implementation of 'Iterable.expand', 'Iterable.fold' and 'Iterable.map' (./lib/src/wrappers.dart, line 414, col 7)
[warning] Missing concrete implementation of 'Iterable.expand', 'Iterable.fold' and 'Iterable.map' (./lib/src/wrappers.dart, line 97, col 7)
[warning] The redirected constructor '() → DefaultEquality' has incompatible parameters with '() → Equality<E>' (./lib/src/equality.dart, line 11, col 30)
[warning] Unsound implicit cast from (dynamic, dynamic) → int to (E, E) → int (./lib/src/priority_queue.dart, line 210, col 15)
[warning] Unsound implicit cast from (dynamic, dynamic) → int to (E, E) → int (./lib/src/priority_queue.dart, line 215, col 38)
[warning] Unsound implicit cast from Iterable<E> to List<dynamic> (./lib/src/queue_list.dart, line 38, col 25)
[warning] Unsound implicit cast from Iterable<E> to List<dynamic> (./lib/src/queue_list.dart, line 55, col 19)
[warning] Unsound implicit cast from List<dynamic> to Iterable<E> (./lib/src/queue_list.dart, line 39, col 40)
[warning] Unsound implicit cast from List<dynamic> to Iterable<E> (./lib/src/queue_list.dart, line 61, col 52)
[warning] Unsound implicit cast from List<dynamic> to Iterable<E> (./lib/src/queue_list.dart, line 67, col 52)
[warning] Unsound implicit cast from List<dynamic> to Iterable<E> (./lib/src/queue_list.dart, line 71, col 52)
[warning] Unsound implicit cast from List<dynamic> to Iterable<E> (./lib/src/queue_list.dart, line 72, col 40)
[warning] Unsound implicit cast from List<dynamic> to List<Comparable<dynamic>> (./lib/src/algorithms.dart, line 36, col 36)
[warning] Unsound implicit cast from List<dynamic> to List<Comparable<dynamic>> (./lib/src/algorithms.dart, line 84, col 34)
[warning] Unsound implicit cast from List<dynamic> to List<Iterator<dynamic>> (./lib/src/iterable_zip.dart, line 33, col 47)
[warning] Unsound implicit cast from dynamic to C (./lib/src/canonicalized_map.dart, line 61, col 11)
[warning] Unsound implicit cast from dynamic to C (./lib/src/canonicalized_map.dart, line 93, col 30)
[warning] Unsound implicit cast from dynamic to E (./lib/src/equality.dart, line 68, col 36)
[warning] Unsound implicit cast from dynamic to E (./lib/src/equality.dart, line 68, col 49)
[warning] Unsound implicit cast from dynamic to E (./lib/src/unmodifiable_wrappers.dart, line 59, col 28)
[warning] Unsound implicit cast from dynamic to E (./lib/src/unmodifiable_wrappers.dart, line 63, col 21)
[warning] Unsound implicit cast from dynamic to K (./lib/src/wrappers.dart, line 443, col 13)
[warning] Unsound implicit cast from dynamic to V (./lib/src/unmodifiable_wrappers.dart, line 151, col 41)
[warning] Unsound implicit cast from dynamic to V (./lib/src/unmodifiable_wrappers.dart, line 159, col 27)

Already tagged on github. Thanks!

E.g., "const ListEquality()" causes the following warnings:

[INFO] The object type 'DefaultEquality' cannot be assigned to the field '_elementEquality', which has type 'Equality' [CONST_CONSTRUCTOR_FIELD_TYPE_MISMATCH]
[INFO] The object type 'DefaultEquality' cannot be assigned to a parameter of type 'Equality' [CONST_CONSTRUCTOR_PARAM_TYPE_MISMATCH]

This is because of the type mismatch in ListEquality's default constructor parameters:
final Equality _elementEquality;
const ListEquality([Equality elementEquality = const DefaultEquality()])
: _elementEquality = elementEquality;

and can be fixed by adding the generic type. I'll send a pull request for this and similar classes.

<img src="https://avatars.githubusercontent.com/u/17034?v=3" align="left" width="96" height="96"hspace="10"> Issue by kevmoo
Originally opened as dart-lang/sdk#17947

Point folks to dart:collection instead

...once the dev version changes to 1.4 series, of course

The pub site can show example code for a package.
https://www.dartlang.org/tools/pub/package-layout#examples

Let me know if you want me to try working on this.

related issue : dart-lang/site-www#413

It's nice that PriorityQueue allows for different implementations, but (like the core collection APIs) it should have a factory constructor that forwards to the default implementation. Right now, it's confusing that you can't construct a PriorityQueue using new PriorityQueue().

The following test fails:

final map = CombinedMapView([{'1': 1, '2': 2, '3': 3}, {'2': 22, '4': 44}]);
expect(map.length, equals(4));
expect(map.keys.toList(), equals(['1', '2', '3', '4']));

The first expectation fails because length returns 5.
The second, because keys returns ['1', '2', '3', '2', '4'].

This seems to violate Map's interface, which says:

There is a finite number of keys in the map, and each key has exactly one value associated with it.

This was a problem for me because I needed something that looks just like a normal Map but based on two other Maps, and which lets a map coming first "override" values on the map coming later in the list of maps. I believe that's the main purpose of combining maps (possibly unmodifiable), but due to this issue, it can't be used like that.

running tests in dart 2 mode has failures

Expected: throws UnsupportedError
Actual: <Closure: () => Null>
Which: threw ?:<type '_GeneratorIterable' is not a subtype of type 'Iterable' of 'iterable' where
_GeneratorIterable is from dart:core
Iterable is from dart:core
int is from dart:core
>
stack dart:collection _ListBase&Object&ListMixin.setRange
../../collection/test/unmodifiable_collection_test.dart 338:13 testNoWriteList.

type '_CompactLinkedHashSet' is not a subtype of type 'Set' of 'component' where...
type '_CompactLinkedHashSet' is not a subtype of type 'Set' of 'component' where
_CompactLinkedHashSet is from dart:collection
Set is from dart:core
int is from dart:core
package:collection/src/union_set_controller.dart UnionSetController.add
../../collection/test/union_set_controller_test.dart 20:16 main.

type '_CompactLinkedHashSet' is not a subtype of type 'Set' of 'other' where...
type '_CompactLinkedHashSet' is not a subtype of type 'Set' of 'other' where
_CompactLinkedHashSet is from dart:collection
Set is from dart:core
int is from dart:core
package:collection/src/wrappers.dart DelegatingSet.union
../..dart/collection/test/unmodifiable_collection_test.dart 476:20 testReadSet.

and more....

<img src="https://avatars.githubusercontent.com/u/5475521?v=3" align="left" width="96" height="96"hspace="10"> Issue by ricowind
Originally opened as dart-lang/sdk#19391

https://code.google.com/p/dart/source/detail?r=37255
Made the pkgbuild package repo testing fail with:
FAILED: none-vm release_ia32 pkgbuild/pkg/collection
Expected: Pass
Actual: PubGetError
CommandOutput[dir_copy]:
diagnostics:
CommandOutput[modify_pubspec]:
diagnostics:
CommandOutput[pub_get]:

stdout:
Resolving dependencies...

stderr:
Package collection 1.0.0-dev does not match >=0.9.1 <0.10.0 derived from:

• angular 0.9.8 depends on version >=0.9.1 <1.0.0
• args 0.11.0+1 depends on version >=0.9.0 <0.10.0

I will suppress this for now. I am tentatively marking this high priority and milestone 1.5, if this is not aimed at 1.5 please reset.

As a short-hand (and even potentially implemented with) for:

mapMap(map, key: (k, v) => v, value: (k, v) => k)

This is much cheaper than a full BiMap implementation when you just need it flipped once.

Thoughts?

It's not fair to introduce 1600 analysis hints in a repository without either fixing it, having a plan to fix it, etc. This is just noise for the average developer and doesn't help anyone.

I'm proposing removing this lint pending some sort of "fix all" from the analyzer.

/cc @kevmoo

The documentat of PriorityQueue states:

  /// The [comparison] is a [Comparator] used to compare the priority of
  /// elements. An element that compares as less than another element has
  /// a higher priority.

(btw: the documentation doesn't state what the function should return).

However, the comparison function is also used as equality function.
For example, PriorityQueue.contains, or PriorityQueue.remove both use this function to determine equality. In some cases that works, but a common use case is to extract a priority field from one of many fields.

Example:

class PriorityPoint {
  int x, y, priority;
  PriorityPoint(this.x, this.y, this.priority);
}

var queue = new PriorityQueue(comparison: (p1, p2) => p2.priority - p1.priority);
queue.add(new PriorityPoint(0, 1, 5));
queue.contains(new PriorityPoint(-1, -3, 5));  // Should probably return false.

I'm not sure what the best solution is, but the current behavior and documentation are not consistent.
Furthermore, the current behavior makes it hard to implement the provided use case.

SplayTreeMap is very useful for managing time series and other sorted data. A common use case involves looking at a range (imagine zooming into a small area of a large chart) efficiently, but the current implementation does not offer methods to do that.

The existing lastKeyBefore and firstKeyAfter methods are not very useful if it's not possible to use them to do tree.subtree(firstKeyAfter(x), lastKeyBefore(y)).

Can we please add such a range method to SplayTreeMap?

Examples in other languages:

• Java
• Rust
• Go

Copied from the sdk issue repo

I need a queue that automatically sorts out duplicates. Right now I do:

final queue = new Set<Something>();
while (queue.isNotEmpty) {
  final something = queue.first;
  queue.remove(something);
  process(something);
}

But having a dedicated class for that would be nice. I can try to implement it, but I'll need help when it comes to benchmarking. (compare sdk/31470?)

... if you think this class belongs in this package, of course.

See TODOs in https://github.com/dart-lang/collection/blob/master/lib/src/wrappers.dart.

Internal users are hitting this when attempting to use .cast and friends:

• Map.addEntries

• Map.entries

• Map.map

• Map.cast

• Map.retype

• Map.update

• Map.updateAll

• Map.removeWhere

• List.cast

• List.+

• Iterable.followedBy

• Iterable.retype

• Iterable.whereType

• Iterable.singleWhere (orElse)

• Iterable.indexWhere

• Iterable.lastIndexWhere

NOTE: Adding tests for every one of these for everyone of the implementing classes... Not a fun experience. I'm going to be skipping TypeSafeX and DelegatingX when writing tests: #81.

I'd like to say that QueueList's cast and retype do not adhere to the contract laid out by List.cast and List.retype but that may be up for debate. In any case, List.cast's documentation says:

Returns a view of this list as a list of R instances, if necessary.

List.retype's documentation says, similarly:

Returns a view of this list as a list of R instances.

(Ignoring for now what "if necessary" must mean...) I believe it is intended that the return value be the same list (just a different view of it), not a new list. For example, let's play with List:

void main() {
  var a = new List<num>()..addAll([1,2,3]);
  var b = a.retype<int>();
  b.add(4); // add 4 to the view.
  a.add(5); // add 5 to the original.
  b.remove(3); // remove 3 from the view.
  print('a: $a'); //=> [1, 2, 4, 5]
  print('b: $b'); //=> [1, 2, 4, 5]
}

They are the same list. Now let's do the same for QueueList:

import 'package:collection/collection.dart';

void main() {
  var c = new QueueList<num>()..addAll([1,2,3]);
  var d = c.retype<int>();
  d.add(4);
  print('c: $c'); //=> {1, 2, 3} // Not the same list!
  print('d: $d'); //=> {1, 2, 3, null, null, null, null, null, 4} // Duck?
  c.add(5);
  print('c: $c'); //=> {1, 2, 3, 5}
  print('d: $d'); //=> {1, 2, 3, null, null, null, null, null, 4}
}

I have not checked the other cast and retype implementations yet, but when I do, I presume I'll just add on to this bug, rather than filing a bug for each class.

I have a piece of dummy code:

import 'package:collection/collection.dart';                                     

int main() {                                                                     
  print(const SetEquality<String>().equals(["a", "b"].toSet(), ["a", "b"].toSet())); 
  return 0;                                                                      
}                                                                                

on running the dartanalyzer in strong mode, I get:

Analyzing [lib/main.dart]...
[info] The object type 'DefaultEquality<E>' cannot be assigned to a parameter of type 'Equality<String>' (/work/modular/src/repo_analyzer_error/lib/main.dart, line 4, col 9)
[info] The object type 'DefaultEquality<E>' cannot be assigned to a parameter of type 'Equality<String>' (/work/modular/src/repo_analyzer_error/lib/main.dart, line 7, col 6330)

in wrapper_test.dart, I see the following with the analyzer:

177: [INFO] The getter 'equals' is not defined for the class 'String' [UNDEFINED_GETTER]
263: [INFO] The getter 'equals' is not defined for the class 'String' [UNDEFINED_GETTER]

These are because Expector is overriding Object's toString() with a method that doesn't return a String. Should we change Expector's method to asString() or something similar?

Originally opened as dart-lang/sdk#22040

This issue was originally filed by [email protected]

What steps will clearly show the issue / need for enhancement?

1. [binarySearch] returns -1 in case an element is not found
2. Often in a program one would first try to find an element in a list and if it is not in the next step is to add it. Knowing where it has to be added avoids to sort the list again after the addition.
3. It is very easy for [binarySearch] to return the insertion point, no additional calculation is needed.

What is the current output?

-1 if an element is not found.

What would you like to see instead?

-insertion point - 1

What version of the product are you using? On what operating system?

collection 1.1.0, Windows 7

Please provide any additional information below.

My proposal for the reworked code:

  /// Returns a position of the [key] in [sortedList], if it is there.
  ///
  /// If the list isn't sorted according to the [compare] function, the result is unpredictable. If
  /// [compare] is omitted, it defaults to calling [Comparable.compareTo] on the objects.
  ///
  /// Returns [-insertion point - 1] if [key] is not in the list. The insertion point is defined as
  /// the point at which the key would be inserted into the list: the index of the first element
  /// greater than the key, or [list.length] if all elements in the list are less than the specified
  /// key. Note that this guarantees that the return value will be >= 0 if and only if the key is
  /// found.
  int binarySearch(List sortedList, var key, { int compare(var a, var b) }) {
    bool useDefault = compare == null;
    int min = 0;
    int max = sortedList.length;
    while (min < max) {
      int mid = min + ((max - min) >> 1);
      var element = sortedList[mid];
      int comp = useDefault ? element.compareTo(key) : compare(element, key);
      if (comp == 0) return mid;
      if (comp < 0) min = mid + 1; else max = mid;
    }
    return -min - 1;
  }

The code also contains a slight enhancement which avoids to have the same method programmed twice as is the case in the current implementation. The enhancement is not performance negative but halves the code size!

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="96" height="96"hspace="10"> Issue by nex3
Originally opened as dart-lang/sdk#18729

Sometimes it's useful to be able to compare nested object structures that can contain self-referential loops. Currently DeepCollectionEquality causes a stack overflow when passed such structures, but it would be nice if it could handle them. This could be done either as a configuration option or as the default if the prospect of storing back-references isn't too worrisome.

Currently the YAML package has its own custom implementation of deep equality, but it would be nice if it could use the standard implementation instead.

There should be a less verbose way to create an Equality implementation for:

abstract class Employee {
  int get idNumber;
  String get name;
}

void main() {
  final equality = new Equality<Employee>.from((e) => e.idNumber);
  assert(
    equality.equals(new Employee(idNumber: 5), new Employee(idNumber: 5)),
  );
}

An implementation example:

typedef Object _GetKey<E>(E object);

class _ClosureEquality<E> implements Equality<E> {
  final _GetKey<E> _getKey;

  _ClosureEquality(Object getKey(E object)) : this._getKey = getKey;

  @override
  bool isValidKey(Object o) => o is E;

  @override
  int hash(E e) => _getKey(e).hashCode;

  @override
  bool equals(E e1, E e2) => _getKey(e1) == _getKey(e2);
}

In the case of Java, binarySearch methods return -(insertion point + 1) when the element can't be found. I think this usage is quite popular and hope to see supported in this package.

Currently I do something like:

  bool operator ==(other) =>
      other is TaskInvocation &&
      name == other.name &&
      const IterableEquality().equals(positionals, other.positionals) &&
      const MapEquality().equals(options, other.options);

  int get hashCode =>
      name == other.name.hashCode ^
      (const IterableEquality().hash(positionals) * 3) ^
      (const MapEquality().hash(options) * 5);

which has lots of duplication between == and hashCode. I'd prefer to have something like:

class AndEquality<E> {
  /// Equality for which elements are equal if equal according to all in [equalities].
  const AndEquality<E>(Iterable<Equality<E>> equalities);
}

https://travis-ci.org/dart-lang/collection/jobs/394385077#L589

  TypeError: Closure 'equals$2' of Instance of 'MapEquality<dynamic, Iterable>': type '(Map<dynamic, Iterable>, Map<dynamic, Iterable>) => bool' is not a subtype of type '(Map, Map) => bool'

<img src="https://avatars.githubusercontent.com/u/17034?v=3" align="left" width="96" height="96"hspace="10"> Issue by kevmoo
Originally opened as dart-lang/sdk#17946

I hit a type collisions between the new UnmodifiableMapView in 1.4 SDK and the type in collection.

pkg/collection 0.9.1+1 should exclude exclude 1.4 to eliminate collisions

Let's start with just discussing combineList, which is currently implemented in various forms internally, and has lots of utility and potential perf-saving.

//// Returns a new list that represents [lists] flattened into a single list.
///
/// All methods and accessors treat the new list as-if it were a single concatenated list,
/// but the underlying implementation delegates to each corresponding list as necessary. 
List<T> combineLists<T>(List<List<T>> lists) => ...

Here is an example of implementing first:

class _CombinedList<T> implements List<T> {
  final List<T> _lists;

  T get first {
    for (final list in _lists) {
     if (list.isNotEmpty) {
       return list.first; 
     }
    }
   throw ...
  }
}

/cc @nex3, @leonsenft, @ferhatb

FWIW I believe @isoos originally implemented something like this for the high-performance table, and it worked really well. I'd also eventually like to see the same thing for Map and Iterable if possible - though to simplify things they may need to be read-only, but worth discussing anyway.

Index is a familiar concept, would be interesting to see how it fits into dart.

the idea is to write

@Indexable(#firstName,#lastName")
class Person {
   final String firstName;
   final String lastName;
   // other stuff
}

and run source_gen generator, so we could write

var index = new PersonIndex$firstName$lastName();
index.addAll(persons); // some collection of persons
var johnDoe = index.find("John", "Doe");

Index is not supposed to create or store keys in the course of normal operation (unless user explicitly wants to get a key).

Generated code contains class PersonIndex$firstName$lastName extends Index
with methods

int getHashCode(Person p);
bool haveEqualKeys(Person p1, Person p2);
bool hasKey(Person p1, Object key)
bool isValidKey(Object key)
Person find(String firstName, String lastName);
Object extractKey(Person p); // rarely needed
// other blows and whistles

For key extraction, generator generates also PersonKey$firstName$lastName

The whole idea is to make it more convenient and save memory on keys. Generated classes will have quite a bit of redundancy. Writing it manually is not worth it.

DelegatingList types the methods while dart:core|Iterable does not.