Package list

Class MyList<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractList<E>

list.MyList<E>

Type Parameters:

E - the type of elements in this list

All Implemented Interfaces:

java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>

public class MyList<E>
extends java.util.AbstractList<E>
implements java.util.List<E>, java.lang.Cloneable

Collections with sorted

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	MyList.Itr	An optimized version of AbstractList.Itr

Field Summary

Fields

Modifier and Type	Field	Description
private static int	DEFAULT_CAPACITY	Default initial capacity.
private static java.lang.Object[]	DEFAULTCAPACITY_EMPTY_ELEMENTDATA	Shared empty array instance used for default sized empty instances.
(package private) java.lang.Object[]	elementData	The array buffer into which the elements of the MyList are stored.
private static java.lang.Object[]	EMPTY_ELEMENTDATA	Shared empty array instance used for empty instances.
private static int	MAX_ARRAY_SIZE	The maximum size of array to allocate (unless necessary).
private int	size	The size of the MyList (the number of elements it contains).
SortI	sortI	Sorted

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

Constructors

Constructor	Description
MyList()	Constructs an empty list with an initial capacity of ten.
MyList(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.

Method Summary

Modifier and Type	Method	Description
void	add(int index, E element)	Inserts the specified element at the specified position in this list and sorts.
boolean	add(E e)	Appends the specified element to the end of this list and sorts.
private void	add(E e, java.lang.Object[] elementData, int s)	This helper method split out from add(E) to keep method bytecode size under 35 (the -XX:MaxInlineSize default value), which helps when add(E) is called in a C1-compiled loop.
boolean	addAll(int index, java.util.Collection<? extends E> c)	Inserts all of the elements in the specified collection into this list, starting at the specified position.
boolean	addAll(java.util.Collection<? extends E> c)	Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's Iterator.
void	clear()	Removes all of the elements from this list.
java.lang.Object	clone()	Returns a shallow copy of this MyList instance.
boolean	contains(java.lang.Object o)	Returns true if this list contains the specified element.
(package private) static <E> E	elementAt(java.lang.Object[] es, int index)
(package private) E	elementData(int index)
private void	fastRemove(int index)	Private remove method that skips bounds checking and does not return the value removed.
E	get(int index)	Returns the element at the specified position in this list.
SortI	getSortI()
private java.lang.Object[]	grow()
private java.lang.Object[]	grow(int minCapacity)	Increases the capacity to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
private static int	hugeCapacity(int minCapacity)
int	indexOf(java.lang.Object o)	Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
boolean	isEmpty()	Returns true if this list contains no elements.
java.util.Iterator<E>	iterator()	Returns an iterator over the elements in this list in proper sequence.
int	lastIndexOf(java.lang.Object o)	Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
private int	newCapacity(int minCapacity)	Returns a capacity at least as large as the given minimum capacity.
private java.lang.String	outOfBoundsMsg(int index)	Constructs an IndexOutOfBoundsException detail message.
private void	rangeCheckForAdd(int index)	A version of rangeCheck used by add and addAll.
E	remove(int index)	Removes the element at the specified position in this list.
boolean	remove(java.lang.Object o)	Removes the first occurrence of the specified element from this list, if it is present.
E	set(int index, E element)	Removes an element by index, and adds newRemoves an element by index, and adds new
void	setSortI(SortI sortI)
int	size()	Returns the number of elements in this list.
private void	sorts()	Sorts MyList
java.lang.Object[]	toArray()	Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[]	toArray(T[] a)	Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

Methods inherited from class java.util.AbstractCollection

containsAll, removeAll, retainAll, toString

Methods inherited from class java.util.AbstractList

equals, hashCode, listIterator, listIterator, removeRange, subList

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.List

containsAll, equals, hashCode, listIterator, listIterator, of, of, of, of, of, of, of, of, of, of, of, of, removeAll, replaceAll, retainAll, sort, spliterator, subList

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Field Detail

DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY

Default initial capacity.

See Also:

Constant Field Values

DEFAULTCAPACITY_EMPTY_ELEMENTDATA

private static final java.lang.Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA

Shared empty array instance used for default sized empty instances. We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.

elementData

transient java.lang.Object[] elementData

The array buffer into which the elements of the MyList are stored. The capacity of the MyList is the length of this array buffer. Any empty MyList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.

EMPTY_ELEMENTDATA

private static final java.lang.Object[] EMPTY_ELEMENTDATA

Shared empty array instance used for empty instances.

MAX_ARRAY_SIZE

private static final int MAX_ARRAY_SIZE

The maximum size of array to allocate (unless necessary). Some VMs reserve some header words in an array. Attempts to allocate larger arrays may result in OutOfMemoryError: Requested array size exceeds VM limit

See Also:

Constant Field Values

size

private int size

The size of the MyList (the number of elements it contains).

sortI

public SortI sortI

Sorted

Constructor Detail

MyList

public MyList()

Constructs an empty list with an initial capacity of ten.

MyList

public MyList(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 into this list

Throws:

java.lang.NullPointerException - if the specified collection is null

Method Detail

add

public void add(int index,
                E element)

Inserts the specified element at the specified position in this list and sorts. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Specified by:

add in interface java.util.List<E>

Overrides:

add in class java.util.AbstractList<E>

Parameters:

index - index at which the specified element is to be inserted

element - element to be inserted

Throws:

java.lang.IndexOutOfBoundsException

add

public boolean add(E e)

Appends the specified element to the end of this list and sorts.

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Overrides:

add in class java.util.AbstractList<E>

Parameters:

e - element to be appended to this list

Returns:

true (as specified by Collection.add(E))

add

private void add(E e,
                 java.lang.Object[] elementData,
                 int s)

This helper method split out from add(E) to keep method bytecode size under 35 (the -XX:MaxInlineSize default value), which helps when add(E) is called in a C1-compiled loop.

addAll

public boolean addAll(int index,
                      java.util.Collection<? extends E> c)

Inserts all of the elements in the specified collection into this list, starting at the specified position. Shifts the element currently at that position (if any) and any subsequent elements to the right (increases their indices). The new elements will appear in the list in the order that they are returned by the specified collection's iterator.

Specified by:

addAll in interface java.util.List<E>

Overrides:

addAll in class java.util.AbstractList<E>

Parameters:

index - index at which to insert the first element from the specified collection

c - collection containing elements to be added to this list

Returns:

true if this list changed as a result of the call

Throws:

java.lang.IndexOutOfBoundsException

java.lang.NullPointerException - if the specified collection is null

addAll

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

Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's Iterator. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this list, and this list is nonempty.)

Specified by:

addAll in interface java.util.Collection<E>

Specified by:

addAll in interface java.util.List<E>

Overrides:

addAll in class java.util.AbstractCollection<E>

Parameters:

c - collection containing elements to be added to this list

Returns:

true if this list changed as a result of the call

Throws:

java.lang.NullPointerException - if the specified collection is null

clear

public void clear()

Removes all of the elements from this list. The list will be empty after this call returns.

Specified by:

clear in interface java.util.Collection<E>

Specified by:

clear in interface java.util.List<E>

Overrides:

clear in class java.util.AbstractList<E>

clone

public java.lang.Object clone()

Returns a shallow copy of this MyList instance. (The elements themselves are not copied.)

Overrides:

clone in class java.lang.Object

Returns:

a clone of this MyList instance

contains

public boolean contains(java.lang.Object o)

Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that Objects.equals(o, e).

Specified by:

contains in interface java.util.Collection<E>

Specified by:

contains in interface java.util.List<E>

Overrides:

contains in class java.util.AbstractCollection<E>

Parameters:

o - element whose presence in this list is to be tested

Returns:

true if this list contains the specified element

elementAt

static <E> E elementAt(java.lang.Object[] es,
                       int index)

elementData

E elementData(int index)

fastRemove

private void fastRemove(int index)

Private remove method that skips bounds checking and does not return the value removed.

get

public E get(int index)

Returns the element at the specified position in this list.

Specified by:

get in interface java.util.List<E>

Specified by:

get in class java.util.AbstractList<E>

Parameters:

index - index of the element to return

Returns:

the element at the specified position in this list

Throws:

java.lang.IndexOutOfBoundsException

getSortI

public SortI getSortI()

grow

private java.lang.Object[] grow()

grow

private java.lang.Object[] grow(int minCapacity)

Increases the capacity to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

Parameters:

minCapacity - the desired minimum capacity

Throws:

java.lang.OutOfMemoryError - if minCapacity is less than zero

hugeCapacity

private static int hugeCapacity(int minCapacity)

indexOf

public int indexOf(java.lang.Object o)

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest index i such that Objects.equals(o, get(i)), or -1 if there is no such index.

Specified by:

indexOf in interface java.util.List<E>

Overrides:

indexOf in class java.util.AbstractList<E>

isEmpty

public boolean isEmpty()

Returns true if this list contains no elements.

Specified by:

isEmpty in interface java.util.Collection<E>

Specified by:

isEmpty in interface java.util.List<E>

Overrides:

isEmpty in class java.util.AbstractCollection<E>

Returns:

true if this list contains no elements

iterator

public java.util.Iterator<E> iterator()

Returns an iterator over the elements in this list in proper sequence.

The returned iterator is fail-fast.

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.List<E>

Overrides:

iterator in class java.util.AbstractList<E>

Returns:

an iterator over the elements in this list in proper sequence

lastIndexOf

public int lastIndexOf(java.lang.Object o)

Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the highest index i such that Objects.equals(o, get(i)), or -1 if there is no such index.

Specified by:

lastIndexOf in interface java.util.List<E>

Overrides:

lastIndexOf in class java.util.AbstractList<E>

newCapacity

private int newCapacity(int minCapacity)

Returns a capacity at least as large as the given minimum capacity. Returns the current capacity increased by 50% if that suffices. Will not return a capacity greater than MAX_ARRAY_SIZE unless the given minimum capacity is greater than MAX_ARRAY_SIZE.

Parameters:

minCapacity - the desired minimum capacity

Throws:

java.lang.OutOfMemoryError - if minCapacity is less than zero

outOfBoundsMsg

private java.lang.String outOfBoundsMsg(int index)

Constructs an IndexOutOfBoundsException detail message. Of the many possible refactorings of the error handling code, this "outlining" performs best with both server and client VMs.

rangeCheckForAdd

private void rangeCheckForAdd(int index)

A version of rangeCheck used by add and addAll.

remove

public E remove(int index)

Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

Specified by:

remove in interface java.util.List<E>

Overrides:

remove in class java.util.AbstractList<E>

Parameters:

index - the index of the element to be removed

Returns:

the element that was removed from the list

Throws:

java.lang.IndexOutOfBoundsException

remove

public boolean remove(java.lang.Object o)

Removes the first occurrence of the specified element from this list, if it is present. If the list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that Objects.equals(o, get(i)) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call).

Specified by:

remove in interface java.util.Collection<E>

Specified by:

remove in interface java.util.List<E>

Overrides:

remove in class java.util.AbstractCollection<E>

Parameters:

o - element to be removed from this list, if present

Returns:

true if this list contained the specified element

set

public E set(int index,
             E element)

Removes an element by index, and adds newRemoves an element by index, and adds new

Specified by:

set in interface java.util.List<E>

Overrides:

set in class java.util.AbstractList<E>

Parameters:

index - index of the element to replace

element - element to be stored at the specified position

Returns:

the element previously at the specified position

Throws:

java.lang.IndexOutOfBoundsException

setSortI

public void setSortI(SortI sortI)

size

public int size()

Returns the number of elements in this list.

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.List<E>

Specified by:

size in class java.util.AbstractCollection<E>

Returns:

the number of elements in this list

sorts

private void sorts()

Sorts MyList

toArray

public java.lang.Object[] toArray()

Returns an array containing all of the elements in this list in proper sequence (from first to last element).

The returned array will be "safe" in that no references to it are maintained by this list. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.List<E>

Overrides:

toArray in class java.util.AbstractCollection<E>

Returns:

an array containing all of the elements in this list in proper sequence

toArray

public <T> T[] toArray(T[] a)

Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.

If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of the list only if the caller knows that the list does not contain any null elements.)

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.List<E>

Overrides:

toArray in class java.util.AbstractCollection<E>

Parameters:

a - the array into which the elements of the list are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.

Returns:

an array containing the elements of the list

Throws:

java.lang.ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this list

java.lang.NullPointerException - if the specified array is null