org.vishia.util

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

java.lang.Object

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

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

Type Parameters:

Type -

All Implemented Interfaces:

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

public class IndexMultiTable<Key extends java.lang.Comparable<Key>,Type>
extends IndexMultiTable_Table<Key,Type>
implements java.util.Map<Key,Type>, java.lang.Iterable<Type>

This class contains sorted references of objects (values) with a sorting key (usual String or Integer) in one or more tables of a defined size.

• This class can be used similar like TreeMap. In opposite to a TreeMap the key need not be unique for all values. More as one value can have the same key. The method get(Object) defined in Map searches the first Object with the given key. The method put(Comparable, Object) replaces an existing value with the same key like defined in Map where the methods add(Comparable, Object), addBefore(Comparable, Object, Object) and append(Comparable, Object) puts the new value with an existing key beside the last existing one.
• There is a method iterator(Comparable) which starts on the first occurrence of the search key or after that key which is one lesser as the key. It iterates both to the end or backward of the whole collection. The user can check the key in the returned Map.Entry whether the key is proper. In this kind a sorted view of a part of the content can be done.
• The container consist of one or more instances of tables which have a limited size. If a table in one instance is filled, two new instances will be created in memory which contains the half amount of elements and the original instance is changed to a hyper table. The size of the instances are equal and less. It means, the search time is less and the memory requirement is constant. In this kind this class is able to use in C programming with a block heap of equal size blocks in an non-dynamic memory management system (long living fast real time system).

The inner class Table contains the table of objects and the table of key of type Comparable. The tables are simple arrays of a fix size.
An instance of Table class may be either a hyper table which have some children, or it is a end-table of keys and its references. An 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 a binary search algorithm. 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
protected class	IndexMultiTable.Entry
protected class	IndexMultiTable.EntrySetIterator
(package private) class	IndexMultiTable.IndexBox
private static class	IndexMultiTable.IteratorHelper<Key extends java.lang.Comparable<Key>,Type> This class contains the data for a IndexMultiTable.IteratorImpl for one table.
protected class	IndexMultiTable.IteratorImpl This class is the Iterator for the outer class.
(package private) static class	IndexMultiTable.KindofAdd
static interface	IndexMultiTable.Provide<Key> This interface is necessary to provide tables and the minimum and maximum value for any user specific type.
private static class	IndexMultiTable.XXXTable<Key extends java.lang.Comparable<Key>,Type> One table contains keys and values in two array lists in sorted order.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) java.util.Set<java.util.Map.Entry<Key,Type>>	entrySet
(package private) Key	maxKey__
(package private) Key	minKey__
private int	modcount modification access counter for Iterator.
(package private) IndexMultiTable.Provide<Key>	provider
static IndexMultiTable.Provide<java.lang.String>	providerString Provider for String keys.
(package private) boolean	shouldCheck
static java.lang.String	sVersion Version, history and license.

Fields inherited from class org.vishia.util.IndexMultiTable_Table

aKeys, aValues, identParent, identParent_, isHyperBlock, ixInParent, maxBlock, parent, rootIdxTable, sizeAll, sizeBlock

Constructor Summary

Constructors

Constructor and Description
IndexMultiTable(IndexMultiTable.Provide<Key> provider) constructs an empty instance without data.

Method Summary

Modifier and Type	Method and Description
void	add(Key key, Type value) Adds the (key - value) pair to the container.
void	addBefore(Key key, Type value, Type valueNext) Adds the (key - value) pair to the container.
void	append(Key key, Type obj) Appends the (key - value) pair to the container.
int	checkIndex() Executes a consistency check.
void	checkTable() Checks the consistency of the table.
void	clear() Delete all content.
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object arg0)
java.util.Set<java.util.Map.Entry<Key,Type>>	entrySet()
Type	get(java.lang.Object keyArg)
boolean	isEmpty()
java.util.ListIterator<Type>	iterator() Returns an iterator over the table.
java.util.ListIterator<Type>	iterator(Key fromKey) Creates an iterator which is placed in the occurrence of the given key.
java.util.Set<Key>	keySet()
Type	put(Key key, Type value) Puts the (key - value) pair to the container.
void	putAll(java.util.Map<? extends Key,? extends Type> m)
Type	remove(java.lang.Object keyArg)
Type	search(Key key) Searches the object with exact this key or the object which's key is the nearest lesser one.
Type	search(Key keyArg, boolean exact, boolean[] retFound) Searches the key in the tables.
void	shouldCheck(boolean val) Enables or disables a check.
int	size()
(package private) void	stop()
java.lang.String	toString()
java.util.Collection<Type>	values()

