How to GET a Cup of Coffee

 An interesting article about REST
How to GET a Cup of Coffee

Trie: Second Implementation in Groovy

This is another version of Trie implementation in my previous post. The new one comes with a flag to identify a complete word.

	class Node {
	/*data to be save*/
	def data
	/*child nodes of this node*/
	def children = [:]
	/*any key finshied in this node? (end of a word)*/
	def flag = false
	}
	class Trie {
	/*Root node with empty data - edited*/
	def root = new Node(data:'')
	def insert(key) {
	def node = root
	key.each {
	/*find the relevant child node*/
	def child = node.children[it]
	/*if child does not exist, creates it*/
	if (child == null) {
	child = node.children[it] = new Node(data:it)
	}
	node = child
	}
	/*flag the last node as end of this word*/
	node.flag = true
	}
	def search(key) {
	def node = root
	def x = key.find {
	node = node.children[it]
	/*if the child does not exist, key does not exist in trie*/
	node == null
	}
	/*check if the chain of characters exists AND its a complete word (flag == true)*/
	return x == null && node.flag
	}
	def disply() {
	print(root, '')
	}
	private print(node, prefix) {
	/*if its a complete word, print it*/
	if (node.flag) {
	println "${prefix}${node.data}"
	}
	/*visit children, to find rest of words*/
	node.children.values().each {
	print(it, prefix + node.data)
	}
	}
	}
	def t = new Trie()
	t.insert("trie")
	t.insert("tree")
	t.insert("i")
	t.insert("it")
	t.insert("ite")
	assert false == t.search("t")
	assert false == t.search("tr")
	assert false == t.search("tri")
	assert true == t.search("trie")
	assert false == t.search("tre")
	assert true == t.search("tree")
	assert true == t.search("i")
	assert true == t.search("it")
	assert true == t.search("ite")
	assert false == t.search("triex")
	assert false == t.search("treexx")
	assert false == t.search("ix")
	t.disply()

view raw gistfile1.groovy hosted with ❤ by GitHub

Groovy : Trie Implementation

From Wikipedia:

In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key it is associated with. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

	class Node {
	/*data to be save*/
	def data
	/*child nodes of this node*/
	def children = [:]
	}
	class Trie {
	/*root node with empty data*/
	def root = new Node(data:'')
	def insert(key) {
	def node = root
	key.each {
	/*find the relevant child node*/
	def child = node.children[it]
	/*if child does not exist, creates it*/
	if (child == null) {
	child = node.children[it] = new Node(data:it)
	}
	node = child
	}
	}
	def search(key) {
	def node = root
	def x = key.find {
	node = node.children[it]
	/*if the child does not exist, key does not exist in trie*/
	node == null
	}
	return x == null
	}
	}
	def t = new Trie()
	t.insert("trie")
	t.insert("tree")
	t.insert("i")
	t.insert("it")
	t.insert("ite")
	assert true == t.search("t")
	assert true == t.search("tr")
	assert true == t.search("tri")
	assert true == t.search("trie")
	assert true == t.search("tre")
	assert true == t.search("tree")
	assert true == t.search("i")
	assert true == t.search("it")
	assert true == t.search("ite")
	assert false == t.search("triex")
	assert false == t.search("treexx")
	assert false == t.search("ix")

view raw gistfile1.groovy hosted with ❤ by GitHub

Introsort implementation by Groovy.

Another groovy homework. this time Introsort.

From Wikipedia :
Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. It is the best of both worlds, with a worst-case O(n log n) runtime and practical performance comparable to quicksort on typical data sets. Since both algorithms it uses are comparison sorts, it too is a comparison sort.

	def introSort(list) {
	// calculate the depth limit.
	def depth = 2 * (int)(Math.log10(list.size()) / Math.log10(2))
	return introLoop(list, depth)
	}
	def introLoop(list, depth) {
	if (list.size() <= 1) {
	return list
	}
	if (depth == 0) {
	return heapSort(list)
	}
	depth--
	//we need to use median of first, last and mid item in the list as pivot.
	def pivot = list[0]
	def partitions = list.groupBy { it <=> list[0] }.withDefault { [] }
	return introLoop(partitions[-1], depth) + partitions[0] + introLoop(partitions[1], depth)
	}
	def heapSort(list) {
	def size = list.size()
	if (size < 2) {
	return list
	}
	/*We need to create a valid binary heap first*/
	heapify(list)
	/*Remove the biggest element in the heap and make sure heap still is valid*/
	(size - 1 .. 1).each {
	/*Remove the biggest element*/
	swap(list, 0, it)
	/*Sift down to make a valid heap*/
	siftDown(list, 0, it - 1)
	}
	return list
	}
	def heapify(list) {
	def size = list.size()
	/*Find the last parent in the heap*/
	def parent = (int)size / 2 - 1
	/*Sift down all parents starting for lowest levels up to root*/
	while (parent != 0) {
	siftDown(list, parent--, size - 1)
	}
	}
	def siftDown(list, start, end) {
	def parent = start
	/*If there is any child for this parent, then check child(s) value to make sure parent is the biggest one*/
	while (parent * 2 + 1 <= end) {
	/*Given p is parent index, left child is in index of p*2 + 1 */
	def leftChild = parent * 2 + 1
	/*Right child is always after left child (if there is any right child)*/
	def rightChild = leftChild + 1
	/*Assume parent is the biggest value*/
	def max = parent
	/*If left child is bigger than parent then left child is a candidate to move up*/
	if (list[leftChild] > list[max]) {
	max = leftChild
	}
	/*If right child is exist its the bigges amoung parent, left and right, then right child needs to move up*/
	if (rightChild <= end && list[rightChild] > list[max]) {
	max = rightChild
	}
	/*If the parent is not the biggest one, swap it with biggest child and continue*/
	if (max != parent) {
	swap(list, parent, max)
	parent = max
	} else {
	break
	}
	}
	}
	def swap(list, i, j) {
	def temp = list[i]
	list[i] = list[j]
	list[j] = temp
	}
	assert [] == introSort([])
	assert [1] == introSort([1])
	assert [1,5] == introSort([5, 1])
	assert [1,2,3,4,5] == introSort([5,1,4,3,2])

