/*
 * Copyright (c) 2001 Matthew Feldt. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided the copyright notice above is
 * retained.
 *
 * THIS SOFTWARE IS PROVIDED ''AS IS'' AND WITHOUT ANY EXPRESSED OR
 * IMPLIED WARRANTIES.
 */

/**
 * LocateNeighbors.java
 *
 * Java Examples In A Nutshell Copyright (c) 2000 David Flanagan
 * Exercise 1-5:
 * The SortNumbers class shows how you can sort an array of doubles. Write a
 * program that uses this class to sort an array of 100 floating-point numbers.
 * Then, interactively prompt the user for numeric input and display the next
 * larger and next smaller number from the array. You should use an efficient
 * binary search algorithm to find the desired position in the sorted array.
 *
 * @author Matthew Feldt <developer@feldt.com>
 * @version 1.0, 01/27/2001 16:58
 */

package com.feldt.examples.basics;
import java.io.*;
import com.davidflanagan.examples.basics.SortNumbers;

public class LocateNeighbors {
	public static void main (String args[]) {
		int SIZE = 100;
		double[] nums = new double[SIZE];
		String input;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		// populate the array
		for (int i = 0; i < nums.length; i++)
			nums[i] = Math.random() * 100;

		// sort the array
		SortNumbers.sort(nums);

		for (int i = 0; i < nums.length; i++)
			System.out.println(i + " " + nums[i]);

		while (true) {
			try {
				// prompt the user and fetch the input
				System.out.print("Type 'quit' to exit > ");
				input = in.readLine();
				if (input == null || input.equals("quit")) break;
				double number = Double.parseDouble(input);

				// binary search...
				int middle = 0, low = 0, high = nums.length-1;
				while (low <= high) {
					middle = (high+low)/2;
					if (nums[middle] > number) { high = middle-1; }
					else if (nums[middle] < number) { low = middle+1; }
					else { low = middle; break; }
				}

				String msg;
				if (number == nums[middle]) {
					msg = ((middle-1) < 0) ? "None smaller" :
						"Next smaller: " + nums[middle-1] + "\n";
					msg += ((middle+1) >= nums.length) ? "None larger" :
						"Next larger: " + nums[middle+1];
				} else if (number > nums[middle]) {
					msg = "Next smaller: " + nums[middle] + "\n";
					msg += ((middle+1) >= nums.length) ? "None larger" :
						"Next larger: " + nums[middle+1];
				} else {
					msg = ((middle-1) < 0) ? "None smaller" :
						"Next smaller: " + nums[middle-1] + "\n";
					msg += "Next larger: " + nums[middle];
				}
				System.out.println(msg);
			} catch(IOException e) {
				System.err.println(e);
			} catch(NumberFormatException e) {
				System.err.println(e);
			}
		}
	}
}