Methods inherited from class org.vishia.util.IndexMultiTable_Table

binarySearchFirstKey, check, checkTable, clearRestArray, compare, delete, movein, putOrAdd, searchAndSortin, searchbackAndSortin, searchInTables, searchLastAndSortin, sortin

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, 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

sVersion

public static final java.lang.String sVersion

Version, history and license.

• 2017-08-27 Hartmut bugfix: last change ... but if a key was searched which is lesser as the lesses first key, then the aValues[0] should be used as start.
• 2017-08-22 Hartmut bugfix: IndexMultiTable.IteratorImpl has start from the next table instead hyper table with lesser key. Presume it was never tested well.
• 2016-10-15 Hartmut bugfix: because of the root table is instanceof IndexMultiTable, a value in IndexMultiTable_Table.aValues which is type of IndexMultiTable has failed. It was recognized as a sub table with the simple check tableStart.aValues[idx] instanceof IndexMultiTable_Table etc. Now it is checked whether the value is not an instance of IndexMultitable itself. The root table is not the point of quest but a sub table. That is not an instance of IndexMultiTable. On the other hand a sub table is never a user value because IndexMultiTable_Table is package private and not free for usage.
• 2016-10-15 Hartmut bugfix: The usage of IndexMultiTable.super works in Oracle-Java version 8.102, but not in a lesser version. To save compatibility it is avoided. Sometimes a typed meta variable is the better solution in any case.
• 2016-09-25 Hartmut chg: The root element is removed, instead this class extends a Table which is the root table. Only one advantage: 1 level lesser for debug-show of the data. But that may be proper for deep nested trees. For the change: The inner class Table is moved to an own IndexMultiTable_Table class. Some delegate methods are overridden now (clear), therefore super.clear() is called, to prevent circular invocation. No functional changes.
• 2015-11-09 Hartmut bug: put(Comparable, Object) fails in a constellation where insertion in the first child table, Table#splitIntoSibling(int, Comparable, Object) with ix=0. The key was not updated in the parent table. fix: Using Table#setKeyValue(int, Comparable, Object) with check whether it is ix=0 and the parent key should be updated.
• 2015-07-09 Hartmut chg: All methods are synchronized now because instances are used in more as one thread usual. The non-synchronized variant may be a special case. It has some more less calculation time. Idea: Offer non-synchronized methods with special name to save calculation time for applications which's instances are guaranteed not used in more as one thread.
• 2015-07-05 Hartmut bugfix: The calculation of Table#sizeAll was faulty. Table#check() improved, it checks the sizeAll and checks all child tables. Calculation of sizeAll improved.
• 2015-03-07 Hartmut bugfix false instanceof check, sub-tables has not worked.
• 2014-12-21 Hartmut chg structure: Now a Table is an own instance. Improved and simplified.
• 2014-12-20 Hartmut new The iterator is a ListIterator now with ListIterator.hasPrevious() etc. The advantage and usage: Set the iterator to a expected point with iterator(Comparable) and traverse back- and forward. There are some changes in algorithm.
• 2014-01-12 Hartmut chg: IndexMultiTable_Table.sortin(int, Comparable, Object) new Algorithm
• 2014-01-12 Hartmut chg: toString better for viewing, with all keys
• 2013-12-02 Hartmut new: Implementation of remove(Object) was missing, #searchInTables(Comparable, boolean, IndexBox) restructured. It returns the table and index, able to use for internal searching.
• 2013-09-15 Hartmut new: Implementation of IndexMultiTable_Table.delete(int) and IndexMultiTable.EntrySetIterator.remove().
• 2013-09-15 Hartmut chg: rename and public search(Comparable, boolean, boolean[]).
• 2013-09-07 Hartmut chg: put(Comparable, Object) should not create more as one object with the same key. Use add to do so.
• 2013-08-07 Hartmut improved.
• 2013-04-21 Hartmut created, derived from IndexMultiTableInteger.
• 2009-05-08 Hartmut corr/bugfix: IteratorImpl(IndexMultiTableInteger firstTable, int startKey) used in iterator(startkey): If a non-exakt start key is found, the iterator starts from the key after it. If no data are available, hasnext() returns false now. TODO test if one hyperTable contains the same key as the next, some more same keys!
• 2009-04-28 Hartmut new: iterator(key) to start the iterator from a current position. It is the first position with the given key. corr: Some empty methods are signed with xxxName, this methods were come from planned but not implemented interface meditated: implement ListInterface instead Interface to supply getPrevious() to iterate starting from a key forward and backward. corr: binarySearch self implemented, regarding the first occurrence of a key.
• 2009-04-26 Hartmut meditated: Several key types in one file isn't good! The search routines are optimal only if the key type is fix. There are some adequate classes necessary for int, long keys. docu chg: Using of class AllocInBlock to get the size of a block. corr: Now more deepness as 2 tables is programmed and tested. Older versions support only 2 tables. It was 1000000 entries max. with a table size of 1000.
• 2009-03-01 Hartmut new: IndexMultiTableInteger(int size, char type): in preparation of using, functionality not ready yet. planned: Type may be int, long, String, size are able to choose. The arrays should be assigned not as embedded instances in C. new: method get() does anything, not tested in all cases.
• 2007-06-00 Hartmut Created.

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

