Java Tutorial/Collections/TreeMap

Cache Map

/*******************************************************************************
 * Copyright (c) 2007, 2008 IBM Corporation and Others
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *    Hisashi MIYASHITA - initial API and implementation
 *    Kentarou FUKUDA - initial API and implementation
 *******************************************************************************/

import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.SortedMap;
import java.util.TreeMap;
/**
 * Utility class for cache map.
 */
public class CacheMap extends TreeMap<String, Object> {
  private static final long serialVersionUID = 6681131647931821052L;
  private final int maxSize;
  private final int evictSize;
  private final LinkedList<Object> accessList = new LinkedList<Object>();
  /**
   * Constructor of cache map. If the map exceed the maximum size, the
   * key/value sets will be removed from map based on specified evict size.
   * 
   * @param maxSize
   *            maximum size of the map
   * @param evictSize
   *            number of evict object
   */
  public CacheMap(int maxSize, int evictSize) {
    this.maxSize = maxSize;
    this.evictSize = evictSize;
  }
  private void evict() {
    Iterator<Object> it = accessList.iterator();
    for (int i = 0; i < evictSize; i++) {
      if (!it.hasNext())
        return;
      Object key = it.next();
      this.remove(key);
      it.remove();
    }
  }
  private int searchAccessList(Object key) {
    return accessList.indexOf(key);
  }
  private void accessEntry(Object key) {
    int idx = searchAccessList(key);
    if (idx >= 0) {
      accessList.remove(idx);
    }
    accessList.add(key);
  }
  public Object put(String key, Object val) {
    if (size() >= maxSize)
      evict();
    accessEntry(key);
    return super.put(key, val);
  }
  public Object get(Object key) {
    accessEntry(key);
    return super.get(key);
  }
  /**
   * Search a key that starts with the specified prefix from the map, and
   * return the value corresponding to the key.
   * 
   * @param prefix
   *            target prefix
   * @return the value whose key starts with prefix, or null if not available
   */
  public Object matchStartsWith(String prefix) {
    SortedMap<String, Object> smap = super.tailMap(prefix);
    Object okey;
    try {
      okey = smap.firstKey();
    } catch (NoSuchElementException e) {
      return null;
    }
    if (!(okey instanceof String))
      return null;
    String key = (String) okey;
    // System.err.println("MSW:" + key + " / " + prefix);
    if (!key.startsWith(prefix))
      return null;
    return super.get(key);
  }
}

Check if a particular key exists in TreeMap

import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String,String>();
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");
    System.out.println(treeMap.containsKey("1"));
  }
}

Check if a particular value exists in TreeMap

import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String, String>();
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");
    System.out.println(treeMap.containsValue("Three"));
  }
}

Get Head Map from TreeMap

import java.util.SortedMap;
import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String,String> treeMap = new TreeMap<String,String>();
    treeMap.put("1", "One");
    treeMap.put("3", "Three");
    treeMap.put("2", "Two");
    treeMap.put("5", "Five");
    treeMap.put("4", "Four");
    SortedMap sortedMap = treeMap.headMap("3");
    System.out.println("Head Map Contains : " + sortedMap);
  }
}

Get lowest and highest key stored in TreeMap

import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String, String>();
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");    
    treeMap.put("4", "Four");
    treeMap.put("5", "Five");
    System.out.println("Lowest key: " + treeMap.firstKey());
    System.out.println("Highest key: " + treeMap.lastKey());
  }
}

Get Set view of Keys from TreeMap

import java.util.Iterator;
import java.util.TreeMap;
import java.util.Set;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String, String>();
    treeMap.put("1", "One");
    treeMap.put("3", "Three");
    treeMap.put("2", "Two");
    Set st = treeMap.keySet();
    Iterator itr = st.iterator();
    while (itr.hasNext()){
      System.out.println(itr.next());
    }
    st.remove("1");
    System.out.println(treeMap.containsKey("1"));
  }
}

Get Sub Map from TreeMap

import java.util.SortedMap;
import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String, String>();
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");
    treeMap.put("4", "Four");
    treeMap.put("5", "Five");    
    SortedMap sortedMap = treeMap.subMap("2", "5");
    System.out.println("SortedMap Contains : " + sortedMap);
  }
}

