From 1bb5297e44de15e0885e38b6d4a0f0cde3ca1398 Mon Sep 17 00:00:00 2001
From: Claudio Sacerdoti Coen <claudio.sacerdoticoen@unibo.it>
Date: Thu, 28 Sep 2006 11:51:22 +0000
Subject: [PATCH] Implemented topological sorting according to the
 dependencies.

---
 components/metadata/metadataDeps.ml  | 10 ++++++++++
 components/metadata/metadataDeps.mli |  3 +++
 2 files changed, 13 insertions(+)

diff --git a/components/metadata/metadataDeps.ml b/components/metadata/metadataDeps.ml
index b393dbb91..f2b1d0496 100644
--- a/components/metadata/metadataDeps.ml
+++ b/components/metadata/metadataDeps.ml
@@ -91,6 +91,16 @@ let inverse_deps ~dbd uri =
   do_query (MetadataTypes.obj_tbl ())
     @ do_query MetadataTypes.library_obj_tbl
 
+let topological_sort ~dbd uris =
+ let module OrderedUri =
+  struct
+   type t = UriManager.uri
+   let compare = UriManager.compare
+  end in
+ let module Topo = HTopoSort.Make(OrderedUri) in
+  Topo.topological_sort uris
+   (fun uri -> fst (List.split (direct_deps ~dbd uri)))
+
 module DepGraph =
 struct
   module UriTbl = UriManager.UriHashtbl
diff --git a/components/metadata/metadataDeps.mli b/components/metadata/metadataDeps.mli
index ee0954d05..f5a6ac22e 100644
--- a/components/metadata/metadataDeps.mli
+++ b/components/metadata/metadataDeps.mli
@@ -35,6 +35,9 @@ val inverse_deps:
   dbd:HMysql.dbd ->
   UriManager.uri -> (UriManager.uri * MetadataTypes.position) list
 
+val topological_sort:
+  dbd:HMysql.dbd -> UriManager.uri list -> UriManager.uri list
+
   (** Representation of a (lazy) dependency graph.
    * Imperative data structure. *)
 module DepGraph:
-- 
2.39.2