Wednesday, April 2, 2014

Placeholdered Maps

Placeholdered map is able to associate keys with values. User can add key value pairs into it and ask for data associated with keys. It works exactly as it would work in an ordinary map.

The additional feature is ability to use placeholders. Placeholder knows when it was created and is useful to cheat on order in which data were added into the map. If the user adds data into placeholder, the datastructure behaves as if the data were added when the placeholder was created.

We will create two such structures. First keeps key value pairs and can return last value associated with the key. Value added into placeholder is returned only if user did not added the same key after the placeholder was created. Second returns all values associated with the key in order they were put in. Placeholders can be used to add data in the middle of those lists.

Table Of Contents

Full Code

Datastructures described in this post are available in a github repository.

Key Value Map

Key value store associates keys with values. It is similar to what Map<M, T> interface is supposed to do, except that default map does not support placeholders.

This chapter is split into three parts. First subchapter shows how to use placeholdered key value map. Second explains how the solution works and the last one shows how it is implemented.

Usage & Test Cases
This subchapter shows the most important part of key value map api. Remaining test cases and examples can be found in KeyValueStorageTest class in our sample project.

Map Like
The storage has three basic map like methods add(key, value), getValue(key) and contains(key). Add associates keys with values and get returns last added value associated with key in parameter. Contains returns true only if the structure contains given key.

Otherwise said, the add method overwrites previously added values:
KeyValueStorage<String, String> storage = 
    new KeyValueStorage<String, String>();

storage.add("key", "first");
storage.add("key", "second");
assertTrue(storage.contains("key"));
assertEquals("second", storage.getValue("key"));

Placeholders Basics
The createPlaceholder method creates new placeholder and the add(placeholder, key, value) method adds data into it.

Example:
//Create map with placeholder. Placeholder is above last lock value and below last key value.
KeyValueStorage<String, String> storage = 
    new KeyValueStorage<String, String>();

storage.add("key", "first");
storage.add("lock", "first");

ValuePlaceholder<String, String> placeholder = 
    storage.createPlaceholder();
storage.add("key", "second");

//add data into placeholder
storage.add(placeholder, "key", "placeholder");
storage.add(placeholder, "lock", "placeholder");

//Last key value is above the placeholder, so placeholder left it unchanged. The value of lock changed, because last lock value is below the placeholder.
assertEquals("second", storage.getValue("key"));
assertEquals("placeholder", storage.getValue("lock"));

Placeholders Management
Our map supports basic placeholders management. It is customized to be convenient in less4j, so api described in this section may seem little bit arbitrary. Nevertheless, the final datastructure is easy to modify for anyone with different needs.

A placeholder can be either closed or open and newly created placeholders are considered open. All open placeholders are kept in a list in order they have been created. Structure supports two operations on that list:
  • addToFirstPlaceholder adds data into first open placeholder,
  • closeFirstPlaceholder removes first placeholder from open placeholders list.

Closing only removes the placeholder from open placeholders list. All its data stay in the structure and user still can use it to add additional data.

Create storage with two placeholders and add data into first one:
// create structure with two placeholders
KeyValueStorage<String, String> storage = 
    new KeyValueStorage<String, String>();
storage.add("key", "1");
storage.createPlaceholder();
storage.add("lock", "1");
storage.createPlaceholder();
    
//add data into first placeholder
storage.addToFirstPlaceholder("key", "placeholder");
storage.addToFirstPlaceholder("lock", "placeholder");

//read data
assertEquals("placeholder", storage.getValue("key"));
assertEquals("1", storage.getValue("lock"));

Use the closeFirstPlaceholder method to remove first placeholder from open placeholders list. The addToFirstPlaceholder now adds data into second placeholder:
// close first placeholder - its data are still available
storage.closeFirstPlaceholder();
assertEquals("placeholder", storage.getValue("key")); 
    
//add data into next open placeholder
storage.addToFirstPlaceholder("lock", "second placeholder");
assertEquals("second placeholder", storage.getValue("lock"));

Bulk Modifications
We needed the ability to replace placeholder with content of another storage. The original placeholder will cease to exist. Data and open placeholders from the other storage will take its place.

First, create two storages:
// create storage with one placeholder
KeyValueStorage<String, String> other = 
    new KeyValueStorage<String, String>();
