org.vishia.util

Class IndexMultiTable_Table<Key extends java.lang.Comparable<Key>,Type>

java.lang.Object

org.vishia.util.IndexMultiTable_Table<Key,Type>

Type Parameters:

Key -

Type -

Direct Known Subclasses:

IndexMultiTable

class IndexMultiTable_Table<Key extends java.lang.Comparable<Key>,Type>
extends java.lang.Object

One Table for a IndexMultiTable. This is a package-private class only used in IndexMultiTable.

Field Summary

Fields

Modifier and Type	Field and Description
protected Key[]	aKeys Array of all keys.
protected java.lang.Object[]	aValues Array of objects appropriate to the keys.
(package private) int	identParent A identifier number for debugging.
(package private) static int	identParent_
protected boolean	isHyperBlock True, than aValues contains instances of this class too.
(package private) int	ixInParent Index of this table in its parent.
protected static int	maxBlock The maximal nr of elements in a block, maximal value of sizeBlock.
(package private) IndexMultiTable_Table<Key,Type>	parent The parent if it is a child table.
(package private) IndexMultiTable<Key,Type>	rootIdxTable Reference to the root data.
(package private) int	sizeAll actual number of leaf objects stored in the table tree of this and its children.
(package private) int	sizeBlock actual number of objects stored in this table.
static java.lang.String	sVersion Version, history and license.

Constructor Summary

Constructors

Constructor and Description
IndexMultiTable_Table(IndexMultiTable.Provide<Key> provider) constructs an empty root table.
IndexMultiTable_Table(IndexMultiTable<Key,Type> root1) constructs an empty table.

Method Summary

Modifier and Type	Method and Description
private void	addSizeAll(int add) Change the size in this table and in all parents.
private static void	assert1(boolean cond)
(package private) int	binarySearchFirstKey(java.lang.Comparable<Key>[] a, int fromIndex, int toIndex, java.lang.Object key) Binary search of the element, which is the first with the given key.
(package private) int	check()
(package private) Key	checkTable(IndexMultiTable_Table<Key,Type> parentP, Key keyParentP, int ixInParentP, Key keylastP) Checks the consistency of the table.
(package private) void	clear() Delete all content.
(package private) void	clearRestArray(IndexMultiTable_Table<Key,Type> dst) Cleanup the part if aKeys and aValues which are not used.
protected int	compare(java.lang.Comparable<Key> val1, java.lang.Object key) Assures that if val1 is a String, the key is converted toString() before comparison.
private void	correctKey0InParents() Correct the key in the parent if the key on aKeys[0] was changed.
protected void	delete(int ix) Deletes the element on ix in the current table.
(package private) int	movein(IndexMultiTable_Table<Key,Type> src, IndexMultiTable_Table<Key,Type> dst, int ixSrc, int ixDst, int nrof) Moves some elements of the src table in the dst table.
(package private) Type	putOrAdd(Key sortKey, Type value, Type valueNext, IndexMultiTable.KindofAdd kind) Puts or adds an object in the table.
(package private) boolean	searchAndSortin(Key sortkey, Type value, int ixstart, Type valueNext) Sorts in the given value before the given element with the same key forward.
(package private) boolean	searchbackAndSortin(Key sortkey, Type value, int ixstart, Type valueNext) Sorts in the given value before the given element with the same key backward.
(package private) IndexMultiTable_Table<Key,Type>	searchInTables(java.lang.Object key1, boolean exact, IndexMultiTable.IndexBox ixFound) Searches the key in the tables.
(package private) boolean	searchLastAndSortin(Key sortkey, Type value, int ixstart) Sorts in the given value after all other values with the same key.
private void	setKeyValue(int ix, Key key, java.lang.Object value)
(package private) void	sortin(int ix, Key sortkey, java.lang.Object value) inserts the given element into the table at given position.
private IndexMultiTable_Table<Key,Type>	splitIntoSibling(int ix, Key key1, java.lang.Object obj1) Split this table in 2 tables referred from the parent table.
private void	splitTopLevel(int idx, Key key1, java.lang.Object obj1) Splits the top level into 2 child tables and inserts the given element.
java.lang.String	toString()
private void	toString(java.lang.StringBuilder u)

