Solved

How do I write an auto-sorting arraylist?

Posted on 2004-10-16
10
330 Views
Last Modified: 2012-06-27
Hi,

I need an arraylist that automatically inserts the object into the sorted position so that when all calls to add() are complete, all objects are in sorted order.

But I only need this if performance will be acceptable. What is the difference in performance between doing it this way and calling Collections.sort() on an unsorted arraylist?

assuming performance is acceptable then here are a few things to keep in mind:

- I will only use add(), not any other methods to insert or change the object at a given position. So I don't really need extends ArrayList, a wrapper is good enough. e.g.:

class SortedArrayList {

  ArrayList a;

  boolean add(Object o) {...}

  Object get(int index);

  int size();
 
}
0
Comment
Question by:ycomp
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
10 Comments
 
LVL 7

Expert Comment

by:lhankins
ID: 12328159
You could provide a SortedList class that implements List and either extends AbstractList or delegates to an underlying concrete List implementation (e.g. ArrayList).

In your SortedList class, you can have a "isSorted" flag.   Anytime the "add" method is called, simply set this flag to false and add the element as normal to the end of your delegate list.

When any of the accessors are called (e.g. get() or iterator()), simply check the "isSorted" flag.  If its set to false, sort the underlying list (using Collections.sort()) before proceeding with the accessor method (e.g. before returning an iterator).  

In this way, you're doing lazy sorting - don't sort each time something is added, only when you're about to hand out a reference to something in the list (and its not already sorted)

Make sense...?
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 12328160
What you want is a TreeMap class.
Auto sorting on an array implementation wastes CPU power.
;JOOP!
0
 
LVL 14

Accepted Solution

by:
sudhakar_koundinya earned 500 total points
ID: 12328212
Check this

import java.util.*;

public class SortedList {
  private ArrayList list = null;

  public SortedList() {
    list = new ArrayList();
  }

  public SortedList(List l) {
    this();
    for (int i = 0; i < l.size(); i += 1) {
      add(l.get(i));
    }
  }

  public SortedList(Object[] array) {
    this();
    for (int i = 0; i < array.length; i += 1) {
      add(array[i]);
    }
  }

  public SortedList(Collection c) {
    this(c.toArray());
  }

  public SortedList(Iterator i) {
    this();
    while (i.hasNext()) {
      add(i.next());
    }
  }

  public SortedList(Enumeration e) {
    this();
    while (e.hasMoreElements()) {
      add(e.nextElement());
    }
  }

  public synchronized List asList() {
    return Collections.synchronizedList(list);
  }

  public synchronized boolean add(Object o) {
    int index = Collections.binarySearch(list, o);
    if (index < 0) {
      index = (index + 1) * -1;
    }
    list.add(index, o);
    return true;
  }

  public synchronized String toString() {
    return list.toString();
  }

  public synchronized int size() {
    return list.size();
  }

  public synchronized int indexOf(Object o) {
    return list.indexOf(o);
  }

  public synchronized int hashCode() {
    return list.hashCode();
  }

  public synchronized Object remove(int index) {

    return list.remove(index);
  }

  public synchronized void clear() {
    list.clear();

  }

  public synchronized boolean remove(Object o) {
    return list.remove(o);
  }



  /**
   * isEmpty
   *
   * @return boolean
   */
  public synchronized boolean isEmpty() {
    return list.isEmpty();
  }

  /**
   * toArray
   *
   * @return Object[]
   */
  public synchronized Object[] toArray() {
    return list.toArray();
  }

  /**
   * contains
   *
   * @param o Object
   * @return boolean
   */
  public synchronized boolean contains(Object o) {
    return list.contains(o);
  }

  /**
   * iterator
   *
   * @return Iterator
   */
  public synchronized Iterator iterator() {
    return list.iterator();
  }

  /**
   * toArray
   *
   * @param a Object[]
   * @return Object[]
   */
  public synchronized Object[] toArray(Object[] a) {
    return list.toArray(a);
  }

  /**
   * get
   *
   * @param index int
   * @return Object
   */
  public synchronized Object get(int index) {
    return list.get(index);
  }

  /**
   * lastIndexOf
   *
   * @param o Object
   * @return int
   */
  public synchronized int lastIndexOf(Object o) {
    return list.lastIndexOf(o);
  }

