google / built_collection.dart Goto Github PK

We can just do "if (T == dynamic)" to check for the dynamic type.

Hi,
can you please increase the dependencies of this lib to support quiver 0.26.0, in order to be able to use this package in the latest master of Flutter?

Thanks a lot

Currently BuiltSet and BuiltMap use Dart's default Set and Map collections, that are not efficient in inserting or deletion large amounts of data. I would like to have ability to specify underlying Set and Map collection implementation, at least as a bool flag to use HashSet and HashMap. Another option would be to use HashSet and HashMap as default backend for those collections. What do you think about it?

Stable means that the return values are identical for all calls. Otherwise, the methods can't be used in Angular.Dart expressions.

We should have an addIterable method that's like fromIterable on Map: takes an iterable and key and value functions.

The documentation of the BuiltSet states that "It preserves iteration order."

It wasn't clear to me that this means/implies that the iteration order is the insertion order. Could this be made clearer in the documentation?

The types are private to the SDK but we may be able to detect them using runtimeType.

Then, we can avoid copying where possible.

Right now, you have to click and follow the Medium link to see some code examples. It might be a faster pitch to include some of the API usage in the README.md for everyone to see. (Some other packages I've seen seem to follow this pattern.)

Using map on a built collection in strong mode produces a warning. For example,
BuiltSet is = new BuiltSet(const [1, 2, 3]);
Iterable ss = is.map((i) => '$i');
produces
Unsound implicit cast from Iterable to Iterable

This can be fixed by changing BuiltSet.map from
Iterable map(f(E element)) => set.map(f);
to
Iterable// map//(/=T_/ f(E e)) => _set.map(f);
as in the built-in Iterable: https://github.com/dart-lang/sdk/blob/master/sdk/lib/core/iterable.dart#L159

I'm working on a patch to fix this across built_collection.

-- hcameron@

e.g. in BuiltList

ListBuilder toBuilder();

should be

ListBuilder<E> toBuilder();

And .where allocates a new Set, whereas .retainWhere works in-place. :)

Some comments/strings are too long.

It should delegate to List.toString() just like BuiltList does.

adding built_collection: 1.3.0 caused

< observable 0.14.0+1 (was 0.20.4) (0.20.4 available)

From google/built_value.dart#155

Any concern about support package:collection's Equality class, optionally?

I have some use cases where I'd like to use BuiltCollection(s), but the keys I don't have control over and don't really want to write wrapper objects just to change the identity.

If you're OK, I can send PRs. :)

Sometimes you do need getters to be able to do inline updates.

The same getters as List/Map/Set/etc should be provided, but without implementing List/Map/Set/Iterable, to prevent builders accidentally being used in place of mutable collections.

B extends A.
If we have a BuiltList<B> but we need it as a BuiltList<A>, we currently need to create a copy of the list.
new BuiltList<A>() should be able to reuse the underlying list and without checking the type of each element.

currently the built collections don't have a toJson() the method which means JSON.encode() won't handle them.

Possible performance improvement: if two collections compare equal, they could then drop one of the equal underlying lists and both point to the same one. This can be used to do faster equality checks later, and will save space.

The comment-based generics syntax will be removed from the Dart SDK tools (like DDC, analyzer) "soon." dart-lang/sdk#28796

Such syntax (like in map) needs to be updated, and the minimum Dart SDK in pubspec.yaml needs to be bumped to 1.21, when the non-comment-based syntax was introduced.

Immutable data structure suggestion:

In general, for an immutable tree, one can perform a "mutation" to any node in the graph in O(depth). Assuming the tree is roughly balanced, this ends up being O(lg(N)) were N is the total number of items in the tree. The "mutation" of course, is only seen in the newly returned tree. Original tree is unchanged. But they share as much structure as possible, to save time and space. This is the typical strategy for all languages that have immutable data structures.

For example, in Clojure, all of their immutable data structures took great pains to get efficient performance on changes. The array-like type used something like a B-tree with 32 as the branching factor. So for example, you can "mutate" a 1000 element array and it only rewrites 2 little Java arrays. (Disclaimer: it was like 5 yrs ago when I last looked, details may have changed.)

Similarly it would be possible to have BuiltMap that supports "mutation", returning a new BuiltMap that shares almost all of the structure with the original map.

Anyway, the reason I bring this up, I've seen a lot of folks use BuiltList/BuiltMap like:

void addItem(Item item) {
  _myBuiltList = _myBuiltList.rebuild((b) => b.add(item));
}

(edit: fixed example to make more sense)

That can easily lead to quadratic code. If you call addItem N times, your calling code will be O(N^2). At least this is what I gathered from reading the current implementation code for BuiltList/Map--that rebuild is O(N).

Anyway if this sounds like I good idea, I might try and prototype something, but I wanted to file this first to check my understanding. (p.s. <3 immutable data structures. this package is super useful.)

ListBuilder could for example have a "builtAt" method that converts the value at the specified index to a builder, similar to the "rebuild" method but for an element in the collection:

var list = new BuiltList<BuiltList>([new BuiltList[1]]);
var rebuiltList = list.rebuild((b) => b.rebuildAt(0).add(2));

--> [[1, 2]]

This should work for nested built collections and for built values.

${key} instead of ${element}

Comparing two maps of same size, same hash code, different key type throws when trying to look up values to compare them because of differing key type.

