org.vishia.util

Class IndexMultiTableInteger<Type>

java.lang.Object

org.vishia.util.IndexMultiTableInteger<Type>

Type Parameters:

Type -

All Implemented Interfaces:

java.lang.Iterable<Type>, java.util.Map<java.lang.Integer,Type>

public class IndexMultiTableInteger<Type>
extends java.lang.Object
implements java.util.Map<java.lang.Integer,Type>, java.lang.Iterable<Type>

This class contains sorted references of objects with an integer key in tables of a limited size, but more as one table (a tree) if necessary. This class contains the table of objects and the table of key of type integer. The tables are simple arrays of a fix size.
An instance of this class may be either a hyper table which have some children, or it is a end-table of keys and its references. A end table may have a parent, which is a hyper table, and some sibling instances. If there isn't so, only the end-table exists. It is, if the number of objects is less than the max capacity of one table, typical for less data. In that case, the data structure is very simple. Commonly a search process should regard the tree of tables. But the tree is not deep, because it is a square function. With a table of 100 entries, a 2-ary tree may contain up to 10000.
Objects with the same key can stored more as one time.
This concept have some advantages:

• A system of simple arrays for the key and a parallel array of the associated object allows fast search using java.util.Arrays.binarysearch(int[], int). It is a simple algorithm. Only less memory objects are needed. It doesn't need nodes for TreeMap etc. It is a simple layout for fast embedded control applications.
• But using only one array of keys and one array of objects,
  • first, the number of objects are limited or a large portion of memory should be provided,
  • second, if a new object is inserted, and the amount of objects is large, a larger calculation time of System.arraycopy() would be necessary.
• Therefore the portioning in more as one table needs no large memory objects. If the number of objects is increased, a additional new memory object with limited size is necessary - no resize of existing object.
• The calculation time for insertion an object is limited because one table is limited, also if the number of objects is large.
• If thread safety is necessary, only that table should be locked or exclusive copied, which is touched, for a limited time too. So the number of clashes is less. In the time this class doesn't support thread safety, but it is planned in two ways, using synchronized and using the lock free atomic mechanism.
• Using lock free programming, the change of data should be done in an copy of the table. This copy have less memory size.
• The limited number of memory space is convenient for the application in fast real time systems.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	IndexMultiTableInteger.IteratorHelper This class contains the data for a IndexMultiTableInteger.IteratorImpl for one table.
private static class	IndexMultiTableInteger.IteratorImpl<Type> This class is the Iterator for the outer class.

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
private boolean	isHyperBlock True, than obj contains instances of this class too.
private int[]	key Array of keys, there are sorted ascending.
private static int	maxBlock The maximal nr of elements in a block, maximal value of sizeBlock.
private int	modcount modification access counter for Iterator.
private java.lang.Object[]	obj Array of objects appropritate to the keys.
private IndexMultiTableInteger<Type>	parent The parent if it is a child table.
private int	sizeBlock actual number of objects stored in this table.

Constructor Summary

Constructors

Constructor and Description
IndexMultiTableInteger() constructs an empty instance without data.

Method Summary

Modifier and Type	Method and Description
(package private) void	assert1(boolean cond)
private static int	binarySearchFirstKey(int[] a, int fromIndex, int toIndex, int key) Binary search of the element, which is the first with the given key.
(package private) void	check()
void	clear() Delete all content.
boolean	containsKey(java.lang.Object arg0)
boolean	containsValue(java.lang.Object arg0)
java.util.Set<java.util.Map.Entry<java.lang.Integer,Type>>	entrySet()
Type	get(java.lang.Object key2)
boolean	isEmpty()
java.util.Iterator<Type>	iterator()
java.util.Iterator<Type>	iterator(int fromKey)
java.util.Set<java.lang.Integer>	keySet()
Type	put(java.lang.Integer arg0, Type obj1) Put a object in the table.
void	putAll(java.util.Map<? extends java.lang.Integer,? extends Type> arg0)
Type	remove(java.lang.Object arg0)
private static int	separateIn2arrays(IndexMultiTableInteger<?> src, IndexMultiTableInteger<?> left, IndexMultiTableInteger<?> right) separates the src into two arrays with the half size .
int	size()
private void	sortin(int idx, int key1, java.lang.Object obj1)
private static void	sortInSeparated2arrays(int idx, int key1, java.lang.Object obj1, IndexMultiTableInteger<?> src, IndexMultiTableInteger<?> left, IndexMultiTableInteger<?> right) separates the src into two arrays with the half size and sort in the object.
(package private) void	stop()
java.util.Collection<Type>	values()
void	xxxadd(int arg0, Type arg1)
boolean	xxxadd(Type arg0)
boolean	xxxaddAll(java.util.Collection<? extends Type> arg0)
boolean	xxxaddAll(int arg0, java.util.Collection<? extends Type> arg1)
boolean	xxxcontains(java.lang.Object arg0)
boolean	xxxcontainsAll(java.util.Collection<?> arg0)
Type	xxxget(int arg0)
int	xxxindexOf(java.lang.Object arg0)
int	xxxlastIndexOf(java.lang.Object arg0)
java.util.ListIterator<Type>	xxxlistIterator()
java.util.ListIterator<Type>	xxxlistIterator(int arg0)
Type	xxxremove(int arg0)
boolean	xxxremoveAll(java.util.Collection<?> arg0)
boolean	xxxretainAll(java.util.Collection<?> arg0)
Type	xxxset(int arg0, Type arg1)
java.util.List<Type>	xxxsubList(int arg0, int arg1)
java.lang.Object[]	xxxtoArray()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

maxBlock