view raw gistfile1.groovy hosted with ❤ by GitHub

Log base 2 of an N-bit integer

Another Groovy training post. This time, three different method to find log base 2 of an N-bit integer.

Note: All algorithms and code credits goes to Bit Twiddling Hacks.

	def log2First(v) {
	def r = 0
	while ((v >>= 1) != 0) r++
	return r
	}
	def log2Second(v) {
	def buffer = java.nio.ByteBuffer.allocate(8)
	double d = buffer.putInt(0x43300000).putInt(v).getDouble(0) - 4503599627370496.0
	return (buffer.putDouble(0, d).getInt(0) >> 20) - 0x3FF
	}
	def log2Third(v) {
	def multiplyDeBruijnBitPosition = [
	0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
	8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
	]
	[1,2,4,8,16].each { v |= v >> it }
	return multiplyDeBruijnBitPosition[ (v * 0x07C4ACDD) >> 27 ]
	}
	(1..100).each {
	assert log2First(it) == log2Second(it)
	assert log2Second(it) == log2Third(it)
	}

view raw gistfile1.groovy hosted with ❤ by GitHub

Note: All algorithms and code credits goes to Bit Twiddling Hacks.

Priority Queue - Groovy Implementation

Here it is :), Another data structure, implemented by me in Groovy as part of my Groovy learning practices. Priority Queue.

	class PriorityQueue {
	/*a list to contains the queue elments in a binary heap format*/
	def list = []
	/*Add new item to the queue*/
	def add(item) {
	list.add(item)
	/*After adding new item, we need to re-validate the heap*/
	siftUp(list, 0, list.size() - 1)
	}
	def pop() {
	if (list.isEmpty()) {
	return null
	}
	def size = list.size()
	/*if there are maximum two items in the queue, we just return the first (root) item in the heap*/
	if (size < 3) {
	return list.remove(0)
	}
	/*Remove the first (root) item and move the last item to first place (root) in the list*/
	def item = list[0]
	list[0] = list.remove(size - 1)
	/*Revalidate the heap*/
	siftDown(list, 0, size - 2)
	return item
	}
	def peek() {
	if (list.isEmpty()) {
	return null
	}
	return list[0]
	}
	def isEmpty() {
	return list.isEmpty()
	}
	def size() {
	return list.size()
	}
	private siftDown(list, start, end) {
	def p = start
	while (p * 2 + 1 <= end) {
	/*Find the left side child*/
	def l = p * 2 + 1
	/*Find the right side child*/
	def r = l + 1
	/*Assume parent is the maximum value.*/
	def max = p
	/*If left child is bigger than parrent then keep it as max value*/
	if (list[max] < list[l]) {
	max = l
	}
	/*If right child exist and its bigger than others (parent and left child) then keep it as max value*/
	if (r <= end && list[max] < list[r]) {
	max = r
	}
	/*If parent is the the biggest value, then swap it with the biggest value*/
	if (p != max) {
	def t = list[p]
	list[p] = list[max]
	list[max] = t
	p = max
	} else {
	break
	}
	}
	}
	private siftUp(list, start, end) {
	def c = end
	while (c > start) {
	/*Find the parent node*/
	def p = (int)((end - 1) / 2)
	/*if the parent is less than child, then swap them*/
	if (list[p] < list[c]) {
	def t = list[p]
	list[p] = list[c]
	list[c] = t
	c = p
	} else {
	break
	}
	}
	}
	}
	/****** Test ******/
	def pq = new PriorityQueue()
	assert true == pq.isEmpty(), 'the queue is empty'
	assert 0 == pq.size(), 'the queue size should be 0'
	assert null == pq.peek(), 'the queue is empty, so there should be nothing to peek'
	assert null == pq.pop(), 'the queue is empty, so there should be nothing to pop'
	pq.add(20)
	assert false == pq.isEmpty(), 'quese is not empty anymore, there is one item (20) in the queue'
	assert 1 == pq.size(), 'queue size must be 1'
	assert 20 == pq.peek(), 'highest value in the queue is the 20'
	assert 20 == pq.pop(), 'removing the highest value which is 20'
	assert true == pq.isEmpty(), 'the queue is empty'
	assert 0 == pq.size(), 'the queue size should be 0'
	pq.add(20)
	pq.add(30)
	pq.add(50)
	assert 50 == pq.peek(), 'the highest value must be 50'
	assert 50 == pq.pop(), 'the highest value must be 50'
	pq.add(10)
	assert 30 == pq.peek(), 'the highest value must be 30'
	assert 30 == pq.pop(), 'the highest value must be 30'

