How do we add an item after/before another item or at a specified index of the collection?

[niieani]

Imagine a chat app which implements offline support:

• you can "send" messages and they're added to the queue and shown immediately (optimistic updates)
• when the client reconnects, it pulls messages that were sent by others: the Date of their messages can thus be before the messages the user has sent out
• we need to place those messages at their appropriate places in the list (e.g. in the middle), not append them.

This is just one use case, but there are many others (like reordering lists, where you'd need to remove an item and re-add it in a different place). I'd imagine a lot of the times you don't know the index and you'd actually need to find after/before which specific item you want your new item to appear with some sort of a search function.

Not sure how a pure/functional API would look like for this case, but if it were a classic mutable state, it'd be something like:

collection.addAfter(newItem, item => item.date < newItem.date)

This would iterate on all the elements until the return value of the search is false, then insert the new item at the index of the first item that returned false.

How can we deal with this case using cycle-collection?

[Hypnosphi]

I think that allowing users to set the item's id manually would really help here.

What you can do now are some hacks like reimplementing the Collection.Pluck method to sort the items before rendering:

function pluckWithSorting (collection$, sinkProperty, sortProperty) {
  const sinks = {};

  function sink$ (item) {
    const key = `${item.name}.${item.id}.${sinkProperty}`;

    if (sinks[key] === undefined) {
      if (sinkProperty === 'DOM') {
        sinks[key] = item[sinkProperty].map(vtree => ({...vtree, key})).remember();
      } else {
        sinks[key] = item[sinkProperty].remember();
      }
    }

    return sinks[key];
  }

  return collection$
    .map(collection => collection.asArray()
        .sort(fst, snd => fst[sortProperty] - snd[sortProperty])
        .map(item => sink$(item)))
    .map(sinkStreams => xs.combine((...items) => items, ...sinkStreams))
    .flatten()
    .startWith([]);

But this shouldn't be really performant as your collection size grows. Alternatively, you can use flexbox with CSS order property for visual rearrangement.

[niieani]

@Hypnosphi Unfortunately flexbox ordering would be a hack not a solution - it would work only if the output is the DOM. If we'd like to use collections as sinks for other drivers, like Canvas, SVG, Audio or anything else for that matter, there usually won't be any equivalent hack available. And as you say, sorting as a post-processing of the stream will incur bad performance, as it would be invoked every time the collection changes. Its better to do it once, as pre-processing of the stream, before adding the new item.

[Hypnosphi]

Btw, unrelated to this repository, API like collection.addAfter(newItem, compareFunction) could as well be a pure/non-mutating inside:

  addAfter(newItem, compareFunction) {
    let index = this.findIndex(item => !compareFunction(item, newItem));
    return this.slice().splice(index, 0, newItem);
  }

[Widdershin]

I have a weird thought. It's a common pattern that you want to apply a sort order to a collection. It's one thing to manually maintain a sort order by inserting at indexes, but what if we provided a collection.sort(compareFunction) that returned the collection sorted for pluck and asArray().

Now the trick part is that often you want to sort on an observable, right? I think the default case should be a reactive sort. So the signature would actually look like collection.sort(sinkName, compareFunction). We could also support sorting on multiple sinks.

What do y'all think?

[Hypnosphi]

This would be post-processing again. What niieani wants is to have some kind of addSorted(compareFunction), but I think it would be even better to have Collection(Item, sources, compareFunction) and always insert items in an order. In that case we can be more effective by using binary search, as we know that collection is always sorted.

[niieani]

@Hypnosphi this indeed makes a lot of sense! Passing a sorting function to the collection definition would ensure the collection is always sorted - there's something so lovably "functional" about that notion. I suppose this will be the most common case.

@Widdershin's proposition seems good too, for other use-cases - it could be that we want to sort a list "onClick" - or even to sort it differently on different observables (e.g. sortable DataGrid / Excel). So both features would be welcome additions.

[Widdershin]

It's a common use case that a user wants to be able to change the sorting of a collection after creation. If we use collection.sort(propertyName, compareFunction) then it can be changed inside of a fold. It also means you can sort the same collection in different ways and have them act as a view.

My problem with the non-reactive approach is what are you actually sorting on? If you're sorting on the properties of your items, it's convention for those to be Observable. And then the return value from that compareFunction would be observable. And since it would be nice to access the actual value in the sink, we want something like pluck with a compareFunction on top.

As for the whole optimization thing, I wonder if we can cross that bridge when we come to it. Who knows how fast xstream works out to be in practice? This might be a good test.

[niieani]

@Widdershin Are you saying that static data which comes from the server should be, as a convention, converted to Observables of Observables? Why? Is there any benefit in doing so if any updates to the data come in the form of new objects altogether? I get that xstream might be fast, but that's still not the point - and that is: redundant computation. To me, this is just something that goes against the whole philosophy of functional programming, or Cycle.js. Thinking of workarounds to the problem instead of real solutions is the reason traditional state management techniques are the mess they are to work with. I really hope there's an elegant way to solve this.

[Hypnosphi]

Items in a collection must have some static key anyway. Currently it's auto-generated but it could be provided by user as well. It's sorting by key what can be done instantly. All the sortings by dynamic properties should be done on the view stage, off course.

[Hypnosphi]

Is there any benefit in doing so if any updates to the data come in the form of new objects altogether?

You just turn the sequence of each item's states into a separate stream by mapping over a responses stream. You should do that if you want reactive updates.

[Widdershin]

All the sortings by dynamic properties should be done on the view stage, off course.

Totally with you now, all "reactive" sorting should be done on top of pluck.

I'm still not clear what exactly we would be sorting on for the sort on addition style.

Could someone provide a real world example?

I'm fine with the notion of providing a compareFunction when creating the collection, but as far I can see that would require the user to provide a key when adding an item. Is that what y'all are after?

[Hypnosphi]

Yes, it is. In the original case of messages timestamp would be the key. It's safe, as it doesn't seem to change in the future. You may be able to remove or even edit your messages, but not to change the sending time =)

[Widdershin]

@niieani: have you had the chance to try out Collection.gather? Does it solve your use case?

[niieani]

@Whiddershin How do you control the position of the added items with gather?

[Widdershin]

Hmmm, @Hypnosphi, is this possible? Or are we missing a sort on idAttribute inside of gather?

[Hypnosphi]

I'm open to adding that, but not really sure that it can be done solely inside of gather. Collection should accept a custom id in add$ for implementing that.

[niieani]

Sorting shouldn't be done on the idAttribute, but on an arbitrary attribute. A chat can receive 2 messages at exactly the same time and thus time cannot always be used as the ID.

[Hypnosphi]

Sounds reasonable, but that attribute should anyway be static (plain value, not stream). Otherwise post-processing is cheaper. And currently gather has no support of static values except for idAttribute.

[TylorS]

I'm not really well versed in the internals of this library, but for whatever its worth, I'd think using idAttribute should be fine. Theoretically events could happen at exactly the same time, but in reality even 1 millisecond difference is going to have have 2 events processed one after the other. Javascript especially doesn't really do any 2 things at the exact same time.

Feel free to tell me I'm wrong, I probably am :)

[atomrc]

Hi guys, any updates on that matter? I feel like sorting is an important subject, am I wrong?

I am using a collection created via gather and my first intuition was that the order of the elements displayed would follow the order of the elements inside the elements$ stream given to the gather method (given I create my collection this way Collection.gather(Cmp, sources, elements$, "id"))

I am actually not sure why this behavior is not the default behavior (given that the first rendering is following the array's order).

I might be doing things wrong here, but right now I don't really know how to sort the elements I add to my collection :(

[FeliciousX]

@atomrc I just faced this exact same issue. I use gather and when I change the order of the array in the observable ( 3rd param ) it doesn't sort ! Hmm

[Widdershin]

Just coming back to this now:

Seems like there are really two issues here.

One is that we want to be able to sort all items inserted into the collection (including via gather), and it should be efficient. Let's call this insertion sort.

Secondly, we want to be able to control the sort order of our items in response to their data changing. For .gather(), it would make sense to be able to control this using the order of items in the incoming array, as then we could .sort that array. Let's term this reactive sort.

My proposal for insertion sorting is to allow collection/gather to take a comparator function to using binary sort to insert new items. This could only operate on static data in the sources, not anything wrapped in an Observable. To that end, we can use my friend Roger's newly published library, sorted-immutable-list.

I think we should make a new issue to discuss potential solutions for "reactive sort". I like the idea of respecting the order of the incoming stream of objects, but it seems trickier to implement so I would like to think it through.

What say you @niieani @Hypnosphi @atomrc @FeliciousX? Would a binary insertion sort on non-observable data (ids and timestamps etc) solve your usecases?

[niieani]

As long as the insertion sort method is configurable, the proposed solution should be fine.