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
