Java Program to Implement ConcurrentSkipListMap API

This Java program is to Implement ConcurrentSkipListMap API. A scalable concurrent ConcurrentNavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This class implements a concurrent variant of SkipLists providing expected average log(n) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads.

Here is the source code of the Java program to Implement ConcurrentSkipListMap API. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.Collection;
  2. import java.util.Comparator;
  3. import java.util.HashMap;
  4. import java.util.Iterator;
  5. import java.util.Map;
  6. import java.util.Map.Entry;
  7. import java.util.NavigableSet;
  8. import java.util.Set;
  9. import java.util.SortedMap;
  10. import java.util.concurrent.ConcurrentNavigableMap;
  11. import java.util.concurrent.ConcurrentSkipListMap;
  12.  
  13. public class ConcurrentSkipListMapImpl<K, V>
  14. {
  15.     private ConcurrentSkipListMap<K, V> concurrentSkipListMap;
  16.  
  17.     /**
  18.      * Constructs a new, empty map, sorted according to the natural ordering of
  19.      * the keys.
  20.      **/
  21.     public ConcurrentSkipListMapImpl()
  22.     {
  23.         concurrentSkipListMap = new ConcurrentSkipListMap<K, V>();
  24.     }
  25.  
  26.     /**
  27.      * Constructs a new, empty map, sorted according to the specified
  28.      * comparator.
  29.      **/
  30.     public ConcurrentSkipListMapImpl(Comparator<? super K> comparator)
  31.     {
  32.         concurrentSkipListMap = new ConcurrentSkipListMap<K, V>(comparator);
  33.     }
  34.  
  35.     /**
  36.      * Constructs a new map containing the same mappings as the given map,
  37.      * sorted according to the natural ordering of the keys.
  38.      **/
  39.     public ConcurrentSkipListMapImpl(Map<? extends K, ? extends V> m)
  40.     {
  41.         concurrentSkipListMap = new ConcurrentSkipListMap<K, V>(m);
  42.     }
  43.  
  44.     /**
  45.      * Constructs a new map containing the same mappings and using the same
  46.      * ordering as the specified sorted map.
  47.      **/
  48.     public ConcurrentSkipListMapImpl(SortedMap<K, ? extends V> m)
  49.     {
  50.         concurrentSkipListMap = new ConcurrentSkipListMap<K, V>(m);
  51.     }
  52.  
  53.     /**
  54.      * Returns a key-value mapping associated with the least key greater than or
  55.      * equal to the given key, or null if there is no such key.
  56.      **/
  57.     public Map.Entry<K, V> ceilingEntry(K key)
  58.     {
  59.         return concurrentSkipListMap.ceilingEntry(key);
  60.     }
  61.  
  62.     /**
  63.      * Returns the least key greater than or equal to the given key, or null if
  64.      * there is no such key.
  65.      **/ 
  66.     public K ceilingKey(K key)
  67.     {
  68.         return concurrentSkipListMap.ceilingKey(key);
  69.     }
  70.  
  71.     /** Removes all of the mappings from this map. **/
  72.     public void clear()
  73.     {
  74.         concurrentSkipListMap.clear();
  75.     }
  76.  
  77.     /** Returns a shallow copy of this ConcurrentSkipListMap instance. **/
  78.     public ConcurrentSkipListMap<K, V> clone()
  79.     {
  80.         return concurrentSkipListMap.clone();
  81.     }
  82.  
  83.     /**
  84.      * Returns the comparator used to order the keys in this map, or null if
  85.      * this map uses the natural ordering of its keys.
  86.      **/
  87.     public Comparator<? super K> comparator()
  88.     {
  89.         return concurrentSkipListMap.comparator();
  90.     }
  91.  
  92.     /** Returns true if this map contains a mapping for the specified key. **/
  93.     public boolean containsKey(Object key)
  94.     {
  95.         return concurrentSkipListMap.containsKey(key);
  96.     }
  97.  
  98.     /** Returns true if this map maps one or more keys to the specified value. **/
  99.     public boolean containsValue(Object value)
  100.     {
  101.         return concurrentSkipListMap.containsValue(value);
  102.     }
  103.  
  104.     /** Returns a reverse order NavigableSet view of the keys contained in this map. **/
  105.     public NavigableSet<K> descendingKeySet()
  106.     {
  107.         return concurrentSkipListMap.descendingKeySet();
  108.     }
  109.  
  110.     /** Returns a reverse order view of the mappings contained in this map. **/
  111.     public ConcurrentNavigableMap<K, V> descendingMap()
  112.     {
  113.         return concurrentSkipListMap.descendingMap();
  114.     }
  115.  
  116.     /** Returns a Set view of the mappings contained in this map. **/
  117.     public Set<Map.Entry<K, V>> entrySet()
  118.     {
  119.         return concurrentSkipListMap.entrySet();
  120.     }
  121.  
  122.     /**
  123.      * Returns a key-value mapping associated with the least key in this map, or
  124.      * null if the map is empty.
  125.      **/
  126.     public Map.Entry<K, V> firstEntry()
  127.     {
  128.         return concurrentSkipListMap.firstEntry();
  129.     }
  130.  
  131.     /** Returns the first (lowest) key currently in this map. **/
  132.     public K firstKey()
  133.     {
  134.         return concurrentSkipListMap.firstKey();
  135.     }
  136.  
  137.     /**
  138.      * Returns the greatest key less than or equal to the given key, or null if
  139.      * there is no such key.
  140.      **/
  141.     public K floorKey(K key)
  142.     {
  143.         return concurrentSkipListMap.floorKey(key);
  144.     }
  145.  
  146.     /**
  147.      * Returns the value to which the specified key is mapped, or null if this
  148.      * map contains no mapping for the key.
  149.      **/
  150.     public V get(Object key)
  151.     {
  152.         return concurrentSkipListMap.get(key);
  153.     }
  154.  
  155.     /**
  156.      * Returns a view of the portion of this map whose keys are strictly less
  157.      * than toKey.
  158.      **/
  159.     public ConcurrentNavigableMap<K, V> headMap(K toKey)
  160.     {
  161.         return concurrentSkipListMap.headMap(toKey);
  162.     }
  163.  
  164.     /**
  165.      * Returns a view of the portion of this map whose keys are less than (or
  166.      * equal to, if inclusive is true) toKey.
  167.      **/
  168.     public ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive)
  169.     {
  170.         return concurrentSkipListMap.headMap(toKey, inclusive);
  171.     }
  172.  
  173.     /**
  174.      * Returns a key-value mapping associated with the least key strictly
  175.      * greater than the given key, or null if there is no such key.
  176.      **/
  177.     public Map.Entry<K, V> higherEntry(K key) 
  178.     {
  179.         return concurrentSkipListMap.higherEntry(key);
  180.     }
  181.  
  182.     /**
  183.      * Returns the least key strictly greater than the given key, or null if
  184.      * there is no such key.
  185.      **/
  186.     public K higherKey(K key)
  187.     {
  188.         return concurrentSkipListMap.higherKey(key);
  189.     }
  190.  
  191.     /** Returns a Set view of the keys contained in this map. **/
  192.     public Set<K> keySet()
  193.     {
  194.         return concurrentSkipListMap.keySet();
  195.     }
  196.  
  197.     /**
  198.      * Returns a key-value mapping associated with the greatest key in this map,
  199.      * or null if the map is empty.
  200.      **/
  201.     public Map.Entry<K, V> lastEntry()
  202.     {
  203.         return concurrentSkipListMap.lastEntry();
  204.     }
  205.  
  206.     /** Returns the last (highest) key currently in this map. **/
  207.     public K lastKey()
  208.     {
  209.         return concurrentSkipListMap.lastKey();
  210.     }
  211.  
  212.     /**
  213.      * Returns a key-value mapping associated with the greatest key strictly
  214.      * less than the given key, or null if there is no such key.
  215.      **/
  216.     public Map.Entry<K, V> lowerEntry(K key)
  217.     {
  218.         return concurrentSkipListMap.lowerEntry(key);
  219.     }
  220.  
  221.     /**
  222.      * Returns the greatest key strictly less than the given key, or null if
  223.      * there is no such key.
  224.      **/
  225.     public K lowerKey(K key)
  226.     {
  227.         return concurrentSkipListMap.lowerKey(key);
  228.     }
  229.  
  230.     /** Returns a NavigableSet view of the keys contained in this map. **/
  231.     public NavigableSet<K> navigableKeySet()
  232.     {
  233.         return concurrentSkipListMap.navigableKeySet();
  234.     }
  235.  
  236.     /**
  237.      * Removes and returns a key-value mapping associated with the least key in
  238.      * this map, or null if the map is empty.
  239.      **/
  240.     public Map.Entry<K, V> pollFirstEntry()
  241.     {
  242.         return concurrentSkipListMap.pollFirstEntry();
  243.     }
  244.  
  245.     /**
  246.      * Removes and returns a key-value mapping associated with the greatest key
  247.      * in this map, or null if the map is empty.
  248.      **/
  249.     public Map.Entry<K, V> pollLastEntry()
  250.     {
  251.         return concurrentSkipListMap.pollLastEntry();
  252.     }
  253.  
  254.     /** Associates the specified value with the specified key in this map. **/
  255.     public V put(K key, V value)
  256.     {
  257.         return concurrentSkipListMap.put(key, value);
  258.     }
  259.  
  260.     /** Copies all of the mappings from the specified map to this map. **/
  261.     public void putAll(Map<? extends K, ? extends V> map)
  262.     {
  263.         concurrentSkipListMap.putAll(map);
  264.     }
  265.  
  266.     /** Removes the mapping for this key from this TreeMap if present. **/
  267.     public V remove(Object key)
  268.     {
  269.         return concurrentSkipListMap.remove(key);
  270.     }
  271.  
  272.     /** Replaces the entry for a key only if currently mapped to some value. **/
  273.     public V replace(K key, V value)
  274.     {
  275.         return concurrentSkipListMap.replace(key, value);
  276.     }
  277.  
  278.     /** Replaces the entry for a key only if currently mapped to a given value. **/
  279.     public boolean replace(K key, V oldValue, V newValue)
  280.     {
  281.         return concurrentSkipListMap.replace(key, oldValue, newValue);
  282.     }
  283.  
  284.     /** Returns the number of key-value mappings in this map. **/
  285.     public int size()
  286.     {
  287.         return concurrentSkipListMap.size();
  288.     }
  289.  
  290.     /**
  291.      * Returns a view of the portion of this map whose keys range from fromKey
  292.      * to toKey.
  293.      **/
  294.     public ConcurrentNavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
  295.            K toKey, boolean toInclusive)
  296.     {
  297.         return concurrentSkipListMap.subMap(fromKey, fromInclusive, toKey, toInclusive);
  298.     }
  299.  
  300.     /**
  301.      * Returns a view of the portion of this map whose keys range from fromKey,
  302.      * inclusive, to toKey, exclusive.
  303.      **/
  304.     public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey)
  305.     {
  306.         return concurrentSkipListMap.subMap(fromKey, toKey);
  307.     }
  308.  
  309.     /** Returns a Collection view of the values contained in this map. **/
  310.     public Collection<V> values()
  311.     {
  312.         return concurrentSkipListMap.values();
  313.     }
  314.  
  315.     public static void main(String... arg)
  316.     {
  317.         ConcurrentSkipListMapImpl<Integer, Integer> concurrentSkipListMap
  318.               = new ConcurrentSkipListMapImpl<Integer, Integer>();
  319.         concurrentSkipListMap.put(10, 100);
  320.         concurrentSkipListMap.put(89, -89);
  321.         concurrentSkipListMap.put(45, 345);
  322.         concurrentSkipListMap.put(90, 23);
  323.         Map<Integer, Integer> anotherMap = new HashMap<Integer, Integer>();
  324.         anotherMap.put(34, 9);
  325.         anotherMap.put(23, 00);
  326.         concurrentSkipListMap.putAll(anotherMap);
  327.  
  328.         System.out.println("the key set of the concurrentSkipListMap map is ");
  329.         Set<Integer> keySet = concurrentSkipListMap.keySet();
  330.         Iterator<Integer> itr = keySet.iterator();
  331.         while (itr.hasNext())
  332.         {
  333.             System.out.print(itr.next() + "\t");
  334.         }
  335.         System.out.println();
  336.         System.out.println("the values of the concurrentSkipListMap is ");
  337.         Collection<Integer> collectionValues = concurrentSkipListMap.values();
  338.         itr = collectionValues.iterator();
  339.         while (itr.hasNext())
  340.         {
  341.             System.out.print(itr.next() + "\t");
  342.         }
  343.         System.out.println();
  344.         System.out.println("poll first entry of the map ");
  345.         Map.Entry<Integer, Integer> pollFirstEntry = concurrentSkipListMap.pollFirstEntry();
  346.         System.out.println("key = " + pollFirstEntry.getKey() + " value = " + pollFirstEntry.getValue());
  347.         System.out.println("poll last entry of the map ");
  348.         Map.Entry<Integer, Integer> pollLastEntry = concurrentSkipListMap.pollLastEntry();
  349.         System.out.println("key = " + pollLastEntry.getKey() + " value = " + pollLastEntry.getValue());
  350.         System.out.println("the entry set of the concurrentSkipListMap is ");
  351.         Iterator<Entry<Integer, Integer>> eitr;
  352.         Set<Entry<Integer, Integer>> entrySet = concurrentSkipListMap.entrySet();
  353.         eitr = entrySet.iterator();
  354.         while (eitr.hasNext())
  355.         {
  356.             System.out.println(eitr.next() + "\t");
  357.         }
  358.         System.out.println("the concurrentSkipListMap contains Key 34 :" 
  359.              + concurrentSkipListMap.containsKey(34));
  360.         System.out.println("the  concurrentSkipListMap contains Value 600 :"
  361.              + concurrentSkipListMap.containsValue(600));		
  362.         System.out.println("the size of the concurrentSkipListMap is " + concurrentSkipListMap.size());
  363.         concurrentSkipListMap.clear();
  364.     }
  365. }

$ javac  ConcurrentSkipListMapImpl.java
$ java ConcurrentSkipListMapImpl
the key set of the concurrentSkipListMap map is 
10	23	34	45	89	90	
the values of the concurrentSkipListMap is 
100	0	9	345	-89	23	
poll first entry of the map 
key = 10 value = 100
poll last entry of the map 
key = 90 value = 23
the entry set of the concurrentSkipListMap is 
23=0	
34=9	
45=345	
89=-89	
the concurrentSkipListMap contains Key 34 :true
the  concurrentSkipListMap contains Value 600 :false
the size of the concurrentSkipListMap is 4

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.