entity-list-test.clj

(ns toolbox.collections.entity-list-test
  (:require [toolbox.collections.entity-list :as entity-list]
            [clojure.test :refer [deftest is] :include-macros true]))

(def el entity-list/create)

(defn indexes [elist]
  (map (fn [v] [(entity-list/item->index elist v) v]) elist))

(deftest test-equiv
  (is (= (el [{:id :a}]) [{:id :a}])))

(deftest test-seq
  (is (= {:id :a} (first (el [{:id :a} {:id :b}])))))

(deftest test-get
  (is (= {:id :b}
         (get (el [{:id :a} {:id :b}]) 1)))
  (is (= {:id :b}
         (get (el [{:id :a} {:id :b}]) :b)))
  (is (nil? (get (el [{:id :a} {:id :b}]) 2)))
  (is (nil? (get (el [{:id :a} {:id :b}]) :c))))

(deftest test-assoc
  ;; add by ID
  (is (= [{:id :a} {:id :b} {:id :c}]
         (assoc (el [{:id :a} {:id :b}]) :c {:id :c})))

  ;; overwrite by ID
  (is (= [{:id :a} {:id :b :v 1}]
         (assoc (el [{:id :a} {:id :b}]) :b {:id :b :v 1})))

  ;; add by index
  (let [elist (assoc (el [{:id :a} {:id :b}]) 2 {:id :c})]
    (is (= [{:id :a} {:id :b} {:id :c}] elist))
    (is (= (map-indexed vector elist)
           (indexes elist))))

  ;; overwrite by index
  (let [elist (assoc (el [{:id :a} {:id :b}]) 1 {:id :b :v 1})]
    (is (= [{:id :a} {:id :b :v 1}] elist))
    (is (= (map-indexed vector elist) (indexes elist))))

  ;; overwrite at different location
  (let [elist (assoc (el [{:id :a} {:id :b} {:id :c}]) 0 {:id :b :v 1})]
    (is (= [{:id :b :v 1} {:id :a} {:id :c} ] elist))
    (is (= (map-indexed vector elist) (indexes elist)))))

(deftest test-dissoc
  ;; dissoc by ID
  (let [elist (dissoc (el [{:id :a} {:id :b} {:id :c}]) :b)]
    (is (= [{:id :a} {:id :c}] elist))
    (is (= (map-indexed vector elist) (indexes elist))))

  ;; dissoc by index
  (let [elist (dissoc (el [{:id :a} {:id :b} {:id :c}]) 1)]
    (is (= [{:id :a} {:id :c}] elist))
    (is (= (map-indexed vector elist) (indexes elist))))

  (let [elist (dissoc (el [{:id :a} {:id :b} {:id :c}]) 0)]
    (is (= [{:id :b} {:id :c}] elist))
    (is (= (map-indexed vector elist) (indexes elist))))

  (let [elist (dissoc (el [{:id :a} {:id :b} {:id :c}]) 2)]
    (is (= [{:id :a} {:id :b}] elist))
    (is (= (map-indexed vector elist) (indexes elist))))

  ;; dissoc non-existent
  (let [elist-1 (el [{:id :a} {:id :b} {:id :c}])
        elist-2 (dissoc elist-1 :non-existent)]
    (is (identical? elist-1 elist-2)))

  (is (thrown? Throwable (dissoc (el [{:id :a} {:id :b} {:id :c}]) 3))))

(deftest test-conj
  (let [elist (conj (el [{:id :a} {:id :b}]) {:id :c})]
    (is (= [{:id :a} {:id :b} {:id :c}] elist))
    (is (= (map-indexed vector elist) (indexes elist)))))

entity-list.clj

(ns toolbox.collections.entity-list
  (:require [toolbox.util :refer [exception]]
            [clojure.pprint :as pprint])
  (:import [clojure.lang IPersistentVector IPersistentMap IObj MapEntry]))