other.add("under", "other placeholder");
other.createPlaceholder();
other.add("above", "other placeholder");
    
// create main storage with one placeholder
KeyValueStorage<String, String> target = 
    new KeyValueStorage<String, String>();
ValuePlaceholder<String, String> holder = target.createPlaceholder();

Then replace the placeholder in target map by content of the other map. Both data and placeholders are moved into the target:
//replace target placeholder
target.replacePlaceholder(holder, other);
//data from other storage are availabe inside main
assertEquals("other placeholder", target.getValue("under"));
assertEquals("other placeholder", target.getValue("above"));

//placeholder from other storage is available
target.addToFirstPlaceholder("under", "later on");
target.addToFirstPlaceholder("above", "later on");
assertEquals("later on", target.getValue("under"));
assertEquals("other placeholder", target.getValue("above"));

Clone
Last requirement was especially important. We needed to clone storages. Each clone must have the same data as the original and placeholders on the same positions. Of course, clone and original storage must also be fully independent from each other.

Create a new storage and clone it:
// create storage with one placeholder
KeyValueStorage<String, String> original = 
    new KeyValueStorage<String, String>();
original.add("key", "original");
original.createPlaceholder();
    
//clone contains the same key value pairs as original storage
KeyValueStorage<String, String> clone = original.clone();
assertEquals("original", clone.getValue("key"));

Storages are independent. Modification in one is not reflected into another:
//modifying original storage will not modify clone
original.add("key", "modified");
original.addToFirstPlaceholder("key", "placeholder");
assertEquals("original", clone.getValue("key"));
    
//clone contain placeholder equivalent to placeholder in original storage
clone.addToFirstPlaceholder("key", "clone has placeholder");
assertEquals("clone has placeholder", clone.getValue("key"));
//modifying it did not changed value in original
assertEquals("placeholder", original.getValue("key"));

Solution
Data are stored in levels. Each level contains either data added to some placeholder or data added between two placeholders. Levels are kept in list in order they have been created.

Datastructure with no placeholders has exactly one level of data and simply passes all calls to that level. When user requests new placeholder, storage creates new level of data and associates it with the placeholder. This new level will be reserved for the placeholder. The storage then creates yet another level on top of it and all following add operations put data to the top level.

Adding data to placeholder is as simple as finding level associated with that placeholder and adding them into it.

Reading data requires us to loop through levels until we find the one containing the key we are searching for. The search has to start at last added level. If it contains the key, then storage returns found value. If it does not, then we check second last level, third last level and so on, until either value is found or all levels are searched.

To sum it up, data are kept in levels and those are searched starting with newest and ending with oldest. The storage adds data only:
  • into level associated with some placeholder,
  • into last level.

That is it.

Implementation
This subchapter shows how the most important key value map methods are implemented. Remaining methods can be found in KeyValueStorage class in our sample project.

Levels
Each level is essentially an ordinary map hidden behind simplified interface:
private static class Level<M, T> implements PubliclyCloneable {

  private Map<M, T> storage = new HashMap<M, T>();

  public void add(M key, T thing) {
    storage.put(key, thing);
  }

  public T getValue(M key) {
    return storage.get(key);
  }

  // ... contains, getAll, toString, etc.

}

The addAll method copy all key value pairs from another level:
public void addAll(Level<M, T> otherLevel) {
  for (Entry<M, T> entry : otherLevel.storage.entrySet()) {
    add(entry.getKey(), entry.getValue());
  }
}

The only slightly interesting method is clone. The default java clone implementation creates shallow clone, so we have to ensure cloned class is independent from original one:
public Level<M, T> clone() {
  try {
    @SuppressWarnings("unchecked")
    Level<M, T> clone = (Level<M, T>) super.clone();
    clone.storage = new HashMap<M, T>(storage);
    return clone;
  } catch (CloneNotSupportedException e) {
    throw new IllegalStateException("Impossible state.");
  }
}

Placeholder Basics
Each placeholder knows its own level:
public static class ValuePlaceholder<M, T> {
  private final Level<M, T> level;

  public ValuePlaceholder(Level<M, T> level) {
    super();
    this.level = level;
  }

}

