Contains utility functions and classes in the style of dart:collection to make working with collections easier

Add a extension function for List getOrNull(int index) returns a element at the given [index] of this list, if [index] out of bounds, return null

Example:

final list = [1,2,3];
list.getOrNull(1); // 2
list.getOrNull(10); // null

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.

…retaining all inserted values and always returning the last inserted value through standard Map API. Additional method, multiple, allows access to all inserted values for a given key. Will be used in http and http_server packages for non-breaking extension of functionality for form parameters and header parameters that have multiple values for the same key.

Referenced Issues: https://github.com/dart-lang/http/issues/47 https://github.com/dart-lang/http/issues/24 https://github.com/dart-lang/http_server/issues/35 https://github.com/dart-lang/sdk/issues/28142

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.

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!

Add a number of useful extension methods to List and Iterable, and to a few other types.

A good part of these extensions are backed by the algorithms of algorithms.dart, which is expanded to support them:

• Added quickSort.
• Add extra optional Random argument to shuffle.
• Generalize some of the functions in algorithms.dart to work on specific properties of the objects (binarySearchBy, lowerBoundBy, insertionSortBy, quickSortBy, mergeSortBy).

My code has several huge priority queues using HeapPriorityQueue, where it occasionally needs to consider all the elements in the queue where the order doesn't matter (e.g. to tally up how long it will take to process the queue, or to consider all the items and move a few to another queue if circumstances changes).

However, HeapPriorityQueue only offers toList() and toSet() for this purpose. However, they spend O(nlogn) to sort the queue (and I need a linear time algorithm) and duplicates the data structure (I just need constant memory). The only way to iterate the queue in linear time in unsorted order is to use removeAll(), however it is destructive.

The HeapPriorityQueue internally just uses a list to manage the data structure, which is what is returned by removeAll(). It could easily gain a Iterable<E> get unsorted getter or something that returns the backing data structure with the appropriate concurrent modification protections.

This is probably a breaking change and needs a major version bump in case anyone implemented HeapPriorityQueue.

I'm currently working around the issue associating each priority queue with a Set in my mod, however it duplicates the amount of memory spent on the queues.

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.

Adds an EmptyUnmodifiableMap implementation which provides a const constructor.

The Mixin classes within unmodifiable_wrappers.dart were changed from abstract class to mixin to modernize the code. This allowed the EmptyUnmodifiableMap to have a const constructor without also defining a const constructor in UnmodifiableMapMixin.

<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.

Fixes https://github.com/dart-lang/collection/issues/109

Adds a custom iterable/iterator that can filter out duplicates and use that for the CombineMapView.keys getter.

Update tests to contain duplicates in maps, and ensure the keys/values from the earlier maps are the ones that are returned.

Updates the changelog and docs to no longer claim O(maps) for the length getter. This now requires iteration of all items and is O(total map entries).

Prepare to publish as 1.14.12

• copy: copies a CanonicalizedMap instance without recalculating the canonical values of the keys.
• toMap: creates a Map<K,V> (with the original key values).
• toMapOfCanonicalKeys: creates a Map<C,V> (with the canocalized keys).

I believe the current implementation produces two iterators: one for isEmpty and one for last:

  /// The last element, or `null` if the iterable is empty.
  T? get lastOrNull {
    if (isEmpty) return null;
    return last;
  }

Unless I'm missing something here, I think this is suboptimal, especially when using this on a lazy Iterable (for example, giantList.where(someCondition).

I have found this extension to be useful, it allows someone to skip the common for loop pattern for accessing elements. It also supersedes the need for specialized methods like mapIndexed, whereIndexed, (I count 14 in this package). BUT the value seems low because technically we have asMap and these specialized methods already

Before

for(var i = 0; i < foo.length; i++){
  print(i);
  print(foo[i]);
}

foo.forEach((value){
  final index = foo.indexOf(value);
  print(index);
  print(value);
}

After

for(final element in foo.enumerated){
  print(element.index);
  print(element.value);
}

foo.enumerated.forEach((element){
  print(element.index);
  print(element.value);
}

Related issues

Lots of JavaScript developers rely on their overloadable map method which allows optionally accessing the index, so tutorials like this are created to shim this missing functionality https://fireship.io/snippets/dart-how-to-get-the-index-on-array-loop-map/

This is a common question on Stack Overflow

Entire videos on YouTube are dedicated to helping people with this

https://www.youtube.com/watch?v=HLMzibT2Wms

There are some related issues here, although admittedly they are closed

https://github.com/dart-lang/sdk/issues/49589 https://github.com/dart-lang/sdk/issues/33965

I cant update to version 1.17.0, i got this message

Because every version of flutter_test from sdk depends on collection 1.16.0 and app depends on collection ^1.17.0, flutter_test from sdk is forbidden. So, because app depends on flutter_test from sdk, version solving failed. pub get failed (1; So, because app depends on flutter_test from sdk, version solving failed.)

Flutter version : 3.3.8

it would be nice if we could stop using Map<String,dynamic> for json and have something like

typedef Json = Map<String,Object?>;

if find this would

• reduce bolilerplate
• be more accurate
• be more readable

• whereIn, whereNotIn, eg: currentPictures.whereNot(removedPictures.contain) vs currentPictures.whereNotIn(removedPictures)
• whereEqual, whereNotEqual eg: currentMedias.whereNot((media) => media == removedMedia) vs currentMedias.whereNotEqual(removedMedia)

Just a suggestion to improve readability, especially for the first one. Those seems vanilla enough to warrant an addition.