;;; A persistent collection that acts like a both map and a list.
;;;
;;; Examples:
;;;
;;; (def v (create [{:id :a} {:id :b}]) =>[{:id :a} {:id :b}]
;;; (get v :a) => {:id :a}
;;; (get v 0) => {:id :a}
;;; (get v 1) => {:id :b}
;;; (assoc v 0 {:id :c}) => [{:id :c} {:id :b}]
;;; (dissoc v :b) => [{:id :a}]

(set! *warn-on-reflection* true)

(declare create EMPTY calc-id->index)

(deftype EntityList [^IPersistentVector items ^IPersistentMap id->index]
  Object

  (toString [_]
    (.toString items))

  (hashCode [_]
    (.hashCode items))

  (equals [this other]
    (.equals items (.items ^EntityList other)))

  IObj

  (withMeta [this m]
    (EntityList. (.withMeta ^IObj items m) id->index))

  (meta [this]
    (.meta ^IObj items))

  IPersistentVector

  (length [this]
    (.length items))

  (assocN [this index val]
    (assert (not (contains? id->index (:id v))))
    (EntityList. (.assocN items index v) (assoc id->index (:id v) index)))

  (seq [this]
    (.seq items))

  ;; conj?
  (cons [this o]
    (when-not (nil? (id->index (:id o)))
      (throw (exception "Cannot conj an item twice" {:id o})))
    (EntityList. (conj items o) (assoc id->index (:id o) (count items))))

  ;; Associative

  (containsKey [this k]
    (if (number? k)
      (< -1 k (count items))
      (contains? id->index k)))

  (entryAt [this k]
    (if (number? k)
      (MapEntry/create k (nth items k nil))
      (MapEntry/create k (nth items (id->index k) nil))))

  (assoc [this k v]
    (if (number? k)
      ;; index key
      (let [id             (:id v)
            existing-index (get id->index id)]
        (cond
          ;; overwrite other or add
          (nil? existing-index)
          (let [old (get items k)]
            (EntityList. (assoc items k v)
                         (-> id->index (dissoc (:id old)) (assoc id k))))

          ;; overwriting itself at same index
          (= k existing-index)
          (EntityList. (assoc items k v) (assoc id->index id k))

          ;; overwriting itself at a different index -> rebuild items
          :else
          (let [new-items (reduce (fn [items i]
                                    (cond
                                      ;; at index, insert v
                                      (= (count items) k)
                                      (conj items v i)

                                      ;; found old entry, delete
                                      (= (:id i) id)
                                      items

                                      ;; add other item
                                      :else
                                      (conj items i)))
                                  [] items)]
            (EntityList. new-items (calc-id->index new-items)))))

      ;; ID key
      (do
        (when-not (= k (:id v))
          (throw (exception "Key does not match value ID" {:key k :value-id (:id v)})))
        (if-some [index (get id->index k)]
          (EntityList. (assoc items index v) id->index)
          (EntityList. (conj items v) (assoc id->index k (count items)))))))

  ;; IPersistentCollection

  (count [this]
    (count items))

  (empty [this]
    EMPTY)

  (equiv [this o]
    (.equiv items o))

  ;; ILookup
  (valAt [this k]
    (if (number? k)
      (.valAt items k)
      (when-some [index (get id->index k)]
        (.valAt items index))))

  (valAt [this k not-found]
    (if (number? k)
      (.valAt items k not-found)
      (let [index (get id->index k)]
        (if index
          (.valAt items index)
          not-found))))

  ;; ISequential (marker)

  ;; Reversible
  (rseq [this]
    (.rseq items))

  ;; Indexed
  (nth [this index]
    (nth items index))

  (nth [this index not-found]
    (nth items index not-found))

  IPersistentMap

  ;; no longer used
  ;; (assocEx [this k v]
  ;;   )

  (without [this k]
    (if-some [index (if (number? k)
                      k
                      (id->index k))]
      (let [new-items (vec (concat (subvec items 0 index) (subvec items (inc index) (count items))))]
        (EntityList. new-items (calc-id->index new-items)))
      this))

  Iterable

  (iterator [this]
    (.iterator ^Iterable items))

  ;; IPersistentStack

  (peek [this]
    (nth items (dec (count items)) nil))

  (pop [this]
    (dissoc this (dec (count items)))))

(defn create
  "A list that acts like a vector, but is efficiently (in ~O(1) time)
  addressable by index and by ID of the contained items (all items
  must have an `:id` field).

  e.g. if v = `[{:id :a} {:id :b} {:id :c}]`, `(get v 1)` and `(get
  v :b)` both yield the same result: `{:id :b}`. Can also `assoc` with
  either an index or ID, and `conj`."
  ([]
   (create []))
  ([items]
   (EntityList. (vec items) (calc-id->index items))))

(defn id->index
  "Get the index of the ID in the list in O(1) time."
  [^EntityList elist id]
  (get (.id->index elist) id))

(defn item->index
  "Get the index of the entity in the list in O(1) time."
  [^EntityList elist item]
  (get (.id->index elist) (:id item)))

(defn- calc-id->index [items]
  (zipmap (map :id items) (range (count items))))

(def EMPTY (create))

(prefer-method pprint/simple-dispatch IPersistentVector IPersistentMap)

(prefer-method print-method IPersistentVector IPersistentMap)