Boot software development: Collections

Showing posts with label Collections. Show all posts

Navigating Treemap in Java

Treemap in java is A Red-Black tree-based NavigableMap implementation. NavigableMap interface provides some interesting methods to navigate the map. In this article, we will quickly go through those methods.

NavigableMap

NavigableMap provides a method to navigate the map in interesting ways. For instance, rather than getting value stored for a key, we can retrieve the value stored against the smallest key or get the next immediate bigger key for the given key. Following are some of the interesting methods that we will look into. We can see actually these methods are helping us to access the TreeMap on both ends like (get the lowest key, get the highest key), etc.

Important method

lowerkey (key): Returns the greatest key strictly less than the given key, or null if there is no such key
lowerEntry (key): Follows the above and returns the key-value mapping for the key.
floorKey (key): Returns the greatest key less than the given key or equal to the given key, or null if there is no such key
floorEntry (key): Follows the above and returns the key-value mapping for the key.
higherKey (key): Returns the lowest key strictly greater than the given key, or null if there is no such key
higherEntry (key): Follows the above and returns the key-value mapping for the key.
ceilingKey (key): Returns the least key greater than or equal to the given key, or null if there is no such key
ceilingEntry (key): Follows the above and returns the key-value mapping for the key.
firstEntry (): Returns a key-value mapping associated with the least key in this map
lastEntry (): Returns a key-value mapping associated with the highest key in this map
pollFirstEntry (): Remove and returns a key-value mapping associated with the least key in this map
pollLastEntry (): Remove and returns a key-value mapping associated with the highest key in this map

Java Code to see above methods

Create and Populate Map

TreeMap<Integer, String> map = new TreeMap<> ();
map.put(15, "banana");
map.put(16, "apple");

lowerKey and lowerEntry Example

Here when we try with lowerKey(16) it looks for available keys and returns the greatest key lower then 16, in this case it is 15.

key = map.lowerKey(16);
test = map.lowerEntry(16);
System.out.println(key);  //15
System.out.println(test); //banana

floorKey and floorKeyEntry Example

Here when we try with floorKey(16) it looks for available keys and returns the greatest key lower than (or equal to 16), in this case, it is 16.

key = map.floorKey(16);
test = map.floorEntry(16);
System.out.println(key);  //16
System.out.println(test); //apple

higherKey and higherEntry

higher key will return the least key strictly greater than the given key and following the same logic higherEntry will return the key-value pair. Note that in this case, 14 key does not exist in the map

key = map.higherKey(14);
test = map.higherEntry(14);
System.out.println(key);  //15
System.out.println(test); //banana

ceilingKey and ceilingEntry

ceilingKey logic is very similar to higherkey, except the fact that it checks for the least key equal to or greater the given key.

key = map.ceilingKey(16);
test = map.ceilingEntry(16);
System.out.println(key); 			  //16
System.out.println(test.getValue()); //apple

Important Points

Treemap is Red-Black tree-based implementation.
Treemap provides guaranteed log(n) time cost for containsKey(), get(), put(), and remove() .

References

Red Black Tree

Convert Java Set to List

In this article, we will go through 4 different ways to convert java Set to Java List object.

Java Set Object

mySet is the Set object which contains 4 Strings.

Set  mySet = new HashSet(Arrays.asList("Red", "Yellow", "Green", "Blue"));

Using Constructor

List  myList = new ArrayList(mySet);

Using addAll

Using the addAll method we can add all the items in the set to list-objects.

List  myList2 = new ArrayList();
myList2.addAll(mySet);

Using for each

By using for each to loop though all the items in the Set we can add them one by one to the List.

List  myList3 = new ArrayList();
mySet.forEach(a->myList3.add(a));

Using Java Stream

List  myList4 = mySet.stream().collect(Collectors.toList());

Full source code