Add into placeholder method adds data into level associated with that placeholder:
public void add(ValuePlaceholder<M, T> placeholder, M key, T thing) {
  placeholder.level.add(key, thing);
}

Map Like Methods
Level are kept in a list:
public class KeyValueStorage<M, T> {
  private LinkedList<Level<M, T>> levels = new LinkedList<Level<M, T>>();
  // ...
}

Add adds data into the last (top) level:
public void add(M key, T thing) {
  Level<M, T> lastLevel = getLastLevel();
  lastLevel.add(key, thing);
}

private Level<M, T> getLastLevel() {
  if (levels.isEmpty()) {
    return addLevel();
  }

  Level<M, T> lastLevel = levels.peekLast();
  return lastLevel;
}

private Level<M, T> addLevel() {
  levels.add(new Level<M, T>());
  return levels.peekLast();
}

Both contains and getValue methods loop though list of levels and stop when they find stored key value pair. The getValue method needs to loop through them in reverse:
public boolean contains(M key) {
  for (Level<M, T> level : levels) {
    if (level.contains(key))
      return true;
  }
  return false;
}

public T getValue(M key) {
  Iterator<Level<M, T>> di = levels.descendingIterator();
  while (di.hasNext()) {
    Level<M, T> level = di.next();
    if (level.contains(key))
      return level.getValue(key);
  }
  return null;
}

Managing Placeholders
The storage keeps list of open placeholders and list of levels:
private LinkedList<ValuePlaceholder<M, T>> placeholders = 
    new LinkedList<ValuePlaceholder<M, T>>();
private LinkedList<Level<M, T>> levels = 
    new LinkedList<Level<M, T>>();

The create placeholder method needs to create two levels. One is associated with placeholder and another is used for data added into storage later on:
public ValuePlaceholder<M, T> createPlaceholder() {
  // create level and associate it with new placeholder
  ValuePlaceholder<M, T> placeholder = 
      new ValuePlaceholder<M, T>(addLevel());
  placeholders.add(placeholder);
  // add level that will be on top of placeholder
  addLevel();
  return placeholder;
}

private Level<M, T> addLevel() {
  levels.add(new Level<M, T>());
  return levels.peekLast();
}

Close placeholder method removes first placeholder from the list of open placeholders:
public void closeFirstPlaceholder() { 
  placeholders.pop();
}

Replace placeholder method completely replaces the placeholder by all placehoders from the other storage and its level by all other storage levels:
public void replacePlaceholder(ValuePlaceholder<M, T> placeholder, KeyValueStorage<M, T> otherStorage) {
  otherStorage = otherStorage.clone();
  //replace in data
  replace(levels, placeholder.level, otherStorage.levels);
  replace(placeholders, placeholder, otherStorage.placeholders);
}

public static <Q> void replace(List<Q> inList, Q oldElement, List<Q> newElements) {
  int level = inList.indexOf(oldElement);
  inList.remove(level);
  inList.addAll(level, newElements);
}

Clone
Cloning is done in two steps. First, all levels are cloned. Second step creates as many placeholders as the original had. Each has to reference clone of the level original placeholder referenced:
public KeyValueStorage<M, T> clone() {
  try {
    @SuppressWarnings("unchecked")
    KeyValueStorage<M, T> clone = (KeyValueStorage<M, T>) super.clone();
    //clone all levels
    clone.levels = deeplyClonedLinkedList(levels);
    //recreate placeholders - they must reference levels clones
    clone.placeholders = new LinkedList<ValuePlaceholder<M, T>>();
    for (ValuePlaceholder<M, T> placeholder : placeholders) {
      int index = levels.indexOf(placeholder.level);
      Level<M, T> levelClone = clone.levels.get(index);
      clone.placeholders.add(new ValuePlaceholder<M, T>(levelClone));
    }
    return clone;
  } catch (CloneNotSupportedException e) {
    throw new IllegalStateException("Impossible state.");
  }
}

public static <T extends PubliclyCloneable> LinkedList<T> deeplyClonedLinkedList(LinkedList<T> list) {
  LinkedList<T> result = new LinkedList<T>();
  for (T t : list) {
    result.add((T)t.clone());
  }
  return result;
}

Key List Map

Key list store associates each key with a list of values. The get method returns all values associated with the key in parameter. Unless placeholders are used, returned list contains values in the same order they were put it.

