I'm having trouble determining the most efficient way of doing this in Dart.

If have two lists that in sorted descending order,

List<int> messages = [10, 5, 4, 1];
List<int> newMessages = [5, 3, 2];

How can I add newMessages to messages so that messages now looks like

messages = [10, 5, 5, 4, 3, 2, 1];

CodePudding user response：

If both lists are long, and are using the default list implementation, it might be more efficient to create a new list based on the two other lists. The reason is that inserting an element inside an existing list requires all elements after this insertion index to be moved forward. Also, when the list grows, it needs to allocate a bigger list and move all elements into this.

If we instead creates a new list, we can inform Dart what the size of this list is going to be exactly and we can prevent moving elements:

void main() {
  List<int> messages = [10, 5, 4, 1];
  List<int> newMessages = [5, 3, 2];

  // The compare argument is given since both lists are sorted in reverse order
  print(newSortedListBasedOnTwoAlreadySortedLists<int>(
      messages, newMessages, (a, b) => b.compareTo(a)));
  // [10, 5, 5, 4, 3, 2, 1]
}

List<E> newSortedListBasedOnTwoAlreadySortedLists<E>(
  List<E> l1,
  List<E> l2, [
  int Function(E a, E b)? compare,
]) {
  Iterator<E> i1 = l1.iterator;
  Iterator<E> i2 = l2.iterator;

  if (!i1.moveNext()) {
    if (!i2.moveNext()) {
      return [];
    } else {
      return l2.toList();
    }
  }

  if (!i2.moveNext()) {
    return l1.toList();
  }

  bool i1alive = true;
  bool i2alive = true;

  return List.generate(l1.length   l2.length, (_) {
    if (i1alive && i2alive) {
      E v1 = i1.current;
      E v2 = i2.current;
      int compareResult = (compare == null)
          ? Comparable.compare(v1 as Comparable, v2 as Comparable)
          : compare(v1, v2);

      if (compareResult > 0) {
        i2alive = i2.moveNext();
        return v2;
      } else {
        i1alive = i1.moveNext();
        return v1;
      }
    } else if (i1alive) {
      E v1 = i1.current;
      i1alive = i1.moveNext();
      return v1;
    } else {
      E v2 = i2.current;
      i2alive = i2.moveNext();
      return v2;
    }
  });
}

Note: The method could in theory take two Iterable as argument as long as we are sure that a call to .length does not have any negative consequences like e.g. need to iterate over the full structure (with e.g. mappings). To prevent this issue, I ended up declaring the method to take List as arguments since we know for sure that .length is not problematic here.

CodePudding user response：

You can use binary search to insert all new messages one by one in a sorted manner while maintaining efficiency.

void main() {
  List<int> messages = [10, 5, 4, 1];
  List<int> newMessages = [5, 3, 2];
  
  for (final newMessage in newMessages) {
    final index = binarySearchIndex(messages, newMessage);
    
    messages.insert(index, newMessage);
  }  
  
  print(messages); // [10, 5, 5, 4, 3, 2, 1]
}

int binarySearchIndex(
  List<int> numList, 
  int value, [
    int? preferredMinIndex, 
    int? preferredMaxIndex,
  ]) {
  
  final minIndex = preferredMinIndex ?? 0;
  final maxIndex = preferredMaxIndex ?? numList.length - 1;
  
  final middleIndex = ((maxIndex - minIndex) / 2).floor()   minIndex;

  final comparator = numList[middleIndex];
  
  if (middleIndex == minIndex) {
    return comparator > value ? maxIndex : minIndex;
  }
  
  return comparator > value ?
     binarySearchIndex(numList, value, middleIndex, maxIndex):
     binarySearchIndex(numList, value, minIndex, middleIndex);
}

CodePudding user response：

This sounds like you need to merge the two lists. As stated elsewhere, it's more efficient to create a new list than to move elements around inside the existing lists.

The merge can be written fairly simply:

/// Merges two sorted lists.
///
/// The lists must be ordered in increasing order according to [compare].
/// 
/// Returns a new list containing the elements of both [first] and [second]
/// in increasing order according to [compare].
List<T> merge<T>(List<T> first, List<T> second, int Function(T, T) compare) {
  var result = <T>[];
  var i = 0;
  var j = 0;
  while (i < first.length && j < second.length) {
    var a = first[i];
    var b = second[j];
    if (compare(a, b) <= 0) {
      result.add(a);
      i  ;
    } else {
      result.add(b);
      j  ;
    }
  }
  while (i < first.length) {
    result.add(first[i  ]);
  }
  while (j < second.length) {
    result.add(second[j  ]);
  }
  return result;
}

(In this case, the lists are descending, so they'll need a compare function which reverses the order, like (a, b) => b.compareTo(a))

CodePudding user response：

void main() {
  List<int> messages = [10, 5, 4, 1];
  List<int> newMessages = [5, 3, 2];
  
  messages = [...messages, ...newMessages]..sort((b, a) => a.compareTo(b));
  print(messages); // [10, 5, 5, 4, 3, 2, 1]
}