# Formal Context
#
# A formal context is a triple *K = (G, M, I)*, where *G* is a set of `objects`,
# *M* is a set of `attributes`, and *I ⊆ G × M* is a binary relation called incidence
# that expresses which objects have which attributes (`objects_attributes`).
#
# Predicate *gIm* designates object *g*'s having attribute *m*.
# For a subset *A ⊆ G* of objects and a subset *B ⊆ M* of attributes, one defines
# two derivation operators as follows:
#
# * *A' = {m ∈ M | ∀ g ∈ A, gIm}*, and dually
# * *B' = {g ∈ G | ∀ m ∈ B, gIm}*.
class FormalContext[O: Object, A: Object]

	# Objects in the context
	var objects = new HashSet[O]

	# Attributes considered to build concepts
	var attributes = new HashSet[A]

	# Association between objects and attributes
	var objects_attributes = new HashMap[O, Set[A]]

	# Associate a set of `attributes` to `object`
	fun set_object_attributes(object: O, attributes: Collection[A]) do
		for attribute in attributes do
			set_object_attribute(object, attribute)
		end
	end

	# Associate an `attribute` to `object`
	fun set_object_attribute(object: O, attribute: A) do
		attributes.add attribute
		objects.add object
		if not objects_attributes.has_key(object) then
			objects_attributes[object] = new HashSet[A]
		end
		objects_attributes[object].add attribute
	end

	# Derive the set of formal concepts from the objects and attributes
	fun formal_concepts: Set[FormalConcept[O, A]] do
		# black magic!

		var concepts = new HashSet[FormalConcept[O, A]]

		var extentsByAttr = new HashMap[Set[A], Set[O]]
		for attribute in attributes do
			var ka = new HashSet[A].from([attribute])
			extentsByAttr[ka] = new HashSet[O]
			for object in objects do
				if not objects_attributes[object].has(attribute) then continue
				extentsByAttr[ka].add(object)
			end
		end

		var nextents = new HashMap[Set[A], Set[O]]
		for k1, v1 in extentsByAttr do
			for k2, v2 in extentsByAttr do
				if k1 == k2 then continue
				var n = v1.intersection(v2)
				if extentsByAttr.values.has(n) then continue
				var ka = k1.union(k2)
				nextents[ka] = n
			end
		end
		extentsByAttr.add_all nextents

		var contained = true
		for k1, v1 in extentsByAttr do
			if not contained then break
			for k2, v2 in extentsByAttr do
				if k1 == k2 then continue
				var n = v1.intersection(v2)
				if extentsByAttr.values.has(n) then continue
				contained = false
				break
			end
		end

		if contained then
			extentsByAttr[new HashSet[A]] = new HashSet[O].from(objects)
		end

		var extents = new HashSet[Set[O]]
		for objects in extentsByAttr.values do
			extents.add objects
		end

		for extent in extents do
			var intents: Set[A] = new HashSet[A]
			var count = 0
			var cl = new FormalConcept[O, A]
			if extent.is_empty then
				intents.add_all(attributes)
			else
				for object in objects do
					if not extent.has(object) then continue
					var prev = objects_attributes[object]
					if count > 0 then
						intents = prev.intersection(intents)
					else
						intents = prev
					end
					count += 1
					cl.objects.add(object)
				end
			end
			cl.attributes.add_all intents
			concepts.add cl
		end

		return concepts
	end
end