# ModelIndex indexes mentities by their name and full name
#
# It provides methods to find mentities based on a prefix or string similarity.
#
# ~~~nitish
# # Build index
# var index = new ModelIndex
# for mentity in model.collect_mentities do
#	if mentity isa MClassDef or mentity isa MPropDef then continue
#	index.index(mentity)
# end
#
# for e in index.find("Foo").uniq.sort(new ScoreComparator).limit(10) do
#	print " * {e.score}: {e.mentity.name} ({e.mentity.full_name})"
# end
# ~~~
class ModelIndex

	# List of all indexed mentities.
	#
	# Faster than traversing the tries.
	var mentities = new Array[MEntity]

	# Map of all mentities indexed by their `name`
	var names = new HashMap[String, Array[MEntity]]

	# Prefix tree for mentities `name`
	#
	# Because multiple mentities can share the same `name`, we use a Trie of
	# arrays of mentities.
	#
	# As for now, we do not index class and property definitions.
	# TODO add an option.
	var name_prefixes = new Trie[Array[MEntity]]

	# Distance tree for mentities `name`
	var name_distances = new BKTree

	# Map of all mentities indexed by their `full_name`
	var full_names = new HashMap[String, MEntity]

	# Prefix tree for mentities `full_name`
	#
	# Even if two mentities cannot share the same `full_name`, we use a Trie of
	# arrays of mentities to be consistent with `name_prefixes`.
	var full_name_prefixes = new Trie[Array[MEntity]]

	# Distance tree for mentities `full_name`
	var full_name_distances = new BKTree

	# Index `mentity` by it's `MEntity::name`
	#
	# See `name_prefixes`.
	private fun index_by_name(mentity: MEntity) do
		var name = mentity.name

		# Index name
		if not names.has_key(name) then
			names[name] = new Array[MEntity]
		end
		names[name].add mentity

		# Index prefix
		if not name_prefixes.has_key(name) then
			name_prefixes[name] = new Array[MEntity]
		end
		name_prefixes[name].add mentity

		# Index distance
		name_distances.add(name)
	end

	# Index `mentity` by its `MEntity::full_name`
	private fun index_by_full_name(mentity: MEntity) do
		var name = mentity.full_name

		# Index full name
		full_names[name] = mentity

		# Index prefix
		if not full_name_prefixes.has_key(name) then
			full_name_prefixes[name] = new Array[MEntity]
		end
		full_name_prefixes[name].add mentity

		# Index distance
		full_name_distances.add(name)
	end

	# Index `mentity` so it can be retrieved by a find query
	#
	# MEntities are indexed by both name and full_name.
	fun index(mentity: MEntity) do
		mentities.add mentity
		index_by_name mentity
		index_by_full_name mentity
	end

	# Translate Trie results to `SearchResult`
	#
	# This method is used internally to translate each mentity returned by a prefix
	# match in a Trie into a SearchResult that can be ranked by score.
	#
	# Results from the Trie are returned in a breadth first manner so we get the
	# matches ordered by prefix.
	# We preserve that order by giving an incremental score to the `array` items.
	private fun score_results_incremental(array: Array[Array[MEntity]], filter: nullable ModelFilter): IndexMatches do
		var results = new IndexMatches
		var score = 1
		for mentities in array do
			for mentity in mentities do
				if filter != null and not filter.accept_mentity(mentity) then continue
				results.add new IndexMatch(mentity, score)
			end
			score += 1
		end
		return results
	end

	# Find all mentities where `MEntity::name` matches the `prefix`
	fun find_by_name_prefix(prefix: String, filter: nullable ModelFilter): IndexMatches do
		return score_results_incremental(name_prefixes.find_by_prefix(prefix), filter)
	end

	# Find all mentities where `MEntity::full_name` matches the `prefix`
	fun find_by_full_name_prefix(prefix: String, filter: nullable ModelFilter): IndexMatches do
		return score_results_incremental(full_name_prefixes.find_by_prefix(prefix), filter)
	end

	# Rank all mentities by the distance between `MEntity::name` and `name`
	#
	# Use the Levenshtein algorithm on all the indexed mentities `name`.
	# Warning: may not scale to large indexes.
	fun find_by_name_similarity(name: String, filter: nullable ModelFilter): IndexMatches do
		var results = new IndexMatches
		for match in name_distances.search(name) do
			var dist = match.distance
			var mname = match.key
			if not names.has_key(mname) then continue
			for mentity in names[mname] do
				if mentity isa MClassDef or mentity isa MPropDef then continue
				if filter != null and not filter.accept_mentity(mentity) then continue
				results.add new IndexMatch(mentity, dist)
			end
		end
		return results
	end

	# Rank all mentities by the distance between `MEntity::full_name` and `full_name`
	#
	# Use the Levenshtein algorithm on all the indexed mentities `full_name`.
	# Warning: may not scale to large indexes.
	fun find_by_full_name_similarity(name: String, filter: nullable ModelFilter): IndexMatches do
		var results = new IndexMatches
		for match in full_name_distances.search(name) do
			var dist = match.distance
			var mname = match.key
			if not full_names.has_key(mname) then continue
			var mentity = full_names[mname]
			if mentity isa MClassDef or mentity isa MPropDef then continue
			if filter != null and not filter.accept_mentity(mentity) then continue
			results.add new IndexMatch(mentity, dist)
		end
		return results
	end

	# Rank all mentities by the distance between `name` and both the mentity name and full name
	fun find_by_similarity(name: String, filter: nullable ModelFilter): IndexMatches do
		var results = new IndexMatches
		results.add_all find_by_full_name_similarity(name, filter)
		results.add_all find_by_name_similarity(name, filter)
		return results
	end

	# Find mentities by name trying first by prefix then by similarity
	fun find_by_name(name: String, filter: nullable ModelFilter): IndexMatches do
		var results = find_by_name_prefix(name, filter)
		results.add_all find_by_name_similarity(name, filter)
		return results
	end

	# Find mentities by full name trying firt by prefix then by similarity
	fun find_by_full_name(name: String, filter: nullable ModelFilter): IndexMatches do
		var results = find_by_full_name_prefix(name)
		results.add_all find_by_full_name_similarity(name, filter)
		return results
	end

	# Find all mentities that matches `name`
	#
	# 1. try by name prefix
	# 2. add full name prefix matches
	# 3. try similarity by name
	# 4. try similarity by full_name
	fun find(name: String, filter: nullable ModelFilter): IndexMatches do
		var results = find_by_name_prefix(name, filter)
		results.add_all find_by_full_name_prefix(name, filter)
		results.add_all find_by_similarity(name, filter)
		return results
	end
end