The only way to add something in the beginning or the middle of a list is to add it into placeholder. Placeholders know what was in each list when they have been created and add data after last value added below them.

As before, the chapter is split into three parts. First subchapter shows how to use placeholdered key value map. Second explains how the solution works and the last one shows how it is implemented.


Usage & Test Cases
This subchapter shows the most important part of key value map api. Remaining test cases and examples can be found in KeyListStorageTest class in our sample project.

Map Like
There are four map-of-lists like methods add(key, value/list), getValues(key) and contains(key). Add adds value(s) to the end of list associated with the key in parameter. Get returns list of all values added into the key. Finally, contains returns true only if the structure contains given key.

Key values list store holds list of values for each key:
storage.add("key", 1);
storage.add("key", "2");
storage.add("lock", "3");

storage.add("key", "10");
storage.add("lock", "11");

print(storage.get("key")); //prints: 1 2 10
print(storage.get("lock")); //prints: 3 11

Placeholders Basics
The createPlaceholder method creates new placeholder and the add(placeholder, key, value) method adds data into it.

Create placeholder in the middle of key list and in the beginning of the lock list:
storage.add("key", "1");
placeholder = storage.createPlaceholder();
storage.add("key", "2");
storage.add("lock", "3");

//placeholder adds data in the middle of list
storage.add(placeholder, "key", "placeholder");
storage.add(placeholder, "lock", "placeholder");

print(storage.get("key")); //prints: 1 placeholder 2
print(storage.get("lock")); //prints: placeholder 3 

Placeholders Management
Basic placeholders management is exactly the same as in the key value map. A placeholder can be either closed or open and newly created placeholders are considered open. All open placeholders are kept in a list in order they have been created. Structure supports two operations on that list:
  • addToFirstPlaceholder adds data into first open placeholder,
  • closeFirstPlaceholder removes first placeholder from open placeholders list.

As before, closing only removes the placeholder from open placeholders list. All its data stay in the structure and user still can use it to add additional data.
Click to expand

Create storage with two placeholders and add data into first one:
KeyListStorage<String, String> storage = 
    new KeyListStorage<String, String>();
storage.add("key", "1");
storage.createPlaceholder();
storage.add("lock", "1");
storage.createPlaceholder();
    
//add data into first placeholder
storage.addToFirstPlaceholder("key", "placeholder");
storage.addToFirstPlaceholder("lock", "placeholder");

//read data
print(storage.getValues("key"));//prints 1 placeholder
print(storage.getValues("lock"));//prints placeholder 1 

Use the closeFirstPlaceholder method to remove first placeholder from open placeholders list. The addToFirstPlaceholder now adds data into second placeholder:
storage.closeFirstPlaceholder();
print(storage.getValues("key")); //prints 1 placeholder
    
//add data into next open placeholder
storage.addToFirstPlaceholder("lock", "second placeholder");
print(storage.getValues("lock")); //prints placeholder 1 second placeholder

Bulk Modifications
User can replace placeholder by content of another storage. The original placeholder will cease to exist. Data and open placeholders from the other storage will take its place.
Click to expand

First, create two storages:
// create storage with one placeholder
KeyListStorage<String, String> other = 
    new KeyListStorage<String, String>();
other.add("under", "other placeholder");
other.createPlaceholder();
other.add("above", "other placeholder");

// create main storage with one placeholder
KeyListStorage<String, String> target = 
    new KeyListStorage<String, String>();
ListPlaceholder<String, String> holder = 
    target.createPlaceholder();

Then replace the placeholder in target map by content of the other map. Both data and placeholders are moved into the target:
//replace target placeholder
target.replacePlaceholder(holder, other);
//data from other storage are availabe inside main
print(target.getValues("under")); // prints: other placeholder
print(target.getValues("above")); // prints: other placeholder

//placeholder from other storage is available
target.addToFirstPlaceholder("other placeholder", "later on");
target.addToFirstPlaceholder("above", "later on");
print(target.getValues("under")); // prints: other placeholder
print(target.getValues("above")); // prints: later on other placeholder

Clone
Finally, clonnig must work exactly the same way as clonning key value maps. Clone must be fully independet from the original object.
Click to expand

