Solved

How do I write an auto-sorting arraylist?

Posted on 2004-10-16
10
328 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
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
Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

 
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

Optimizing Cloud Backup for Low Bandwidth

With cloud storage prices going down a growing number of SMBs start to use it for backup storage. Unfortunately, business data volume rarely fits the average Internet speed. This article provides an overview of main Internet speed challenges and reveals backup best practices.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
numbers ascending pyramid 101 195
how do i compare an object based on two fields 6 54
Java string replace 11 47
String array comparison 4 34
For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

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