Get Synchronized Map from TreeMap

import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap treeMap = new TreeMap();
    Map map = Collections.synchronizedMap(treeMap);
  }
}

Get Tail Map from TreeMap

import java.util.SortedMap;
import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String,String>();
    treeMap.put("1", "One");
    treeMap.put("3", "Three");
    treeMap.put("2", "Two");
    treeMap.put("5", "Five");
    treeMap.put("4", "Four");
    SortedMap sortedMap = treeMap.tailMap("2");
    System.out.println("Tail Map Contains : " + sortedMap);
  }
}

Get TreeMap Size

import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String, String>();
    System.out.println("Size of TreeMap : " + treeMap.size());
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");
    System.out.println("Size of TreeMap after addition : " + treeMap.size());
    treeMap.remove("2");
    System.out.println("Size of TreeMap after removal : " + treeMap.size());
  }
}

Iterate through the values of TreeMap

import java.util.Collection;
import java.util.Iterator;
import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String, String> treeMap = new TreeMap<String,String>();
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");
    Collection c = treeMap.values();
    Iterator itr = c.iterator();
    while (itr.hasNext()){
      System.out.println(itr.next());
    }
  }
}

Remove all values from TreeMap

import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String,String> treeMap = new TreeMap<String,String>();
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");
    treeMap.clear();
    System.out.println(treeMap.size());
  }
}

Remove value from TreeMap

import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    TreeMap<String,String> treeMap = new TreeMap<String,String>();
    treeMap.put("1", "One");
    treeMap.put("2", "Two");
    treeMap.put("3", "Three");
    Object obj = treeMap.remove("2");
    System.out.println(obj + " Removed from TreeMap");
  }
}

TreeMap Class

A TreeMap is a map that maintains its keys ordered within a balanced, red-black tree.

Creating a TreeMap

1. public TreeMap(): creates an empty TreeMap
2. public TreeMap(Map map): the standard copy constructor
3. public TreeMap(Comparator comp): defines a custom sort order
4. public TreeMap(SortedMap map): accepts a SortedMap for an optimized copy constructor

TreeMap<Integer, User defined class>

import java.util.TreeMap;
public class ProductDB {
  public static void main(String[] args) {
    TreeMap<Integer, Product> db = new TreeMap<Integer, Product>();
    db.put(1000, new Product("D", 350));
    db.put(1011, new Product("p", 15.75));
    db.put(1102, new Product("M", 8.50));
    db.put(2023, new Product("A", 150));
    db.put(2034, new Product("T", 9.99));
    System.out.println(db.subMap(1000, 1999) + "\n");
    System.out.println(db.tailMap(1011) + "\n");
    System.out.println(db.headMap(2023));
    System.out.println("First key higher than 2034: " + db.higherKey(2034));
    System.out.println("First key lower than 2034: " + db.lowerKey(2034));
  }
}
class Product {
  String desc;
  double price;
  Product(String desc, double price) {
    this.desc = desc;
    this.price = price;
  }
  public String toString() {
    return "Description=" + desc + ", Price=" + price;
  }
}

Viewing Sub Maps

SortedSet headMap(Object toKey)
SortedSet tailMap(Object fromKey)
SortedSet subMap(Object fromKey, Object toKey)

{key1=value1}

Working with End Points

The firstKey() and lastKey() methods of TreeMap let you quickly access the keys at the end of the map.

If you need to traverse a map backwards(keep getting the last key and the head map before it):

import java.util.TreeMap;
public class MainClass {
  public static void main(String[] a) {
    TreeMap map = new TreeMap();
    map.put("key1", "value1");
    map.put("key2", "value2");
    map.put("key3", "value3");
    if (!map.isEmpty()) {
      Object last = map.lastKey();
      boolean first = true;
      do {
        if (!first) {
          System.out.print(", ");
        }
        System.out.print(last);
        last = map.headMap(last).lastKey();
        first = false;
      } while (last != map.firstKey());
      System.out.println();
    }
  }
}

key3, key2