package myjava.work.general;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class JavaListFromSet {

	public static void main(String[] args) {
		Set<String> mySet = new HashSet<String>(Arrays.asList("Red", "Yellow", "Green", "Blue"));

		// Using Constructor
		List<String> myList = new ArrayList<String>(mySet);
		myList.forEach(a -> System.out.println(a));

		// Using addAll
		List<String> myList2 = new ArrayList<String>();
		myList2.addAll(mySet);
		myList2.forEach(a -> System.out.println(a));

		// Using For Each
		List<String> myList3 = new ArrayList<String>();
		mySet.forEach(a -> myList3.add(a));
		myList3.forEach(a -> System.out.println(a));

		// Using Stream
		List<String> myList4 = mySet.stream().collect(Collectors.toList());
		myList4.forEach(a -> System.out.println(a));

	}
}

What is PriorityQueue

PriorityQueue is a Queue data structure that is available from Java 5. The queue is a FIFO (First In First Out) data structure. In a Queue normally the item we put first will be the one to get out first. So in a Queue, the order in which we add elements to the Queue determines the order in which the elements will come out from the queue(deque). Priority Queue is different in that expect. In PriorityQueue the elements are stored and are ordered by the priority of the elements. Elements with the highest priority are placed at the front of the Queue. When we take out items from the Queue(deque) element from the front of the queue is taken out first, which is an element with the highest priority is taken out first. So In PriorityQueue which item will come out first (deque) does not depend on the order in which elements were added, rather it depends on the priority of the elements. Then how do we assign priority to the elements? It is simple by default the ordering used by PriorityQueu is the natural ordering of the elements (from the front of the queue to back). Meaning smallest item based on the natural ordering is assigned the highest priority. We can also change this behavior by providing a Comparator that is used to order the elements.

java.util.PriorityQueue

In Java java.util.PriorityQueue is the implementation Class. It is an unbounded data structure which can grow as we add more data to it. Internally it uses array to hold the elements. It has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue. The default capacity is 11. PriorityQueue is implemented as Min-Heap, that is element with minimum value is placed at the root of the Heap (front of the queue).

Class Diagram

Following Class diagram depicts Priority Queue in Java.

Constructors

PriorityQueue provides following constructors.

