I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a complexity of $O(\log n)$ or less.
I tried to work around a solution to this problem and created various TreeMaps that has Integer indices and values and vice-versa, and the same with keys.
Just to make it more clear, the indices symbolize the insertion order from the user. So if I had 3 elements then their index values are 0, 1, 2 and if element 0 was deleted then I need to push 1 to 0 and 2 to 1 and a new element would be added with index 2.
My problem is when I remove a key and its value, if I want to insert the next key and value in the right index I have to make sure all the old ones were set back by 1. I don't know how to do it and not to fall into $O(n)$ complexity.
My goal is to use existing data structures and mix them to get this result, please take a look at the methods I implemented as I need those.
What I am asking is how can I create a data structure for keys and values that has the
getIndexByKey methods in it while each method takes $O(\log n)$ or less and the indices change at each deletion.
Is it possible? And if so what is the mixture of Data-structures to create this?