Scala & Java: Merge K Sorted List


Recently I started to learn Scala, and the best way to learn a new language is to write code to resolve real problem.

So here is my code to use Scala for the classic algorithm question: merge K stored list.
The code works, but as I am just a beginner in Scala, it doesn't use Scala's full power or features - I just translated my Java version to Scala.

Scala Code: Merge K Sorted List
As the list can be ArrayList or linkedList, so we use Iterator to check whether it still has elements and get next element.
package org.lifelongprogrammer.scala.algorithms

import scala.collection.mutable
import scala.collection.mutable.PriorityQueue
object MergeKArrays {
  case class Element[E <: Comparable[E]](var value: E, iterator: Iterator[E]) extends Ordered[Element[E]] {
    def compare(that: Element[E]) = that.value.compareTo(this.value)
  }
  def merge[E <: Comparable[E]](lists: List[List[E]]): List[E] =
    {
      if (lists == null || lists.isEmpty)
        return List[E]();

      val pq = new PriorityQueue[Element[E]]()

      for (list <- lists) {
        if (list != null && !list.isEmpty) {
          val it = list.iterator;
          pq.enqueue(Element(it.next, it))
        }
      }

      val result = mutable.ListBuffer[E]();
      while (pq.size > 1) {
        val first = pq.dequeue;
        result.append(first.value)

        val it = first.iterator;
        if (it.hasNext) {
          // reuse first element
          first.value = it.next;
          pq.enqueue(first)
        }
      }

      if (!pq.isEmpty) {
        val first = pq.dequeue;
        result.append(first.value);

        val it = first.iterator;
        while (it.hasNext) {
          result.append(it.next);
        }
      }
      return result.toList;
    }

  def main(args: Array[String]) {
    val lists: List[List[Integer]] = List(List(1, 3, 5), List(2, 4, 6, 8))
    val result = merge(lists);
    print(result)
  }
}
Java: Merge K Sorted List
Here is my Java code:
package org.codeexample.algorithms;
public class MergeKArray {

 private static class Element<E extends Comparable<E>> implements
   Comparable<Element<E>> {
  private E value;
  private Iterator<E> iterator;
  @Override
  public int compareTo(Element<E> o) {
   return this.value.compareTo(o.value);
  }
 }
 /**
  * Preconditions: List can't contain null
  */
 public static <E extends Comparable<E>> List<E> merge(List<List<E>> lists) {
  if (lists == null || lists.isEmpty())
   return new ArrayList<>();

  PriorityQueue<Element<E>> pq = new PriorityQueue<>(lists.size()
  // ,new ElementComparator<E>() // or use external comparator
  );

  int allSize = 0;
  for (List<E> list : lists) {
   if (list != null && !list.isEmpty()) {
    Element<E> e = new Element<>();
    e.iterator = list.iterator();
    e.value = e.iterator.next();
    assert e.value != null;
    pq.add(e);

    allSize += list.size();
   }
  }
  List<E> result = new ArrayList<>(allSize);

  while (pq.size() > 1) {
   Element<E> e = pq.poll();
   assert e.value != null;
   result.add(e.value);
   Iterator<E> iterator = e.iterator;
   if (iterator.hasNext()) {
    e.value = iterator.next();
    assert e.value != null;
    pq.add(e);
   }
  }

  if (!pq.isEmpty()) {
   Element<E> e = pq.poll();
   result.add(e.value);
   while (e.iterator.hasNext()) {
    result.add(e.iterator.next());
   }
  }
  return result;
 }

 private static class ElementComparator<E extends Comparable<E>> implements
   Comparator<Element<E>> {
  public int compare(Element<E> o1, Element<E> o2) {
   return o1.value.compareTo(o2.value);
  }
 }

 public static void main(String[] args) {
  List<List<Integer>> lists = new ArrayList<>();
  lists.add(Arrays.asList(1, 3, 5));
  lists.add(Arrays.asList(2, 4, 6, 8));
  lists.add(Arrays.asList(0, 10, 13, 15));
  System.out.println(merge(lists));
 }
}

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)