How to get the last N objects before a certain object in a Javascript array?

Question

I'm trying to implement the endless loading of items in Javascript. Like the effect you get when you scroll through your messages in your favorite messaging application. I have a big array like this (+1000 objects):

var array = [
    { id : 1, text: "First"},
    { id : 2, text: "Second"},
    { id : 3, text: "Third"},
    { id : 4, text: "Forth"},
    { id : 5, text: "Fifth"},
    { id : 6, text: "Sixth"},
    { id : 7, text: "Seventh"},
    ...
];

Now I want to load only 10 items at a time. For example I'm showing only the items with the id of 30 to 39. Now the user wants to see the items before 30. What is the best way to select last 10 items before that object with the id of 30? As mentioned before, the array's size is big so performance does matter here.

EDIT

The example above is just one case. I should be able to filter my array 10 items at a time as many times as needed.

What I'm trying to achieve is loading a big array but not all at once. I want to load 10 items at a time. I'm keeping track of the first object in my filtered array (e.g 30) and then I want to get the last 10 objects before that particular object.

EDIT 2

This is my View:

<div ng-repeat="message in messages" class="message-wrapper">
     // Show content of message 
</div>

Now initially i'm showing the last 10 items in messages

$scope.init = function(){        
    var messages = Database.AllMessages(); // This function returns all my messages
    $scope.messages =  messages.length > 10 ? messages.slice(-10) : messages;        
}

Now let's say the items returned by this function are the items with the Id of 30 to 39. The user scrolls up and wants to see the messages prior to 30. So how can i filter the whole array returned by AllMessages() to get 10 last items before the 30 message?

Thanks in advance for any insights.

Could you share the html you are using to show the items? Are you using any framework like JQuery or AngularJS ? — www.admiraalit.nl
– www.admiraalit.nl, Commented Nov 14, 2015 at 11:33
You need a better data structure, what you are using currently is not query-able. If id is the only other field, why not just make it an array of text. Also it would be better to tell the exact use case. — nyumerics
– nyumerics, Commented Nov 14, 2015 at 11:40
Perhaps you are looking for some sort of algorithm to do so. Have you tried anything that I can take a look on. Try adding some code or logic which can help others to understand. — ashishraaj
– ashishraaj, Commented Nov 14, 2015 at 11:41
@JossefHarush, no. But Id is always numerical and it's sorted like in the example. — Sobhan
– Sobhan, Commented Nov 14, 2015 at 11:44

Kvam · Accepted Answer · 2015-11-14 12:35:44Z

You want to query your data source as efficient as possible. Make sure the array is sorted by id first:

array.sort(function(a, b) {
  if (a.id === b.id) return 0;
  if (a.id > b.id) return 1;
  return -1;
});

Then, binary search can be performed to find the index of the element you're looking for:

var search = function(arr, val) {
    if (arr.length === 0) {
        return -1;
    }

    var max = arr.length - 1, min = 0;

    while (max !== min) {
        var index = Math.floor((max + min) / 2);

        if (arr[index].id === val) {
            return index;
        }
        else if (arr[index].id < val) {
            min = index;
        }
        else {
            max = index;
        }
    }
    return arr[index].id === val ? index : -1;
}

// find index of element with desired id.
var index = search(array, 30);

Once we know the index, we simply have to select the elements before/after the index:

var rangeMin = index - 10; // Inclusive. 10 is the maximum number of elements you want to render.
var rangeMax = index; // Not inclusive.

if (rangeMin < 0) { rangeMin = 0; }
if (rangeMax > array.length) { rangeMax = array.length; }

var elementsToRender = array.slice(rangeMin, rangeMax);

elementsToRender will now contain all the elements you want to render.

www.admiraalit.nl · Accepted Answer · 2015-11-15 19:21:18Z

1

Now let's say the items returned by this function are the items with the Id of 30 to 39. The user scrolls up and wants to see the messages prior to 30. So how can i filter the whole array returned by AllMessages() to get 10 last items before the 30 message?

(...) my view should show the items 20 to 39

Suppose allMessages contains all messages (very large array).
Suppose ctrl is a controller instance
Suppose ctrl.messages contains the items currently displayed.
Suppose currentIndex is 30
Suppose stepSize is 10
Then the following code will extend messages to contain items 20 to 39 and will set currentIndex to 20:

currentIndex -= stepSize; // the new first message will have index 20
var extraItems = allMessages.slice(currentIndex, currentIndex+stepSize);
Array.prototype.push.apply(extraItems, ctrl.messages); // append ctrl.messages to extraItems
ctrl.messages = extraItems;

