Find or Select by Row Entity's 'ID'

[nkoterba]

Our dataset, as I'm sure many others also use, has an ID for records, let's call this field: id

In our web application, instead of passing around entire entities, we just pass the ids of these records.

NOTE: Our grids do not display the ID column so our columnDefs does not include this column. Perhaps including this column and making the column hidden would allow faster selection/searching? But then we are also adding potentially many unnecessary DOM elements to the GRID.

What's the most efficient way to find a grid row for selection using an id.

The only way I can think of achieving this is by:

1. Iterate through $scope.gridOptions.data looking for item
2. Call $scope.gridApi.selection.selectRow(rowEntity, event) passing in item found in step 1 for rowEntity.

However, I'm not sure if there's a more efficient way (using grid hashing maybe)?

In some instances, I get an array of IDs to select. So I would have to loop through the above pseudo-code for each ID in IDs, which would create an O(n^2) operation. I was hoping there would be something more performant.

[nkoterba]

I'm further elaborating on this, because the current Ui-Grid select/deselect functions cause even more performance issues than initially thought.

My use case is the same as above:

1. I get an array of IDs I need to select in grid
2. Since UI-Grid doesn't contain a selectRows method, I must iterate through gridOptions.data for each Entity.
3. I then call gridApi.selection.selectRow(entity) if my entity's ID is contained in the array of IDs from step 1
4. Internally gridApi.selection.selectRow(entity) calls: var row = grid.getRow(rowEntity) which is adding yet another loop (https://github.com/angular-ui/ui-grid/blob/9c256bf/src/features/selection/js/selection.js#L178)

So on a grid of say 115,000 rows, I'm now running an O(n^3) operation.

I discovered the uiGridSelectionService.toggleRowSelection which slightly improves things, because instead of calling selectRow or unselectRow directly, which adds the third loop, I can call toggleRowSelection.

So now I'm at O(n^2) for 115,000 rows, which still hangs browser.

Which led me to a solution that does indeed work.

The internal grid.getRow method makes use of the rowEquality function: (https://github.com/angular-ui/ui-grid/blob/9c256bf/src/js/core/factories/Grid.js#L1056)

Grid.prototype.getRow = function getRow(rowEntity, lookInRows) {
    var self = this;

    lookInRows = typeof(lookInRows) === 'undefined' ? self.rows : lookInRows;

    var rows = lookInRows.filter(function (row) {
      return self.options.rowEquality(row.entity, rowEntity);
    });
    return rows.length > 0 ? rows[0] : null;
  };

By overriding the rowEquality function I can trick the grid into finding rows based on some entity property versus an entity themselves. So here's my gridOptions.rowEquality override:

rowEquality: function (entityA, entityB) {
                    var aId = angular.isObject(entityA) ? entityA.id : entityA;
                    var bId = angular.isObject(entityB) ? entityB.id : entityB;

                    return aId === bId;
                },

In short, if entityA and entityB are both objects, assume they have an id property otherwise assume they are the actual id.

My selectRows function now becomes:

function selectRows(rowIds) {
       gridApi.selection.clearSelectedRows();  // Necessary to clear any existing selection; O(n) operation

    rowIds.forEach(function(id) {
        var row = vm.gridApi.selection.selectRow(id);  // O(n^2) due to getRow inside selectRow
    });
}

As long as rowIds is a small size, this runs relatively well (much better than my O(n^3)).

However, it would be really, really, really nice if UI-Grid supported the following functions:

gridApi.selection.selectRows(rowIds, objectIdProperty, event)
gridApi.selection.unselectRows(rowIds, objectIdProperty, event)

// where objectIdProperty is in my case 'id'

So I didn't have to hack the rowEquality override. The functions could iterate each rowId but instead of calling grid.getRow just iterate over the existing rows, checking each row's objectIdProperty and see it matches rowId and if so, select it.

I would also suggest the following function:

gridApi.selection.selectOnlyRows(rowIds, objectIdProperty, event)

This function like the two suggested above, would iterate over all existing rows, but would make sure that any rows not in rowIds would set isSelected = false because right now gridApi.selection.selectRow doesn't clear any existing selection (or maybe add a boolean flag to selectRows above to clear any existing selection).

This third function would reduce selection complexity from O(n) + O(n^2) to just O(n^2) because we wouldn't need that initial clear function/loop.

None of the above actually addresses my initial issue/question which is if it's possible to select/unselect rows WITH an id and not with the rowEntity itself. I've achieved this by overriding the rowEquality callback/function, but wondering if there's a better way...

Ideally, it would be nice to get selectRows(rowIds) and have it execute in < O(n^2) though I'm not sure that's possible without sorting both arrays first and/or using a hash map/lookup.

[nkoterba]

For those who might stumble across this issue, I found a very good solution performance wise.

Assume you have a array of row IDs that you want to select, called selectedIds. I'm using Lodash to create a lookup hash (for performance), but in general this code should be O(2n) which is much better than my previous attempts. It doesn't use any of the public GridAPI which means it doesn't provide the same functionality. Ideally, a method selectRows would be added to the public GridApi.

Here's the code:

// Make things super performant by creating a hash of ids
                var idLookup = _.indexBy(selectedIds);

                vm.gridApi.grid.rows.forEach(function(row) {
                    if (idLookup[row.entity.id])
                        row.setSelected(true);
                    else
                        row.setSelected(false);
                });

WARNING: This logic fails to:

• Broadcast any selection events
• Update the selectAll property
• Only selects the row ids passed in; all other rows are deselected (thus, it's not a additive selection)

because I'm using internal grid methods and iteration.

[daenuprobst]

If anyone else stumbles upon this. _.indexBy was renamed to ._keyBy.
lodash/lodash#1840

[aih]

@nkoterba, any update on whether this has been implemented in uiGrid or if there is a patch to implement it? Selecting by id is exactly my use case.