Quants

An interesting documentation about quants, including Emanuel Derman,

starts in Dutch first, but in English later.

http://player.omroep.nl/?aflID=10567577

Java: Sorted List

Sometimes you might have the need for a Java list, that is sorted with every element insertion. If you use a sorted TreeSet, you are stuck with iterators, no random access for elements. If you use an ArrayList, you could call Collections.sort() after every add, but that's not necessarily efficient. Collection.sort() will have to check the order for every element. If your list is long, this might take time.

But here's the trick: if you know your list was already sorted before your insertion, there's no need to re-sort everything again. You can find the proper insertion point with a quick binary search, and insert the new element at the proper position. Voilà, your list is always sorted.

Surprisingly simple to do this in Java:

/** A LinkedList that efficiently sorts itself with every add.
 * 
 * @author apodehl
 *
 */
public class SortedList< T extends Comparable> extends LinkedList
{
  /** Adds this element to the list at the proper sorting position.
   * If the element already exists, don't do anything.
   */
  @Override
  public boolean add(T e)
  {
    if( size()==0 ) {
      
      return super.add(e);
    }
    else {
      
      // find insertion index
      int idx = -Collections.binarySearch(this, e)-1;
      
      if( idx < 0 ) {
        return true; // already added
      }
      
      // add at this position
      super.add(idx, e);
      return true;
    }
  }
}

Java BiMap, BidiMap

After doing some research and trying to find just the right Java Bi-Map, I couldn't find any, so I had to roll my own :-( To my surprise, implementation of a Bi-Maps is not straight-forward, there's not such thing as the 'one Bi-Map functionality'.

The interesting case is this one: say there are mappings A->1 and B->2. What happens once you insert C->2 ?

Will you remove B->2 to ensure uniqueness of keys and values ? (resulting in A->1 and C->2)

or not, resulting in A->1, B->2 and C->2. Please note that in the latter case, there's no well-defined lookup for value "2". Is it B or is it C ?

So what I needed was uniqueness of both keys and values, in all cases, using generics. Here it goes:

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * One possible implementation of a Bi-directional Map.
 * 
 * Note: there are several variations of BiMap, depending on the behaviour of put(k,v)... Is it allowed to have more
 * than one k for one value ?? Modify
 * 
 * @author apodehl
 * 
 * @param 
 * @param 
 */
public class BiMap implements Map
{
  Map keyVal; // maps key->value

  Map valKey; // maps value->key

  public BiMap()
  {
    keyVal = new LinkedHashMap();
    valKey = new LinkedHashMap();
  }

  @Override
  public V put(K key, V val)
  {
    // --- this implementation allows one-to-one ONLY !! ---
    if (valKey.containsKey(val)) {
      keyVal.remove(valKey.get(val));
    }
    if (keyVal.containsKey(key)) {
      valKey.remove(keyVal.get(key));
    }
    // --- remove above if that's not what you want ---

    // 
    valKey.put(val, key);
    return keyVal.put(key, val);
  }

  @Override
  public void putAll(Map< ? extends K, ? extends V> m)
  {
    for (Entry< ? extends K, ? extends V> e : m.entrySet()) {
      put(e.getKey(), e.getValue());
    }
  }

  /**
   * Type-safe get.
   * 
   * @param key
   * @return
   */
  public K getKey(V val)
  {
    return valKey.get(val);
  }

  /**
   * Type-safe get.
   * 
   * @param key
   * @return
   */
  public V getVal(K key)
  {
    return keyVal.get(key);
  }

  @Override
  // unfortunately Map interface isn't type-safe
  public V get(Object key)
  {
    return getVal((K) key);
  }

  /**
   * Type-safe contains.
   * 
   * @param key
   * @return
   */
  public boolean contains(K key)
  {
    if (keyVal == null) return false;
    return keyVal.containsKey(key);
  }

  /**
   * Type-safe containsValue.
   * 
   * @param key
   * @return
   */
  public boolean containsVal(V val)
  {
    if (valKey == null) return false;
    return valKey.containsKey(val);
  }

  // unfortunately Map interface isn't type safe here ..
  @Override
  public boolean containsKey(Object key)
  {
    return contains((K) key);
  }

  // unfortunately Map interface isn't type safe here ..
  @Override
  public boolean containsValue(Object value)
  {
    return containsVal((V) value);
  }

  @Override
  public Set< java.util.Map.Entry> entrySet()
  {
    return keyVal.entrySet();
  }

  @Override
  public boolean isEmpty()
  {
    return keyVal.isEmpty();
  }

  @Override
  public int size()
  {
    return keyVal.size();
  }

  @Override
  public Collection values()
  {
    return keyVal.values();
  }

  public V removeByKey(K key)
  {
    V val = keyVal.remove(key);
    valKey.remove(val);
    return val;
  }

  public K removeByVal(V val)
  {
    K key = valKey.remove(val);
    keyVal.remove(key);
    return key;
  }

  // unfortunately Map interface isn't type-safe
  @Override
  public V remove(Object key)
  {
    return removeByKey((K) key);
  }

  @Override
  public Set keySet()
  {
    return keyVal.keySet();
  }

  @Override
  public void clear()
  {
    keyVal.clear();
    valKey.clear();
  }

  public String toString()
  {
    String s = "BiMap:\n";
    s += "  key->value: " + keyVal.toString();
    s += "\n";
    s += "  value->key: " + valKey.toString();
    return s;
  }

  public static void main(String[] args)
  {

    BiMap biMap = new BiMap();
    biMap.put("A", 1);
    biMap.put("B", 2);
    System.out.println(biMap); // {A=1, B=2}

    biMap.put("C", 2);
    System.out.println(biMap); // {A=1, C=2}

    biMap.removeByVal(1);
    System.out.println(biMap); // {C=2}
  }
}