view raw gistfile1.groovy hosted with ❤ by GitHub

Quick Sort, My Groovy Implementation

My Groovy Implementation for QuickSort:

	def quickSort(list) {
	/*Make sure there are at least 2 elements in the list*/
	if (list == null || list.size() < 2) {
	return list
	}
	/*break the list to three different groups
	group 1: with elements less than pivot
	group 2: with elements equal to pivot
	group 3: with elements greater than pivot */
	def partitions = list.groupBy { it <=> list[0] }.withDefault { [] }
	/* sort group 1 and 3 and merge them with group 3 */
	return quickSort(partitions[-1]) + partitions[0] + quickSort(partitions[1])
	}
	assert [] == quickSort([])
	assert [1] == quickSort([1])
	assert [1,5] == quickSort([5, 1])
	assert [1,2,3,4,5] == quickSort([5,1,4,3,2])

view raw gistfile1.groovy hosted with ❤ by GitHub

Heap Sort Implementation in Groovy

My Heap Sort Implementation in Groovy :

	def heapSort(list) {
	def size = list.size()
	if (size < 2) {
	return list
	}
	/*We need to create a valid binary heap first*/
	heapify(list)
	/*Remove the biggest element in the heap and make sure heap still is valid*/
	(size - 1 .. 1).each {
	/*Remove the biggest element*/
	swap(list, 0, it)
	/*Sift down to make a valid heap*/
	siftDown(list, 0, it - 1)
	}
	return list
	}
	def heapify(list) {
	def size = list.size()
	/*Find the last parent in the heap*/
	def parent = (int)size / 2 - 1
	/*Sift down all parents starting for lowest levels up to root*/
	while (parent != 0) {
	siftDown(list, parent--, size - 1)
	}
	}
	def siftDown(list, start, end) {
	def parent = start
	/*If there is any child for this parent, then check child(s) value to make sure parent is the biggest one*/
	while (parent * 2 + 1 <= end) {
	/*Given p is parent index, left child is in index of p*2 + 1 */
	def leftChild = parent * 2 + 1
	/*Right child is always after left child (if there is any right child)*/
	def rightChild = leftChild + 1
	/*Assume parent is the biggest value*/
	def max = parent
	/*If left child is bigger than parent then left child is a candidate to move up*/
	if (list[leftChild] > list[max]) {
	max = leftChild
	}
	/*If right child is exist its the bigges amoung parent, left and right, then right child needs to move up*/
	if (rightChild <= end && list[rightChild] > list[max]) {
	max = rightChild
	}
	/*If the parent is not the biggest one, swap it with biggest child and continue*/
	if (max != parent) {
	swap(list, parent, max)
	parent = max
	} else {
	break
	}
	}
	}
	def swap(list, i, j) {
	def temp = list[i]
	list[i] = list[j]
	list[j] = temp
	}
	assert [] == heapSort([])
	assert [1] == heapSort([1])
	assert [1,5] == heapSort([5, 1])
	assert [1,2,3,4,5] == heapSort([5,1,4,3,2])

view raw gistfile1.groovy hosted with ❤ by GitHub

My Merge Sort in Groovy

I'm Learning Groovy :) and This is my groovy implementation of Merge Sort.

	def mergeSort(list) {
	def size = list.size()
	if (size < 2) {
	return list
	} else {
	def m = (int)(size / 2)
	def left = list[0..<m]
	def right = list[m..<size]
	return merge(mergeSort(left), mergeSort(right))
	}
	}
	def merge(left, right) {
	def result = []
	def l = 0
	def r = 0
	def lsize = left.size()
	def rsize = right.size()
	while (l < lsize && r < rsize){
	result.add((left[l] <= right[r]) ? left[l++] : right[r++])
	}
	if (l < lsize) {
	result += left[l..-1]
	}
	if (r < rsize) {
	result += right[r..-1]
	}
	return result
	}
	assert [1,2,3,4,5] == mergeSort([1,5,3,2,4])

view raw gistfile1.groovy hosted with ❤ by GitHub