r/javaexamples • • Feb 26 '17

Shuffling Arrays and Lists, and Reservoir Sampling

3 Upvotes

Shuffling Arrays and Lists, and Reservoir Sampling

Shuffle

One beginner problem I see often is how to take an array of numbers in a range, and generate them in a randomized order. Usually the beginner will bang their head on the wall trying to make a loop that tries to insert random numbers in the array, checking each time for duplicates until the array is full. Think shuffling a deck of cards.

Well, the answer is a simple shuffle algorithm. Java has one already in place, Collections.shuffle() which works on Lists, but not primitive arrays. You could use it by converting the array to a list and back to an array, which seems inefficient.

The most common algorithm for shuffle, known in slightly different variations as the Fisher/Yates shuffle or the Knuth shuffle, is actually very simple, and shuffles the array in place in linear time.

The implementation of the shuffle is like this:

public static void shuffle(int[] array) {
    Random rand = new Random();

    // loop through array backwards
    for (int i = array.length - 1; i > 0; i--) {
        // get random number from 0 to current index position
        int j = rand.nextInt(i);

        // if not the same as current index position
        if (j != i) {
            //swap
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

So, we can create an array of the numbers from 0 - 9:

    int[] a = new int[10];
    for (int i = 0; i < 10; i++) {
        a[i] = i;
    }

Or, using Java 8:

    int[] a = IntStream.range(0,10).toArray();

Now, we shuffle it:

    System.out.println(Arrays.toString(a));
    shuffle(a);
    System.out.println(Arrays.toString(a));

Output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 4, 0, 8, 6, 3, 7, 9, 2, 5]

Let's make a generic version to handle arrays of any object type:

public static <E> void shuffle(E[] array) {
    Random rand = new Random();
    for (int i = array.length - 1; i > 0; i--) {
        int j = rand.nextInt(i);
        if (j != i) {
            E temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

And a version that does the same for Lists:

public static <E> void shuffle(List<E> list) {
    Random rand = new Random();
    for (int i = list.size() - 1; i > 0; i--) {
        int j = rand.nextInt(i);
        if (j != i) {
            E temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
        }
    }
}

Reservoir Sampling

What if you need just a smaller, random subset of the entire data? You could just shuffle the array and take the first n items, of course. But what if the data set is very large? What if it is even too large to fit in available memory, or is being streamed from the internet or some other source?

In comes a technique called Reservoir Sampling.

This algorithm is very similar to the shuffle. The steps go as followed:

  1. Create a new array the size of sampleSize as the 'reservoir'

  2. Copy all of the elements from the input array, from 0 to sampleSize into the new array

  3. Loop from sampleSize to the end of the array

  4. Get a random int of range 0 to current position i

  5. If random int is less than sampleSize, replace the element in the 'reservoir' array with the element at the position i in the input array

  6. return the reservoir array

Here is an example for int[] array:

public static int[] sample(int[] array, int sampleSize) {
    if (sampleSize >= array.length) {
        throw new IllegalArgumentException("Sample size must be smaller than full list.");
    }

    Random rand = new Random();

    // create new array to return
    int[] reservoir = new int[sampleSize];

    // copy all the elements from the input array up to sampleSize
    System.arraycopy(array, 0, reservoir, 0, sampleSize);

    // replace elements with gradually decreasing probability
    for (int i = sampleSize; i < array.length; i++) {
        int select = rand.nextInt(i);
        if (select < sampleSize) {
            reservoir[select] = array[i];
        }
    }
    return reservoir;
}

Testing code:

int[] a = new int[10000];
for (int i = 0; i < a.length; i++) {
    a[i] = i;
}

int[] sampled = sample(a, 10);
System.out.println(Arrays.toString(sampled));

Output:

[3466, 7334, 6037, 8728, 579, 5397, 4585, 3660, 7651, 4884]

See the complete code for a generic, List version.

How is this useful

Here are two 'real-world' examples.

For the first one, let's use ol' trusty enable1.txt, a text file with a large collection of English words. We can use reservoir Sampling to get a smaller sample of random words, without having to load and store the entire file in memory:

public static List<String> sampleWordsFromFile(File filename, int sampleSize) {
    List<String> reservoir = new ArrayList<>(sampleSize);
    Random rand = new Random();
    try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
        String input;
        for (int i = 0; i < sampleSize; i++) {
            input = br.readLine();
            if (input == null) {
                throw new IllegalArgumentException("Sample size must be smaller than words in file");
            }
            input = input.split(" ")[0]; // get rid of any more than 1 word
            reservoir.add(input);
        }
        int i = sampleSize;
        while ((input = br.readLine()) != null) {
            int select = rand.nextInt(i);
            if (select < sampleSize) {
                reservoir.set(select, input);
            }
            i++;
        }
    } catch (IOException ioe) {
        ioe.printStackTrace();
    }
    return reservoir;
}

And to test:

    List<String> words = ReservoirSampling.sampleWordsFromFile(new File("enable1.txt"), 20);

    System.out.println(words.stream().collect(Collectors.joining(", ")));

output:

aggrieve, flaunter, denizens, generalized, vulcanisations, upbearer, gundog, preemptor, tungstate, grassily,
focal, pursers, squeaked, enskies, striae, tressure, gynandromorphic, conceptualization, comportment, ornithologists

Another example: Creating a music playlist by walking a file tree.

If you are like me, you have many gigabytes of music on your hard drive. Ever wonder how your music player would make a shuffled list of songs without having to store and index the entire collection? Enter reservoir sampling again.

Code (not including some extra methods/variables you can find in the full code listing):

public static List<String> sampleFileNamesFromPath(Path path, int sampleSize) {
    List<String> reservoir = new ArrayList<>(sampleSize);
    Random rand = new Random();

    // note: pointer is declared at class level so it can be used in an anonymous class
    pointer = 0;
    try {
        Files.walkFileTree(path, new SimpleFileVisitor<Path>(){
            @Override
            public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException {
                String filename = file.getFileName().toString();
                if (isMusicFile(filename)) {
                    if (pointer < sampleSize) {
                        reservoir.add(file.getFileName().toString());
                        pointer++;
                    } else {
                        int select = rand.nextInt(pointer);
                        if (select < sampleSize) {
                            reservoir.set(select, file.getFileName().toString());
                        }
                        pointer++;
                    }
                }
                return super.visitFile(file, attrs);
            }
        });
    } catch (IOException ioe) {
        ioe.printStackTrace();
    }
    return reservoir;
}

Test code:

List<String> songs = ReservoirSampling.sampleFileNamesFromPath(Paths.get("C:/Users/tim/Music"), 100);

songs.forEach(System.out::println);

Sample of output:

11-God Is in the Radio-Queens of the Stone Age.mp3
modest mouse - The Moon and Antarctica - 10 - wild packs of family dogs.mp3
08 I Don't Believe You (She Acts Like We Never Have Met).mp3
05. Itoshisa Wa Fuhai Nitsuki.mp3
13 Skin It Back [Outtake].mp3
10 Blue Veins.mp3
traffic_1973 on the road_03 (sometimes i feel so) unspired.mp3
15 It's A Good Thing We Get Paid To Do This.mp3
(09) [Frank Zappa] Eat That Question.mp3
09 Where It's At.mp3
Dir en Grey-06 GLASS SKIN-UROBOROS [Remastered &amp; Expanded].mp3
07-the grand conjuration.mp3
01 - Alone.mp3
ph161229d1_08_46_Days.flac
2-17 Cortez The Killer.mp3
(08) [Jethro Tull] A Song for Jeffrey (Live At The Stockholm Konserthuset - 9th January 1969) [S....flac
04 Emperor's New Clothes.m4a
traffic_1967 mr fantasy_09 hope i never find me there.mp3
12 In the Highways.mp3
Liquid Tension Experiment - Another Dimension.mp3
...

Here's the full code

Thanks as always for reading!!


r/javaexamples • • Feb 17 '17

Spring Boot Thymeleaf Integration Example

3 Upvotes

r/javaexamples • • Aug 13 '15

A Search Engine for Java Examples

3 Upvotes

r/javaexamples • • Jun 14 '15

Simple Stack and Queue

3 Upvotes

Simple Stack and Queue

Two common implementations of Linked Lists are the Stack and the Queue. The main difference is that a Stack is LIFO - Last In, First Out (Picture a waiting line for an ATM), and a Stack is FIFO - First In, First Out (Picture a stack of plates in the sink).

They are both already available as implementations of LinkedList in java.util, but for educational purposes, we will be making them from scratch.

Both use the same inner class for Node:

/**
 * Inner Node Class
 */
class Node
{
	E value;
	Node next;

	public Node(E value, Node next)
	{
		this.value = value;
		this.next = next;
	}

	@Override
	public String toString()
	{
		return this.value + " ";
	}
}

The Stack

The Stack has three main methods: push(), pop() and peek():

  • push() places a new element at the top of the stack.

  • pop() removes and returns the element at the top of the stack,

  • peek() returns the top element without removing it.

The rest of the methods will be the same for both implementations:

  • clear() clears the list

  • isEmpty() true if list is empty

  • size() number of elements in the list

Here is the code for Stack:

import java.util.NoSuchElementException;

/**
 * Simple Stack
 * @author /u/Philboyd_Studge
 */
public class Stack<E>
{
	private Node root;
	private int length;

	/**
	 * Default - Create empty Stack
	 */
	public Stack()
	{
		root = null;
		length = 0;
	}

	/**
	 * @return length number of elements in the Stack
	 */
	public int size()
	{
		return length;
	}

	/**
	 * @return true if empty
	 */
	public boolean isEmpty()
	{
		return (root==null);
	}

/**
 * 
 */
public void clear()
{
	root = null;
	length = 0;
}
    
	/**
	 * Push an element E onto top of stack
	 * @param value element of type E to be pushed
	 */
	public void push(E value)
	{
		Node node = new Node(value, root);
		root = node;
		length++;
	}

	/**
	 * Pop the top value off of the stack and remove it
	 * @return E element of type E
	 */
	public E pop()
	{
		if (root==null) throw new NoSuchElementException("List is empty.");
		E value = root.value;
		root = root.next;
		length--;
		return value;
	}

	/**
	 * return the element from the top of the stack without removing it
	 * @return E element of type E
	 */
	public E peek()
	{
		if (root==null) throw new NoSuchElementException("List is empty.");
		return root.value;
	}

	/**
	 * Inner Node Class
	 */
	class Node
	{
		E value;
		Node next;

		public Node(E value, Node next)
		{
			this.value = value;
			this.next = next;
		}

		@Override
		public String toString()
		{
			return this.value + " ";
		}
	}

	public static void main(String[] args)
	{
		try
		{
			// test with Integers
			Stack<Integer> s = new Stack<>();
			s.push(34);
			s.push(23);
			s.push(12);
			s.push(99);

			System.out.println(s.pop());
			System.out.println(s.peek());
			System.out.println(s.pop());

			while (!s.isEmpty())
			{
				System.out.println(s.pop());
			}

			// test with objects
			Stack<Person> people = new Stack<>();
			people.push(new Person("Bob jones", 34));
			people.push(new Person("Wilma Flintstone", 999));
			people.push(new Person("Adam West", 69));

			while (!people.isEmpty()) System.out.println(people.pop());

			// throw exception on purpose
			System.out.println(people.peek());
		}
		catch (NoSuchElementException e)
		{
			System.out.println(e.getClass() + " : " + e.getMessage());
		}


	}
}

The Queue

The three main methods of a Queue are add(), poll(), and peek():

  • add() adds a new element to the end of the queue

  • poll() returns and removes the element at the head of the queue

  • peek() returns the element at the head of the queue without removing it.

Here is the code for the Queue:

import java.util.NoSuchElementException;

/**
 * Simple Queue
 * @author /u/Philboyd_Studge
 */
public class Queue<E>
{
	private Node root;
	private Node end;
	private int length;

	/**
	 * Default - create empty Queue
	 */
	public Queue()
	{
		root = null;
		end = null;
		length = 0;
	}

	/**
	 * @return length number of elements E in Queue
	 */
	public int size()
	{
		return length;
	}

	/**
	 * @return true if empty
	 */
	public boolean isEmpty()
	{
		return (root==null);
	}

	/**
	 * 
	 */
	public void clear()
	{
		root = null;
		length = 0;
	}

	/**
	 * @param value element of type E
	 */
	public void add(E value)
	{
		if (root==null)
		{
			// first node
			root = new Node(value, null);
			end = root;
		}
		else
		{
			Node node = new Node(value, null);
			// link current end node to new node
			end.next = node;
			// make new node end node
			end = node;
		}
		length++;
	}

	/**
	 * Remove and return first element in queue
	 * @return E element of type E
	 */
	public E poll()
	{
		if (root==null) throw new NoSuchElementException("List is empty");
		E value = root.value;
		root = root.next;
		length--;
		return value;
	}

	/**
	 * Return first element in queue without removing it
	 * @return E element of type E
	 */
	public E peek()
	{
		if (root==null) throw new NoSuchElementException("List is empty");
		return root.value;
	}

	/**
	 * Inner Node Class
	 */
	class Node
	{
		E value;
		Node next;

		public Node(E value, Node next)
		{
			this.value = value;
			this.next = next;
		}

		@Override
		public String toString()
		{
			return this.value + " ";
		}
	}

	public static void main(String[] args)
	{
		try
		{
			// test with integers
			Queue<Integer> s = new Queue<>();
			s.add(34);
			s.add(23);
			s.add(12);
			s.add(99);

			System.out.println(s.poll());
			System.out.println(s.peek());
			System.out.println(s.poll());

			while (!s.isEmpty())
			{
				System.out.println(s.poll());
			}

			// test with objects
			Queue<Person> people = new Queue<>();
			people.add(new Person("Bob jones", 34));
			people.add(new Person("Wilma Flintstone", 999));
			people.add(new Person("Adam West", 69));

			while (!people.isEmpty()) System.out.println(people.poll());

			// throw exception on purpose
			System.out.println(people.poll());
		}
		catch (NoSuchElementException e)
		{
			System.out.println(e.getClass() + " : " + e.getMessage());
		}
	}
}

r/javaexamples • • Jun 06 '15

Sorted, Singly-Linked List with Iterator

3 Upvotes

Sorted, Singly-Linked List with Iterator

This post here showed you how to implement a sorted doubly-linked list, but today it came up that someone needed a sorted singly-linked list, so I put this together.

A Linked List is a very simple data structure, which consists of Nodes that contain a value, and a pointer to the next node in the list. While normally Linked Lists are used as a Stack or a Queue, with either a LIFO(Last In First Out) or FIFO(First In First Out) order, sometimes they are needed as a automatically sorted list. Elements are automatically sorted as they are added to the list, so it is never more than O(n) time complexity to insert the element.

in this example I have included an example of how to implement the Iterable and Iterator interfaces, which allow the end user to use a For-Each loop.

Here is the code:

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Sorted, Singly Linked List with Iterator
 * @author /u/Philboyd_Studge
 */
public class SList<E extends Comparable<E>> implements Iterable<E>, Iterator<E>
{
	private Node root;
	private int length;

	// for iteration
	private Node current;

	/**
	 * Default Constructor
	 */
	public SList()
	{
		root = null;
		length = 0;
		current = null;
		last = null;
	}

	/**
	 * Returns number of elements in the list.
	 * @return int number of elements
	 */
	public int size()
	{
		return this.length;
	}

	/**
	 * Adds elements to list using Insertion Sort
	 * @param value value of type E
	 */
	public void add(E value)
	{
		if (root==null)
		{
			// list empty, add new root node
			root = new Node(value, null);
		}
		else
		{
			// see if new value is lower than root node
			if (value.compareTo(root.value) < 0)
			{
				Node temp = new Node(root.value, root.next);
				root = new Node(value, temp);
			}
			else
			{
				// loop through list and see where
				// to insert value
				Node lastNode = root;
				Node nextNode = root.next;
				while (nextNode!=null)
				{
					if (value.compareTo(nextNode.value) < 0)
					{
						Node temp = new Node(value, nextNode);
						lastNode.next = temp;
						length++;
						return;
					}
					lastNode = nextNode;
					nextNode = nextNode.next;
				}
				// value is greater than all others, put at end of list
				Node temp = new Node(value, null);
				lastNode.next = temp;
			}
		}
		length++;
	}

	/**
	 * @return true if list is empty
	 */
	public boolean isEmpty()
	{
		return (root==null);
	}

	/**
	 * clears list
	 */
	public void clear()
	{
		length = 0;
		root = null;
		current = null;
	}

	/**
	 * find by value
	 * @param value value of type E
	 * @return Node node found or null if not found
	 */
	private Node find(E value)
	{
		Node each = root;
		while(each!=null)
		{
			if (value.equals(each.value)) return each;
			each = each.next;
		}
		return null;
	}

	/**
	 * removes a node from the list based on value
	 * @param value value of type E
	 */
	public void remove(E value)
	{
		Node found = find(value);
		if (found!=null)
		{
			if (found.equals(root)) 
			{
				root = found.next;
				length--;
				return;
			}
			Node each = root;

			while(each!=null)
			{
				if (found.equals(each.next))
				{
					each.next = found.next;
				}
				each = each.next;
			}
			length--;
		}
	}

	/**
	 * @param value value of type E
	 * @return true if found
	 */
	public boolean contains(E value)
	{
		Node found = find(value);
		if (found == null) return false;
		return true;
	}

	/**
	 * get element's value by index
	 * @param index integer of index to get
	 * @return E value of type E or null if not found
	 */
	public E get(int index)
	{
		if (index < length)
		{
			Node each = root;
			for (int i = 0; i < length; i++)
			{
				if (i == index) return each.value;
				each = each.next;
			}
			return null;		
		}
		return null;
	}

	/**
	 * @return E value of root or null if empty
	 */
	public E getFirst()
	{
		if (!isEmpty()) return root.value;
		return null;
	}

	/**
	 * Implement method for Iterable
	 * @return Iterator of type E
	 */
	@Override
	public Iterator<E> iterator()
	{
		current = root;
		return this;
	}

	/**
	 * Implement method for Iterator
	 * @return E next element's value
	 */
	@Override
	public E next()
	{
		E value = current.value;
		current = current.next;
		return value;
	}

	/**
	 * Implement method for Iterator
	 * @return true if list has more elements
	 */
	@Override
	public boolean hasNext()
	{
		return (current != null);
	}

	/**
	 * Implement method for Iterator
	 * removes most recent element in iterator
	 */
	@Override
	public void remove()
	{
		if (last==null) return;
		remove(last.value);
	}

	/**
	 * @return String of value
	 */
	@Override
	public String toString()
	{
		return current.value.toString();
	}

	/**
	 * Inner class Node
	 */
	class Node
	{
		E value;
		Node next;

		public Node(E value, Node next)
		{
			this.value = value;
			this.next = next;
		}

		@Override
		public String toString()
		{
			return this.value.toString();
		}
	}

	public static void main(String[] args)
	{
		// test with strings
		SList<String> list = new SList<>();
		list.add("bob");
		list.add("frank");
		list.add("joe");
		list.add("bill");
		list.add("bob");
		list.add("zachary");
		list.add("andy");

		System.out.println(list.size());
		list.remove("andy");

		System.out.println(list.size());

		list.add("aardvark");
		list.add("poop");

		// test Iterator
		for (String each : list)
		{
			// will still be printed in this iteration
			if (each.equals("joe")) list.remove();
			System.out.println(each);
		}

		System.out.println("Joe is gone:");

		for (String each : list) System.out.println(each);

		// test with objects
		SList<Person> people = new SList<>();
		people.add(new Person("Bob Bobsmith", 25));
		people.add(new Person("Zachary Tyler", 145));
		people.add(new Person("Mark Robertson", 55));
		people.add(new Person("Joe Jobson", 13));
		people.add(new Person("Able Baker", 1));
		people.add(new Person("Jane Doe", 34));

		for (Person each : people) System.out.println(each);


	}

}

and the test object class:

public class Person implements Comparable<Person>
{
	private String name;
	private int age;

	public Person(String name, int age)
	{
		this.name = name;
		this.age = age;
	}

	public String getName() { return name; }

	@Override
	public String toString()
	{
		return name + " , " + age;
	}

	@Override
	public int compareTo(Person p)
	{
		return this.name.compareTo(p.getName());
	}
}

Output

7
6
aardvark
bill
bob
bob
frank
joe
poop
zachary
Joe is gone:
aardvark
bill
bob
bob
frank
poop
zachary
Able Baker , 1
Bob Bobsmith , 25
Jane Doe , 34
Joe Jobson , 13
Mark Robertson , 55
Zachary Tyler , 145

r/javaexamples • • Jun 02 '15

[Intermediate] Generic, Directed, Weighted Graph with Dijkstra's Shortest Path

3 Upvotes

[Intermediate] Generic Directed, Weighted Graph with Dijkstra's Shortest Path Implementation

Ain't that a mouthful? Building from this example of an un-directed Edge Graph, we can add the idea of direction and weight to our Edge graph.

This type of Graph is made up of Edges that each contain two Vertices, and a value for weight or cost. This could be anything in a real-world situation, such as miles, time, money, etc. An Edge with direction simply makes one vertex the 'from', or 'source' and the other vertex the 'to' or 'target'.

So, say we have an airline that flies to and from multiple cities. each leg of the flight will have an associated cost:

graph.add("SACRAMENTO", "PHOENIX", 150);

Would be a flight from Sacramento to Phoenix at a cost of $150. This defines an Edge where:

Vertex from.value = "SACRAMENTO";
Vertex to.value = "PHOENIX";
int cost = 150;

Now we can add another:

graph.add("PHOENIX", "SACRAMENTO", 135);

This would be an Edge from Phoenix to Sacramento at a cost of $130. (I don't know. Cheaper cost because of prevailing winds?)

So, in our test class we would create a graph and define a bunch of edges:

	// create graph
	DiGraph graph = new DiGraph();

	// add a bunch of edges
	graph.add("SACRAMENTO", "PHOENIX", 150);
	graph.add("PHOENIX", "SACRAMENTO", 135);
	graph.add("PHOENIX", "SLC", 120);
	graph.add("SLC", "SACRAMENTO", 175);
	graph.add("SACRAMENTO", "PHOENIX", 160); // edge already exists!!!
	graph.add("SACRAMENTO", "PORTLAND", 90);
	graph.add("PORTLAND", "SLC", 185);
	graph.add("OAKLAND", "SACRAMENTO", 45);
	graph.add("PORTLAND", "OAKLAND", 100);
	graph.add("SLC", "OAKLAND", 150);
	graph.add("LAX","OAKLAND", 75);
	graph.add("SLC", "LAS VEGAS", 100);
	graph.add("LAS VEGAS", "CHICAGO", 250);

So, say we want to find the cheapest (shortest in cost) flight plan from one city to another. In comes Dijkstra's Algorithm! which is actually less difficult to implement than it sounds. I'm not going to explain too much of how the algorithm works, you can look up many detailed explanations online. I based my implementation on this one.

My full code here on Gist

The Vertex

class Vertex implements Comparable<Vertex>
{
	T value;

	// variables for Dijkstra Tree
	Vertex previous = null;
	int minDistance = Integer.MAX_VALUE;

	List<Vertex> incoming;
	List<Vertex> outgoing;
	State state;

	/**
	 * Creates new Vertex with value T
	 * @param value T
	 */
	public Vertex(T value)
	{
		this.value = value;
		incoming = new ArrayList<>();
		outgoing = new ArrayList<>();
		state = State.UNVISITED;
	}

	/**
	 * @param other Vertex to compare to
	 */
	@Override
	public int compareTo(Vertex other)
	{
		return Integer.compare(minDistance, other.minDistance);
	}

	/**
	 * Add Vertex to adjacent incoming list
	 * @param vert Vertex of incoming adjacent
	 */
	public void addIncoming(Vertex vert)
	{
		incoming.add(vert);
	}
	public void addOutgoing(Vertex vert)
	{
		outgoing.add(vert);
	}

	/**
	 * Get string of Vertex with all it's ingoing and outgoing adjacencies
	 * @ return string
	 */
	@Override
	public String toString()
	{
		String retval = "";
		retval += "Vertex: " + value + " : ";
		retval += " In: ";
		for (Vertex each : incoming) retval+= each.value + " ";
		retval += "Out: ";
		for (Vertex each : outgoing) retval += each.value + " ";
		return retval;
	}
}

The Edge

class Edge
{
	Vertex from;
	Vertex to;
	int cost;

	/**
	 * @param v1 value of type T for 'from' vertex
	 * @param v2 value of type T for 'to' vertex
	 * @param cost integer value for cost/weight of edge
	 */
	public Edge(T v1, T v2, int cost)
	{
		from = findVertex(v1);
		if (from == null)
		{
			from = new Vertex(v1);
			vertices.add(from);
		}
		to = findVertex(v2);
		if (to == null)
		{
			to = new Vertex(v2);
			vertices.add(to);
		}
		this.cost = cost;

		from.addOutgoing(to);
		to.addIncoming(from);
	}

	/**
	 * @return Edge as string
	 */
	@Override
	public String toString()
	{
		return "Edge From: " + from.value + " to: " + to.value + " cost: " + cost;
	}
}

The DiGraph

The class definition for the DiGraph is very simple, and is the same as our un-directed graph. We could have done some inheritance here:

public class DiGraph<T extends Comparable<T>>
{
	public enum State { UNVISITED, VISITED, COMPLETE };

	private ArrayList<Vertex> vertices;
	private ArrayList<Edge> edges;

	/**
	 * Default Constructor
	 */
	public DiGraph()
	{
		vertices = new ArrayList<>();
		edges = new ArrayList<>();
	}

Now our add() method:

/**
 * Creates Edge from two values T directed from -- to
 * @param from Value for Vertex 1
 * @param to Value for Vertex 2
 * @param cost Cost or weight of edge
 */
public void add(T from, T to, int cost)
{
	Edge temp = findEdge(from, to);
	if (temp != null)
	{
		// Don't allow multiple edges, update cost.
		System.out.println("Edge " + from + "," + to + " already exists. Changing cost.");
		temp.cost = cost;
	}
	else
	{
		// this will also create the vertices
		Edge e = new Edge(from, to, cost);
		edges.add(e);
	}
}

I add Depth-First and Breadth-First Search methods, and some other methods that are very similar to the un-directed graph versions. See full code

Now we add our shortest path methods:

/**
 * Creates path information on the graph using the Dijkstra Algorithm,
 * Puts the information into the Vertices, based on given starting vertex.
 * @param v1 Value of type T for starting vertex
 * @return true if successfull, false if empty or not found.
 */
private boolean Dijkstra(T v1)
{
	if (vertices.isEmpty()) return false;

	// reset all vertices minDistance and previous
	resetDistances();

	// make sure it is valid
	Vertex source = findVertex(v1);
	if (source==null) return false;

	// set to 0 and add to heap
	source.minDistance = 0;
	PriorityQueue<Vertex> pq = new PriorityQueue<>();
	pq.add(source);

	while (!pq.isEmpty())
	{
		//pull off top of queue
		Vertex u = pq.poll();

		// loop through adjacent vertices
		for (Vertex v : u.outgoing)
		{
			// get edge
			Edge e = findEdge(u, v);
			if (e==null) return false;
			// add cost to current
			int totalDistance = u.minDistance + e.cost;
			if (totalDistance < v.minDistance)
			{
				// new cost is smaller, set it and add to queue
				pq.remove(v);
				v.minDistance = totalDistance;
				// link vertex
				v.previous = u;
				pq.add(v);
			}
		}
	}
	return true;
}

/**
 * Goes through the result tree created by the Dijkstra method
 * and steps backward
 * @param target Vertex end of path
 * @return string List of vertices and costs
 */
private List<String> getShortestPath(Vertex target)
{
	List<String> path = new ArrayList<String>();

	// check for no path found
	if (target.minDistance==Integer.MAX_VALUE)
	{
		path.add("No path found");
		return path;
	}

	// loop through the vertices from end target 
	for (Vertex v = target; v !=null; v = v.previous)
	{
		path.add(v.value + " : cost : " + v.minDistance);
	}

	// flip the list
	Collections.reverse(path);
	return path;
}

/**
 * for Dijkstra, resets all the path tree fields
 */
private void resetDistances()
{
	for (Vertex each : vertices)
	{
		each.minDistance = Integer.MAX_VALUE;
		each.previous = null;
	}
}

/**
 * PUBLIC WRAPPER FOR PRIVATE FUNCTIONS
 * Calls the Dijkstra method to build the path tree for the given
 * starting vertex, then calls getShortestPath method to return
 * a list containg all the steps in the shortest path to
 * the destination vertex.
 * @param from value of type T for Vertex 'from'
 * @param to value of type T for vertex 'to'
 * @return ArrayList of type String of the steps in the shortest path.
 */
public List<String> getPath(T from, T to)
{
	boolean test = Dijkstra(from);
	if (test==false) return null;
	List<String> path = getShortestPath(findVertex(to));
	return path;
}

Test Code

public class DiGraphTest
{
	public static void main(String[] args)
	{

		// create graph
		DiGraph graph = new DiGraph();

		// add a bunch of edges
		graph.add("SACRAMENTO", "PHOENIX", 150);
		graph.add("PHOENIX", "SACRAMENTO", 135);
		graph.add("PHOENIX", "SLC", 120);
		graph.add("SLC", "SACRAMENTO", 175);
		graph.add("SACRAMENTO", "PHOENIX", 160); // edge already exists!!!
		graph.add("SACRAMENTO", "PORTLAND", 90);
		graph.add("PORTLAND", "SLC", 185);
		graph.add("OAKLAND", "SACRAMENTO", 45);
		graph.add("PORTLAND", "OAKLAND", 100);
		graph.add("SLC", "OAKLAND", 150);
		graph.add("LAX","OAKLAND", 75);
		graph.add("SLC", "LAS VEGAS", 100);
		graph.add("LAS VEGAS", "CHICAGO", 250);

		System.out.println("Graph is connected: " + graph.DepthFirstSearch());
		System.out.println("Connected from LAX:" + graph.BreadthFirstSearch("LAX"));
		System.out.println();

		System.out.println(graph);
		System.out.println(graph.edgesToString());

		System.out.println("LAX to PORTLAND");
		List<String> path = graph.getPath("LAX", "PORTLAND");
		for (String each : path) 
			System.out.println(each);

		System.out.println("\nSLC to PHOENIX");
		path = graph.getPath("SLC", "PHOENIX");
		for (String each : path) 
			System.out.println(each);

		System.out.println("Adding Edge Las Vegas to Phoenix at cost $120");
		graph.add("LAS VEGAS", "PHOENIX", 120);

		System.out.println("\nSLC to PHOENIX");
		path = graph.getPath("SLC", "PHOENIX");
		for (String each : path) 
			System.out.println(each);

		System.out.println("\nSACRAMENTO to LAX");
		path = graph.getPath("SACRAMENTO", "LAX");
		for (String each : path) 
			System.out.println(each);

		System.out.println("\nSACRAMENTO to CHICAGO");
		path = graph.getPath("SACRAMENTO", "CHICAGO");
		for (String each : path) 
			System.out.println(each);
	}
}

Output

Edge SACRAMENTO,PHOENIX already exists. Changing cost.
Graph is connected: false
Connected from LAX:true

Vertex: SACRAMENTO :  In: PHOENIX SLC OAKLAND Out: PHOENIX PORTLAND
Vertex: PHOENIX :  In: SACRAMENTO Out: SACRAMENTO SLC
Vertex: SLC :  In: PHOENIX PORTLAND Out: SACRAMENTO OAKLAND LAS VEGAS
Vertex: PORTLAND :  In: SACRAMENTO Out: SLC OAKLAND
Vertex: OAKLAND :  In: PORTLAND SLC LAX Out: SACRAMENTO
Vertex: LAX :  In: Out: OAKLAND
Vertex: LAS VEGAS :  In: SLC Out: CHICAGO
Vertex: CHICAGO :  In: LAS VEGAS Out:

Edge From: SACRAMENTO to: PHOENIX cost: 160
Edge From: PHOENIX to: SACRAMENTO cost: 135
Edge From: PHOENIX to: SLC cost: 120
Edge From: SLC to: SACRAMENTO cost: 175
Edge From: SACRAMENTO to: PORTLAND cost: 90
Edge From: PORTLAND to: SLC cost: 185
Edge From: OAKLAND to: SACRAMENTO cost: 45
Edge From: PORTLAND to: OAKLAND cost: 100
Edge From: SLC to: OAKLAND cost: 150
Edge From: LAX to: OAKLAND cost: 75
Edge From: SLC to: LAS VEGAS cost: 100
Edge From: LAS VEGAS to: CHICAGO cost: 250

LAX to PORTLAND
LAX : cost : 0
OAKLAND : cost : 75
SACRAMENTO : cost : 120
PORTLAND : cost : 210

SLC to PHOENIX
SLC : cost : 0
SACRAMENTO : cost : 175
PHOENIX : cost : 335
Adding Edge Las Vegas to Phoenix at cost $120

SLC to PHOENIX
SLC : cost : 0
LAS VEGAS : cost : 100
PHOENIX : cost : 220

SACRAMENTO to LAX
No path found

SACRAMENTO to CHICAGO
SACRAMENTO : cost : 0
PORTLAND : cost : 90
SLC : cost : 275
LAS VEGAS : cost : 375
CHICAGO : cost : 625

r/javaexamples • • May 31 '15

[Intermediate]Generic Min/Max Binary Heap

3 Upvotes

Generic Min/Max Binary Heap

A binary heap is a type of binary tree where each node is either greater than (Max Heap) or less than (Min Heap) all of its children. There is no order between child nodes, however, like a BST. but you know that the root value will always be either the minimum or maximum value of the heap.

A min heap is also called a Priority Queue where the smallest value will always be pulled off the front of the queue. This implementation allows for the usage of any type that implements Comparable which includes most non-primitive type (and primitive types will work by autoboxing). If you want to use it with your own class you will need to implement Comparable and override compareTo().

Heaps can be implemented differently than Trees, Graphs and other abstract data structures. Since the nodes can be found mathematically, the tree can be kept in a simple Array or ArrayList.

This was based heavily on this code

Gist with test code & output

BinaryHeap.java

/* Generic Min/Max Binary Heap
* for /r/javaexamples
* 
*/
import java.util.Arrays;

@SuppressWarnings("unchecked")

/**
 * Creates an array-based binary heap. Defaults to 'min' (Priority Queue)
 *
 * @author /u/Philboyd_Studge
 */
public class BinaryHeap<T extends Comparable<T>>
{
	private static final int DEFAULT_CAPACITY = 10;
	private T[] heap;
	private int length;
	private boolean min;

	/**
	 * Default Constructor
	 * <p>default capacity of 9 (0 index is not used)
	 * <p>default type of heap is min
	 */
	public BinaryHeap()
	{
		heap = (T[]) new Comparable[DEFAULT_CAPACITY];
		length = 0;
		min = true;
	}

	/**
	 * Constructor - takes an array of type T and a boolean for min/max
	 * @param array T[] array
	 * @param min boolean true = min heap, false = max heap
	 */
	public BinaryHeap(T[] array, boolean min)
	{
		heap = (T[]) new Comparable[DEFAULT_CAPACITY];
		length = 0;
		this.min = min;

		// add each element to the heap
		for (T each : array)
		{
			add(each);
		}
	}

	/**
	 * Constructor - specify boolean true = min heap, false = max heap
	 * @param min boolean true = min heap, false = max heap
	 */
	public BinaryHeap(boolean min)
	{
		heap = (T[]) new Comparable[DEFAULT_CAPACITY];
		length = 0;
		this.min = min;

	}

	/**
	 * get the heap array
	 * note: can cause casting issues
	 * @return Array of type T[]
	 */
	public T[] getHeap()
	{
		return Arrays.copyOfRange(heap, 1, length + 1);
	}

	/**
	 * adds a generic type T to heap
	 * <p>percolates down the tree
	 * @param value type T value
	 */
	public void add(T value)
	{
		// resize if needed
		if (this.length >= heap.length - 1)
		{
			heap = this.resize();
		}

		length++;
		heap[length] = value;
		bubbleUp();
	}

	/**
	 * Removes min or max item from heap
	 * <p>re-heapifies 
	 * @return value of T that is minimum or maximum value in heap
	 */
	public T remove()
	{
		T result = peek();

		swap(1, length);
		heap[length] = null;
		length--;

		bubbleDown();

		return result;
	}
	/**
	 * Removes min or max item from heap
	 * same as <code>remove()</code> but does not throw exception on empty
	 * <p>re-heapifies 
	 * @return value of T that is minimum or maximum value in heap;  or <code>null</code> if empty
	 */
	public T poll()
	{
		if (isEmpty()) return null;

		T result = peek();

		swap(1, length);
		heap[length] = null;
		length--;

		bubbleDown();

		return result;
	}

	/**
	 * Checks if heap is empty
	 * @return <code>true</code> if empty
	 */
	public boolean isEmpty()
	{
		return length == 0;
	}

	/**
	 * returns min/max value without removing it
	 * @return value type T
	 * @throws IllegalStateException if empty
	 */
	public T peek()
	{
		if (isEmpty()) throw new IllegalStateException();
		return heap[1];
	}

	/**
	 * Length/size of heap
	 * @return int size of heap
	 */
	public int length()
	{
		return length;
	}

	/**
	 * Add DEFAULT_CAPACITY to length of <code>heap</code> array
	 * @return new array of type T
	 */
	private T[] resize()
	{
		// add 10 to array capacity
		return Arrays.copyOf(heap, heap.length + DEFAULT_CAPACITY);
	}

	/**
	 * percolates new values up based on min/max
	 */
	private void bubbleUp()
	{
		int index = length;
		if (min)
		{
			while (hasParent(index) && (parent(index).compareTo(heap[index]) > 0))
			{
				swap(index, parentIndex(index));
				index = parentIndex(index);
			}	
		}
		else
		{
			while (hasParent(index) && (parent(index).compareTo(heap[index]) < 0))
			{
				swap(index, parentIndex(index));
				index = parentIndex(index);
			}	

		}
	}

	/**
	 * percolates values down based on min/max
	 */
	private void bubbleDown()
	{
		int index = 1;
		if (min) // min heap
		{

			while (hasLeftChild(index))
			{
				// find smaller of child values
				int smaller = leftIndex(index);
				if (hasRightChild(index) && heap[leftIndex(index)].compareTo(heap[rightIndex(index)]) > 0)
				{
					smaller = rightIndex(index);
				}
				if (heap[index].compareTo(heap[smaller]) > 0)
				{
					swap(index, smaller);
				}
				else break;

				index = smaller;
			}				
		}
		else // max heap
		{
			while (hasLeftChild(index))
			{
				// find larger of child values
				int larger = leftIndex(index);
				if (hasRightChild(index) && heap[leftIndex(index)].compareTo(heap[rightIndex(index)]) < 0)
				{
					larger = rightIndex(index);
				}
				if (heap[index].compareTo(heap[larger]) < 0)
				{
					swap(index, larger);
				}
				else break;

				index = larger;
			}				

		}
	}

	/**
	 * if child has a parent
	 * @param i integer - index
	 * @return true if index > 1
	 */
	private boolean hasParent(int i)
	{
		return i > 1;
	}

	/**
	 * Get left index mathematically
	 * @param i index
	 * @return index of left node from index i
	 */
	private int leftIndex(int i)
	{
		return i * 2;
	}

	/**
	 * Get right index mathematically
	 * @param i index
	 * @return index of right node from index i
	 */
	private int rightIndex(int i)
	{
		return i * 2 + 1;
	}

	/**
	 * Test to see if node has left child
	 * @param i index
	 * @return true if it does
	 */
	private boolean hasLeftChild(int i)
	{
		return leftIndex(i) <= length;
	}

	/**
	 * Test to see if node has right child
	 * @param i index
	 * @return true if it does
	 */
	private boolean hasRightChild(int i)
	{
		return rightIndex(i) <= length;
	}

	/**
	 * get index of parent from child node
	 * @param i index
	 * @return index of parent
	 */
	private int parentIndex(int i)
	{
		return i / 2;
	}

	/**
	 * get parent value
	 * @param i index
	 * @return value of type T
	 */
	private T parent(int i)
	{
		return heap[parentIndex(i)];
	}

	/**
	* Swap two values in heap
	* @param index1 int first index
	* @param index2 int second index
	*/
	private void swap(int index1, int index2)
	{
		T temp = heap[index1];
		heap[index1] = heap[index2];
		heap[index2] = temp;
	}

	/**
	 * Overridden toString method
	 * @return String all values in heap without null values
	 */
	@Override
	public String toString()
	{
		String retval = "";
		for (T each : heap)
		{
			if (each != null) retval += each + " : ";
		}
		return retval + "\n";
	
	}

}

r/javaexamples • • May 22 '15

[Intermediate] Generic, Self-Balancing Key-Value Binary Search Tree

3 Upvotes

A Generic, Self-Balancing Key-Value Binary Search Tree

Much like a Linked List, a Binary Search Tree is really just a bunch of Nodes that are linked together in a recursive fashion. Instead of the nodes being next and 'previous like in a List, in a tree they are labeled left and right and the idea is very simple: As new nodes get added, and node with a value lower than the root node gets put on the left side of the tree, any node with a higher value gets put on the right side of the tree, and recursively drop down the tree until they come to an unused leaf. so, say the entry order is { 5, 2, 7, 6, 3, 8, 1} the tree would look like this:

     5
    / \
   /   \
  2     7
 / \   / \
1   3 6   8

This makes for very fast searching, as you can see the maximum possible iterations to search for any number in that tree is 3.

Learning this data structure is also a great lesson in recursion, as almost every method in it uses recursion in some way.

The Class Declaration

public class BinaryTreeKV<K extends Comparable<K>, V>

We want two generic types, K and V, for Key and Value. The key is comparable for sorting, so any object sent to it must implement the Comparable interface.

The Node

First, we define an inner Node class. This will contain both Key and Value:

	class Node
	{
		Node left;
		Node right;
		K key;
		V value;
		
		Node(K newKey, V newValue)
		{
			left = null;
			right = null;
			key = newKey;
			value = newValue;
		}

		public K getKey()
		{
			return key;
		}

		public V getValue()
		{
			return value;
		}

		public void setValue(V val)
		{
			value = val;
		}

		@Override
		public String toString()
		{
			return key + ":" + value + " ";
		}
	}

Insert Method

Now we need an insert() method. This goes through the tree, starting at the root, checks to see if the key being added is less than, greater than, or equal to the node it is comparing to, and goes to the left or right sides of the tree, creating new nodes when necessary:

public void insert(K key, V value)
{
	// call recursive function with root node
	root = insert(root, key, value);
}

private Node insert(Node node, K key, V value)
{
	// create new node if new leaf
	if (node==null)
	{
		node = new Node(key, value);
	}
	else
	{
		// if key already exists, just update the value
		if (key.compareTo(node.key)==0)
		{
			node.setValue(value);
		}
		else
		{
			// create new branch
			if (key.compareTo(node.key) < 0)
			{
				node.left = insert(node.left, key, value);
			}
			else
			{
				node.right = insert(node.right, key, value);
			}

		}
	}
	return node;
}

Now some display functions:

public void printTree()
{
	printTree(root);
	System.out.println();
}

private void printTree(Node node)
{
	if (node==null) return;

	printTree(node.left);
	System.out.print(node);
	printTree(node.right);
}

public void printPostOrder()
{
	printPostOrder(root);
	System.out.println();
}

public void printPostOrder(Node node)
{
	if (node==null) return;
	printPostOrder(node.left);
	printPostOrder(node.right);
	System.out.print(node);
}

public void printLevelOrder()
{
	printLevelOrder(root);
	System.out.println();
}
public void printLevelOrder(Node node)
{
	Queue<Node> q = new LinkedList<>();
	q.add(node);
	while (!q.isEmpty())
	{
		Node temp = q.poll();
		System.out.print(temp);
		if (temp.left != null) q.add(temp.left);
		if (temp.right != null) q.add(temp.right);
	}
}

Some other standard methods:

public void clear()
{
	root = null;
}

public boolean isEmpty()
{
	return root==null;
}

public int size()
{
	return size(root);
}

public int size(Node node)
{
	if (node==null) return 0;
	return size(node.left) + 1 + size(node.right);
}

public int depth()
{
	return depth(root);
}

public int depth(Node node)
{
	if (node == null) return 0;
	int left = depth(node.left);
	int right  = depth(node.right);
	return (left > right) ? left + 1 : right + 1;
}

And these methods to search the tree for a specific key, returning either the value or the node itself:

public Node getNode(K key)
{
	return getNode(root, key);
}

public Node getNode(Node node, K key)
{
	if (node==null) return null;
	if (key.compareTo(node.key) == 0) return node;
	if (key.compareTo(node.key) < 0) return getNode(node.left, key);
	return getNode(node.right, key);
}

public V get(K key)
{
	return get(root, key);
}

private V get(Node node, K key)
{
	if (node==null) return null;
	if (key.compareTo(node.key) ==0) return node.getValue();
	if (key.compareTo(node.key) < 0) return get(node.left, key);
	return get(node.right, key);
}

Here we have a function to fill a Linked List of the sorted elements. The List is a member variable so it can be used by other methods, mainly the balancing and delete methods:

public void getInorderList()
{
	if (!inOrderList.isEmpty()) inOrderList.clear();
	getInorderList(root);
}

private void getInorderList(Node node)
{
	if (node==null) return;
	getInorderList(node.left);
	inOrderList.add(node);
	getInorderList(node.right);

}

Balancing the Tree

As you add items to the tree, they stay in a sorted order, but, depending on the order they are added, the tree may have deeper subtrees than it needs. Balancing restores the tree to the minimum depth possible.

I did not implement a true AVL tree here, instead I just re-balance the tree using the in-ordered list, finding the mid-point of the list and making that the root and then inserting the nodes on each side of the mid point. This is much easier than rotating the nodes, although probably would be a performance hit if the tree was very large.

private void balance()
{
	// get the sorted list
	getInorderList();
	// clear the tree
	clear();
	// get the number of elements
	int count = inOrderList.size();
	// call the recursive function with min = 0 and max = size
	balanceTree(0, count - 1);
	// finished, set flag to false
	balancing = false;

}

private void balanceTree(int min, int max)
{
	// recurse until min > max
	if (min <= max)
	{
		// get middle index
		int mid = (int) Math.ceil((double) (min + max) / 2);
		// create temp node to get key & value of middle object
		Node temp = inOrderList.get(mid);
		// insert into tree
		insert(temp.key, temp.value);
		// recurse lower elements
		balanceTree(min, mid - 1);
		// recurse higher elements
		balanceTree(mid + 1, max);
	}
}

We have to modify the insert() method thusly:

public void insert(K key, V value)
{
	if (!balancing)
	{
		if (root != null && size() > 2)
			if (depth() > size() / 2)
				System.out.println("Balancing...");
				balancing = true;
				balance();
	}
	root = insert(root, key, value);
}

This is for two purposes: To trigger the balancing when the depth of the tree becomes greater than half of the size, and to keep the balance operation from being triggered while it is already in progress, potentially causing an infinite loop.

Delete Method

Since we are 'cheating' using the in-ordered List for balancing, we can do the same to make the delete() method easier:

public void delete(K key)
{
	Node node = getNode(key);
	if (node == null) return;
	getInorderList();
	if (inOrderList.contains(node))
	{
		inOrderList.remove(node);
		clear();
		balancing = true;
		balanceTree(0, inOrderList.size()-1);
		balancing = false;
	}
}

Usage

Here's our main method:

public static void main( String [] args )
{

	BinaryTreeKV<Integer, String> tree = new BinaryTreeKV<>();
	System.out.println("Is tree empty:" + tree.isEmpty());
	tree.insert(5, "Bill");
	tree.insert(3, "bob");
	tree.insert(1, "poop");
	tree.insert(2, "jane");
	tree.insert(8, "what");
	tree.insert(6, "this");
	tree.insert(7, "dsdfs");

	System.out.println("Is tree empty:" + tree.isEmpty());
	System.out.println("Tree depth:" + tree.depth());
	System.out.println("Lookup value for key `3` = " + tree.getNode(3));

	System.out.println("Inorder List");
	tree.getInorderList();
	tree.printList();
	System.out.println("Level Order:");
	tree.printLevelOrder();
	System.out.println("Tree depth:" + tree.depth());

	tree.insert(4,"dog");
	tree.insert(10,"cat");
	tree.insert(9,"help");

	tree.getInorderList();
	tree.printList();
	System.out.println("Tree depth:" + tree.depth());
	System.out.println("deleting '3'");
	tree.printLevelOrder();
	tree.delete(3);
	tree.printLevelOrder();
	tree.printTree();

}

Output

Is tree empty:true
Balancing...
Balancing...
Balancing...
Balancing...
Is tree empty:false
Tree depth:4
Lookup value for key `3` = 3:bob
Inorder List
1:poop 2:jane 3:bob 5:Bill 6:this 7:dsdfs 8:what
Level Order:
5:Bill 2:jane 8:what 1:poop 3:bob 6:this 7:dsdfs
Tree depth:4
Balancing...
1:poop 2:jane 3:bob 4:dog 5:Bill 6:this 7:dsdfs 8:what 9:help 10:cat
Tree depth:4
deleting '3'
5:Bill 3:bob 8:what 2:jane 4:dog 7:dsdfs 10:cat 1:poop 6:this 9:help
6:this 4:dog 9:help 2:jane 5:Bill 8:what 10:cat 1:poop 7:dsdfs
1:poop 2:jane 4:dog 5:Bill 6:this 7:dsdfs 8:what 9:help 10:cat

Here's the gist of the full program


r/javaexamples • • May 19 '15

Using Arrays and ArrayLists

3 Upvotes

Using Arrays and ArrayLists

Learning how to use Arrays, and the more dynamic Array Lists is an important part of learning how to program Java.

The simplest way to think of an array is like a set of shelves, drawers or boxes. Each drawer has a number, starting at zero and going to -> number of drawers - 1.

See Here

An array can hold any data type, even other arrays.

	// create an array of ints, size 10
	int[] grades = new int[10];

	// create an array of strings, size 20
	String[] arrayOfStrings = new String[20];

	// create an array of Integer objects, size 5
	Integer[] arrayOfIntegerObjects = new Integer[5];

	// create an array of used defined object
	MyObject[] foo = new MyObject[100];

	// create an array of linked lists - note: will throw unchecked operation warning
	LinkedList<Integer>[] arrayOfLinkedLists = new LinkedList[3];

You can also declare an array with initial values, like this:

    int[] numbers = { 1, 2, 3, 43, 57 };

This will automatically size the array properly.

Accessing Elements of the Array

Just reference the index number using square brackets. Don't forget the index starts at zero!

System.out.println(numbers[0]);

Would output 1 in the above example.

System.out.println(numbers[4]);

Would output 57, and saying numbers[5] will cause an ArrayOutOfBounds exception.

Looping through Arrays

There are two main ways to loop through an array, a for loop and a for-each loop. Use the first if you need the index value, use the second if you just need to loop through them all. See also

The For Loop

for (int i = 0; i < arrayName.length; i++) {
    System.out.println(arrayName[i]);
}

The For-Each Loop

for (type current : arrayName) {}

so in our example above:

for (int current : numbers) {
	System.out.println(current);
}

So, lets make an array and fill it with random values:

	// create an array of ints, size 10
	int[] grades = new int[10];

	//loop through array and fill with random data
	// actually counts from 0 to 9
	for(int i = 0; i < grades.length; i++)
	{
		// random integer from 50 - 100
		// assumes you have declared & imported Random rand
		grades[i] = rand.nextInt(50) + 51;
		System.out.println("Array location " + i + " = " + grades[i]);
	}
	System.out.println();

Output from above:

Array location 0 = 57
Array location 1 = 95
Array location 2 = 72
Array location 3 = 86
Array location 4 = 56
Array location 5 = 76
Array location 6 = 61
Array location 7 = 98
Array location 8 = 73
Array location 9 = 77

Now you can sort the array like this:

Arrays.sort(grades);

See the full code below for more examples of operations upon arrays, like arraycopy, and getting the sum and average of array elements.

Arrays are fast and powerful, but have one main problem: You need to know the size of the data you have upon creation! Many times you will not know the size of the data you are working with, so we need to use a more complex object. here is where the ArrayList comes in.

ArrayList is generic, so it is instantiated with the diamond brackets, and cannot use primitive types (int, double etc. - although, use the Object types of each, and you can still add primitive elements to the list, the compiler will automatically convert them, this is called autoboxing).

So for ints, you would say:

ArrayList<Integer> myList = new ArrayList<>();

and then, to add an element, say:

myList.add(123);

To get the value at a certain index, use:

myList.get(index);

To find a specific value use:

int index = myList.indexOf(123);

returns the index found, or -1 if not found.

See the example program for more:

// Arrays example
// by /u/Philboyd_Studge for /r/javaexamples
// 
// Example of Arrays and ArrayLists
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;


public class ArraysExample
{
	public static Random rand = new Random();
	public static Scanner scan = new Scanner(System.in);
	
	public static void main(String[] args)
	{

		// create an array of ints, size 10
		int[] grades = new int[10];

		//loop through array and fill with random data
		// actually counts from 0 to 9
		for(int i = 0; i < grades.length; i++)
		{
			grades[i] = rand.nextInt(50) + 51;
			System.out.println("Array location " + i + " = " + grades[i]);
		}
		System.out.println();

		// or directly access by index number
		grades[4] = 100;

		System.out.println("Changed index 4");

		// display them again
		for(int i = 0; i < 10; i++)
		{
			System.out.println("Array index " + i + " = " + grades[i]);
		}
		System.out.println();

		//sort the array
		Arrays.sort(grades);

		System.out.println("Sorted:");

		// Here's another way to loop through them
		for(int each : grades)
		{
			System.out.println("Grade = " + each);
		}

		//search a sorted array
		System.out.println("100 found at index " + Arrays.binarySearch(grades, 100));

		// let's get a sum
		int sum = 0;
		for(int each : grades) 
		{
			sum += each;
		}
		System.out.println("Sum of array = " + sum);

		// get average
		double avg = sum/10.0;
		System.out.println("Average = " + avg);

		// let's fill the array with user entries
		String input = "";
		for (int i = 0; i < 10; i++)
		{
			System.out.print("Enter an integer:");
			input = scan.nextLine();
			try
			{
				grades[i] = Integer.parseInt(input);
			}
			catch (NumberFormatException nfe)
			{
				grades[i] = 0;
			}
		}

		// sort
		Arrays.sort(grades);

		// display
		for (int each : grades) System.out.println(each);

		// array copy
		int[] array2 = new int[5];

		System.arraycopy(grades, 5, array2, 0, 5);

		System.out.println("Copied last 5 elements:");
		for (int each : array2) System.out.println(each);

		// now, let's use an ArrayList
		ArrayList<Integer> gradeList = new ArrayList<>();

		// let's fill the array with user entries
		while (!input.equalsIgnoreCase("done"))
		{
			System.out.print("Enter an integer (or 'done'):");
			input = scan.nextLine();
			if (input.equalsIgnoreCase("done")) break;
			try
			{
				gradeList.add(Integer.parseInt(input));
			}
			catch (NumberFormatException nfe)
			{
				System.out.println("Incorrect entry.");
			}
		}

		// add arbitrary value in case user entered no values
		if (gradeList.isEmpty()) gradeList.add(25);

		// sort, slightly different from array sort
		Collections.sort(gradeList);


		//add specific index
		gradeList.add(gradeList.size() - 1, 100 );
		// for-each display
		for (Integer each : gradeList) System.out.println(each);

		//find in array
		System.out.println("Found '100' at index = " + gradeList.indexOf(100));

		// get
		System.out.println("Get list index 0 = " + gradeList.get(0));

		// display list with index
		for (int i = 0; i < gradeList.size(); i++)
		{
			System.out.println("Index " + i + " = " + gradeList.get(i));
		}

		// min/max

		System.out.println("Min: " + Collections.min(gradeList));
		System.out.println("Max: " + Collections.max(gradeList));




	}	
}

Example output:

Array location 0 = 85
Array location 1 = 57
Array location 2 = 56
Array location 3 = 92
Array location 4 = 88
Array location 5 = 78
Array location 6 = 61
Array location 7 = 60
Array location 8 = 94
Array location 9 = 67

Changed index 4
Array index 0 = 85
Array index 1 = 57
Array index 2 = 56
Array index 3 = 92
Array index 4 = 100
Array index 5 = 78
Array index 6 = 61
Array index 7 = 60
Array index 8 = 94
Array index 9 = 67

Sorted:
Grade = 56
Grade = 57
Grade = 60
Grade = 61
Grade = 67
Grade = 78
Grade = 85
Grade = 92
Grade = 94
Grade = 100
100 found at index 9
Sum of array = 750
Average = 75.0
Enter an integer:33
Enter an integer:44
Enter an integer:12345
Enter an integer:2
Enter an integer:3
Enter an integer:1
Enter an integer:9909
Enter an integer:poop
Enter an integer:4567
Enter an integer:-3
-3
0
1
2
3
33
44
4567
9909
12345
Copied last 5 elements:
33
44
4567
9909
12345
Enter an integer (or 'done'):44
Enter an integer (or 'done'):poop
Incorrect entry.
Enter an integer (or 'done'):1.2
Incorrect entry.
Enter an integer (or 'done'):345
Enter an integer (or 'done'):929394
Enter an integer (or 'done'):23
Enter an integer (or 'done'):1
Enter an integer (or 'done'):22
Enter an integer (or 'done'):done
1
22
23
44
345
100
929394
Found '100' at index = 5
Get list index 0 = 1
Index 0 = 1
Index 1 = 22
Index 2 = 23
Index 3 = 44
Index 4 = 345
Index 5 = 100
Index 6 = 929394
Min: 1
Max: 929394

r/javaexamples • • May 02 '15

Writing and Appending Data to a Text File

3 Upvotes

Writing and Appending to a Text file

This is a follow up to this post about Reading CSV Data from a file.

The Java file io functions BufferedWriter and FileWriter work very much like the BufferedReader and FileReader classes. you can save a little typing by declaring one instance inside the other, like this:

BufferedWriter *variablename* = new BufferedWriter(new FileWriter("filename.txt", boolean *append*))

The boolean append tells it whether you want to create a new file or append an existing one. Use this carefully, as you can easily delete important data. Set this to true to append, or false to create a new file. Also note, if this is set to true, if the file does not exist it will still be created. Both BufferedReader and BufferedWriter have checked exceptions, which means they must be handled in some way, such as a try/catch block.

So, say we wanted to add an entry to our Inventory text file from the last example. Remember it is a CSV, or comma-delimited file like this: (inventory.txt)

Blinker Fluid,10,10.99
Duncel Component,100,27.85
Widget1a,25,15.25
Widget2b,100,4.99

And the Inventory class:

public class Inventory
{
    private String item;
    private int qty;
    private float price;

    public Inventory(String item, int qty, float price)
    {
        this.item = item;
        this.qty = qty;
        this.price = price;
    }

    public float getTotal()
    {
        return qty * price;
    }

    public String toString()
    {
        return "Item: " + item + "\n" + "Quantity: " + qty + "\n"
                    + "Price: " + price;
    }
}

here is the code to add one line to the file:

try
{
	// create Bufferedwriter instance with a FileWriter
	// the flag set to 'true' tells it to append a file if file exists
	BufferedWriter out = new BufferedWriter(new FileWriter("inventory.txt", true));

	// write the text string to the file
	out.write("Left Handed Wrench,200,2.78f");

	// write a `newline` to the file
	out.newLine();

	// close the file
	out.close();
}

// handle exceptions
catch (IOException ioe)
{
	ioe.printStackTrace();
}

The output file will now look like:

Blinker Fluid,10,10.99
Duncel Component,100,27.85
Widget1a,25,15.25
Widget2b,100,4.99
Left Handed Wrench,200,2.78f

Note that the write() command does not add a new line at the end, so that must be done manually, or of course you could add it to the end of the string with a "\n".

Also, if you want to write multiple lines of text before the close() function is called, you want to use the flush() method to push the lines from the buffer to the file.

Now, in our last example, we were loading the data from the file into an ArrayList of Inventory objects. Let's say you wanted to take an existing Inventory object you created and write it to the file. The esiest way would e to add another method to the Inventory class first that returns a comma-delimited string like this:

public String toCSVString()
{
	return item + "," + qty + "," + price;
}

We also should wrap the file writing code into a static method, so it is easier to reuse:

public static void writeFile(String filename, String output, boolean append)
{
	try
	{
		// create Bufferedwriter instance with a FileWriter
		// the flag set to 'true' tells it to append a file if file exists
		BufferedWriter out = new BufferedWriter(new FileWriter(filename, append));
		out.write(output);
		out.newLine();
		out.close();
	}
	catch (IOException ioe)
	{
		ioe.printStackTrace();
	}
}

Here is both our first example and an example of using objects, with the static method:

	// append line to file

	FileFunctions.writeFile("inventory.txt", "Left Handed Wrench,200,2.78f", true);

	// make new Inventory object
	Inventory newItem = new Inventory("Cool Hat", 150, 19.99f);

	// write to file using object method to get 
	// comma-delimited string, with `append` flag set to false
	// OVER-WRITES FILE!!
	FileFunctions.writeFile("inventory.txt", newItem.toCSVString(), false);

The output will just be this:

Cool Hat,150,19.99

As we over-write the file in that last line.

Here is the full program FileFunctions.java:

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class FileFunctions
{

	public static void writeFile(String filename, String output, boolean append)
	{
		try
		{
			// create Bufferedwriter instance with a FileWriter
			// the flag set to 'true' tells it to append a file if file exists
			BufferedWriter out = new BufferedWriter(new FileWriter(filename, append));
			out.write(output);
			out.newLine();
			out.close();
		}
		catch (IOException ioe)
		{
			ioe.printStackTrace();
		}
	}

	public static ArrayList<Inventory> readFile(String filename)
	{
		// create ArrayList to store the invetory objects
		ArrayList<Inventory> invItem = new ArrayList<>();
		try
		{
			// create a Buffered Reader object instance with a FileReader
			BufferedReader br = new BufferedReader(new FileReader("inventory.txt"));

			// read the first line from the text file
			String fileRead = br.readLine();

			// loop until all lines are read
			while (fileRead != null)
			{

				// use string.split to load a string array with the values from each line of
				// the file, using a comma as the delimiter
				String[] tokenize = fileRead.split(",");

				// assume file is made correctly
				// and make temporary variables for the three types of data
				String tempItem = tokenize[0];
				int tempQty = Integer.parseInt(tokenize[1]);
				float tempPrice = Float.parseFloat(tokenize[2]);

				// creat temporary instance of Inventory object
				// and load with three data values
				Inventory tempObj = new Inventory(tempItem, tempQty, tempPrice);

				// add to array list
				invItem.add(tempObj);

				// read next line before looping
				// if end of file reached 
				fileRead = br.readLine();
			}

			// close file stream
			br.close();
		}
		
		// handle exceptions
		catch (FileNotFoundException fnfe)
		{
			System.out.println("file not found");
			return null;
		}

		catch (IOException ioe)
		{
			ioe.printStackTrace();
		}

		return invItem;		
	}

	public static void main( String [] args )
	{

		List<Inventory> invList = FileFunctions.readFile("inventory.txt");
		// display inventory
		for (Inventory each : invList)
		{
			System.out.println("====================");
			System.out.println(each);
			System.out.println();
			System.out.printf("Total value = %8.2f %n", each.getTotal());

		}

		// append line to file

		FileFunctions.writeFile("inventory.txt", "Left Handed Wrench,200,2.78f", true);

		// make new Inventory object
		Inventory newItem = new Inventory("Cool Hat", 150, 19.99f);

		// write to file using object method to get 
		// comma-delimited string
		// OVER-WRITES FILE!!
		FileFunctions.writeFile("inventory.txt", newItem.toCSVString(), false);

	}

}

r/javaexamples • • Apr 27 '15

A quick explanation of loops

3 Upvotes

Lots of people seem to be confused by for loops, which are probably the most useful constructs in Java. They generally take the following form:

 for (int i = 0; i < 100; i++) {


     //some code


 }

(In that example, 0 and 100 are just arbitrary values.)

Breaking apart that for declaration is actually fairly simple. It consists of three parts: an initialisation, termination, and mutation statement. The initialisation statement is executed once, before the rest of the loop is executed. This is where starting values for counter variables are usually set. The termination statement is checked at the beginning of the loop each execution. If it's false, the loop exits. The mutation statement is executed at the end of the loop each execution. It's usually used to increment or decrement a counter variable.

Therefore, a for statement like the one above is, for all intents and purposes, equivalent to:

 int i = 0;


 while (i < 100) {


     //some code


     i++;


 }

Now, you may have encountered a somewhat different-looking for loop of the following form:

 for (Object o : Iterable c) {


     //some code


 }

This is referred to as the enhanced for loop, or more commonly, the foreach loop. Both terms are pretty accurate. This type of for loop is good for iterating over collections and arrays, because it gets the contents of a normal for loop declaration from the size of the collection or array itself. For example:

 char[] c = new char[]{'t', 'i', 't', 't', 'y', 's', 'p', 'r', 'i', 'n', 'k', 'l', 'e', 's'};


 for (int i = 0; i < c.length; i++) {


     System.out.println(c[i]);


 }

Could be more easily accomplished with:

 char[] c = new char[]{'t', 'i', 't', 't', 'y', 's', 'p', 'r', 'i', 'n', 'k', 'l', 'e', 's'};


 for (char i : c) {


     System.out.println(i);


 }

The foreach loop takes care of all the counters internally, leaving you with a much cleaner declaration. One way to remember how this functions is simply saying it out loud: “for each chari in c, print i”. While it may seem like a lot more effort to learn, this is a fairly simple example. As your code becomes more advanced and you shift away from primitive arrays to Collection subtypes, you'll find yourself using the foreach loop as much as possible.

With foreach loops, you as a developer don't have to worry about increments, decrements, or orders. You just retrieve elements from the array or collection in whatever order they're given to you, and use them as such. In almost all cases, you should use a foreach whenever possible to iterate through any sort of array or collection.


r/javaexamples • • Mar 31 '26

Ujorm3: Lightning-fast, minimalist ORM for Java Records and JavaBeans

Thumbnail reddit.com
2 Upvotes

r/javaexamples • • Dec 09 '25

Julia fractal graphics zoom

2 Upvotes

r/javaexamples • • Oct 10 '25

Spring JPA Specification and Pageable

Thumbnail
reddit.com
2 Upvotes

r/javaexamples • • Aug 30 '24

Connect to Minio from Java.

2 Upvotes

Minio is an open source object storage similar to S3. This article explains how to connect to Minio from Java.

https://www.blackslate.io/articles/connect-to-minio-from-java


r/javaexamples • • Jun 13 '24

Proof Key for Code Exchange (PKCE) in Web Applications with Spring Security

2 Upvotes

Implementing OpenID Connect authentication in Java Web Applications with Okta Spring Boot Starter and Spring Security support for Authorization Code Flow with PKCE

Read more…


r/javaexamples • • Jan 06 '24

Use cases of interface and abstract class after jdk1.8

2 Upvotes

Hi , I tried to dig up little bit more about the use cases of interface and abstract class. Since jdk1.8, it is really difficult to understand when one should use abstract class and when one should be using interface.

Can somebody please share any examples or documents to get the actual scenarios?


r/javaexamples • • Nov 13 '23

Java Microservices with Spring Boot and Spring Cloud

2 Upvotes

This tutorial shows you how to build a microservices architecture with Spring Boot and Spring Cloud.
Read more…


r/javaexamples • • Jul 18 '23

Deploy Secure Spring Boot Microservices on Amazon EKS Using Terraform and Kubernetes

2 Upvotes

Deploy a cloud-native Java Spring Boot microservice stack secured with Auth0 on Amazon EKS using Terraform and Kubernetes.
Read more…


r/javaexamples • • Feb 18 '23

Java CountDownLatch Example for Beginners - [Multithreading Tutorial]

2 Upvotes

r/javaexamples • • Feb 08 '23

25 Examples of ConcurrentHashMap in Java

2 Upvotes

r/javaexamples • • May 31 '22

How do I decide the order of players in a game?

2 Upvotes

I am making a simple snake and ladder game. The actual game is working fine, but I am stuck on a specific requirement about the players.

The user entered number of players(numOfPlayers) is restricted between 2 to 4. I have written a method to do that and it is working.

I have a method for dice roll too.

Before any of the players starts playing, the order of playing turns must be determined. For that, each player must throw the dice to obtain the largest possible number. In case of a tie between any of the players, the process is repeated only between those players. This process is concluded once the order of playing is determined.

I just couldn't figure out how to do this. If I create an array and populate it with random numbers and reorganize in ascending order, it still doesn't give me an answer. Also, how do I solve the repeated dice roll issue? The code below is what I used to get the number of players and to confirm it is within limits.

public static int player() {
Scanner kb = new Scanner(System.in);
for (int i = 0; i < 3; i++) {
System.out.println("Please enter the # of players for your game-Number must be between 2 and 4 inclusively.");
int numOfPlayers = kb.nextInt();
if (numOfPlayers >= 2 && numOfPlayers <= 4) {
System.out.println("You have " + numOfPlayers + " players.");
return numOfPlayers;
}
else {
System.out.println("Bad Attempt" + i + "\n-Invalid # of players. Please enter a # between 2 and 4 inclusively.");
}
}
System.out.println("Bad Attempt 4! you have exhausted all your chances.\n Program will terminate.");
// System.exit(0);
return 0;
}

r/javaexamples • • May 25 '22

Method Overloading in Java

2 Upvotes

A new video on Method Overloading is out now!!!. You can check it out here:


r/javaexamples • • May 12 '22

Quiz #2 (Please Answer in the comments section below)

2 Upvotes

2. Which of the following are true? (Mention all that apply.)

a. javac compiles a .class file into a .java file.

b. javac compiles a .java file into a .bytecode file.

c. javac compiles a .java file into a .class file.

d. java accepts the name of the class as a parameter.

e. java accepts the filename of the .bytecode file as a parameter.

f. java accepts the filename of the .class file as a parameter.


r/javaexamples • • May 11 '22

Quiz #1

2 Upvotes
  1. Which of the following are true statements? (Choose all that apply.)

60 votes, May 12 '22
1 Java allows operator overloading.
9 Java code compiled on Windows can run on Linux.
0 Java has pointers to specific locations in memory.
0 Java is a procedural language.
50 Java is an object-oriented language.
0 Java is a functional programming language.