Methods inherited from class java.lang.Object

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

Field Detail

sVersion

public static final java.lang.String sVersion

Version, history and license.

• 2016-09-25 Hartmut new, copied from IndexMultiTable .Table without functional changes.

Copyright/Copyleft: For this source the LGPL Lesser General Public License, published by the Free Software Foundation is valid. It means:

1. You can use this source without any restriction for any desired purpose.
2. You can redistribute copies of this source to everybody.
3. Every user of this source, also the user of redistribute copies with or without payment, must accept this license for further using.
4. But the LPGL is not appropriate for a whole software product, if this source is only a part of them. It means, the user must publish this part of source, but don't need to publish the whole source of the own product.
5. You can study and modify (improve) this source for own using or for redistribution, but you have to license the modified sources likewise under this LGPL Lesser General Public License. You mustn't delete this Copyright/Copyleft inscription in this source file.

If you are intent to use this sources without publishing its usage, you can get a second license subscribing a special contract with the author.

See Also:

Constant Field Values

maxBlock

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

identParent_

static int identParent_

aKeys

protected final Key extends java.lang.Comparable<Key>[] aKeys

Array of all keys. Note: It is the first element to see firstly while debugging.

aValues

protected final java.lang.Object[] aValues

Array of objects appropriate to the keys. It is either a IndexMultiTable_Table if this is a hyper-table, or a Type-instance

sizeBlock

int sizeBlock

actual number of objects stored in this table.

sizeAll

int sizeAll

actual number of leaf objects stored in the table tree of this and its children.

isHyperBlock

protected boolean isHyperBlock

True, than aValues contains instances of this class too.

identParent

final int identParent

A identifier number for debugging.

ixInParent

int ixInParent

Index of this table in its parent.

parent

IndexMultiTable_Table<Key extends java.lang.Comparable<Key>,Type> parent

The parent if it is a child table. The parent is always a hypertable.

rootIdxTable

final IndexMultiTable<Key extends java.lang.Comparable<Key>,Type> rootIdxTable

Reference to the root data.

Constructor Detail

IndexMultiTable_Table

IndexMultiTable_Table(IndexMultiTable.Provide<Key> provider)

constructs an empty root table.

IndexMultiTable_Table

IndexMultiTable_Table(IndexMultiTable<Key,Type> root1)

constructs an empty table.

Method Detail

binarySearchFirstKey

int binarySearchFirstKey(java.lang.Comparable<Key>[] a,
                         int fromIndex,
                         int toIndex,
                         java.lang.Object 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)

compare

protected int compare(java.lang.Comparable<Key> val1,
                      java.lang.Object key)

Assures that if val1 is a String, the key is converted toString() before comparison.

Parameters:

val1 -

key -

Returns:

putOrAdd

Type putOrAdd(Key sortKey,
              Type value,
              Type valueNext,
              IndexMultiTable.KindofAdd kind)

Puts or adds an object in the table. The key may be ambiguous. On adding a new object with the same key is placed after an containing object with this key. On puting that object which is found with the key will be replaces. If the table is full, a new table will be created internally.

searchLastAndSortin

boolean searchLastAndSortin(Key sortkey,
                            Type value,
                            int ixstart)

Sorts in the given value after all other values with the same key.

• If this table has a parent table and the parent table or its parent has a next child with the same key, then this method is started in the parent. It searches the last key in the parent firstly. Therewith it is faster to search the end of entries with this key.
• Elsewhere the last key is searched in this table. Only this table and maybe its children contains the key.
• If this table is not a hyper block, the value is sortin(int, Comparable, Object) after the last found key.
• If this table is a hyper block, the last child table with the same key is entered with this method to continue in the child.

Parameters:

sortkey - The key for sort values.

value -

ixstart - The start index where a this key is found.

Returns:

searchAndSortin

boolean searchAndSortin(Key sortkey,
                        Type value,
                        int ixstart,
                        Type valueNext)

Sorts in the given value before the given element with the same key forward. Starting from the given position all elements where iterate.

Parameters:

sortkey - The key for sort values.

value -

ixstart - The start index where a this key is found.

valueNext - the requested next value.

Returns:

searchbackAndSortin

