package org.andengine.util.adt.list;
/**
* This implementation is particular useful/efficient for enter/poll operations of elements that need to be sorted by natural order instead of the order they are queue.
* Its {@link java.util.List} like behavior performs better than a plain {@link java.util.ArrayList}, since it automatically shift the contents of its internal Array only when really necessary.
* Besides sparse allocations to increase the size of the internal Array, {@link com.zynga.mobileville.path.SortedList} is allocation free (unlike the {@link java.util.LinkedList} family).
*
* (c) Zynga 2012
*
* @author Nicolas Gramlich <ngramlich@zynga.com>
* @author Greg Haynes
* @since 15:02:40 - 24.02.2012
*/
public class SortedList<T extends Comparable<T>> implements ISortedList<T> {
// ===========================================================
// Constants
// ===========================================================
private static final int INDEX_INVALID = -1;
// ===========================================================
// Fields
// ===========================================================
private final IList<T> mList;
// ===========================================================
// Constructors
// ===========================================================
public SortedList(final IList<T> pList) {
this.mList = pList;
}
// ===========================================================
// Getter & Setter
// ===========================================================
// ===========================================================
// Methods for/from SuperClass/Interfaces
// ===========================================================
@Override
public boolean isEmpty() {
return this.mList.isEmpty();
}
@Override
public T get(final int pIndex) throws IndexOutOfBoundsException {
return this.mList.get(pIndex);
}
@Override
@Deprecated
public void set(final int pIndex, final T pItem) throws IndexOutOfBoundsException {
this.mList.set(pIndex, pItem);
}
@Override
public int indexOf(final T pItem) {
return this.binarySearch(pItem, false);
}
@Override
@Deprecated
public void add(final int pIndex, final T pItem) {
this.mList.add(pItem);
}
@Override
public void add(final T pItem) {
final int index = this.binarySearch(pItem, true);
if(index < 0) {
this.mList.add(ListUtils.encodeInsertionIndex(index), pItem);
} else {
this.mList.add(index, pItem);
}
}
@Override
public T removeFirst() {
return this.mList.removeFirst();
}
@Override
public T removeLast() {
return this.mList.removeLast();
}
@Override
public boolean remove(final T pItem) {
if(pItem == null) {
return this.mList.remove(pItem);
}
final int index = this.binarySearch(pItem, false);
if(index >= 0) {
this.mList.remove(index);
return true;
} else {
return false;
}
}
@Override
public T remove(final int pIndex) {
return this.mList.remove(pIndex);
}
@Override
public int size() {
return this.mList.size();
}
@Override
public void clear() {
this.mList.clear();
}
// ===========================================================
// Methods
// ===========================================================
private int binarySearch(final T pItem, final boolean pReturnSequenceEndIfNoEqualItemFound) {
final int size = this.mList.size();
final int guess = this.binarySearch(0, size, pItem);
if(guess >= 0) {
return this.scanForEqualItem(0, size, guess, pItem, pReturnSequenceEndIfNoEqualItemFound);
} else {
return guess;
}
}
private int binarySearch(final int pStart, final int pEnd, final T pItem) {
int low = pStart;
int high = pEnd - 1;
while(low <= high) {
final int mid = (low + high) >>> 1;
final T midVal = this.mList.get(mid);
final int diff = pItem.compareTo(midVal);
if(diff > 0) {
low = mid + 1;
} else if(diff < 0) {
high = mid - 1;
} else {
return mid;
}
}
return ListUtils.encodeInsertionIndex(low);
}
/**
* Scans for items around <code>pGuess</code> that fulfill <code>pItem.compareTo(item) == 0</code> and starting from the leftmost found, it returns the index of the first one that fulfills <code>pItem.equals(item)</code>.
*
* @param pStart left bound.
* @param pEnd right bound.
* @param pGuess index to start the search.
* @param pItem to perform <code>pItem.compareTo(item) == 0</code> and <code>pItem.equals(item)</code> checks on.
* @param pReturnSequenceEndIfNoEqualItemFound
* @return
*/
private int scanForEqualItem(final int pStart, final int pEnd, final int pGuess, final T pItem, final boolean pReturnSequenceEndIfNoEqualItemFound) {
/* Quickly move to the beginning of the sequence. */
int i = pGuess - 1;
while((i >= pStart) && (pItem.compareTo(this.mList.get(i)) == 0)) {
i--;
}
i++;
/* From the beginning of the sequence, advance until the first item equals pItem or the end has been reached. */
while(i < pEnd) {
final T item = this.mList.get(i);
if(i <= pGuess) {
/* Since the compartTo check has already been performed, only equals needs to be checked. */
if(pItem.equals(item)) {
/* Item found. */
return i;
}
} else {
/* Check if the sequence is still ongoing. */
if(pItem.compareTo(item) == 0) {
if(pItem.equals(item)) {
/* Item found. */
return i;
}
} else {
/* Return the last known position. */
return ListUtils.encodeInsertionIndex(i);
}
}
i++;
}
if(pReturnSequenceEndIfNoEqualItemFound) {
return i;
} else {
return SortedList.INDEX_INVALID;
}
}
// ===========================================================
// Inner and Anonymous Classes
// ===========================================================
}