private static final int maxBlock

The maximal nr of elements in a block, maximal value of sizeBlock. It is the same value as obj.length or key.length.

sizeBlock

private int sizeBlock

actual number of objects stored in this table.

isHyperBlock

private boolean isHyperBlock

True, than obj contains instances of this class too.

modcount

private int modcount

modification access counter for Iterator.

obj

private final java.lang.Object[] obj

Array of objects appropritate to the keys.

key

private final int[] key

Array of keys, there are sorted ascending. The same key can occure some times.

parent

private IndexMultiTableInteger<Type> parent

The parent if it is a child table.

Constructor Detail

IndexMultiTableInteger

public IndexMultiTableInteger()

constructs an empty instance without data.

Method Detail

put

public Type put(java.lang.Integer arg0,
                Type obj1)

Put a object in the table. The key may be ambiguous, a new object with the same key is placed after an containing object with this key. If the table is full, a new table will be created internally.

Specified by:

put in interface java.util.Map<java.lang.Integer,Type>

sortin

private void sortin(int idx,
                    int key1,
                    java.lang.Object obj1)

sortInSeparated2arrays

private static void sortInSeparated2arrays(int idx,
                                           int key1,
                                           java.lang.Object obj1,
                                           IndexMultiTableInteger<?> src,
                                           IndexMultiTableInteger<?> left,
                                           IndexMultiTableInteger<?> right)

separates the src into two arrays with the half size and sort in the object.

Parameters:

idx - Primordially index of the obj in the src array.

key1 - The key value

obj1 - The object

src - The src table

left - The left table. It may be the same as src.

right - The right table.

separateIn2arrays

private static int separateIn2arrays(IndexMultiTableInteger<?> src,
                                     IndexMultiTableInteger<?> left,
                                     IndexMultiTableInteger<?> right)

separates the src into two arrays with the half size .

Parameters:

src - The src table

left - The left table. It may be the same as src.

right - The right table.

Returns:

the first key of the right table.

clear

public void clear()

Delete all content.

Specified by:

clear in interface java.util.Map<java.lang.Integer,Type>

See Also:

Map.clear()

containsKey

public boolean containsKey(java.lang.Object arg0)

Specified by:

containsKey in interface java.util.Map<java.lang.Integer,Type>

containsValue

public boolean containsValue(java.lang.Object arg0)

Specified by:

containsValue in interface java.util.Map<java.lang.Integer,Type>

entrySet

public java.util.Set<java.util.Map.Entry<java.lang.Integer,Type>> entrySet()

Specified by:

entrySet in interface java.util.Map<java.lang.Integer,Type>

get

public Type get(java.lang.Object key2)

Specified by:

get in interface java.util.Map<java.lang.Integer,Type>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<java.lang.Integer,Type>

keySet

public java.util.Set<java.lang.Integer> keySet()

Specified by:

keySet in interface java.util.Map<java.lang.Integer,Type>

putAll

public void putAll(java.util.Map<? extends java.lang.Integer,? extends Type> arg0)

Specified by:

putAll in interface java.util.Map<java.lang.Integer,Type>

size

public int size()

Specified by:

size in interface java.util.Map<java.lang.Integer,Type>

values

public java.util.Collection<Type> values()

Specified by:

values in interface java.util.Map<java.lang.Integer,Type>

xxxadd

public boolean xxxadd(Type arg0)

xxxadd

public void xxxadd(int arg0,
                   Type arg1)

xxxaddAll

public boolean xxxaddAll(java.util.Collection<? extends Type> arg0)

xxxaddAll

public boolean xxxaddAll(int arg0,
                         java.util.Collection<? extends Type> arg1)

xxxcontains

public boolean xxxcontains(java.lang.Object arg0)

xxxcontainsAll

public boolean xxxcontainsAll(java.util.Collection<?> arg0)

xxxget

public Type xxxget(int arg0)

xxxindexOf

public int xxxindexOf(java.lang.Object arg0)

iterator

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

Specified by:

iterator in interface java.lang.Iterable<Type>

iterator

public java.util.Iterator<Type> iterator(int fromKey)

xxxlastIndexOf

public int xxxlastIndexOf(java.lang.Object arg0)

xxxlistIterator

public java.util.ListIterator<Type> xxxlistIterator()

xxxlistIterator

public java.util.ListIterator<Type> xxxlistIterator(int arg0)

xxxremove

public Type xxxremove(int arg0)

xxxremoveAll

public boolean xxxremoveAll(java.util.Collection<?> arg0)

xxxretainAll

public boolean xxxretainAll(java.util.Collection<?> arg0)

xxxset

public Type xxxset(int arg0,
                   Type arg1)

xxxsubList

public java.util.List<Type> xxxsubList(int arg0,
                                       int arg1)

xxxtoArray

public java.lang.Object[] xxxtoArray()

remove

public Type remove(java.lang.Object arg0)

Specified by:

remove in interface java.util.Map<java.lang.Integer,Type>

stop

void stop()

check

void check()

assert1

void assert1(boolean cond)

binarySearchFirstKey

private static int binarySearchFirstKey(int[] a,
                                        int fromIndex,
                                        int toIndex,
                                        int key)

Binary search of the element, which is the first with the given key. The algorithm is modified from the known algorithm (for example in copied from Arrays.binarySearch0(...)) The modification is done because more as one entry with the same key can be existing. The algorithm searches the first occurrence of it.

Parameters:

a - The array

fromIndex - start index, first position

toIndex - end index. exclusive last position in a

key - search key

Returns:

index in a where the key is found exactly the first time (lessest index) or negative number: insertion point index is (-return -1)