UnusedClass is not needed (and the current code fails for e.g. BuiltList).

Instead we could use CheckNotDynamic:

import 'package:unittest/unittest.dart';

class CheckNotDynamic<T> {
  CheckNotDynamic() {
    if (isDynamic) {
      throw new UnsupportedError('explicit element type required');
    }
  }

  bool get isDynamic => null is T && T != Object;
}

class IsDynamic<T> {
  bool isDynamic() => null is T && T != Object;
}

void main() {
  new CheckNotDynamic<Type>();
  new CheckNotDynamic<String>();
  new CheckNotDynamic<Object>();

  expect(new IsDynamic<Type>().isDynamic(), false);
  expect(new IsDynamic<String>().isDynamic(), false);
  expect(new IsDynamic<Object>().isDynamic(), false);

  expect(new IsDynamic().isDynamic(), true);
  expect(new IsDynamic<dynamic>().isDynamic(), true);
}

I like this library, but one thing stopping me from using it is that I don't want to require other users to use built_collection, so I tend to only use it as an implementation detail and pass a toList/toMap/toSet as part of my API.

I would use asList/Map/Set, where they could be, for example:

List<T> asList() => new List<T>.unmodifiable(_backingList);

By wrapping in a new class we can provide extra utility methods, e.g. toBuiltList, toBuiltSet.

This will be helpful for the "map" method on built collections, to allow you to map then convert immediately into another built collection.

How do I add an element to a contained BuiltSet?

MapBuilder does not allow me to retrieve elements and update them. Why is there no operator []?

Ideally, there was special casing for keys and values of BuiltMap such that toBuilder returned MapBuilder<String, ListBuilder> in this case.

What's a good workaround?

Right now, I've only been able to come up with:

BuiltMap<String, BuiltSet<String>> setMap;
String key, value;

setMap = setMap.rebuild((b) => 
    b[key] = (setMap[key] ?? new BuiltSet<String>()).rebuild((b) => b.add(value)));

Thanks,
Andreas

Repeated calling of listBuilder.build() should return the same BuiltList.

Same for BuiltSet and BuiltMap.

The interface claims they support Object, but the implementation assumes they are of Key type.

I went through the BuiltList implementation and I assume the concept is the same for every built collection type. This is only an educated guess. In either case, what I saw in BuiltList can be found here: https://github.com/google/built_collection.dart/blob/f91f2307a919f3675f23cff8fef9be8daa9174bf/lib/src/list/built_list.dart#L65-74

Let's assume the following:
We create two BuiltList<String> collection instances. Both have got the same strings in it.

var al = new BuiltList<String>([ 'a', 'b' ]);
var bl = new BuiltList<String>([ 'a', 'b' ]);

We know that strings are always going to be equal if they are built up of the same code units. It's hashing algorithm will take that into account.

var a = 'a'; 
var b = 'a';
print('${a.hashCode == b.hashCode && a == b}'); // true

Since BuiltList combines the hashCodes of it's members, the hashCode of 2 BuiltList instances are going to be equal if their members have the same hashCodes.

var aa = [ 'a', 'b' ];
var bb = [ 'a', 'b' ];
print("${quiver.hashObjects( aa ) == quiver.hashObjects( bb )} "); // true

It stands to reason in such situations, a simple hashCode comparison would be sufficient to reliably determine if our 2 BuiltList instances are made up of the same strings without having to iterate over them and do all those extra steps.

bool opreator==(other) {
    return other is BuiltList && other.hashCode == hashCode;
}

Question: what am I missing, why the seemingly wasteful algorithm for comparison?

Currently Set.intersection takes another Set, which means you can't intersect with something that might contain non-E elements. Should it take Set instead?

e.g. CopyOnWriteList.takeWhile returns Iterable instead of Iterable.

It seems like MapBuilder only supports setting values, not getting them. My scenario is that I am using a MapBuilder<String, List<Foo>>. I have a loop where for each iteration the List for a particular String key in the map may be added to for a particular key in the map. I tried something like this but it does not seem to work since I cannot fetch the value for the key.

   var builder = new MapBuilder<String, List<Foo>>();
   for (Bar bar in bars) {
      var list = builder[bar.name]; // This line fails
      if(list == null) {
       list = new List<Foo>();
       builder[bar.name] = list;
      }
      list.add(bar.foos);
    }

Is there some other way to solve this scenario? I could use a regular Map in the loop and then create the MapBuilder from that, but I feel that would defeat the purpose of a MapBuilder :-).

B extends A

listB = new BuiltList<B>();
listA = new BuiltList<A>(listB);

In this case listA has the same runtime type as listB because listA is BuiltList<B> evaluates to true in the copy constructor of BuiltList. This later causes problems when trying to rebuild listA with new elements of type A.

I have written a class Superset that implements all methods of BuiltSet. I would like to actually write implements BuiltSet (for the static analysis hints during development), but that would break this line in your code.

Related(?) issue: dart-lang/site-www#382

Btw: I can contribute a pull request for this (and the other issues I opened recently). I guess you assign yourself to an issue if you started working on it?

Some operations do not check types if checked mode is turned off, e.g.

new BuiltList(['string'])

per the Built Collection docs they should always check types.

SetBuilder and ListBuilder will throw an ArgumentError, but not reset their internal state.