For more information about Array.prototype.push.apply, see Mozilla (scroll down to 'Merging two arrays').

Here is small app to demonstrate it (you'll have to add logic to protect the user to cross the array boundaries):

<html>
<head>
    <script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.4.2/angular.min.js"></script>
    <script>
        var myApp = angular.module('myApp', []);

        myApp.controller('MyController', function() {
            var ctrl = this;
            var allMessages = Database.AllMessages();
            var stepSize = 10;
            var currentIndex = allMessages.length - stepSize;

            // show the last 10 messages
            ctrl.messages = allMessages.length > 10 ? allMessages.slice(-10) : allMessages;

            // show ten more messages
            ctrl.showMore = function () {
                currentIndex -= stepSize;
                var extraItems = allMessages.slice(currentIndex, currentIndex+stepSize);
                Array.prototype.push.apply(extraItems, ctrl.messages);
                ctrl.messages = extraItems;
            };
        });
    </script>
</head>
<body ng-app="myApp">

<div ng-controller="MyController as ctrl">
    <table>
        <tr ng-repeat="message in ctrl.messages"><td>{{message.text}}</td></tr>
    </table>
    <button ng-click="ctrl.showMore();">show more</button>
</div>
</body>
</html>

edited Nov 15, 2015 at 19:21

answered Nov 14, 2015 at 20:03

www.admiraalit.nl

6,1331 gold badge23 silver badges37 bronze badges

2 Comments

Sobhan Over a year ago

The messages' id are not always the same as their index in the allMessages array. but they are always numerical and they are sorted.

www.admiraalit.nl Over a year ago

Allright, but what is the impact of these ids on the solution? I have edited the app to first show the last 10 messages and then offer a button 'show more' to let the user request for 10 more messages. Is this the behavior you are looking for, or otherwise, please describe how the desired behavior differs from the app I have posted.

Haring10 · Accepted Answer · 2015-11-14 11:45:52Z

0

You can try this to get the object with id 30 without a loop using the following code:

var array = [
        { id : 1, text: "First"},
        { id : 2, text: "Second"},
        { id : 3, text: "Third"},
        { id : 4, text: "Forth"},
        { id : 5, text: "Fifth"},
        { id : 6, text: "Sixth"},
        { id : 7, text: "Seventh"}
    ];  

    var result = $.grep(array, function(e){ return e.id == 5; });
    console.log(result);

answered Nov 14, 2015 at 11:45

Haring10

1,5571 gold badge19 silver badges39 bronze badges

Comments

sebilasse · Accepted Answer · 2015-11-14 12:40:04Z

0

What is the best way to select last 10 items before that object with the id of 30?

var index = 30;
var count = 10;
// 10 items before 30 :
array.slice(index-count, index);

answered Nov 14, 2015 at 12:40

sebilasse

4,6662 gold badges41 silver badges36 bronze badges

Comments

Donnie D'Amato · Accepted Answer · 2015-11-15 19:37:02Z

I knew this thing I made could be helpful to somebody. Here's the relevant piece:

$('button.getResult').on('click', function(e) {
  e.preventDefault();
  var limit = $('input.getResult').val();
  if (limit != '' && !isNaN(limit)) {
    var dots = $('ul li');
    if (dots.length > limit) {
      //show the limit as group
      var foundSelected = false;
      var counter = 0;
      for (var i = dots.length - 1; i >= 0; i--) {

        dots.eq(i).addClass('group');
        dots.eq(i + parseInt(limit)).removeClass('group');
        counter++;
        if (i == $('li.selected').index()) {
          foundSelected = true;
        };
        if (foundSelected && counter >= limit) {
          i = -1;
        };

      };
    } else {
      //show all as group
      dots.addClass('group');
    };
  };
  return false;
});

dots is basically your array and the first conditional is just checking to make sure the number of results you want is smaller than the length of the array. Then a loop is performed through the array (backwards in my case) checking for the important item. If I find it, I change the boolean to true.

Additionally, I mark each as selected as I iterate and if the selected index is outside of the limit of pagination, then I remove the selected mark (to keep the pagination). Once I've both found the important item and have marked the correct number of items past the important one, I stop the loop.

Of course, you might not be able to mark things in your case but I figure you could look at this for some inspiration.

Collectives™ on Stack Overflow

How to get the last N objects before a certain object in a Javascript array?

EDIT

EDIT 2

5 Answers 5

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

EDIT

EDIT 2

5 Answers 5

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related