Create new storage and clone it:
// create storage with one placeholder
KeyListStorage<String, String> original = new KeyListStorage<String, String>();
original.createPlaceholder();
original.add("key", "original");

//clone contains the same key value pairs as original storage
KeyListStorage<String, String> clone = original.clone();
assertListsEquals(original.getValues("key"), clone.getValues("key"));

Storages are independent. Modification in one is not reflected into another:
//modifying original storage will not modify clone
original.add("key", "modified");
original.addToFirstPlaceholder("key", "placeholder");
assertOneMemberList("original", clone.getValues("key"));
assertListsEquals(Arrays.asList("placeholder", "original", 
    "modified"), original.getValues("key"));

//placeholder was cloned too
clone.addToFirstPlaceholder("key", "clone has placeholder");
assertListsEquals(Arrays.asList("clone has placeholder", "original"), clone.getValues("key"));

Solution
Key list map is very similar to key value map shown above. Data are stored in levels. Each level contains either data added to some placeholder or data added between two placeholders. Levels are kept in a list List<Level<M, T>>.

Datastructure with no placeholders has exactly one level of data and simply passes all calls to that level. When user requests new placeholder, storage creates new level of data and associates it with the placeholder. This new level will be reserved for the placeholder. The storage then creates yet another level on top of it and all following add operations put data to the top level.

Adding data to placeholder is as simple as finding level associated with that placeholder and adding them into it. Reading data requires slightly more, because we have to loop through all levels and put result together from partial lists.

Implementation
This subchapter shows implementation of the most important key list map methods. Remaining methods can be found in KeyListStorage class in our sample project.

Since the implementation of key list map is extremely similar to the key value map, common parts shown in previous chapter are hidden expandable boxes.

Levels
Levels keep data in Map<M, List<T>> and accessed it via getStoredList method:
private Map<M, List<T>> storage = new HashMap<M, List<T>>();

private List<T> getStoredList(M key) {
  List<T> list = storage.get(key);
  if (list == null) {
    list = new ArrayList<T>();
    storage.put(key, list);
  }
  return list;
}

Accessor methods add, get and contains are fairly straightforward and very similar to those in previous key value map.
Click to expand

public void add(M key, T thing) {
  getStoredList(key).add(thing);
}

public void add(M key, List<T> things) {
  getStoredList(key).addAll(things);
}

public boolean contains(M key) {
  return storage.containsKey(key);
}

public List<T> getValues(M key) {
  return storage.containsKey(key) ? storage.get(key) : 
     new ArrayList<T>();
}

// ... addAll, getAllValues, ...

The only interesting method is clone. The default java clone implementation creates shallow clone, so we have to ensure cloned level is independent from original one. The map the clone must be filled by copies of original lists:
public Level<M, T> clone() {
  try {
    @SuppressWarnings("unchecked")
    Level<M, T> clone = (Level<M, T>) super.clone();
    clone.storage = deeplyClonedMapOfList(storage);
    return clone;
  } catch (CloneNotSupportedException e) {
    throw new IllegalStateException("Impossible state.");
  }
}

public static <K, T> Map<K, List<T>> deeplyClonedMapOfList(Map<K, List<T>> map) {
  Map<K, List<T>> result = new HashMap<K, List<T>>();
  for (Entry<K, List<T>> t : map.entrySet()) {
    result.put(t.getKey(), new ArrayList<T>(t.getValue()));
  }
  return result;
}

Placeholder Basics
Each placeholder keeps reference to its own level and add into placeholder method adds data into it.

The code is almost the same as in the case of key value map:
Click to expand

public static class ListPlaceholder<M, T> {
  private final Level<M, T> level;

  public ListPlaceholder(Level<M, T> level) {
    this.level = level;
  }
}

public void add(ListPlaceholder<M, T> placeholder, M key, List<T> thing) {
  placeholder.level.add(key, thing);
}

Map Like Methods
Level are kept in a list:
LinkedList<Level<M, T>> levels = 
    new LinkedList<Level<M, T>>();

Add adds data into the last (top) level:
Click to expand

public void add(M key, T thing) {
  Level<M, T> lastLevel = getLastLevel();
  lastLevel.add(key, thing);
}

