DLList

package rrc12;
import java.util.*;
import rrc12.util.*;
/** An example of the use of the DLList class.  DLList implements
 * java.lang.Cloneable, java.io.Externalizable, java.util.list, and
 * java.util.Deque.  It can directly replace java.util.LinkedList (but see
 * below for the few things LinkedList does that DLList does not).  It
 * provides additional features for using linked lists efficiently in
 * analyzing data.  This class demonstrates those features.
 *
 * 
Linked lists make life easy for memory management and scale nicely
 * on-the-fly, unlike arrays and the classes that use them.  If sequential
 * access is good enough for a problem, linked lists are the preferred
 * solution.  java.util.LinkedList, however, does not provide much beyond
 * basic adds, reads, and removes.  Sorting data, splitting a list, and
 * merging lists involve working outside the linkages in LinkedList.
 *
 * 
DLList handles these things internally and therefor much more
 * efficiently.  It was originally written for the AI for a computer game.
 * It originally served to collect diverse objects from various places,
 * sort them, then peel a section off the top or bottom (or both) for
 * various missions.  Once it existed, I found it the obvious solution
 * to a lot of other problems as well.  The example here reflects the AI
 * usage.
 *
 * 
Unlike with java.util.LinkedList:  DLList's sublist
 * method does not work (being a poor fit for any linked list).
 * DLList does not check for concurrent modification (trading safety for
 * speed).  It does not accept null entries.  And it does not track its
 * size; its size method counts the entries when it is
 * called (improving performance if you are careful).  Like LinkedList,
 * DLList is not thread-safe; take care to synchronize method calls
 * properly.
 */
public class DLListExample  {
    // A class for objects with size and speed.
    private static class Unit  {
        int  size;       // In tons.
        int  speed;      // In kph.
        Unit( int size, int speed )  {
            this.size = size;
            this.speed = speed;
        }
    }

    private static Random  diceRoll = new Random();

    private static DLList generateList( int size )  {
        DLList  list = new DLList();
        for (int i = 0; i < size; i++)  {
            list.add( new Unit( diceRoll.nextInt( 99 ) + 1,
                        diceRoll.nextInt( 99 ) + 1 ) );
        }
        return list;
    }

    public static void main( String[] args )  {

        // Generate data.  In real world, or game, may be gathered from
        // several places.  Here, there are two sources that are merged.
        DLList  mainBody = generateList( 25000 );
        DLList  more = generateList( 25000 );
        // Unlike with, say, java.util.Collection's "addAll", "merge"
        // does not need to generate links and is much faster.  Indeed,
        // it takes no time at all.
        mainBody.merge( more, true );
        // Note that "more" is now empty.

        // Pick out things that are big and fast for a rapid response
        // team.
        // Pick out things that are small and slow to be place out of
        // the way.
        // Start by sorting on size and speed.
        mainBody.doSort( new Comparator()  {
            public int compare( Unit u1, Unit u2 )   {
                int  value1 = u1.size * u1.speed;
                int  value2 = u2.size * u2.speed;
                // Big values sort first.
                if (value1 > value2)  return -1;
                if (value1 < value2)  return 1;
                return 0;
            }
        } );
        // Defining elite units in the real world might take some
        // analysis. The minimum and maximum could now be picked up by
        // looking at the first and last entries in the list.  Searching
        // the list sequentially might reveal sudden changes in total
        // value that would give a clear boundary.
        // Here, with numbers more random than in real life and a pretty
        // good idea in advance about what they look like, I am going
        // to assume arbitrarily that anything over 6000 is elite and
        // anything under 1000 is only an obstruction.
        DLList.It  it = mainBody.getIterator();
        while (it.hasNext())  {
             Unit  u = it.next();
             if (u.size * u.speed < 6000)
                 break;
        }
        DLList  eliteGroup = it.subList( true, false );

        // Get the useless group also.
        it.atLast();
        while (it.hasPrevious())  {
            Unit  u = it.previous();
            if (u.size * u.speed >= 1000)
                break;
        }
        DLList  impedimenta = it.subList( false, false );

        // Sort Note:  I prefer "doSort" for being friendlier to memory
        // allocation and management.  "Collections.sort", when called,
        // allocates two large arrays, which can be difficult when memory
        // is fragmented.  However, "sort" IS faster when the data is in
        // random order. ("sort" sorts a DLList in about two thirds the
        // time it takes to sort a LinkedList.)

        // Now get a list of the remaining large units.
        // We have work for them.
        // Sort by size.
        Collections.sort( mainBody, new Comparator()  {
            public int compare( Unit u1, Unit u2 )  {
                if (u1.size > u2.size)  return -1;
                if (u1.size < u2.size)  return 1;
                return 0;
            }
        } );
        // Get the big ones.
        // Anything over 50 is considered big here.
        // (In real life, a bit more analysis might be called for.)
        DLList.It  bgi = mainBody.getIterator();
        while (bgi.hasNext())  {
             Unit  u = bgi.next();
             if (u.size < 50)
                 break;
        }
        DLList  bigGroup = bgi.subList( true, false );

        // Check that all the generated lists have reasonable values.
        Unit  unit;
        System.out.println( "mainBody size is: " + mainBody.size() );
        unit = mainBody.peekFirst();
        if (unit != null)
            System.out.println( "First mainBody element is:  size: " +
                        unit.size + "   speed: " + unit.speed );
        unit = mainBody.peekLast();
        if (unit != null)
            System.out.println( "Last mainBody element is:  size: " +
                        unit.size + "   speed: " + unit.speed );
        if (more.isEmpty())
            System.out.println( "more is empty." );
        else
            System.out.println( "more is NOT empty (problem!)." );
        System.out.println( "" );

        System.out.println( "eliteGroup size is: " + eliteGroup.size() );
        unit = eliteGroup.peekLast();
        if (unit != null)
            System.out.println( "Last eliteGroup element is:  size: " +
                        unit.size + "   speed: " + unit.speed );
        System.out.println( "" );

        System.out.println( "impedimenta size is: " +
                    impedimenta.size() );
        unit = impedimenta.peekFirst();
        System.out.println( "First impediment element is:  size: " +
                    unit.size + "   speed: " + unit.speed );
        System.out.println( "" );

        System.out.println( "bigGroup size is: " + bigGroup.size() );
        unit = bigGroup.peekFirst();
        if (unit != null)
            System.out.println( "First bigGroup element is:  size: " +
                        unit.size + "   speed: " + unit.speed );
        unit = bigGroup.peekLast();
        if (unit != null)
            System.out.println( "Last bigGroup element is:  size: " +
                        unit.size + "   speed: " + unit.speed );
    }
}

