Hello Thanks for your answer. Yes it should throw an exception - there should be no cyclic orders.
I want to use this for the initialisation functions of the game I am developing (http://resatori.com/cyber-dungeon-quest-alpha-1) There is a number of those functions and some need to come after some others; most of them dont care about order. I thougt about the best way to do is, is introducing an :after key and a type. So after the gui is initialized, i can add frames for example. On 9 Mai, 07:07, Ken Wesson <kwess...@gmail.com> wrote: > On Sun, May 8, 2011 at 10:56 PM, msappler <damnedmar...@web.de> wrote: > > I want to order a sequence of maps with keys: > > obligatory :type > > optional :before [types]; which means the types should occur before > > this element in the sequence. > > That's a quite complex and somewhat difficult problem. > > First of all, what if you have > > A: {:type :foo :before [:bar]} > B: {:type :bar :before [:foo]} > ? > > Which comes first then? > > Probably you should throw an Exception or an Error then because the > constraints are unsatisfiable. > > More generally, the :before values create directed outbound edges of a > directed graph and this needs to be acyclic. If it's cyclic you have a > problem. Otherwise, you can order the nodes such that any node is > "left" of any node it has an outbound edge to -- nodes with no > outbound edges are at far "right", nodes with outbound edges to them > are one "step" to the left, nodes with outbound edges to those are two > "steps" to the left, and so forth. This determines a partial order on > the nodes by how-far-"left", and you want to sort by this, and sort on > :type as the tiebreaker within the nodes that are a particular > distance "left". > > Something like this: > > (defn subset? [a-seq a-set] > (if a-seq > (if (contains? a-set (first a-seq)) > (recur (next a-seq) a-set)) > true)) > > (defn presort [node-seq] > (loop [out nil nodes node-seq] > (if (empty? nodes) > out > (let [toright (set (map :type (apply concat out))) > nextnode? #(subset? (seq (:before %)) toright) > nextnodes (filter nextnode? nodes)] > (if (empty? nextnodes) (throw (Error. "circularity"))) > (recur (cons nextnodes out) (remove nextnode? nodes)))))) > > (defn sort [node-seq] > (mapcat #(sort-by :type %) (presort node-seq))) > > user=> (sort [{:type 1 :before [2 5]} {:type 2} {:type 3 :before [4]} > {:type 4 :before []} {:type 5 :before [4]}]) > ({:type 1, > :before [2 5]} > {:type 3, > :before [4]} > {:type 5, > :before [4]} > {:type 2} > {:type 4, > :before []}) > user=> -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