boolean searchbackAndSortin(Key sortkey,
                            Type value,
                            int ixstart,
                            Type valueNext)

Sorts in the given value before the given element with the same key backward. Starting from the given position all elements where iterate. TODO not ready yet.

Parameters:

sortkey - The key for sort values.

value -

ixstart - The start index where a this key is found.

valueNext - the requested next value.

Returns:

sortin

void sortin(int ix,
            Key sortkey,
            java.lang.Object value)

inserts the given element into the table at given position. If the table is less, it will be split either in an additional sibling or, if it is the top level table, into two new tables under the top table. Split is done with splitIntoSibling(int, Comparable, Object) or splitTopLevel(int, Comparable, Object). If the table is split, the value is inserted in the correct table.

Parameters:

ix - The index position for the actual table where the value should be sorted in.

sortkey - sorting string to insert.

value - value to insert.

splitTopLevel

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

Splits the top level into 2 child tables and inserts the given element. The top level will refer this 2 tables after them. Note: Splitting of sub tables creates 2 tables from one given, another algorithm.

Parameters:

idx -

key1 -

obj1 -

splitIntoSibling

private IndexMultiTable_Table<Key,Type> splitIntoSibling(int ix,
                                                         Key key1,
                                                         java.lang.Object obj1)

Split this table in 2 tables referred from the parent table. This is not applicable for the root table.

Parameters:

ix - if <0 then do not sortin a key, obj1

key1 -

obj1 -

movein

int movein(IndexMultiTable_Table<Key,Type> src,
           IndexMultiTable_Table<Key,Type> dst,
           int ixSrc,
           int ixDst,
           int nrof)

Moves some elements of the src table in the dst table. Note that this method does not need any information of this. It is a static method. Only because Key and Src should be known - the same like the calling instance - this method is not static.

Parameters:

src - The source table

dst - The destination table

ixSrc - Position in src

ixDst - Position in dst

nrof - number of elements to move from src to dst.

Returns:

the number of elements moved inclusively all elements in children, to build sizeAll

clearRestArray

void clearRestArray(IndexMultiTable_Table<Key,Type> dst)

Cleanup the part if aKeys and aValues which are not used. Note: sizeBlock have to be set correctly.

Parameters:

dst - The table where clean up is done.

delete

protected void delete(int ix)

Deletes the element on ix in the current table.

Parameters:

ix -

clear

void clear()

Delete all content.

See Also:

Map.clear()

searchInTables

IndexMultiTable_Table<Key,Type> searchInTables(java.lang.Object key1,
                                               boolean exact,
                                               IndexMultiTable.IndexBox ixFound)

Searches the key in the tables.

Parameters:

key1 - The key

exact - if true then returns null and retFound[0] = false if the key was not found if false then returns the first value at or after the key, see #search(Comparable).

ixFound - should be create newly or initialize. If the key was found, the found is set to true. If the key is not found, the found is not touched. It should be false initially. If the key is found and the value for this key is null, found true. Only with this the #containsKey(Object) works probably. ix is set in any case if this method does not return null.

Returns:

The table where the element is found. null if the key is lesser than all other keys (it should the first position). null if the value for this key is null. null if exact = true and the key is not found.

addSizeAll

private void addSizeAll(int add)

Change the size in this table and in all parents.

Parameters:

add - usual +1 or -1 for add and delete.

correctKey0InParents

private void correctKey0InParents()

Correct the key in the parent if the key on aKeys[0] was changed. This method is invoked on put or delete.

setKeyValue

private void setKeyValue(int ix,
                         Key key,
                         java.lang.Object value)

check

int check()

assert1

private static void assert1(boolean cond)

checkTable

Key checkTable(IndexMultiTable_Table<Key,Type> parentP,
               Key keyParentP,
               int ixInParentP,
               Key keylastP)

Checks the consistency of the table. This method is only proper for test of the algorithm and assurance of correctness.

Parameters:

parentP - The parent of this table or null for the top table.

keyParentP - The key of this table in the parents entry. null for top table.

ixInParentP - The position of this table in the parent's table. -1 for top table.

keylastP - The last key from the walking through the last child, minimal key for top table.

Returns:

The last found key in order of tables.

toString

private void toString(java.lang.StringBuilder u)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object