public abstract class AbstractBlockIntegerList extends Object implements IntegerListInterface
The class works as follows;
NOTE: The following methods are NOT optimal: get(pos), add(val, pos), remove(pos)
Specifically, they slow as 'pos' nears the end of large lists.
This type of structure is very fast for large sorted lists where values can be inserted at any position within the list. Care needs to be taken for lists where values are inserted and removed constantly, because fragmentation of the list blocks can occur. For example, adding 60,000 random entries followed by removing 50,000 random entries will result in many only partially filled blocks. Since each block takes a constant amount of memory, this may not be acceptable.
Modifier and Type | Field and Description |
---|---|
protected ArrayList |
block_list
The list of blocks (objects in this list are of type
'IntegerListBlockInterface'.
|
Constructor and Description |
---|
AbstractBlockIntegerList()
Constructs the list.
|
AbstractBlockIntegerList(IntegerListBlockInterface[] blocks)
Constructs the list from the given set of initial blocks.
|
AbstractBlockIntegerList(IntegerListInterface i_list)
Copies the information from the given BlockIntegerList into a new
object and performs a deep clone of the information in this container.
|
AbstractBlockIntegerList(IntegerVector ivec)
Constructs the list by copying the contents from an IntegerVector.
|
Modifier and Type | Method and Description |
---|---|
void |
add(int val)
Adds an int to the end of the list.
|
void |
add(int val,
int pos)
Adds an int at the given position in the list.
|
void |
checkSorted(IndexComparator c) |
static void |
checkSorted(IntegerIterator iterator,
IndexComparator c) |
boolean |
contains(int val)
Assuming the list is sorted, this performs a binary search and returns
true if the value is found, otherwise returns false.
|
boolean |
contains(Object key,
IndexComparator c)
Assuming the list is sorted, this performs a binary search and returns
true if the value is found, otherwise returns false.
|
protected void |
deleteListBlock(IntegerListBlockInterface list_block)
Called when the class decides this ListBlock is no longer needed.
|
int |
get(int pos)
Returns the int at the given position in the list.
|
void |
insertSort(int val)
Inserts plain 'int' values into the list in sorted order.
|
void |
insertSort(Object key,
int val,
IndexComparator c)
Inserts the key/index pair into the list at the correct sorted position
(determine by the IndexComparator).
|
boolean |
isImmutable()
Returns true if this interface is immutable.
|
IntegerIterator |
iterator()
Returns an IntegerIterator that will walk from the start to the end
this list.
|
IntegerIterator |
iterator(int start_offset,
int end_offset)
Returns an IntegerIterator that will walk from the start offset
(inclusive) to the end offset (inclusive) of this list.
|
protected abstract IntegerListBlockInterface |
newListBlock()
Creates a new ListBlock for the given implementation.
|
int |
remove(int pos)
Removes an int from the given position in the list.
|
protected int |
removeFromBlock(int block_index,
IntegerListBlockInterface block,
int position)
Removes the value from the given position in the specified block.
|
boolean |
removeSort(int val)
Removes a plain 'int' value from the sorted position in the list only if
it's already in the list.
|
int |
removeSort(Object key,
int val,
IndexComparator c)
Removes the key/val pair from the list by first searching for it, and then
removing it from the list.
|
int |
searchFirst(Object key,
IndexComparator c)
Returns the index of the first value in this set that equals the given
value.
|
int |
searchLast(Object key,
IndexComparator c)
Returns the index of the last value in this set that equals the given
value.
|
void |
setImmutable()
Sets the list as immutable (we aren't allowed to change the contents).
|
int |
size()
The number of integers that are in the list.
|
String |
toString() |
boolean |
uniqueInsertSort(int val)
Inserts plain 'int' value into the sorted position in the list only if
it isn't already in the list.
|
protected ArrayList block_list
public AbstractBlockIntegerList()
public AbstractBlockIntegerList(IntegerListBlockInterface[] blocks)
public AbstractBlockIntegerList(IntegerVector ivec)
public AbstractBlockIntegerList(IntegerListInterface i_list)
protected abstract IntegerListBlockInterface newListBlock()
protected void deleteListBlock(IntegerListBlockInterface list_block)
protected final int removeFromBlock(int block_index, IntegerListBlockInterface block, int position)
public final void setImmutable()
setImmutable
in interface IntegerListInterface
public final boolean isImmutable()
isImmutable
in interface IntegerListInterface
public final int size()
size
in interface IntegerListInterface
public final int get(int pos)
get
in interface IntegerListInterface
public final void add(int val, int pos)
add
in interface IntegerListInterface
public final void add(int val)
add
in interface IntegerListInterface
public final int remove(int pos)
remove
in interface IntegerListInterface
public final boolean contains(int val)
We must supply a 'IndexComparator' for how the list is sorted.
contains
in interface IntegerListInterface
public final void insertSort(int val)
insertSort
in interface IntegerListInterface
public final boolean uniqueInsertSort(int val)
uniqueInsertSort
in interface IntegerListInterface
public final boolean removeSort(int val)
removeSort
in interface IntegerListInterface
public final boolean contains(Object key, IndexComparator c)
We must supply a 'IndexComparator' for how the list is sorted.
contains
in interface IntegerListInterface
public final void insertSort(Object key, int val, IndexComparator c)
insertSort
in interface IntegerListInterface
public final int removeSort(Object key, int val, IndexComparator c)
NOTE: There will be a list scan (bad performance) for the erronious case when the key/val pair is not present in the list.
removeSort
in interface IntegerListInterface
public final int searchLast(Object key, IndexComparator c)
searchLast
in interface IntegerListInterface
public final int searchFirst(Object key, IndexComparator c)
searchFirst
in interface IntegerListInterface
public IntegerIterator iterator(int start_offset, int end_offset)
This iterator supports the 'remove' method.
iterator
in interface IntegerListInterface
public IntegerIterator iterator()
This iterator supports the 'remove' method.
iterator
in interface IntegerListInterface
public void checkSorted(IndexComparator c)
public static void checkSorted(IntegerIterator iterator, IndexComparator c)
Copyright © 2015. All rights reserved.