public void add(M key, List<T> thing) {
  Level<M, T> lastLevel = getLastLevel();
  lastLevel.add(key, thing);
}

The contains method loops though list of levels and stops when it finds stored key list pair:
Click to expand

public boolean contains(M key) {
  for (Level<M, T> level : levels) {
    if (level.contains(key))
      return true;
  }
  return false;
}

The getValues method has to go though all levels compose result from partial lists:
public List<T> getValues(M key) {
  LinkedList<T> result = new LinkedList<T>();
  for (Level<M, T> level : levels) {
    result.addAll(level.getValues(key));
  }

  return result;
}

Managing Placeholders
The storage keeps list of open placeholders and list of levels. As before, the create placeholder method needs to create two new levels. One is associated with placeholder and another is used for data added into storage later on.
Click to expand

private LinkedList<Level<M, T>> levels = 
    new LinkedList<Level<M, T>>();
private LinkedList<ListPlaceholder<M, T>> placeholders = 
    new LinkedList<ListPlaceholder<M, T>>();

public ListPlaceholder<M, T> createPlaceholder() {
  ListPlaceholder<M, T> placeholder = 
      new ListPlaceholder<M, T>(addLevel());
  placeholders.add(placeholder);
  // add level that will be on top of placeholder
  addLevel(); 
  return placeholder;
}

private Level<M, T> addLevel() {
  levels.add(new Level<M, T>());
  return levels.peekLast();
}

Close placeholder method removes first placeholder from the list of open placeholders.
Click to expand

public void closeFirstPlaceholder() { 
  placeholders.pop();
}

Replace placeholder method completely replaces the placeholder by all placehoders from the other storage and its level by all other storage levels:
Click to expand

public void replacePlaceholder(ListPlaceholder<M, T> placeholder, KeyListStorage<M, T> otherStorage) {
  otherStorage = otherStorage.clone();
  //replace in data
  replace(levels, placeholder.level, otherStorage.levels);
  replace(placeholders, placeholder, otherStorage.placeholders);
}

private <Q> void replace(List<Q> inList, Q oldElement, LinkedList<Q> newElements) {
  int indx = inList.indexOf(oldElement);
  inList.remove(indx);
  inList.addAll(indx, newElements);
}

Clone
Cloning is done in two steps. First, all levels are cloned. Second step creates as many placeholders as the original had. Each has to reference clone of the level original placeholder referenced.
Click to expand

public KeyListStorage<M, T> clone() {
  try {
    @SuppressWarnings("unchecked")
    KeyListStorage<M, T> clone = 
        (KeyListStorage<M, T>) super.clone();
    //clone all levels
    clone.levels = deeplyClonedLinkedList(levels);
    //recreate placeholders - they must reference levels clones
    clone.placeholders = new LinkedList<ListPlaceholder<M, T>>();
    for (ListPlaceholder<M, T> placeholder : placeholders) {
      int index = levels.indexOf(placeholder.level);
      Level<M, T> levelClone = clone.levels.get(index);
      clone.placeholders.add(new ListPlaceholder<M, T>(levelClone));
    }
    return clone;
  } catch (CloneNotSupportedException e) {
    throw new IllegalStateException("Impossible state.");
  }
}

public static <T extends PubliclyCloneable> LinkedList<T> deeplyClonedLinkedList(LinkedList<T> list) {
  LinkedList<T> result = new LinkedList<T>();
  for (T t : list) {
    result.add((T)t.clone());
  }
  return result;
}

Discussion

As you can see, the contains and get operations need to go through all levels to find data. That is ok for less4j, because we will not need too many placeholders. There are going to be only few of them.

If you need a lot of placeholders, another approach with faster get data methods might be needed. Its disadvantage is that it requires more code and is harder to maintain.

Store all data in one map. No looping is needed inside get data methods, they simply query the map. Each placeholder knows two things for each key:
  • how many elements are stored between it and previous placeholder,
  • how many elements are stored inside this placeholder.

Adding key value pair into placeholder differ for both storages. Both have to count all elements stored under the placeholder. Key value map uses that value to find out whether new key value pair should overwrite the one stored in the global map. Key list map uses it as index of where the data should be put in the stored list.

Initially we used something similar, but we replaced it by solution described in the above post. It is shorter and easier to read.

0 comments:

Post a Comment