Under MIT Licence Copyright (c) 2016 "Vivek Mangla"
An efficient & small algorithm for different types of random insert , delete , retrieve data along with that's implementation on AVL TREE.
A FAST substitute for ArrayList , Array , OBST , AVL TREE , Self Balancing Trees and few other collections in the cases, if index/key collision occurs data shifting is required.
Performs faster in cases where during insertion on pre-occupied index , previous data has to be shifted instead of replacement.
To see how to use , read Client.java file in client package.
Read summmaryOfAlgorithm package to know about algorithm
Do study summaryOfAlgorithm package to understand it's limitations.
::This API is Thread Safe except test package ,if client uses ClientCommunicator.java as in Client.java .
This API is Not Thread Safe if client directly calls functions provided by Service.java .
Why I created this API ?
When you insert data in ,say array, and let us say the index was pre occupied .
Data was present at indexes 3,4,5,6,7,8,12,234,3000... then
Insert at 4 means new indexes will be 3,4,5,6,7,8,9,12,234,3000. i.e. data at 4,5,6,7,8 are being shifted ahead.
eg.:Say data is present at 0,1,2,10,11,56,65,100,2000,2001,2002.
So insert at 0 ,new array will contain data at 0,1,2,3,10,11,56,65,100,2000,2001,2002.
Insert at 56 ,new array will contain data at 0,1,2,3,10,11,56,57,65,100,2000,2001,2002.
Insert at 2002 , new array will contain data at 0,1,2,3,10,11,56,57,65,2000,2001,2002,2003.
Insert at 2004 ,new array will contain data at 0,1,2,3,10,11,56,57,65,2000,2001, 2002,2003,2004.
Also this type of insertion can be somewhere in between MOST of the times and at ends i.e. at 0th index or at LAST index the LEAST.
::To solve such type of insertion problems along with few other different types(will be available in future releases) in less possible time(without much delay other than that of Base Data Structure),URA has been designed.
URA with AVL TREE as base can be used as an alternative to ArrayList , Array , AVL TREE , Self Balancing Trees and few other collections .
::When I tested URA with AVL TREE as base in different cases of Array and OBST(Ordered Binary Search Tree) ,I found it to be faster than both of them in all cases except for one case of Array and that was due to log(n) factor of AVL_TREE (infact,this algo was not designed for the case of insertion on non-repetitive indexes ONLY ).
These test cases were designed by me specifically for Array and OBST i.e. the cases favourable OR unfavourable to both of them.
::Please read these test cases inside Info.java of test package.
These were best , average and worst .
Best Cases are the ones in which Array and OBST will perform fastest among all other test cases.
For Array , best case is ::Firstly insert an element at lastIndex and then insert remaining elements in sequentially increasing order without any repetitive insertion on an index(without any insert on pre-occupied index ) uptill lastIndex-1. and
For OBST ,best case is ::Insert all elements at sequentially increasing index from 0 to lastIndex without any repetitive insertion on an index ( without any insert on pre-occupied index )
Similarly , worst cases are the ones in which array and OBST will perform slowest .
For array , one among them is ::Insert all elements on 0th index.
For OBST , one of them is insert first element at lastIndex and insert rest elements in 2 phases:: In 1st phase , Insert at all even indexes.In 2nd phase , insert at same even indexes as before.
Average case = Insert half elements as in Best case AND Insert other halves as in Worst Case and Vice-Versa.
::On i3 processor with Windows Operating System ,for 10^7 ( 10 million ) elements , URA with AVL TREE as Base proved that ::
*It is faster than OBST in OBST's best , Worst and Average cases by 1 second ,12 seconds and 3 seconds respectively.
*It is faster than Array in Array's Worst and Average Cases by 2876 seconds(47 minutes) and 1128 seconds(18.8 minutes) respectively merely for 10^6 elements.
*It is little bit slow than Array in Array's best case by 6.5 seconds due to log(n) factor of AVL_TREE ... ( remember this algo is not designed for unique insertion i.e. for insertion on non-repetitive indexes ONLY )
::I also named this implementation as VM's Lazy Array or VMLazy Array , just for fun .
This implementation on AVL TREE will give Almost Constant or Almost fixed time complexity of O(log n) in all types of insertions , deletions , retrieval of data , where n = Number of data / element present.
::Limitations :: This algorithm(URA) will work for specific data structures only .Study is going on to find exact properties of those .As this algo. depends upon path traversal properties ,so below are the ones I have concluded till now and all should be fulfilled::
1.)There must be a unique path to reach every element.
2.)There should be a common starting point for all paths.
3.)VMFactor must be updated accordingly in the decision node of index collided path.
DataStructures satisfying above properties and hence compatible with URA are :: LinkedList ( Single and Double ) , BST , AVL TREE .
::I am also developing it further to provide further types of insertions , deletions like if insert on same index :: shift backwards OR re-trigger that insertion to some other point via some algo and much more .
Till Then ENJOY!!