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

Reply via email to