Announcing FIC: Fast Immutable Collections

Plus extension methods and comparators for native Dart collections

Marcelo Glasberg
Flutter Community

--

Photo by Ross Findon on Unsplash

A native Dart list is mutable, meaning you can change its items:

var list = [1, 2];
list.add(3);

You can prevent mutability by using the List.unmodifiable constructor, but this will not remove the add method. It just fails at runtime:

var list = List.unmodifiable([1, 2]);
var list.add(3); // Throws an exception.

Once you have a list you can’t change, you may still add or remove items by making copies with the desired changes. For example:

var myList = List.unmodifiable([1, 2]); // You can't change this.
var newList = List.unmodifiable(myList.toList()..add(3));
// Prints [1, 2]
print(myList);
// Prints [1, 2, 3]
print(newList);

There is a better way

As you can see above, using a mutable List as immutable is possible. But it’s a lot of boilerplate to write, and makes the code hard to read. There is a better way, by using an IList instead of a List. An IList is naturally immutable, and very easy to use.

To create an IList you can simply “lock” a List:

IList<int> ilist = [1, 2].lock;

You can’t modify an IList. However it still has an add method, which now returns a new IList with the added item. For example:

var myList = [1, 2].lock; // You can’t change this.
var newList = myList.add(3));
// Prints [1, 2]
print(myList);
// Prints [1, 2, 3]
print(newList);

FIC

The Fast Immutable Collections package, or FIC for short, provides immutable collections out of the box. FIC is a Dart package competitor to the excellent built_collection and kt_dart packages, but it’s much easier to use than the former, and orders of magnitude faster than the latter.

Go to https://pub.dev/packages/fast_immutable_collections to see the benchmarks that compare its speed with the alternatives. Sometimes it’s even faster than the native Dart collections:

Usage

The immutable collections are named IList, ISet and IMap. To create an immutable collection you can simply “lock” a mutable one:

IList<int> ilist = [1, 2].lock;
ISet<int> iset = {1, 2}.lock;
IMap<String, int> imap = {"a": 1, "b": 2}.lock;

Any Iterable can also be locked into an immutable list or set, by using toIList() and toISet(), or by using constructors:

IList<int> ilist = myIterable.toIList();
ISet<int> iset = myIterable.toISet();
// Also works:
IList<int> ilist = IList(myIterable);
ISet<int> iset = ISet(myIterable);

And you can “unlock” immutable collections back into mutable native Dart ones:

List<int> list = ilist.unlock;
Set<int> set = iset.unlock;
Map<String, int> map = imap.unlock;
// Also works:
List<int> list = ilist.toList();
Set<int> set = iset.toSet();
// Also works:
List<int> list = List.of(ilist);
Set<int> set = Set.of(iset);

But remember, methods that change items now return new collections, instead of modifying the original ones. For example:

var ilist1 = [1, 2].lock;

// Results in: 1, 2, 3
var ilist2 = ilist1.add(3);

// Results in: 1, 3
var ilist3 = ilist2.remove(2);

// Still: 1, 2
print(ilist1);

Because of that, you can easily chain methods:

// Results in: 1, 3, 4.
var ilist = [1, 2, 3].lock.add(4).remove(2);

Equality

By default, FIC collections are equal if they have the same items in the same order.

var ilist1 = [1, 2].lock;
var ilist2 = [1, 2].lock;

// False!
print(identical(ilist1 == ilist2));

// True!
print(ilist1 == ilist2);

This is in sharp contrast to regular Lists, which are compared by identity:

var list1 = [1, 2];
var list2 = [1, 2];

// Regular Lists compare by identity:
print(identical(ilist1 == ilist2)); // False!
print(list1 == list2); // False!
// While ILists compare by deep equals:
print(list1.lock == list2.lock); // True!

However, ILists are configurable, and you can actually create ILists which compare their internals by identity:

// These ILists compare by deep equals:
var ilist1 = [1, 2].lock;
var ilist2 = [1, 2].lock;
print(ilist1 == ilist2); // True!
// Now, these ILists compare by identity:
var ilist3 = [1, 2].lock.withIdentityEquals;
var ilist4 = [1, 2].lock.withIdentityEquals;
print(ilist3 == ilist4); // False!

Sort

Both ISet and IMapmay keep the insertion order, or may be sorted, depending on their configuration:

/// Default is insertion order. Prints: "2,4,1,9,3"
var iset = {2, 4, 1, 9, 3}.lock;
print(iset.join(","));
/// Prints sorted: "1,2,3,4,9"
var iset = {2, 4, 1, 9, 3}.lock.withConfig(ConfigSet(sort: true));
print(iset.join(","));

IMapOfSets

When you lock a Map<K, V> it turns into an IMap<K, V>.

However, a locked Map<K, Set<V>> turns into an IMapOfSets<K, V>:

/// Map to IMap
IMap<K, V> map = {'a': 1, 'b': 2}.lock;
/// Map to IMapOfSets
IMapOfSets<K, V> map = {'a': {1, 2}, 'b': {3, 4}}.lock;