  /**
   * subList
   *
   * @param fromIndex int
   * @param toIndex int
   * @return List
   */
  public synchronized SortedList subList(int fromIndex, int toIndex) {
    SortedList _list = new SortedList();
    for (int i = fromIndex; i < toIndex; i++) {
      _list.add(list.get(i));
    }
    return _list;
  }

  /**
   * listIterator
   *
   * @return ListIterator
   */
  public synchronized ListIterator listIterator() {
    return list.listIterator();
  }

  /**
   * listIterator
   *
   * @param index int
   * @return ListIterator
   */
  public synchronized ListIterator listIterator(int index) {
    return list.listIterator(index);
  }

  public synchronized void removeAll() {
    for (; ; ) {
      if (list.size() <= 0) {
        break;
      }
      list.remove(0);
    }
  }

  public static void main(String s[]) {
   SortedList list1 = new SortedList();
   list1.add(new Integer(100));
   list1.add(new Integer(1010));
   list1.add(new Integer(1));
   list1.add(new Integer( -100));

   List l = list1.asList();
   System.err.println(list1);
   System.err.println(l);
 }


}
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 14

Expert Comment

by:sudhakar_koundinya
ID: 12328219
Actually main work of that class is from following method

public synchronized boolean add(Object o) {
    int index = Collections.binarySearch(list, o);
    if (index < 0) {
      index = (index + 1) * -1;
    }
    list.add(index, o);
    return true;
  }
0
 

Author Comment

by:ycomp
ID: 12328234
thanks lhankins.

sciuriware... I guess I will just call Collections.sort() afterwards. The reason I wanted to do this was because there are many positions in my code where I need to sort different instances of this class and if I don't do it then it can lead to difficult to track down bugs. I just wanted to do it this way to avoid potential future bugs when adding to the code and forgetting to call sort when it is required.

I was thinking for auto-sorting that some kind of binary search is done on each insertion. So a tree is much more efficient than a binary search insertion then? (I don't remember much about trees).

But I did check out TreeMap which is not applicable to my case because if you add 2 objects that are different are the same (I'm not sure if it uses the compareTo or equals() or what but if they are the same then only one is added to the tree). Which for my case is no good because my compareTo is related to positioning (row, col) which is in the top-level class. Subclasses have different other properties not related to positioning. But I want to be able to have 2 different objects at the same position (so they would compare equal). And I can't see how to do that with a treemap. Please correct me if I'm wrong.
0
 

Author Comment

by:ycomp
ID: 12328253
thanks sudhakar.... I'll check it out.


What do you think about performance of a binary search insertion vs. tree ? and both of these compared to just sorting once the unsorted list?
0
 
LVL 14

Expert Comment

by:sudhakar_koundinya
ID: 12328344


Did u try with SortedSet

from: http://www.javaalmanac.com/egs/java.util/coll_SortSet.html

A sorted set is a set that maintains its items in a sorted order. Inserts and retrievals are more expensive in a sorted set but iterations over the set is always in order.



    // Create the sorted set
    SortedSet set = new TreeSet();
   
    // Add elements to the set
    set.add("b");
    set.add("c");
    set.add("a");
   
    // Iterating over the elements in the set
    Iterator it = set.iterator();
    while (it.hasNext()) {
        // Get element
        Object element = it.next();
    }
    // The elements are iterated in order: a, b, c
   
    // Create an array containing the elements in a set (in this case a String array).
    // The elements in the array are in order.
    String[] array = (String[])set.toArray(new String[set.size()]);
0
 
LVL 14

Expert Comment

by:sudhakar_koundinya
ID: 12328357
>>What do you think about performance of a binary search insertion vs. tree ?

I have no Idea on that. But my perception is Tree is better

Although look into this link. You might get some idea
http://www.cs.rit.edu/~std3246/thesis/node8.html
0
 

Author Comment

by:ycomp
ID: 12328373
TreeSet is no good for same reason as TreeMap. I need to have multiple objects that compare and equals the same.
0
 
LVL 14

Expert Comment

by:sudhakar_koundinya
ID: 12328799
thanks :)
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
This video teaches viewers about errors in exception handling.

756 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question