# Pre-order set graph.
# This class models an incremental pre-order graph where new nodes and edges can be added (but not removed).
# Pre-order graph has two characteristics:
#  * reflexivity: an element is in relation with itself (ie `self.has(e) implies self.has_edge(e,e)`)
#  * transitivity: `(self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)`
#
# Nodes and edges are added to the POSet.
#
# ~~~
# var pos = new POSet[String]
# pos.add_edge("A", "B") # add A->B
# pos.add_edge("B", "C") # add B->C
# pos.add_node("D") # add unconnected node "D"
#
# # A -> B -> C    D
#
# assert pos.has_edge("A", "B") == true  # direct
# ~~~
#
# Since a poset is transitive, direct and indirect edges are considered by default.
# Direct edges (transitive-reduction) can also be considered independently.
#
# ~~~
# assert pos.has_edge("A", "C") == true  # indirect
# assert pos.has_edge("A", "D") == false # no edge
# assert pos.has_edge("B", "A") == false # edges are directed
#
# assert pos.has_direct_edge("A", "B") == true  # direct
# assert pos.has_direct_edge("A", "C") == false # indirect
# ~~~
#
# POSet are dynamic.
# It means that the transitivity is updated while new nodes and edges are added.
# The transitive-reduction (*direct edges*)) is also updated,
# so adding new edges can make some direct edge to disappear.
#
# ~~~
# pos.add_edge("A","D")
# pos.add_edge("D","B")
# pos.add_edge("A","E")
# pos.add_edge("E","C")
#
# # A -> D -> B
# # |         |
# # v         v
# # E ------> C
#
# assert pos.has_edge("D", "C") == true # new indirect edge
# assert pos.has_edge("A", "B") == true # still an edge
# assert pos.has_direct_edge("A", "B") == false  # but no-more a direct one
# ~~~
#
# Thanks to the `[]` method, elements can be considered relatively to the poset.
# SEE `POSetElement`
class POSet[E]
	super Collection[E]
	super Comparator
	super Cloneable
	super Serializable

	redef type COMPARED: E is fixed

	redef fun iterator do return elements.keys.iterator

	# All the nodes
	private var elements = new HashMap[E, POSetElement[E]]

	redef fun has(e) do return self.elements.keys.has(e)

	# Add a node (an element) to the posed
	# The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
	# Return the POSetElement associated to `e`.
	# If `e` is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
	fun add_node(e: E): POSetElement[E]
	do
		if elements.keys.has(e) then return self.elements[e]
		var poe = new POSetElement[E](self, e, elements.length)
		poe.tos.add(e)
		poe.froms.add(e)
		self.elements[e] = poe
		return poe
	end

	# Return a view of `e` in the poset.
	# This allows to view the elements in their relation with others elements.
	#
	#     var poset = new POSet[String]
	#     poset.add_chain(["A", "B", "D"])
	#     poset.add_chain(["A", "C", "D"])
	#     var a = poset["A"]
	#     assert a.direct_greaters.has_exactly(["B", "C"])
	#     assert a.greaters.has_exactly(["A", "B", "C", "D"])
	#     assert a.direct_smallers.is_empty
	#
	# REQUIRE: has(e)
	fun [](e: E): POSetElement[E]
	do
		assert elements.keys.has(e)
		return self.elements[e]
	end

	# Add an edge from `f` to `t`.
	# Because a POSet is transitive, all transitive edges are also added to the graph.
	# If the edge already exists, the this function does nothing.
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_edge("A", "B") # add A->B
	# assert pos.has_edge("A", "C") == false
	# pos.add_edge("B", "C") # add B->C
	# assert pos.has_edge("A", "C") == true
	# ~~~
	#
	# If a reverse edge (from `t` to `f`) already exists, a loop is created.
	#
	# FIXME: Do something clever to manage loops.
	fun add_edge(f, t: E)
	do
		var fe = add_node(f)
		var te = add_node(t)
		# Skip if edge already present
		if fe.tos.has(t) then return
		# Add the edge and close the transitivity
		for ff in fe.froms do
			var ffe = self.elements[ff]
			for tt in te.tos do
				var tte = self.elements[tt]
				tte.froms.add ff
				ffe.tos.add tt
			end
		end
		# Update the transitive reduction
		if te.tos.has(f) then return # Skip the reduction if there is a loop

		# Remove transitive edges.
		# Because the sets of direct is iterated, the list of edges to remove
		# is stored and is applied after the iteration.
		# The usual case is that no direct edges need to be removed,
		# so start with a `null` list of edges.
		var to_remove: nullable Array[E] = null
		for x in te.dfroms do
			var xe = self.elements[x]
			if xe.tos.has(f) then
				if to_remove == null then to_remove = new Array[E]
				to_remove.add x
				xe.dtos.remove(t)
			end
		end
		if to_remove != null then
			for x in to_remove do te.dfroms.remove(x)
			to_remove.clear
		end

		for x in fe.dtos do
			var xe = self.elements[x]
			if xe.froms.has(t) then
				xe.dfroms.remove(f)
				if to_remove == null then to_remove = new Array[E]
				to_remove.add x
			end
		end
		if to_remove != null then
			for x in to_remove do fe.dtos.remove(x)
		end

		fe.dtos.add t
		te.dfroms.add f
	end

	# Add an edge between all elements of `es` in order.
	#
	# ~~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D"])
	# assert pos.has_direct_edge("A", "B")
	# assert pos.has_direct_edge("B", "C")
	# assert pos.has_direct_edge("C", "D")
	# ~~~~
	fun add_chain(es: SequenceRead[E])
	do
		if es.is_empty then return
		var i = es.iterator
		var e = i.item
		i.next
		for f in i do
			add_edge(e, f)
			e = f
		end
	end

	# Is there an edge (transitive or not) from `f` to `t`?
	#
	# SEE: `add_edge`
	#
	# Since the POSet is reflexive, true is returned if `f == t`.
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_node("A")
	# assert pos.has_edge("A", "A") == true
	# ~~~
	fun has_edge(f,t: E): Bool
	do
		if not elements.keys.has(f) then return false
		var fe = self.elements[f]
		return fe.tos.has(t)
	end

	# Is there a direct edge from `f` to `t`?
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C"]) # add A->B->C
	# assert pos.has_direct_edge("A", "B") == true
	# assert pos.has_direct_edge("A", "C") == false
	# assert pos.has_edge("A", "C")        == true
	# ~~~
	#
	# Note that because of loops, the result may not be the expected one.
	fun has_direct_edge(f,t: E): Bool
	do
		if not elements.keys.has(f) then return false
		var fe = self.elements[f]
		return fe.dtos.has(t)
	end

	# Write the POSet as a graphviz digraph.
	#
	# Nodes are labeled with their `to_s` so homonymous nodes may appear.
	# Edges are unlabeled.
	fun write_dot(f: Writer)
	do
		f.write "digraph \{\n"
		var ids = new HashMap[E, Int]
		for x in elements.keys do
			ids[x] = ids.length
		end
		for x in elements.keys do
			var xstr = (x or else "null").to_s.escape_to_dot
			var nx = "n{ids[x]}"
			f.write "{nx}[label=\"{xstr}\"];\n"
			var xe = self.elements[x]
			for y in xe.dtos do
				var ny = "n{ids[y]}"
				if self.has_edge(y,x) then
					f.write "{nx} -> {ny}[dir=both];\n"
				else
					f.write "{nx} -> {ny};\n"
				end
			end
		end
		f.write "\}\n"
	end

	# Display the POSet in a graphical windows.
	# Graphviz with a working -Txlib is expected.
	#
	# See `write_dot` for details.
	fun show_dot
	do
		var f = new ProcessWriter("dot", "-Txlib")
		write_dot(f)
		f.close
		f.wait
	end

	# Compare two elements in an arbitrary total order.
	#
	# This function is mainly used to sort elements of the set in an coherent way.
	#
	# ~~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D", "E"])
	# pos.add_chain(["A", "X", "C", "Y", "E"])
	# var a = ["X", "C", "E", "A", "D"]
	# pos.sort(a)
	# assert a == ["E", "D", "C", "X", "A"]
	# ~~~~
	#
	# POSet are not necessarily total orders because some distinct elements may be incomparable (neither greater or smaller).
	# Therefore this method relies on arbitrary linear extension.
	# This linear extension is a lawful total order (transitive, anti-symmetric, reflexive, and total), so can be used to compare the elements.
	#
	# The abstract behavior of the method is thus the following:
	#
	# ~~~~nitish
	# if a == b then return 0
	# if has_edge(b, a) then return -1
	# if has_edge(a, b) then return 1
	# return -1 or 1 # according to the linear extension.
	# ~~~~
	#
	# Note that the linear extension is stable, unless a new node or a new edge is added.
	redef fun compare(a, b)
	do
		var ae = self.elements[a]
		var be = self.elements[b]
		var res = ae.tos.length <=> be.tos.length
		if res != 0 then return res
		return elements[a].count <=> elements[b].count
	end

	# Filter elements to return only the smallest ones
	#
	# ~~~
	# var s = new POSet[String]
	# s.add_edge("B", "A")
	# s.add_edge("C", "A")
	# s.add_edge("D", "B")
	# s.add_edge("D", "C")
	# assert s.select_smallest(["A", "B"]) == ["B"]
	# assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
	# assert s.select_smallest(["B", "C", "D"]) == ["D"]
	# ~~~
	fun select_smallest(elements: Collection[E]): Array[E]
	do
		var res = new Array[E]
		for e in elements do
			for f in elements do
				if e == f then continue
				if has_edge(f, e) then continue label
			end
			res.add(e)
		end label
		return res
	end

	# Filter elements to return only the greatest ones
	#
	# ~~~
	# var s = new POSet[String]
	# s.add_edge("B", "A")
	# s.add_edge("C", "A")
	# s.add_edge("D", "B")
	# s.add_edge("D", "C")
	# assert s.select_greatest(["A", "B"]) == ["A"]
	# assert s.select_greatest(["A", "B", "C"]) == ["A"]
	# assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
	# ~~~
	fun select_greatest(elements: Collection[E]): Array[E]
	do
		var res = new Array[E]
		for e in elements do
			for f in elements do
				if e == f then continue
				if has_edge(e, f) then continue label
			end
			res.add(e)
		end label
		return res
	end

	# Sort a sorted array of poset elements using linearization order
	# ~~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D", "E"])
	# pos.add_chain(["A", "X", "C", "Y", "E"])
	# var a = pos.linearize(["X", "C", "E", "A", "D"])
	# assert a == ["E", "D", "C", "X", "A"]
	# ~~~~
	fun linearize(elements: Collection[E]): Array[E] do
		var lin = elements.to_a
		sort(lin)
		return lin
	end

	redef fun clone do return sub(self)

	# Return an induced sub-poset
	#
	# The elements of the result are those given in argument.
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D", "E"])
	# pos.add_chain(["A", "X", "C", "Y", "E"])
	#
	# var pos2 = pos.sub(["A", "B", "D", "Y", "E"])
	# assert pos2.has_exactly(["A", "B", "D", "Y", "E"])
	# ~~~
	#
	# The full relationship is preserved between the provided elements.
	#
	# ~~~
	# for e1 in pos2 do for e2 in pos2 do
	#    assert pos2.has_edge(e1, e2) == pos.has_edge(e1, e2)
	# end
	# ~~~
	#
	# Not that by definition, the direct relationship is the transitive
	# reduction of the full reduction. Thus, the direct relationship of the
	# sub-poset may not be included in the direct relationship of self because an
	# indirect edge becomes a direct one if all the intermediates elements
	# are absent in the sub-poset.
	#
	# ~~~
	# assert pos.has_direct_edge("B", "D")  == false
	# assert pos2.has_direct_edge("B", "D") == true
	#
	# assert pos2["B"].direct_greaters.has_exactly(["D", "Y"])
	# ~~~
	#
	# If the `elements` contains all then the result is a clone of self.
	#
	# ~~~
	# var pos3 = pos.sub(pos)
	# assert pos3 == pos
	# assert pos3 == pos.clone
	# ~~~
	fun sub(elements: Collection[E]): POSet[E]
	do
		var res = new POSet[E]
		for e in self do
			if not elements.has(e) then continue
			res.add_node(e)
		end
		for e in res do
			for f in self[e].greaters do
				if not elements.has(f) then continue
				res.add_edge(e, f)
			end
		end
		return res
	end

	# Two posets are equal if they contain the same elements and edges.
	#
	# ~~~
	# var pos1 = new POSet[String]
	# pos1.add_chain(["A", "B", "C", "D", "E"])
	# pos1.add_chain(["A", "X", "C", "Y", "E"])
	#
	# var pos2 = new POSet[Object]
	# pos2.add_edge("Y", "E")
	# pos2.add_chain(["A", "X", "C", "D", "E"])
	# pos2.add_chain(["A", "B", "C", "Y"])
	#
	# assert pos1 == pos2
	#
	# pos1.add_edge("D", "Y")
	# assert pos1 != pos2
	#
	# pos2.add_edge("D", "Y")
	# assert pos1 == pos2
	#
	# pos1.add_node("Z")
	# assert pos1 != pos2
	# ~~~
	redef fun ==(other) do
		if not other isa POSet[nullable Object] then return false
		if not self.elements.keys.has_exactly(other.elements.keys) then return false
		for e, ee in elements do
			if ee.direct_greaters != other[e].direct_greaters then return false
		end
		assert hash == other.hash
		return true
	end

	redef fun hash
	do
		var res = 0
		for e, ee in elements do
			if e == null then continue
			res += e.hash
			res += ee.direct_greaters.length
		end
		return res
	end

	redef fun core_serialize_to(serializer)
	do
		# Optimize written data because this structure has duplicated data
		# For example, serializing the class hierarchy of a simple program where E is String
		# result is before: 200k, after: 56k.
		serializer.serialize_attribute("elements", elements)
	end

	redef init from_deserializer(deserializer)
	do
		deserializer.notify_of_creation self
		var elements = deserializer.deserialize_attribute("elements")
		if elements isa HashMap[E, POSetElement[E]] then
			self.elements = elements
		end
	end
end