A “map of sets” is a type of multimap. The IMapOfSets lets you add and remove values, without having to think about the sets that contain them. For example:

IMapOfSets<K, V> map = {'a': {1, 2}, 'b': {3, 4}}.lock;// Prints {'a': {1, 2, 3}, 'b': {3, 4}}
print(map.add('a', 3));

In this link you will find an example class called StudentsPerCourse which lets you arrangeStudents into Courses. Each student can be enrolled into one or more courses. This can be modeled by a map where the keys are the courses, and the values are sets of students.

ListSet

Despite its name, FIC also offers some mutable goods. For example, a ListSet is, at the same time:

  1. A mutable, fixed-sized, ordered, Set.
  2. A mutable, fixed-sized, List, in which values can't repeat.
ListSet<int> listSet = ListSet.of([1, 2, 3]);
expect(listSet[2], 3);
expect(listSet.contains(2), isTrue);
List<int> list = listSet;
Set<int> set = listSet;
expect(list[2], 3);
expect(set.contains(2), isTrue);

When viewed as a Set and compared to a LinkedHashSet, a ListSet is also ordered and has a similar performance. But a ListSet takes less memory and can be sorted or otherwise rearranged, just like a list. Also, you can directly get its items by index, very efficiently (constant time).

The disadvantage, of course, is that ListSet has a fixed size, while aLinkedHashSet does not. The ListSet is efficient both as a List and as aSet. So, for example, it has an efficient sort method, while aLinkedHashSet would force you to turn it into a List, then sort it, then turn it back into a Set.

Extensions, helpers and comparators

FIC also comes with:

Iterable helpers and extensions

  • combineIterables is a top-level function that combines two iterables into one, by applying a combine function.
  • Iterable.isNullOrEmpty, Iterable.isNotNullOrEmpty and Iterable.isEmptyButNotNull.
  • Iterable.deepEquals compare all items, in order, using operator ==.
  • Iterable.deepEqualsByIdentity compare all items, in order, using identical.
  • Iterable.findDuplicates finds duplicates and then returns a set with the duplicated elements.
  • Iterable.removeNulls removes nulls from the iterable.
  • Iterable.removeDuplicates removes all duplicates. Optionally, you can provide an by function to compare the items. If you pass removeNulls true, it will also remove the nulls.
  • Iterable.sortedLike returns a list, sorted according to the order specified by the ordering iterable. Items which don't appear in the ordering iterable will be included in the end.

List extensions

  • List.sortOrdered is similar to sort, but uses a merge sort algorithm. Contrary to sort, orderedSort is stable, meaning distinct objects that compare as equal end up in the same order as they started in.
  • List.sortLike sorts this list according to the order specified by an ordering iterable. Items which don't appear in ordering will be included in the end, in no particular order.
  • List.moveToTheFront moves the first occurrence of the item to the start of the list.
  • List.moveToTheEnd moves the first occurrence of the item to the end of the list.
  • List.whereMoveToTheFront moves all items that satisfy the provided test to the start of the list.
  • List.whereMoveToTheEnd moves all items that satisfy the provided test to the end of the list.
  • List.toggle If the item does not exist in the list, add it and return true. If it already exists, remove the first instance of it and return false.
  • List.compareAsSets returns true if the lists contain the same items (in any order). Ignores repeated items.
  • List.mapIndexed maps each element of the list. The map function gets both the original item and its index.
  • List.splitList splits a list, according to a predicate, removing the list item that satisfies the predicate.
  • List.divideList Search a list for items that satisfy a test predicate (matching items), and then divide that list into parts, such as each part contains one matching item. Except maybe for the first matching item, it will keep the matching items as the first item in each part.
  • List.divideListAsMap searches a list for items that satisfy a test predicate (matching items), and then divide that list into a map of parts, such as each part contains one matching item, and the keys are given by the key function.
  • List.addBetween return a new list, adding a separator between the original list items.
  • List.concat returns an efficient concatenation of up to 5 lists
  • List.splitByLength cuts the original list into one or more lists with at most length items.
  • List.update returns a list where new items are added or updated, by their id.
  • List.distinct removes all duplicates, leaving only the distinct items.
  • List.reversedView returns a list of the objects in this list, in reverse order.

List extensions

  • Set.toggle If the item doesn't exist in the set, add it and return true. Otherwise, if the item already exists in the set, remove it and return false.

Iterator extensions

  • toIterable, toList, toSet, toIList, and toISet convert the iterator into an Iterable, List, Set, IList, and ISet, respectively.

Boolean extensions

  • compareTo makes true > false.

Comparators

  • compareObject
  • compareObjectTo
  • sortBy
  • sortLike
  • if0

This package is brought to you by Philippe Fanaro, and myself, Marcelo Glasberg.

Read more from me:

Layout packages I’ve authored:

Other Flutter packages I’ve authored:

https://github.com/marcglasberg

https://twitter.com/GlasbergMarcelo

https://stackoverflow.com/users/3411681/marcg

Follow Flutter Community on Twitter: https://www.twitter.com/FlutterComm

--

--