PriorityQueue(): Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering of the elements.
PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
PriorityQueue(int initialCapacity, Comparator comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue(PriorityQueue c): Creates a PriorityQueue containing the elements in the specified priority queue.
PriorityQueue(SortedSet c): Creates a PriorityQueue containing the elements in the specified sorted set.

Important methods

Following are the important methods that are inherited from Queue

peek:Retrieves, but does not remove, the front most element of the queue
poll: Retrieves and removes the front most element of the queue.
offer: add item to the front of the queue.
add: add item to the front of the queue, throws exception if element cannot be added.
remove: remove the front most item from the queue. It throws exception if queue is empty.

Examples

Example 1

Following example creates a priority queue with no argument constructor. Adds 3 items to it. Since we are not passing any Comparator, the items will be sorted based on the natural order. 1 will be at the front of the queue, followed by 2 and 3.
.

 Rear    6, 5, 1   Front

Call peek and pop to see the items it returns. Notice that after calling poll() and then subsequently calling peek() it is returning a different item. As by calling poll() we have already removed the original element from the head of the queue.

//Create a PriorityQueue
Queue pq = new PriorityQueue<>();

//add item to the queue
pq.offer(1);
pq.offer(6);
pq.offer(5);
 
//print the content of the queue
System.out.println("\n Print Priority Queue");
pq.forEach(a->System.out.print(a + ", ")); 1, 6, 5, 
 
System.out.println("\n Peek the head of the queue: " + pq.peek());//1
System.out.println("\n Poll the head of the queue: " + pq.poll());//1
System.out.println("\n Peek the head of the queue: " + pq.peek());//5

Example 2

In this example we create a Priority Queue by supplying the capacity and Comparator Collections.reverseOrder(). This will make the Priority Queue to sort the elements in reverse order. So Highest element is at the front of the queue. This makes the Priority Queue like a Max Heap.

PriorityQueue pq2 = new PriorityQueue(15, Collections.reverseOrder());
pq2.add(1);
pq2.add(6);
pq2.add(5);
System.out.println("Print Priority Queue");
pq2.forEach(a->System.out.print(a + ",") ); 1, 6, 5, 

//print the content of the queue
System.out.println("\nPrint Priority Queue By poll");

System.out.println("\n Peek the head of the queue: " + pq2.peek());//6
System.out.println("\n Poll the head of the queue: " + pq2.poll());//6
System.out.println("\n Peek the head of the queue: " + pq2.peek());//5

Printing content of Queue

Example 3

In this example we see how we can print the content of the Queue.

//Create Queue
PriorityQueue pq1 = new PriorityQueue<>();
//Add 3 items
pq1.add(1);
pq1.add(6);
pq1.add(5);

System.out.println("Print Queue");
pq1.forEach(a->System.out.print(a + ", "));

System.out.println("Print Using Stream");
pq1.stream().forEach(a->System.out.print(a + ", "));

System.out.println("Print Using Iterator");
Iterator it = pq1.iterator();
while(it.hasNext()) {
  System.out.print(it.next() + ", ");
}

Order While Iterating

Order in which the elements will be accessed in the Priority Queue is not guaranteed while iterating it or accessing it though forEach method. Only when we use the method peek() or poll() methods guarantees that the item will be accessed from the front of the queue.

Key Points

Priority Queue is not synchronized.
O(log(n)) time for the enqueuing and dequeuing methods.
Linear time for the remove( ) and contains( ) methods.
Constant time for the peek( ) and size( ) methods.
We can specify the Comparator to manage the ordering of the data in the PriorityQueue.
PriorityQueue cannot contain null value.
While using Iterator or forEach loop does not guarantee any specific order.

References

PriorityQueue Doc.

Iterate over Java MAP

Map is an interface and is a part of the java collections framework. Java collections framework provides a number of Map implementations like HashMap, TreeMap, LinkedHashMap etc. This post contains different ways of traversing through a HashMap, which are given below:

Following section illustrates different ways to traverse the map data. Since map contains key-value data, most of them traverse through the keys and get the corresponding data.

Map initialization

Following code creates instance of a TreeMap and puts 5 key-value pairs to it.

Map map = new TreeMap();
map.put(1,"A");
map.put(3,"C");
map.put(2,"B");
map.put(4,"D");
map.put(5,"E");

Iterator

Traverse using Iterator of the key set.

System.out.println("Print using Iterator");
Iterator it = map.keySet().iterator();

while (it.hasNext()) {
  Integer k = it.next();
  String  v = map.get(k);
  System.out.print( "Key=" + k + " Value=" + v);
}

Forloop

Following code traverse the map by using a for loop on the key set.

//For loop over the keySet
System.out.println("\nPrint using for loop");
for (Integer k : map.keySet()) {
  String  v = map.get(k);
  System.out.print( "Key=" + k + " Value=" + v);
}

Stream

Following code traverse the map using a stream on the key set.

System.out.println("\nPrint using stream");
map.keySet().stream().forEach(key -> {System.out.print ("Key=" + key + " Value=" + map.get(key)); });

forEach

Following code traverse using forEach method. forEach method was introduced in java 8.

System.out.println("\nPrint using forEach");
map.forEach((k, v) ->System.out.print( "Key=" + k + " Value=" + v)) ;

Navigating Treemap in Java

Navigating Treemap in Java

NavigableMap

Java Code to see above methods

References

Convert Java Set to Java List

Convert Java Set to List

PriorityQueue Example in Java

What is PriorityQueue

java.util.PriorityQueue

Class Diagram

Constructors

Important methods

Examples

Printing content of Queue

References

Traverse a Map in Java

Iterate over Java MAP

Popular Posts

Total Pageviews