<commit_before>package ru.bsearch

import org.junit.Test
import org.scalatest.matchers.ShouldMatchers

/**
 * User: dima
 * Date: 18/06/2012
 */

class BSearch13 extends ShouldMatchers {
	@Test def should_find_element_index_in_a_sequence() {
		bsearch(1, Seq()) should equal(None)

		bsearch(0, Seq(1)) should equal(None)
		bsearch(1, Seq(1)) should equal(Some(0))
		bsearch(2, Seq(1)) should equal(None)

		bsearch(0, Seq(1, 2)) should equal(None)
		bsearch(1, Seq(1, 2)) should equal(Some(0))
		bsearch(2, Seq(1, 2)) should equal(Some(1))
		bsearch(3, Seq(1, 2)) should equal(None)

		bsearch(0, Seq(1, 2, 3)) should equal(None)
		bsearch(1, Seq(1, 2, 3)) should equal(Some(0))
		bsearch(2, Seq(1, 2, 3)) should equal(Some(1))
		bsearch(3, Seq(1, 2, 3)) should equal(Some(2))
		bsearch(4, Seq(1, 2, 3)) should equal(None)
	}

	case class State(n: Int, values: Seq[Int], shift: Int, result: Option[Option[Int]])

	def bsearch(n: Int, values: Seq[Int]): Option[Int] = {
		var state = State(n, values, 0, None)
		while (state.result == None) {
			state = doBinarySearch(state.n, state.values, state.shift)
		}
		state.result.get
	}

	@Test def should_go_from_one_state_of_binary_search_to_another() {
		doBinarySearch(1, Seq(), 0) should equal(State(1, Seq(), 0, Some(None)))

		doBinarySearch(0, Seq(1), 0) should equal(State(0, Seq(), 0, None))
		doBinarySearch(1, Seq(1), 0) should equal(State(1, Seq(1), 0, Some(Some(0))))
		doBinarySearch(2, Seq(1), 0) should equal(State(2, Seq(), 1, None))

		doBinarySearch(0, Seq(1, 2), 0) should equal(State(0, Seq(1), 0, None))
		doBinarySearch(1, Seq(1, 2), 0) should equal(State(1, Seq(1), 0, None))
		doBinarySearch(2, Seq(1, 2), 0) should equal(State(2, Seq(1, 2), 0, Some(Some(1))))
		doBinarySearch(3, Seq(1, 2), 0) should equal(State(3, Seq(), 2, None))

		doBinarySearch(0, Seq(1, 2, 3), 0) should equal(State(0, Seq(1), 0, None))
		doBinarySearch(1, Seq(1, 2, 3), 0) should equal(State(1, Seq(1), 0, None))
		doBinarySearch(2, Seq(1, 2, 3), 0) should equal(State(2, Seq(1, 2, 3), 0, Some(Some(1))))
		doBinarySearch(3, Seq(1, 2, 3), 0) should equal(State(3, Seq(3), 2, None))
		doBinarySearch(4, Seq(1, 2, 3), 0) should equal(State(4, Seq(3), 2, None))

		doBinarySearch(1, Seq(1), 3) should equal(State(1, Seq(1), 3, Some(Some(3))))
	}

	def doBinarySearch(n: Int, values: Seq[Int], shift: Int): State = {
		if (values.isEmpty) return State(n, values, shift, Some(None))

		val midPos = values.size / 2
		if (n == values(midPos)) State(n, values, shift, Some(Some(shift + midPos)))
		else if (n < values(midPos)) State(n, values.slice(0, midPos), shift, None)
		else State(n, values.slice(midPos + 1, values.size), shift + midPos + 1, None)
	}
}<commit_msg>bsearch 13<commit_after>package ru.bsearch

import org.junit.Test
import org.scalatest.matchers.ShouldMatchers

/**
 * User: dima
 * Date: 18/06/2012
 */