minKey__

final Key extends java.lang.Comparable<Key> minKey__

maxKey__

final Key extends java.lang.Comparable<Key> maxKey__

provider

final IndexMultiTable.Provide<Key extends java.lang.Comparable<Key>> provider

shouldCheck

boolean shouldCheck

modcount

private int modcount

modification access counter for Iterator.

providerString

public static final IndexMultiTable.Provide<java.lang.String> providerString

Provider for String keys. Used for IndexMultiTable(Provide).

entrySet

java.util.Set<java.util.Map.Entry<Key extends java.lang.Comparable<Key>,Type>> entrySet

Constructor Detail

IndexMultiTable

public IndexMultiTable(IndexMultiTable.Provide<Key> provider)

constructs an empty instance without data.

Method Detail

clear

public void clear()

Delete all content.

Specified by:

clear in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

Overrides:

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

See Also:

Map.clear()

put

public Type put(Key key,
                Type value)

Puts the (key - value) pair to the container. An existing value with the same key will be replaced like described in the interface. If more as one value with this key are existing, the first one will be replaced only.
See add(Comparable, Object) and append(Comparable, Object).

Specified by:

put in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

Parameters:

key -

value -

Returns:

The last value with this key if existing.

add

public void add(Key key,
                Type value)

Adds the (key - value) pair to the container. All existing values with the same key will be retained. If one or some values with the same key are contained in the container already, the new value is placed in a non-defined order with that values. The order depends from the search algorithm. It is the fastest variant to sort in a new value. This method should be used if the order of values with the same key are not regardless.
See put(Comparable, Object) and append(Comparable, Object).

Parameters:

key -

value -

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

shouldCheck

public void shouldCheck(boolean val)

Enables or disables a check.
The method IndexMultiTable_Table.check() (package private) is called whenever a changing operation is done, before and after the operation. It checks the consistency of the table. Because this operation needs calculation time, the flag shouldCheck(boolean) can be set or reset. If the check fails there is a bug in this algorithm. For bugfix in development it is proper to program a check of the current key before the operation and step with the debugger.

Parameters:

val - true enables, false disables the ckeck.

checkIndex

public int checkIndex()

Executes a consistency check. If it fails, an RuntimeException is thrown. Note: set a breakpoint in debugger to the RuntimeException.

Returns:

number of stored elements.

