jhelp.util.list

Class SortedArray<TYPE>

java.lang.Object

jhelp.util.list.SortedArray<TYPE>

Type Parameters:

TYPE - Type of stored elements

All Implemented Interfaces:

java.lang.Iterable<TYPE>

public final class SortedArray<TYPE>
extends java.lang.Object
implements java.lang.Iterable<TYPE>

Array of sorted element.
The sort is "natural order" (Only possible for Comparable elements) or as indicates by a Comparator.
The sort can be unique, that is to say if try to add an element and exists an other inside array that compare equals, in unique mode, the element is not add.
The adding, remove are in O(n * LN(n)). The search is in O(LN(n)).

Author:

JHelp

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static class	SortedArray.ComparatorNatural<ELEMENT> Comparator for "natural order" of Comparable

Field Summary

Fields

Modifier and Type	Field and Description
private TYPE[]	array Stored elements
private java.util.Comparator	comparator Comparator to use
private int	size Actual array size
private java.lang.Class<TYPE>	typeClass Type of element stored
private boolean	unique Indicates if we are in unique mode

Constructor Summary

Constructors

Constructor and Description
SortedArray(java.lang.Class<TYPE> typeClass) Create a new instance of SortedArray in not unique mode.
SortedArray(java.lang.Class<TYPE> typeClass, boolean unique) Create a new instance of SortedArray.
SortedArray(java.lang.Class<TYPE> typeClass, java.util.Comparator<TYPE> comparator) Create a new instance of SortedArray in not unique mode.
SortedArray(java.lang.Class<TYPE> typeClass, java.util.Comparator<TYPE> comparator, boolean unique) Create a new instance of SortedArray.
SortedArray(java.lang.Class<TYPE> typeClass, java.util.Comparator<TYPE> comparator, int initialSize, boolean unique) Create a new instance of SortedArray.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(TYPE element) Add an element
private void	checkIndex(int index) Check if an index is out of the array
void	clear() Clear the array.
boolean	contains(TYPE element) Indicates if an element is inside the array
private void	expand(int more) Expand the array (if need) to have more space
protected void	finalize() Called when garbage collector want free is memory Parent documentation:
TYPE	getElement(int index) Give an element of the array
int	getSize() Actual array size
int	indexOf(TYPE element) Get an element index or -1 if not present
private int	insertIn(TYPE element) Compute the index where insert an element.
Pair<java.lang.Integer,java.lang.Integer>	intervalOf(TYPE element) Compute interval index where should be insert a given element.
boolean	isEmpty() Indicates if array is empty
boolean	isUnique() Indicates if array is in unique mode
java.util.Iterator<TYPE>	iterator() Compute iterator over the list Parent documentation:
TYPE	obtainElement(java.lang.Object object) Search an element similar to the object.
int	obtainIndex(java.lang.Object object) Search index of similar element.
TYPE	remove(int index) Remove an element
TYPE	remove(TYPE element) Remove an element.
TYPE[]	toArray() Transform the array to a an array with size the same as this array, with same element in same order
java.lang.String	toString() String representation Parent documentation:

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

array

private TYPE[] array

Stored elements

comparator

private java.util.Comparator comparator

Comparator to use

size

private int size

Actual array size

typeClass

private java.lang.Class<TYPE> typeClass

Type of element stored

unique

private boolean unique

Indicates if we are in unique mode

Constructor Detail

SortedArray

public SortedArray(java.lang.Class<TYPE> typeClass)

Create a new instance of SortedArray in not unique mode.
The type of class must be a Comparable to use the "natural order"

Parameters:

typeClass - Type of element to store

SortedArray

public SortedArray(java.lang.Class<TYPE> typeClass,
           boolean unique)

Create a new instance of SortedArray.
The type of class must be a Comparable to use the "natural order"

Parameters:

typeClass - Type of element to store

unique - Indicates if use unique mode or not

SortedArray

public SortedArray(java.lang.Class<TYPE> typeClass,
           java.util.Comparator<TYPE> comparator)

Create a new instance of SortedArray in not unique mode.
If the comparator is null, the type of class must be a Comparable to use the "natural order"

Parameters:

typeClass - Type of elements

comparator - Comparator to use

SortedArray

public SortedArray(java.lang.Class<TYPE> typeClass,
           java.util.Comparator<TYPE> comparator,
           boolean unique)

Create a new instance of SortedArray.
If the comparator is null, the type of class must be a Comparable to use the "natural order"

Parameters:

typeClass - Type of element

comparator - Comparator to use

unique - Indicates if the unique mode is activated

SortedArray

public SortedArray(java.lang.Class<TYPE> typeClass,
           java.util.Comparator<TYPE> comparator,
           int initialSize,
           boolean unique)

Create a new instance of SortedArray.
If the comparator is null, the type of class must be a Comparable to use the "natural order"

Parameters:

typeClass - Type of element

comparator - Comparator to use

initialSize - Initial array capacity

unique - Indicates if the unique mode is enable

Method Detail

checkIndex

private void checkIndex(int index)

Check if an index is out of the array

Parameters:

index - Index to set

Throws:

java.lang.IllegalArgumentException - If the index is out of bounds

expand

private void expand(int more)

Expand the array (if need) to have more space

Parameters:

more - Number space more need

insertIn

private int insertIn(TYPE element)

Compute the index where insert an element.
The result may be negative. It happen if the element already present and we are in unique mode. We can have the index by using the formula :
index = insertIn(element); if(index<0) index = -index-1;

Parameters:

element - Element search

Returns:

Index of insertion

finalize

protected void finalize()
                 throws java.lang.Throwable

Called when garbage collector want free is memory

Parent documentation:

Overrides:

finalize in class java.lang.Object

Throws:

java.lang.Throwable - On issue

See Also:

Object.finalize()

add

public boolean add(TYPE element)

Add an element

Parameters:

element - element to add

Returns:

true if element added. false if unique mode and already present, so not added

Throws:

java.lang.NullPointerException - if the element is null

clear

public void clear()

Clear the array.
It will be empty after that

contains

public boolean contains(TYPE element)

Indicates if an element is inside the array

Parameters:

element - Tested element

Returns:

true if an element is inside the array

Throws:

java.lang.NullPointerException - if the element is null

getElement

public TYPE getElement(int index)

Give an element of the array

Parameters:

index - Element index

Returns:

Element

Throws:

java.lang.IllegalArgumentException - if the index is out of bounds

getSize

public int getSize()

Actual array size

Returns:

Actual array size

indexOf

public int indexOf(TYPE element)

Get an element index or -1 if not present

Parameters:

element - Element tested

Returns:

Element index or -1 if not present

Throws:

java.lang.NullPointerException - if element is null

intervalOf

public Pair<java.lang.Integer,java.lang.Integer> intervalOf(TYPE element)

Compute interval index where should be insert a given element.
The couple (min, max) returned can be interpreted like that (where size is the size of the list) :

• (-1, 0) means that the element is before the first element of the list
• (size, -1) means that the element is after the last element of the list
• (index, index) in other word min==max, means that the element is at exactly the index min
• Other case (min ,max) min < max means that the element is after the element at min index and before the element at max index

Parameters:

element - Element search

Returns:

Couple (min, max)

isEmpty

public boolean isEmpty()

Indicates if array is empty

Returns:

true if array is empty

isUnique

public boolean isUnique()

Indicates if array is in unique mode

Returns:

true if array is in unique mode

iterator

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

Compute iterator over the list

Parent documentation:

Specified by:

iterator in interface java.lang.Iterable<TYPE>

Returns:

Iterator

See Also:

Iterable.iterator()

obtainElement

public TYPE obtainElement(java.lang.Object object)

Search an element similar to the object. Because it use the comparator, is the comparator say the object is the same of one element inside the array, they are declared similar

Parameters:

object - Object to be similar

Returns:

Element similar to the object, or null if no element are similar

obtainIndex

public int obtainIndex(java.lang.Object object)

Search index of similar element. Because it use the comparator, is the comparator say the object is the same of one element inside the array, they are declared similar

Parameters:

object - Object to be similar

Returns:

Index of similar element, or -1 if not found

remove

public TYPE remove(int index)

Remove an element

Parameters:

index - Element index

Returns:

The removed element

Throws:

java.lang.IllegalArgumentException - if index is out of bounds

remove

public TYPE remove(TYPE element)

Remove an element.
It removes an element equals to the given element, not necessary the element itself

Parameters:

element - Element to remove

Returns:

Real element removed or null if element not found

Throws:

java.lang.NullPointerException - if element is null

toArray

public TYPE[] toArray()

Transform the array to a an array with size the same as this array, with same element in same order

Returns:

Extracted array

toString

public java.lang.String toString()

String representation

Parent documentation:

Overrides:

toString in class java.lang.Object

Returns:

String representation

See Also:

Object.toString()