class BSearch13 extends ShouldMatchers {
	@Test def should_find_element_index_in_a_sequence() {
		bsearch(1, Seq()) should equal(None)

		bsearch(0, Seq(1)) should equal(None)
		bsearch(1, Seq(1)) should equal(Some(0))
		bsearch(2, Seq(1)) should equal(None)

		bsearch(0, Seq(1, 2)) should equal(None)
		bsearch(1, Seq(1, 2)) should equal(Some(0))
		bsearch(2, Seq(1, 2)) should equal(Some(1))
		bsearch(3, Seq(1, 2)) should equal(None)

		bsearch(0, Seq(1, 2, 3)) should equal(None)
		bsearch(1, Seq(1, 2, 3)) should equal(Some(0))
		bsearch(2, Seq(1, 2, 3)) should equal(Some(1))
		bsearch(3, Seq(1, 2, 3)) should equal(Some(2))
		bsearch(4, Seq(1, 2, 3)) should equal(None)
	}

	@Test def should_go_from_one_state_of_binary_search_to_another() {
		doBinarySearch(1, Seq(), 0) should equal(State(1, Seq(), 0, Some(None)))

		doBinarySearch(0, Seq(1), 0) should equal(State(0, Seq(), 0, None))
		doBinarySearch(1, Seq(1), 0) should equal(State(1, Seq(1), 0, Some(Some(0))))
		doBinarySearch(2, Seq(1), 0) should equal(State(2, Seq(), 1, None))

		doBinarySearch(0, Seq(1, 2), 0) should equal(State(0, Seq(1), 0, None))
		doBinarySearch(1, Seq(1, 2), 0) should equal(State(1, Seq(1), 0, None))
		doBinarySearch(2, Seq(1, 2), 0) should equal(State(2, Seq(1, 2), 0, Some(Some(1))))
		doBinarySearch(3, Seq(1, 2), 0) should equal(State(3, Seq(), 2, None))

		doBinarySearch(0, Seq(1, 2, 3), 0) should equal(State(0, Seq(1), 0, None))
		doBinarySearch(1, Seq(1, 2, 3), 0) should equal(State(1, Seq(1), 0, None))
		doBinarySearch(2, Seq(1, 2, 3), 0) should equal(State(2, Seq(1, 2, 3), 0, Some(Some(1))))
		doBinarySearch(3, Seq(1, 2, 3), 0) should equal(State(3, Seq(3), 2, None))
		doBinarySearch(4, Seq(1, 2, 3), 0) should equal(State(4, Seq(3), 2, None))

		doBinarySearch(1, Seq(1), 3) should equal(State(1, Seq(1), 3, Some(Some(3))))
	}

	case class State(n: Int, values: Seq[Int], shift: Int, result: Option[Option[Int]]) {
		def next(that: State): State = {
			if (values.isEmpty) return State(n, values, shift, Some(None))

			val midPos = values.size / 2

			if (n == values(midPos)) State(n, values, shift, Some(Some(shift + midPos)))
			else if (n < values(midPos)) State(n, values.slice(0, midPos), shift, None)
			else State(n, values.slice(midPos + 1, values.size), shift + midPos + 1, None)
		}
	}

	def bsearch(n: Int, values: Seq[Int]): Option[Int] = {
		var state = State(n, values, 0, None)
		while (state.result == None) {
			state = doBinarySearch(state.n, state.values, state.shift)
		}
		state.result.get
	}

	def doBinarySearch(n: Int, values: Seq[Int], shift: Int): State = {
		if (values.isEmpty) return State(n, values, shift, Some(None))

		val midPos = values.size / 2
		if (n == values(midPos)) State(n, values, shift, Some(Some(shift + midPos)))
		else if (n < values(midPos)) State(n, values.slice(0, midPos), shift, None)
		else State(n, values.slice(midPos + 1, values.size), shift + midPos + 1, None)
	}
}
{'fraction_non_alphanumeric': 0.18838331609789727, 'fraction_numerical': 0.05618752154429507, 'mean_word_length': 4.994834710743802, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3094298', 'n_tokens_mistral': 2627, 'n_tokens_neox': 2364, 'n_words': 622}