Javadoc for DLList in plain text. Only methods unique to DLList have been included to save space. See also the documentation for DLList.It, the ListIterator extension.

rrc12.util Class DLList<E>

java.lang.Object rrc12.util.DLList<E>

All Implemented Interfaces: java.io.Externalizable, java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Deque<E>, java.util.List<E>, java.util.Queue<E>

public class DLList<E> extends java.lang.Object implements java.lang.Cloneable, java.io.Externalizable, java.util.List<E>, java.util.Deque<E>

A doubly-linked list like java.util.LinkedList. Does not accept null entries. Allows, for better and for worse, concurrent modification: the list may be modified while iterators are active so long as entries at the iterators' current locations are not altered. This class is not thread-safe, and care should be taken that interleaved operations on various sections of a list do not interfere with each other. (It may be accessed from multiple threads so long as it is not modified, but this class is not particularly useful for queries and does not lend itself to this.)

DLList lists may be split in two and joined into one at virtually no cost, regardless of size. (As a side benefit, a set of DLList instances with no duplicate entries is in no danger of generating duplicates with these operations.)

Other benefits: as a linked list, DLList is marginally faster than java.util.LinkedList. In cases where the size method is not used and there is little danger of concurrent modification, switching to DLList will provide an immediate, though not stunning, performance boost. DLList also provides a sort, doSort, that works better than Collections.sort for lists that are already partly sorted. And it avoids allocating large blocks of memory for arrays, which can be a performance problem when free memory is fragmented.

Original Purpose: I had a bunch of lists, each containing objects doing a particular job or waiting in a particular place. I continually had to check each list for objects that were not effective on that job or that were needed more elsewhere. This involved, to simplify greatly, sorting the units for relative effectiveness on this job or on another, and then transferring objects from either the start or the end of the list to another list. The jobs and the objects' abilities, relative and absolute, changed continuously, so the analysis had to be fast to get answers while they were still relevant.

This class is designed for high-speed linked-list performance. Avoid methods concerned with the list's size. Even more: avoid methods that use indexes.

DLList does not follow all the rules. The preferred add methods do nothing when passed nulls rather than throwing NullPointerExceptions. And the subList method does nothing.

There are a lot of methods that are almost duplicates in the interfaces supported by DLList. The preferred methods are: addFirst (instead of offerFirst, and push), addLast (instead of add, offer, and offerLast), pollFirst (instead of poll, pop, remove, and removeFirst), pollLast (instead of removeLast), peekFirst (instead of getFirst, peek, and element), peekLast (instead of getLast), remove( Object ) (instead of removeFirstOccurrence), and, usually, sizeOver (instead of size).

The documentation on each method specifies whether it is the right one to use, what to use if it is not, and why it should or should not be used.

Nested Class Summary static interface DLList.It<E> An iterator for DLList instances.

Constructor Detail

DLList()

public DLList()

Creates a new, empty instance of DLList.

DLList()

public DLList(java.util.Collection<? extends E> c)

Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Parameters:

• c - the collection whose elements are to be placed in this list. May be null.

Method Detail

sizeOver()

public boolean sizeOver(int test)

Returns true if the size is greater than the passed number. Highly efficient for small numbers. Always faster than using size and checking the return value. With small values and large lists, will be much, much, much faster.

Parameters:

• test - the number. May be anything. Negative values will always return true.

Returns: true if the size is less than the passed number and false if it is equal to it or larger.

getIterator()

public DLList.It<E> getIterator()

