Solved

How do I write an auto-sorting arraylist?

Posted on 2004-10-16
10
324 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
10 Comments
 
LVL 7

Expert Comment

by:lhankins
Comment Utility
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
Comment Utility
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
Comment Utility
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
 
LVL 14

Expert Comment

by:sudhakar_koundinya
Comment Utility
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
Comment Utility
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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:ycomp
Comment Utility
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
Comment Utility


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
Comment Utility
>>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
Comment Utility
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
Comment Utility
thanks :)
0

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

772 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now