[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 338
  • Last Modified:

How do I write an auto-sorting arraylist?

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
ycomp
Asked:
ycomp
1 Solution
 
lhankinsCommented:
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
 
sciuriwareCommented:
What you want is a TreeMap class.
Auto sorting on an array implementation wastes CPU power.
;JOOP!
0
 
sudhakar_koundinyaCommented:
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
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
sudhakar_koundinyaCommented:
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
 
ycompAuthor Commented:
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
 
ycompAuthor Commented:
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
 
sudhakar_koundinyaCommented:


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
 
sudhakar_koundinyaCommented:
>>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
 
ycompAuthor Commented:
TreeSet is no good for same reason as TreeMap. I need to have multiple objects that compare and equals the same.
0
 
sudhakar_koundinyaCommented:
thanks :)
0

Featured Post

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now