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 index's in which key's and values were put in like arraylist do just 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 - index's and valuse and vise-versa, and the same with keys.

Just to make it more clear, the Index's symbolize the insertion order from the user. So if I had 3 elements then their index's 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 structure's and mixing them to get this result, please take a look at the methods I implemented as I need those.

I am adding my code for reference, any help would be much appreciated.

Thank you

Tom

Quote:

---

import java.util.Collection;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map;

public class SuperStruct<K,V>
{
private Map<K,V> mInternalKeyToValueMap;//all the keys and their values
private Map<Integer,V> mIndexToValueMap;//index's for values according to the entrance order to
private Map<V,Integer> mValueToIndexMap;//values and their index's
private Map<Integer,K> mIndexToKeyMap;//index's and their keys according to entrance order
private Map<K,Integer> mKeyToIndexMap;//keys and their index's
private int mNextIndex;//index for the data structure according to the order data was received by user

public SuperStruct(){
mInternalKeyToValueMap = new TreeMap<K,V>();
mIndexToValueMap = new TreeMap<Integer,V>();
mValueToIndexMap = new TreeMap <V,Integer>();
mIndexToKeyMap = new TreeMap <Integer, K>();
mKeyToIndexMap = new TreeMap <K,Integer>();
}
public boolean containsKey(Object key) {
boolean containable = mInternalKeyToValueMap.containsKey(key);
return containable;
}

public boolean containsValue(Object value) {
boolean containable = mValueToIndexMap.containsKey(value);
return containable;
}

public V get(Object key) {
if(mInternalKeyToValueMap.containsKey(key)){
V value = mInternalKeyToValueMap.get(key);
return value;
}
return null;
}



public Collection<K> keySet() {

return mInternalKeyToValueMap.keySet();
}
/**
* This method is putting the key and the value in the main TreeMap "mInternalKeyToValueMap", while on the mean time updating 4 other TreeMaps
* with data regarding to the index in which data was received from the user.
* all in all this method runs in complexity of 6*(O(log n)) that sums down to O(log n) cause constants don't calculate over the whole
* Complexity calculation
* In case that a key already had a mapping to it and we overwrite the value we will run in complexity of 11*(O(log n)) which still sums down to O(log n)
* cause constants don't calculate over the whole
*/

public V put(K key, V value) {
if(mValueToIndexMap.containsKey(value))//preventing duplications of value
return value;
if(mInternalKeyToValueMap.containsKey(key)){//when a key already exist in system and we want to overwrite its value
int indexToDelete = mKeyToIndexMap.get(key);//we get the index of the value we over-write
V value1 = mIndexToValueMap.get(indexToDelete);//using this index we get the value
mValueToIndexMap.remove(value1);//we remove the value and its index
mIndexToValueMap.remove(indexToDelete);//we remove the index and its value
}
mInternalKeyToValueMap.put(key, value);//putting the new value for the key in the main TreeMap
mValueToIndexMap.put(value, mNextIndex);//populating the TreeMap of values and their index's - the order we received them from the user
mIndexToValueMap.put(mNextIndex, value);//This TreeMap holds the index's for each value according to the order of insertion by user
mIndexToKeyMap.put(mNextIndex, key);//This TreeMap holds the index's for each key according to the order of insertion by user
mKeyToIndexMap.put(key,mNextIndex);//populating the TreeMap of keys and their index's - the order we received them from the user
++mNextIndex;//advancing the index which mark the insertion order of arguments to structure
return null;

}


public V remove(Object key) {
if(mInternalKeyToValueMap.containsKey(key)==true && (mInternalKeyToValueMap.get(key)!=null))
{
V value = mInternalKeyToValueMap.get(key);
mInternalKeyToValueMap.remove(key);//removing map for the value
int mIndexToRemoveValue = mValueToIndexMap.get(value);//getting the right index to remove the value
mIndexToValueMap.remove(mIndexToRemoveValue);//vacating the value for this index
mIndexToKeyMap.remove(mIndexToRemoveValue);//vacating the key for this index
mKeyToIndexMap.remove(key);//removing a key and index in the keyToIndex Map
mValueToIndexMap.remove(value);//removing a key and index in the ValueToIndex Map
return value;

}
return null;
}


public Collection<V> values() {
return mInternalKeyToValueMap.values();
}

public Collection<V> getStrcutureSorted(){
return mValueToIndexMap.keySet();
}

public V getValueByIndex(int index){//return the index in which the value sits in, if not present null
V value = mIndexToValueMap.get(index);
return value;
}

public Integer getIndexByKey(K key){
Integer returnable = mKeyToIndexMap.get(key);
if(returnable == null)
return -1;
return returnable;


}
public K getKeyByIndex(int index){
return mIndexToKeyMap.get(index);
}
}

---