list_schema.edn

;;   Copyright 2014 Pellucid Analytics
;;
;;   Licensed under the Apache License, Version 2.0 (the "License");
;;   you may not use this file except in compliance with the License.
;;   You may obtain a copy of the License at
;;
;;       http://www.apache.org/licenses/LICENSE-2.0
;;
;;   Unless required by applicable law or agreed to in writing, software
;;   distributed under the License is distributed on an "AS IS" BASIS,
;;   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
;;   See the License for the specific language governing permissions and
;;   limitations under the License.


[

 ;; a linked list

 {:db/id #db/id[:db.part/db]
  :db/ident :linklist/first
  :db/valueType :db.type/ref
  :db/cardinality :db.cardinality/one
  :db/doc "The first node of this list"
  :db.install/_attribute :db.part/db}


 ;; a linked node

 {:db/id #db/id[:db.part/db]
  :db/ident :linknode/next
  :db/valueType :db.type/ref
  :db/cardinality :db.cardinality/one
  :db/doc "The node after this node"
  :db.install/_attribute :db.part/db}

 {:db/id #db/id[:db.part/db]
  :db/ident :linknode/list
  :db/valueType :db.type/ref
  :db/cardinality :db.cardinality/one
  :db/doc "The list this node belongs to"
  :db.install/_attribute :db.part/db}


 ;; the empty node

 [:db/add #db/id[:db.part/user] :db/ident :linknode/empty]


 ;; db functions

 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/prepend
  :db/doc
  "Tx fn to prepend an element to a list.
     Takes a database value, an entity id for a list,
     and an entity id to prepend."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-id]
   :code
   (do
     (when (= list-id
              (-> db
                  (d/entity elem-id)
                  (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "can't prepend an element already in the list")))
     (let [old-first (-> db
                         (d/entity list-id)
                         (get-in [:linklist/first :db/id] :linknode/empty))]
       [{:db/id elem-id
         :linknode/list list-id
         :linknode/next old-first}
        [:db/add list-id :linklist/first elem-id]]))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/find-last-node
  :db/doc
  "Db fn to find the last node of a list.
     Takes a database value and an entity id for a list"
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id]
   :code
   (->>
    (d/q '[:find ?node
           :in $ ?list
           :where
           [?node :linknode/next :linknode/empty]
           [?node :linknode/list ?list]]
         db list-id)
    ffirst)}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/append
  :db/doc
  "Tx fn to append an element to a list
     Takes a database value, an entity id for a list,
     and an entity id to append."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-id]
   :code
   (do
     (when (= list-id
              (-> db
                  (d/entity elem-id)
                  (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "can't append an element already in the list")))
     (let [last-id (d/invoke db :linklist.fn/find-last-node db list-id)]
       (if last-id
         [{:db/id elem-id
           :linknode/list list-id
           :linknode/next :linknode/empty}
          [:db/add last-id :linknode/next elem-id]]
         [[:linklist.fn/prepend list-id elem-id]])))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/insert
  :db/doc
  "Tx fn to insert an element into a list.
     Takes a database value, an entity id for a list,
     an entity id that is already present in the list,
     and an entity id to insert. The entity that is
     already present in the list will serve as the
     anchor for the insertion."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id anchor-id elem-id]
   :code
   (do
     (when (not= list-id
                 (-> db
                     (d/entity anchor-id)
                     (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "anchor element for insert must be in the list")))
     (when (= list-id
              (-> db
                  (d/entity elem-id)
                  (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "can't insert an element already in the list")))
     (let [after (-> db
                     (d/entity anchor-id)
                     (get-in [:linknode/next :db/id] :linknode/empty))]
       [{:db/id elem-id
         :linknode/list list-id
         :linknode/next after}
        [:db/add anchor-id :linknode/next elem-id]]))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/chain-elems
  :db/doc
  "A partial tx fn for chaining elems with a sequence of nodes.
     Takes a entity id for a list and a sequence of entity ids that
     will be chained together to be later added to the list. This
     is a helper function for other transaction functions."
  :db/fn #db/fn
  {:lang :clojure
   :params [list-id elem-ids]
   :code
   (concat
    (for [elem-id elem-ids]
      [:db/add elem-id :linknode/list list-id])
    (for [[elem-id next-id] (map vector elem-ids (next elem-ids))]
      [:db/add elem-id :linknode/next next-id]))}}

 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/initialize
  :db/doc
  "Tx fn to initialize a list.
     Takes a database value, a temp id for a list,
     and a sequence of temp ids for the initial elements."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-ids]
   :code
   (if-let [s (seq elem-ids)]
     [[:linklist.fn/chain-elems list-id s]
      [:db/add list-id :linklist/first (first s)]
      [:db/add (last s) :linknode/next :linknode/empty]]
     [[:db/add list-id :linklist/first :linknode/empty]])}}

 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/prepend-many
  :db/doc
  "Tx fn to prepend elements to a list.
     Takes a database value, an entity id for a list,
     and a sequence of entity ids to be prepended to the list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-ids]
   :code
   (do
     (when (empty? elem-ids)
       (throw (IllegalArgumentException. "elements to prepend must be non-empty")))
     (doseq [elem-id elem-ids]
       (when (= list-id
                (-> db
                    (d/entity elem-id)
                    (get-in [:linknode/list :db/id])))
         (throw (IllegalStateException. "can't prepend elements already in the list"))))
     (when-let [s (seq elem-ids)]
       (let [old-first (-> db
                           (d/entity list-id)
                           (get-in [:linklist/first :db/id] :linknode/empty))]
         [[:linklist.fn/chain-elems list-id s]
          [:db/add list-id :linklist/first (first s)]
          [:db/add (last s) :linknode/next old-first]])))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/append-many
  :db/doc
  "Tx fn to append elements to a list.
     Takes a database value, an entity id for a list,
     and a sequence of entity idds to be append to the list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-ids]
   :code
   (do
     (when (empty? elem-ids)
       (throw (IllegalArgumentException. "elements to append must be non-empty")))
     (doseq [elem-id elem-ids]
       (when (= list-id
                (-> db
                    (d/entity elem-id)
                    (get-in [:linknode/list :db/id])))
         (throw (IllegalStateException. "can't append elements already in the list"))))
     (when-let [s (seq elem-ids)]
       (let [old-last-id (d/invoke db :linklist.fn/find-last-node db list-id)]
         [[:linklist.fn/chain-elems list-id s]
          [:db/add (last s) :linknode/next :linknode/empty]
          (if old-last-id
            [:db/add old-last-id :linknode/next (first s)]
            [:db/add list-id :linklist/first (first s)])])))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/insert-many
  :db/doc
  "Tx fn to insert elements into a list after an anchor.
     Takes a database value, an entity id for a list,
     a entity id that is already present in the list,
     and a sequence of entity ids to be inserted into the list.
     The elements will be inserted after the anchor element."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id anchor-id elem-ids]
   :code
   (do
     (when (empty? elem-ids)
       (throw (IllegalArgumentException. "elements to insert must be non-empty")))
     (when (not= list-id
                 (-> db
                     (d/entity anchor-id)
                     (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "anchor element for insert must be in the list")))
     (doseq [elem-id elem-ids]
       (when (= list-id
                (-> db
                    (d/entity elem-id)
                    (get-in [:linknode/list :db/id])))
         (throw (IllegalStateException. "can't insert elements already in the list"))))
     (when-let [s (seq elem-ids)]
       (let [after (-> db
                       (d/entity anchor-id)
                       (get-in [:linknode/next :db/id] :linknode/empty))]
         [[:linklist.fn/chain-elems list-id s]
          [:db/add anchor-id :linknode/next (first s)]
          [:db/add (last s) :linknode/next after]])))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/remove-first
  :db/doc
  "Tx fn to remove the first element of the list.
     Takes a database value and an entity id for a list.
     The first entity in the list will be unlinked: this
     will only retract the linklist specific attributes
     on the entity."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id]
   :code
   (let [first-entity (-> db (d/entity list-id) (get :linklist/first))]
     (if (keyword? first-entity)
       (throw (IllegalStateException. "can't remove first of empty list"))
       (let [after (get-in first-entity [:linknode/next :db/id] :linknode/empty)]
         [[:db/add list-id :linklist/first after]
          [:db/retract (:db/id first-entity) :linknode/list list-id]
          [:db/retract (:db/id first-entity) :linknode/next after]])))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/find-before-and-after
  :db/doc
  "Db fn to query for the nodes before and after the given node.
     Takes a database value and an entity id for a list element.
     If they exist, this query will find the elements that come
     before and after in the list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db node-id]
   :code
   (->>
    (d/q '[:find ?before ?after
           :in $ ?node
           :where
           [?before :linknode/next ?node]
           [?node   :linknode/next ?after]]
         db node-id)
    first)}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/remove
  :db/doc
  "Tx fn to remove an element of the list.
     Takes a database value, and entity id for a list,
     and an entity id for an element to remove from the
     list. This will fail if the element is not in the
     list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-id]
   :code
   (do
     (when (not= list-id
                 (-> db
                     (d/entity elem-id)
                     (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "the element to remove must belong to the list")))
     (let [first-entity (-> db (d/entity list-id) (get :linklist/first))]
       (cond
        (keyword? first-entity)
        (throw (IllegalStateException. "can't remove from empty list"))
        (= elem-id (:db/id first-entity))
        (let [after (get-in first-entity [:linknode/next :db/id] :linknode/empty)]
          [[:db/add list-id :linklist/first after]
           [:db/retract elem-id :linknode/list list-id]
           [:db/retract elem-id :linknode/next after]])
        :else
        (let [[before-id after-id] (d/invoke db :linklist.fn/find-before-and-after db elem-id)]
          [[:db/add before-id :linknode/next after-id]
           [:db/retract elem-id :linknode/list list-id]
           [:db/retract elem-id :linknode/next after-id]]))))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/relink-nodes
  :db/doc
  "Partial tx fn to relink nodes to skip deleted nodes.
     Takes a collection of entity ids that are the
     elements of a list, and a set of entity ids that
     are the subset of these to delete. This returns
     tx data to relink the remaining entities."
  :db/fn #db/fn
  {:lang :clojure
   :params [node-ids delete-set]
   :code
   (loop [[last-id penul-id & rest-ids :as ids] (reverse node-ids)
          next-id :linknode/empty
          ops []]
     (cond
      (nil? last-id)                    ; empty, return accum
      [next-id ops]
      (delete-set last-id)
      (cond
       (nil? penul-id)                ; delete singleton, return accum
       [next-id ops]
       (delete-set penul-id)            ; delete last and penultimate
       (recur (rest ids) next-id ops)
       :else                           ; delete last, keep penultimate
       (recur rest-ids penul-id (conj ops [:db/add penul-id :linknode/next next-id])))
      :else                             ; keep last
      (recur (rest ids) last-id ops)))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/list-nodes
  :db/doc
  "Db fn to enumerate the entities in a list.
     Take a entity map of a list, and returns
     a vector of the element entities in order."
  :db/fn #db/fn
  {:lang :clojure
   :params [list-entity]
   :code
   (loop [n (:linklist/first list-entity)
          l []]
     (if (keyword? n)
       l
       (recur (:linknode/next n) (conj l n))))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/remove-many
  :db/doc
  "Tx fn to remove many elements from a list.
     Takes a database value, an entity id of a list,
     and a collection of entity ids to remove from
     the list. This will fail if any of the entities
     to delete are not in the list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-ids]
   :code
   (do
     (doseq [elem-id elem-ids]
       (when (not= list-id
                   (-> db
                       (d/entity elem-id)
                       (get-in [:linknode/list :db/id])))
         (throw (IllegalStateException. "the elements to be removed must belong to the list"))))
     (let [delete-set (set elem-ids)
           list-entity (d/entity db list-id)
           list-nodes (d/invoke db :linklist.fn/list-nodes list-entity)
           [first-id relink-tx] (d/invoke db :linklist.fn/relink-nodes (mapv :db/id list-nodes) delete-set)
           first-in-list (get-in list-entity [:linklist/first :db/id])]
       (concat
        (when (delete-set first-in-list) [[:db/add list-id :linklist/first first-id]])
        (map #(vector :db/retract % :linknode/list list-id) delete-set)
        (->>
         list-nodes
         (mapcat
          #(when
               (delete-set (:db/id %))
             [[:db/retract (:db/id %)
               :linknode/next (get-in % [:linknode/next :db/id] :linknode/empty)]])))
        relink-tx)))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/remove-and-prepend-many
  :db/doc
  "Tx fn to remove one collection of elems
     and prepend another collection of elems.
     Takes a database value, an entity id of a list,
     a collection of entity ids to remove from
     the list, and a collection of entity ids to
     prepend to the list. This will fail if any of
     the entities to remove are not in the list,
     or if any of the entities to add are already
     in the list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id delete-elem-ids new-elem-ids]
   :code
   (do
     (doseq [elem-id delete-elem-ids]
       (when (not= list-id
                   (-> db
                       (d/entity elem-id)
                       (get-in [:linknode/list :db/id])))
         (throw (IllegalStateException. "the elements to be removed must belong to the list"))))
     (doseq [elem-id new-elem-ids]
       (when
           (= list-id (-> db
                          (d/entity elem-id)
                          (get-in [:linknode/list :db/id])))
         (throw (IllegalStateException. "the elements to be added must not already be in the list"))))
     (let [delete-set (set delete-elem-ids)
           list-entity (d/entity db list-id)
           list-nodes (d/invoke db :linklist.fn/list-nodes list-entity)
           [first-id relink-tx] (d/invoke db :linklist.fn/relink-nodes (mapv :db/id list-nodes) delete-set)
           first-in-list (get-in list-entity [:linklist/first :db/id])]
       (concat
        (if-let [s (seq new-elem-ids)] ;; if there are new elems
          [[:db/add list-id :linklist/first (first s)]
           [:db/add (last s) :linknode/next first-id]
           [:linklist.fn/chain-elems list-id s]]
          ;; else relink first if first was deleted
          (when (delete-set first-in-list) [[:db/add list-id :linklist/first first-id]]))
        (map #(vector :db/retract % :linknode/list list-id) delete-set)
        (->>
         list-nodes
         (mapcat
          #(when
               (delete-set (:db/id %))
             [[:db/retract (:db/id %)
               :linknode/next (get-in % [:linknode/next :db/id] :linknode/empty)]])))
        relink-tx)))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/move-first
  :db/doc
  "Tx fn to move an elem to the start of the list.
     Takes a database value, an entity id for a list,
     and an entity id of an element of the list. The
     given element will be moved to the beginning of
     the list. This will fail if the element to move
     is not already in the list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-id]
   :code
   (do
     (when (not= list-id
                 (-> db
                     (d/entity elem-id)
                     (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "the element to move must belong to the list")))
     (let [first-id (-> db
                        (d/entity list-id)
                        (get-in [:linklist/first :db/id] :linknode/empty))]
       (if (= elem-id first-id)
         []                             ; nothing to do, already first
         (let [[before-id after-id] (d/invoke db :linklist.fn/find-before-and-after db elem-id)]
           [[:db/add before-id :linknode/next after-id]
            [:db/add elem-id :linknode/next first-id]
            [:db/add list-id :linklist/first elem-id]]))))}}


 {:db/id #db/id[:db.part/user]
  :db/ident :linklist.fn/move
  :db/doc
  "Tx fn to move an elem after another elem.
     Takes a database value, an entity id for a list,
     an entity id of an element to move, and an
     entity id of an element to use as an anchor.
     The element to move will be placed directly after
     the anchor. This will fail if either elements are
     not already in the list."
  :db/fn #db/fn
  {:lang :clojure
   :params [db list-id elem-id anchor-id]
   :code
   (do
     (when (not= list-id
                 (-> db
                     (d/entity elem-id)
                     (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "the element to move must belong to the list")))
     (when (not= list-id
                 (-> db
                     (d/entity anchor-id)
                     (get-in [:linknode/list :db/id])))
       (throw (IllegalStateException. "the anchor of the move must belong to the list")))
     (when (= elem-id anchor-id)
       (throw (IllegalArgumentException. "elem can't have itself as its next")))
     (let [after (-> db
                     (d/entity anchor-id)
                     (get-in [:linknode/next :db/id] :linknode/empty))]
       (if (= elem-id after) ;; false if after-node is :linknode/empty
         []                  ; no work to be done
         [[:db/add anchor-id :linknode/next elem-id]
          [:db/add elem-id :linknode/next after]
          (let [[before-id after-id] (d/invoke db :linklist.fn/find-before-and-after db elem-id)]
            (if (nil? before-id) ; elem is in list, so it must be first
              [:db/add list-id :linklist/first (-> db
                                                   (d/entity elem-id)
                                                   (get-in [:linknode/next :db/id]))]
              [:db/add before-id :linknode/next after-id]))])))}}


 ]