Returns an It iterator of the elements in this list.

merge()

public void merge(DLList<? extends E> merger,
                  boolean append)

Appends (or prepends) another DLList into this one. This method executes in (almost) no time at all, and the sizes of the two lists have no affect on the time. This speed is a key DLList feature.

Parameters:

• merger - a list whose elements are to be merged in with this list. May be null, in which case nothing will happen. The passed list will be empty when this method returns. This method is a move rather than a copy (and highly efficient as a result.)
• append - if true merger will be appended to this list. If false it will be placed at the start of this list.

mergeSort()

public void mergeSort(java.util.Comparator<E> c,
                      DLList<? extends E> merger)

Efficiently merges another DLList into this one. The passed list is added in sorted order relative to this one, so if both lists are sorted properly to start with, this list will be sorted properly when the method is done. When two elements are equal, the element in merger is placed after the element in this DLList. Do note that two elements in the same list will end up in the same order regardless of how they compare; for best results, both lists must already be properly sorted. This method does check to see if the passed list can be placed completely before or completely after this list, thus avoiding iterating through both lists.

Parameters:

• c - the Comparator instance for ordering the objects in the list. Must not be null!
• merger - a list whose elements are to be merged in with this list. May be null, in which case nothing will happen. The passed list will be empty when this method returns. (This method is a move rather than a copy, and highly efficient as a result.)

doSort()

public void doSort(java.util.Comparator<E> c)

Sorts this DLList. Entries of equal value will keep their original order. The algorithm is pretty much a simple Merge Sort. It will try to speed things by taking advantage if parts of the list are already sorted or reverse sorted. Works with DLList's structure for better performance (theoretically) than the same technique would have had from outside a DLList instance. In practice, with random data, Collections.sort() will outperform doSort. doSort does better when there is some order to the data. Collections.sort does allocate two arrays, each with as many elements as there are entries in the list. Allocating memory in big blocks can be effortless, but it is usually easier for a memory system to find smaller blocks. When a program has been making heavy use of CPU and memory for a period of time, memory can get fragmented. Finding big blocks can involve a lot of searching and moving. This sort sticks with the linked list philosophy of using as little memory as possible in the smallest blocks as possible, and is apt to perform better in hard use--in my opinion. Collections.sort sorts DLList notably faster than LinkedList. (I suspect this is due to not tracking the list size and not doing concurrency checking.) With random data, DLList with doSort is almost as fast as LinkedList with Collections.sort.

Parameters:

• c - the comparator used to order the elements in this list for sorting. Must not be null!

The following is the javadoc for DLList.It, a ListIterator extension, in plain text. Only extension methods are included here:

rrc12.util Interface DLList.It<E>

All Superinterfaces: java.util.Iterator<E>, java.util.ListIterator<E>

Enclosing class: DLList<E>

public static interface DLList.It<E>extends java.util.ListIterator<E>

An iterator for DLList instances. Extends Iterator and ListIterator. As returned from DLList, these are highly efficient except for nextIndex and previousIndex, which should not be used.

Methods inherited from interface java.util.ListIterator add, hasNext, hasPrevious, next, nextIndex, previous, previousIndex, remove, set

Method Detail

atFirst()

void atFirst()

Places the iterator at the start of the list.

atLast()

void atLast()

Places the iterator at the end of the list.

insert()

void insert(E element)

Inserts the specified element into the list ahead of the last returned element. It will not affect the last returned element. Unlike with java.util.ListIterator.add, a call to remove will still remove the last returned element. While that add places the new element after the element just returned, insert places it before that element.

insert()

void insert(DLList<? extends E> list)

Inserts the specified DLList instance contents into the list ahead of the last returned element. (It will not affect the last returned element.)

copy()

DLList.It<E> copy()

Returns an independent copy of this DLList.It, which can then be used alongside this one. Take care not to use one of them to delete an entry that the other one is looking at! (DLList sacrifices safety for speed!)

move()

E move(int count)

Advances this iterator through the list by the specified number of entries. Much like calling next count times, except that NoSuchElementException is not thrown. If there are not enough entries, this iterator is merely placed at the end of the list.

Parameters:

• count - the number of entries to advance. If negative, this iterator just moves backward instead of forward. If zero, merely rereturns the last returned element.

Returns: the object at the new iterator location. Can be null (if count is zero).

subList()

DLList<E> subList(boolean before,
                  boolean inclusive)

Removes a set of entries from this list and places them in a new DLList object, which is returned. Based on the last returned entry. If there is none, returns an empty list. This method takes practically no time at all, no matter how many entries are to be removed.

Parameters:

• before - if true, removes all the entries before the last returned entry. If false returns all the entries after the last returned entry.
• inclusive - if true, the last returned element is moved to the new list. If false it remains in the old list.

Returns: the list of entries that were removed, as a new DLList. The new list will be ordered just like this list. All entries in the list are independent, having been removed from the list they previously inhabited. Never null, but list will be empty if there was no returned element to base a sublist upon, or if the returned element was the first and only elements ahead of it were to be taken or last and only elements after it were to be taken.