append

public void append(Key key,
                   Type obj)

Appends the (key - value) pair to the container. All existing values with the same key will be retained. If one or some values with the same key are contained in the container already, the new value is placed in order after all other. The values with the same key are sorted by its append order. If some more values with the same key are existing, the searching can be need some calculation time. But the time is less if the table size is less. This method should be used if the order of values with the same key is need.
See put(Comparable, Object) and append(Comparable, Object).

Parameters:

key -

value -

addBefore

public void addBefore(Key key,
                      Type value,
                      Type valueNext)

Adds the (key - value) pair to the container. All existing values with the same key will be retained. The value is placed before the given next value which must have the same key. If the nextValue is not found, the key is placed in a non deterministic order. If some more values with the same key are existing, the searching can be need some calculation time. This method should be used only if that order of values with the same key is need.
See put(Comparable, Object), add(Comparable, Object) and append(Comparable, Object).

Parameters:

key -

value -

containsValue

public boolean containsValue(java.lang.Object arg0)

Specified by:

containsValue in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

entrySet

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

Specified by:

entrySet in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

get

public Type get(java.lang.Object keyArg)

Specified by:

get in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

search

public Type search(Key key)

Searches the object with exact this key or the object which's key is the nearest lesser one. For example if given is "Bx, By, Bz" as keys and "Bya" is searched, the value with the key "By" is returned. The user should check the returned object whether it is matching to the key or whether it is able to use. The found key is unknown outside of this routine but the key or adequate properties should able to get from the returned value.

Parameters:

key -

Returns:

search

public Type search(Key keyArg,
                   boolean exact,
                   boolean[] retFound)

Searches the key in the tables.

Parameters:

keyArg - 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).

retFound - If null then not used. If not null then it must initialized with new boolean[1]. retFound[0] is set to true or false if the key was found or not. Note: If the key is found and the value for this key is null, retFound[0] is set to true. Only with this the containsKey(Object) works probably.

Returns:

The exact found value or the non exact found value with key before. 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.

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

keySet

public java.util.Set<Key> keySet()

Specified by:

keySet in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

size

public int size()

Specified by:

size in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

values

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

Specified by:

values in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

iterator

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

Returns an iterator over the table. Note: The code which uses the iterator may be crimped by a synchronized(...){...} because the table should not be changed.

Specified by:

iterator in interface java.lang.Iterable<Type>

See Also:

Iterable.iterator()

iterator

public java.util.ListIterator<Type> iterator(Key fromKey)

Creates an iterator which is placed in the occurrence of the given key. The ListIterator.previous() is lesser or equal and the ListIterator.next() is greater or equal. If a lesser or greater element is not found then the ListIterator.hasPrevious() and ListIterator.hasNext() returns false. Note: The code which uses the iterator may be crimped by a synchronized(...){...} because the table should not be changed.

Parameters:

fromKey - The start key.

Returns:

remove

public Type remove(java.lang.Object keyArg)

Specified by:

remove in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

Parameters:

keyArg -

Returns:

stop

void stop()

checkTable

public void checkTable()

Checks the consistency of the table. This method is only proper for test of the algorithm and assurance of correctness. The check starts with the top table. It iterates over all children in order of the tables and checks:

• IndexMultiTable_Table.ixInParent and IndexMultiTable_Table.parent of a child hyper table.
• equality of the IndexMultiTable_Table.aKeys[ixInParent] in the parent and IndexMultiTable_Table.aKeys[0] in the child hyper table.
• Order of all sort keys in all tables.
• All not used entries in IndexMultiTable_Table.aKeys should have the IndexMultiTable.Provide.getMaxSortKey() and all not used entries in IndexMultiTable_Table.aValues should have null.

If any error is found, an RuntimeException is invoked. It is recommended to test in a debugger. If the algorithm in this class is correct, the exception should not be invoked.

putAll

public void putAll(java.util.Map<? extends Key,? extends Type> m)

Specified by:

putAll in interface java.util.Map<Key extends java.lang.Comparable<Key>,Type>

toString

public java.lang.String toString()

Overrides:

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