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));
 }
}
Post a Comment

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts