Package com.mckoi.util

## Class AbstractBlockIntegerList

- java.lang.Object
- - com.mckoi.util.AbstractBlockIntegerList

All Implemented Interfaces:
  `IntegerListInterface`

Direct Known Subclasses:
  `BlockIntegerList`

    public abstract class AbstractBlockIntegerList
    extends java.lang.Object
    implements IntegerListInterface

An implementation of a list of integer values that are stored across an array of blocks. This allows for quicker insertion and deletion of integer values, including other memory saving benefits.

The class works as follows;

1. The list can contain any number of 'int' values.
2. Each value is stored within a block of int's. A block is of finite size.
3. When a block becomes full, int values are moved around until enough space is free. This may be by inserting a new block or by shifting information from one block to another.
4. When a block becomes empty, it is removed.

The benefits of this system are that inserts and deletes are fast even for very large lists. There are no megabyte sized arraycopys. Also, the object could be extended to a version that pages un-used blocks to disk thus saving precious system memory.

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.

Author:
  Tobias Downer

### Field Summary

Fields
`protected java.util.ArrayList` `block_list` The list of blocks (objects in this list are of type 'IntegerListBlockInterface'.

### Constructor Summary

Constructors
`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.

### Method Summary

All Methods Static Methods Instance Methods Abstract Methods Concrete Methods
`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​(java.lang.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​(java.lang.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​(java.lang.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​(java.lang.Object key, IndexComparator c)` Returns the index of the first value in this set that equals the given value.
`int` `searchLast​(java.lang.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.
`java.lang.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.

### Methods inherited from class java.lang.Object

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

### Field Detail

#### block_list

    protected java.util.ArrayList block_list

The list of blocks (objects in this list are of type 'IntegerListBlockInterface'.

### Constructor Detail

#### AbstractBlockIntegerList

    public AbstractBlockIntegerList()

Constructs the list.

#### AbstractBlockIntegerList

    public AbstractBlockIntegerList​(IntegerListBlockInterface[] blocks)

Constructs the list from the given set of initial blocks.

#### AbstractBlockIntegerList

    public AbstractBlockIntegerList​(IntegerVector ivec)

Constructs the list by copying the contents from an IntegerVector.

#### AbstractBlockIntegerList

    public 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.

### Method Detail

#### newListBlock

    protected abstract IntegerListBlockInterface newListBlock()

Creates a new ListBlock for the given implementation.

#### deleteListBlock

    protected void deleteListBlock​(IntegerListBlockInterface list_block)

Called when the class decides this ListBlock is no longer needed. Provided as an event for derived classes to intercept.

#### removeFromBlock

    protected final int removeFromBlock​(int block_index,
                                        IntegerListBlockInterface block,
                                        int position)

Removes the value from the given position in the specified block. It returns the value that used to be at that position.

#### setImmutable

    public final void setImmutable()

Sets the list as immutable (we aren't allowed to change the contents).

Specified by:
  `setImmutable` in interface `IntegerListInterface`

#### isImmutable

    public final boolean isImmutable()

Returns true if this interface is immutable.

Specified by:
  `isImmutable` in interface `IntegerListInterface`

#### size

    public final int size()

The number of integers that are in the list.

Specified by:
  `size` in interface `IntegerListInterface`

#### get

    public final int get​(int pos)

Returns the int at the given position in the list. NOTE: This is not a very fast routine. Certainly a lot slower than IntegerVector intAt.

Specified by:
  `get` in interface `IntegerListInterface`

#### add

    public final void add​(int val,
                          int pos)

Adds an int at the given position in the list.

Specified by:
  `add` in interface `IntegerListInterface`

#### add

    public final void add​(int val)

Adds an int to the end of the list.

Specified by:
  `add` in interface `IntegerListInterface`

#### remove

    public final int remove​(int pos)

Removes an int from the given position in the list. Returns the value that used to be at that position.

Specified by:
  `remove` in interface `IntegerListInterface`

#### contains

    public final 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.

We must supply a 'IndexComparator' for how the list is sorted.

Specified by:
  `contains` in interface `IntegerListInterface`

#### insertSort

    public final void insertSort​(int val)

Inserts plain 'int' values into the list in sorted order.

Specified by:
  `insertSort` in interface `IntegerListInterface`

#### uniqueInsertSort

    public final boolean uniqueInsertSort​(int val)

Inserts plain 'int' value into the sorted position in the list only if it isn't already in the list. If the value is inserted it returns true, otherwise if the value wasn't inserted because it's already in the list, it returns false.

Specified by:
  `uniqueInsertSort` in interface `IntegerListInterface`

#### removeSort

    public final boolean removeSort​(int val)

Removes a plain 'int' value from the sorted position in the list only if it's already in the list. If the value is removed it returns true, otherwise if the value wasn't removed because it couldn't be found in the list, it returns false.

Specified by:
  `removeSort` in interface `IntegerListInterface`

#### contains

    public final boolean contains​(java.lang.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.

We must supply a 'IndexComparator' for how the list is sorted.

Specified by:
  `contains` in interface `IntegerListInterface`

#### insertSort

    public final void insertSort​(java.lang.Object key,
                                 int val,
                                 IndexComparator c)

Inserts the key/index pair into the list at the correct sorted position (determine by the IndexComparator). If the list already contains identical key then the value is put on the end of the set. This way, the sort is stable (the order of identical elements does not change).

Specified by:
  `insertSort` in interface `IntegerListInterface`

#### removeSort

    public final int removeSort​(java.lang.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.

NOTE: There will be a list scan (bad performance) for the erronious case when the key/val pair is not present in the list.

Specified by:
  `removeSort` in interface `IntegerListInterface`

#### searchLast

    public final int searchLast​(java.lang.Object key,
                                IndexComparator c)

Returns the index of the last value in this set that equals the given value.

Specified by:
  `searchLast` in interface `IntegerListInterface`

#### searchFirst

    public final int searchFirst​(java.lang.Object key,
                                 IndexComparator c)

Returns the index of the first value in this set that equals the given value.

Specified by:
  `searchFirst` in interface `IntegerListInterface`

#### iterator

    public 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.

This iterator supports the 'remove' method.

Specified by:
  `iterator` in interface `IntegerListInterface`

#### iterator

    public IntegerIterator iterator()

Returns an IntegerIterator that will walk from the start to the end this list.

This iterator supports the 'remove' method.

Specified by:
  `iterator` in interface `IntegerListInterface`

#### toString

    public java.lang.String toString()

Overrides:
  `toString` in class `java.lang.Object`

#### checkSorted

    public void checkSorted​(IndexComparator c)

#### checkSorted

    public static void checkSorted​(IntegerIterator iterator,
                                   IndexComparator c)