den1k/dll-test.cljc

## dll-test.cljc
;   Copyright (c) Dennis Heihoff. All rights reserved.

(ns vimsical.vcs.data.dll-test
  (:require
   #?(:clj  [clojure.test :as t :refer [is deftest testing]]
      :cljs [cljs.test :as t :refer-macros [is deftest testing]])
   [vimsical.vcs.data.dll :as dll])
  #?(:clj (:import [vimsical.vcs.data.dll DoublyLinkedList])))

(def test-kfn str)

(deftest ds-dll
  (testing "new dll"
    (let [dll (dll/doubly-linked-list test-kfn)]
      (is (dll/dll? dll))
      (is (nil? (.-head dll)))
      (is (nil? (.-tail dll)))
      (is (empty? (.-m dll)))))
  (testing "new dll with values"
    (let [dll (dll/doubly-linked-list test-kfn 1 2 3)]
      (is (= '(1 2 3) (seq dll)))
      (is (= "1" (.-head dll)))
      (is (= "3" (.-tail dll)))))
  (testing "add after/before, dll/update, disj, nth"
    (let [dll (dll/doubly-linked-list test-kfn 1 2 3)]
      (testing "add-after"
        (let [dll-mid  (dll/add-after dll 1 100)
              dll-tail (dll/add-after dll 3 100)]
          (is (= '(1 100 2 3) (seq dll-mid)))
          (is (= '(1 2 3 100) (seq dll-tail)))
          (is (= "100" (.-tail dll-tail)))))
      (testing "add-before"
        (let [dll-mid  (dll/add-before dll 2 100)
              dll-head (dll/add-before dll 1 100)]
          (is (= '(1 100 2 3) (seq dll-mid)))
          (is (= '(100 1 2 3) (seq dll-head)))
          (is (= "100" (.-head dll-head)))))
      (testing "replace"
        (let [dll-mid  (dll/replace dll 2 1000)
              dll-head (dll/replace dll 1 1000)
              dll-tail (dll/replace dll 3 1000)]
          (is (= '(1 1000 3) (seq dll-mid)))
          (is (= '(1000 2 3) (seq dll-head)))
          (is (= "1000" (.-head dll-head)))
          (is (= '(1 2 1000) (seq dll-tail)))
          (is (= "1000" (.-tail dll-tail)))))
      (testing "disj"
        (let [dll-mid  (disj dll 2)
              dll-head (disj dll 1)
              dll-tail (disj dll 3)]
          (is (= '(1 3) (seq dll-mid)))
          (is (= '(2 3) (seq dll-head)))
          (is (= "2" (.-head dll-head)))
          (is (= '(1 2) (seq dll-tail)))
          (is (= "2" (.-tail dll-tail)))))
      (testing "get"
        (is (= 2 (get dll 2)))
        (is (= 100 (get dll :not-there 100))))
      (testing "update"
        (let [dll-upd (dll/update dll 2 + 10)]
          (is (= '(1 12 3) (seq dll-upd)))))
      (testing "first"
        (is (= 1 (first dll))))
      (testing "last"
        (is (= 3 (last dll))))
      (testing "next"
        (is (= '(2 3) (next dll))))
      (testing "peek"
        (is (= 3 (peek dll))))
      (testing "nth"
        (is (= 1 (nth dll 0)))
        (is (= 3 (nth dll 2)))
        #?(:clj (is (thrown? Exception (nth dll 1000)))))))
  (testing "range"
    (let [dll (into (dll/doubly-linked-list str) (range 1 11))]
      (is (= '(3 4) (dll/subrange dll 3 5)))
      (is (= '(3 4) (take 2 (dll/subrange dll 3))))
      (is (= '(8 9 10) (dll/subrange dll 8 1000))))))

## dll.cljc
;   Copyright (c) Dennis Heihoff. All rights reserved.

(ns vimsical.vcs.data.dll
  "A Doubly Linked List set-like data structure implemented on top of hash-map."
  (:refer-clojure :exclude [replace update])
  #?(:clj (:require [clojure.pprint :as pprint])))


(defprotocol PDoublyLinkedList
  (make-key [this x])
  (get-head [this])
  (get-tail [this])
  (set-head [this x])
  (set-tail [this x])
  (get-head-node [this])
  (get-tail-node [this])
  (get-node [this x])
  (get-node-by-key [this k])
  (add-before [this node-val x])
  (add-after [this node-val x])
  (get-prev [this node-val])
  (get-next [this node-val])
  (seq-from [this start-val dir])
  (replace [this node-val x])
  (subrange [this from] [this from to]))

(defrecord Node [prev next val])

#?(:cljs
   (extend-type Node
     IPrintWithWriter
     (-pr-writer [this writer _]
       (-write writer (str "#DoublyLinkedList/Node" (into {} this))))))

(defn make-node [prev next val]
  (Node. prev next val))

(defn seq*
  ([m start-key next-key]
   (seq* m start-key ::none next-key))
  ([m start-key stop-key next-key]
   (when-let [node (get m start-key)]
     (cons (:val node) (lazy-seq
                        (when-not (= start-key stop-key)
                          (seq* m (next-key node) stop-key next-key)))))))

(defn- entry-seq [m start next-key]
  (lazy-seq
   (when-let [[_ node :as node-entry] (find m start)]
     (cons node-entry (entry-seq m (next-key node) next-key)))))

(defn nth* [dll n not-found]
  (loop [node (.-head dll) i 0]
    (if-let [next-node (get (.-m dll) node)]
      (if (= i n)
        (:val next-node)
        (recur (:next next-node) (inc i)))
      not-found)))

(deftype DoublyLinkedList [m head tail kfn]
  #?@(:clj
      [Object
       (toString [_]
                 (str "#DoublyLinkedList" {:head head :tail tail :m m}))
       clojure.lang.Sequential
       clojure.lang.Counted
       (count [_] (count m))
       clojure.lang.Seqable
       (seq [_] (seq* m head tail :next))
       clojure.lang.Reversible
       (rseq [_] (seq* m tail head :prev))
       clojure.lang.ISeq
       (empty [_]
              (DoublyLinkedList. (empty m) nil nil kfn))
       (first [this]
              (get-head this))
       (next [this]
             (next (seq this)))
       (cons [this x]
             (if-let [tail-val (get-tail this)]
               (add-after this tail-val x)
               (set-tail this x)))
       clojure.lang.IPersistentStack
       (peek [this]
             (get-tail this))
       clojure.lang.IPersistentSet
       (equiv
        [this other]
        (and
         (= (type this) (type other))
         (= (.-m this) (.-m other))
         (= (.-head this) (.-head other))
         (= (.-tail this) (.-tail other))))
       (disjoin [_ node-val]
                (let [node-key (kfn node-val)
                      {:keys [next prev]} (get m node-key)]
                  (when-not (and node-val node-key)
                    (throw (ex-info "Node does not exist."
                                    {:node-key node-key
                                     :node-val node-val})))
                  (let [m    (-> m
                                 (dissoc node-key)
                                 (cond->
                                     prev (clojure.core/update prev assoc :next next)
                                     next (clojure.core/update next assoc :prev prev)))
                        head (if (= head node-key) next head)
                        tail (if (= tail node-key) prev tail)]
                    (DoublyLinkedList. m head tail kfn))))
       clojure.lang.ILookup
       (valAt [_ k]
              (let [node-key (kfn k)]
                (:val (.valAt m node-key nil))))
       (valAt [_ k not-found]
              (let [node-key (kfn k)]
                (or (:val (.valAt m node-key)) not-found)))]
      :cljs
      [Object
       (toString [_] (str "#DoublyLinkedList" {:head head :tail tail :m m}))
       IEquiv
       (-equiv
        [this other]
        (and
         (= (type this) (type other))
         (= (.-m this) (.-m other))
         (= (.-head this) (.-head other))
         (= (.-tail this) (.-tail other))))
       ICounted
       (-count [_] (count m))
       ISeqable
       (-seq [_] (seq* m head tail :next))
       IReversible
       (-rseq [_] (seq* m tail head :prev))
       IEmptyableCollection
       (-empty [this] (DoublyLinkedList. (empty m) nil nil kfn))
       ICollection
       (-conj
        [this x]
        (if-let [tail-val (get-tail this)]
          (add-after this tail-val x)
          (set-tail this x)))
       ISet
       (-disjoin
        [_ node-val]
        (let [node-key (kfn node-val)
              {:keys [next prev]} (get m node-key)]
          (when-not (and node-val node-key)
            (throw (ex-info "Node does not exist."
                            {:node-key node-key
                             :node-val node-val})))
          (let [m    (-> m
                         (dissoc node-key)
                         (cond->
                             prev (clojure.core/update prev assoc :next next)
                             next (clojure.core/update next assoc :prev prev)))
                head (if (= head node-key) next head)
                tail (if (= tail node-key) prev tail)]
            (DoublyLinkedList. m head tail kfn))))
       IIndexed
       (-nth [this i] (nth this i nil))
       (-nth [this i not-found] (nth* this i not-found))
       IStack
       (-peek
        [this]
        (get-tail this))
       ILookup
       (-lookup [this x] (-lookup this x nil))
       (-lookup
        [_ x not-found]
        (let [k (kfn x)]
          (or (:val (get m k)) not-found)))
       IPrintWithWriter
       (-pr-writer
        [this writer _]
        (-write writer (str "#DoublyLinkedList" (interpose '<-> (seq this)))))])
  PDoublyLinkedList
  (make-key [_ x]
    (let [k (kfn x)]
      (when-not (get m k)
        (throw (ex-info (str "Node must exist for key " k ".")
                        {:provided-value x
                         :generated-key  k})))
      k))
  (get-head [this]
    (:val (get-head-node this)))
  (get-tail [this]
    (:val (get-tail-node this)))
  (get-head-node [_]
    (get m head))
  (get-tail-node [_]
    (get m tail))
  (set-head [_ x]
    (let [next-head (kfn x)
          m         (cond-> m
                      (not (get m next-head))
                      (assoc next-head (make-node nil head x)))
          tail      (or tail next-head)]
      (when-not next-head
        (throw (ex-info "Head cannot be nil" {:val x})))
      (DoublyLinkedList. m next-head tail kfn)))
  (set-tail [_ x]
    (let [next-tail (kfn x)
          m         (cond-> m
                      (not (get m next-tail))
                      (assoc next-tail (make-node tail nil x)))
          head      (or head next-tail)]
      (when-not next-tail
        (throw (ex-info "Tail cannot be nil" {:val x})))
      (DoublyLinkedList. m head next-tail kfn)))
  (get-node [_ node-val]
    (when-let [k (kfn node-val)]
      (get m k)))
  (get-node-by-key [_ k]
    (get m k))
  (get-prev [this node-val]
    (let [node-key (kfn node-val)]
      (:val (get-node-by-key this (:prev (get m node-key))))))
  (get-next [this node-val]
    (let [node-key (kfn node-val)]
      (:val (get-node-by-key this (:next (get m node-key))))))
  (add-after [_ node-val x]
    (let [x-key     (kfn x)
          node-key  (kfn node-val)
          node-next (:next (get m node-key))]
      (when-not (and node-val node-key)
        (throw (ex-info "Node after which to insert does not exist"
                        {:node     node-val
                         :node-key node-key
                         :x        x})))
      (when-let [exists (get m x-key)]
        (throw (ex-info (str "Node at key " x-key " already exists. Use assoc "
                             "to replace an existing node.")
                        {:key           x-key
                         :existing-node exists})))
      (let [m    (-> m
                     (assoc x-key (make-node node-key node-next x))
                     (clojure.core/update node-key assoc :next x-key)
                     (cond->
                         node-next (clojure.core/update node-next assoc :prev x-key)))
            tail (if (= node-key tail) x-key tail)]
        (DoublyLinkedList. m head tail kfn))))
  (add-before [_ node-val x]
    (let [x-key     (kfn x)
          node-key  (kfn node-val)
          node-prev (:prev (get m node-key))]
      (when-not (and node-val node-key)
        (throw (ex-info "Node before which to insert does not exist"
                        {:node     node-val
                         :node-key node-key
                         :x        x})))
      (when-let [exists (get m x-key)]
        (throw (ex-info (str "Node at key " x-key " already exists. Use assoc "
                             "to replace an existing node.")
                        {:key           x-key
                         :existing-node exists})))
      (let [m    (-> m
                     (assoc x-key (make-node node-prev node-key x))
                     (clojure.core/update node-key assoc :prev x-key)
                     (cond->
                         node-prev (clojure.core/update node-prev assoc :next x-key)))
            head (if (= node-key head) x-key head)]
        (DoublyLinkedList. m head tail kfn))))
  (replace [_ node-val x]
    (let [x-key    (kfn x)
          node-key (kfn node-val)
          {node-next :next node-prev :prev} (get m node-key)]
      (when-not (and node-val node-key)
        (throw (ex-info "Node which to replace does not exist"
                        {:node     node-val
                         :node-key node-key
                         :x        x})))
      (let [m    (-> m
                     (dissoc node-key)
                     (assoc x-key (make-node node-prev node-next x))
                     (cond->
                         node-prev (clojure.core/update node-prev assoc :next x-key)
                         node-next (clojure.core/update node-next assoc :prev x-key)))
            head (if (= head node-key) x-key head)
            tail (if (= node-key tail) x-key tail)]
        (DoublyLinkedList. m head tail kfn))))
  (seq-from [_ start-val dir]
    {:pre [(get #{:next :prev} dir)]}
    (seq* m (kfn start-val) dir))
  (subrange [this from]
    (subrange this from (get-tail-node this)))
  (subrange [_ from-val to-val]
    (let [to-key (kfn to-val)]
      (sequence (comp (take-while (fn [[k _]] (not= to-key k)))
                      (map (comp :val second)))
                (entry-seq m (kfn from-val) :next)))))

(defn update [^DoublyLinkedList dll node-val f & args]
  (let [kfn      (.-kfn dll)
        m        (.-m dll)
        node-key (kfn node-val)
        cval     (:val (get m node-key))]
    (when-not (and node-val node-key)
      (throw (ex-info "Node which to update does not exist"
                      {:node     node-val
                       :node-key node-key})))
    (replace dll cval (apply f cval args))))

(defn doubly-linked-list
  ([kfn]
   (DoublyLinkedList. {} nil nil kfn))
  ([kfn & vals]
   (into (DoublyLinkedList. {} nil nil kfn) vals)))

#?(:clj (defmethod print-method DoublyLinkedList [dll w]
          (print-method (symbol "#DoublyLinkedList") w)
          (print-method (interpose '<-> (seq dll)) w)))

;; Fixes pretty print
#?(:clj (defmethod clojure.pprint/simple-dispatch DoublyLinkedList [o]
          ((get-method pprint/simple-dispatch clojure.lang.ISeq) o)))

#?(:clj (defmethod print-method Node [n w]
          (print-method (symbol "#DoublyLinkedList/Node") w)
          (print-method (into {} n) w)))

(comment
  (require '[criterium.core :refer [quick-bench]])
  (let [med       (vec (range 10000))
        large     (vec (range 1000000))
        dll-med   (apply doubly-linked-list str med)
        dll-large (apply doubly-linked-list str large)]

   ;;; Medium Size

                                        ;(quick-bench (apply doubly-linked-list str med))
                                        ;Execution time mean : 11.010305 ms

                                        ;(quick-bench (seq dll-med))
                                        ;Execution time mean : 24.671025 ns

    ;; subrange - small

                                        ;(quick-bench (subrange dll-med 5000 10000))
                                        ;Execution time mean : 2.858399 ms

                                        ;(quick-bench (assoc dll-med 5000 1000000000000000))
                                        ;Execution time mean : 1.511168 µs

   ;;; Large Size

                                        ;(quick-bench (apply doubly-linked-list str large))
                                        ;Execution time mean : 2.373459 sec

                                        ;(quick-bench (seq dll-large))
                                        ;Execution time mean : 16.552517 ns

    ;; subrange - small

                                        ;(quick-bench (subrange dll-large 5000 10000))
                                        ;Execution time mean : 4.663050 ms

    ;; subrange - large

                                        ;(quick-bench (subrange dll-large 500000 1000000))
                                        ;Execution time mean : 399.820492 ms

                                        ;(quick-bench (assoc dll-large 5000000 1000000000000000))
                                        ;Execution time mean : 619.556069 ns
    ))

(defn dll? [x] (and x (satisfies? PDoublyLinkedList x)))
	; Copyright (c) Dennis Heihoff. All rights reserved.

	(ns vimsical.vcs.data.dll-test
	(:require
	#?(:clj [clojure.test :as t :refer [is deftest testing]]
	:cljs [cljs.test :as t :refer-macros [is deftest testing]])
	[vimsical.vcs.data.dll :as dll])
	#?(:clj (:import [vimsical.vcs.data.dll DoublyLinkedList])))

	(def test-kfn str)

	(deftest ds-dll
	(testing "new dll"
	(let [dll (dll/doubly-linked-list test-kfn)]
	(is (dll/dll? dll))
	(is (nil? (.-head dll)))
	(is (nil? (.-tail dll)))
	(is (empty? (.-m dll)))))
	(testing "new dll with values"
	(let [dll (dll/doubly-linked-list test-kfn 1 2 3)]
	(is (= '(1 2 3) (seq dll)))
	(is (= "1" (.-head dll)))
	(is (= "3" (.-tail dll)))))
	(testing "add after/before, dll/update, disj, nth"
	(let [dll (dll/doubly-linked-list test-kfn 1 2 3)]
	(testing "add-after"
	(let [dll-mid (dll/add-after dll 1 100)
	dll-tail (dll/add-after dll 3 100)]
	(is (= '(1 100 2 3) (seq dll-mid)))
	(is (= '(1 2 3 100) (seq dll-tail)))
	(is (= "100" (.-tail dll-tail)))))
	(testing "add-before"
	(let [dll-mid (dll/add-before dll 2 100)
	dll-head (dll/add-before dll 1 100)]
	(is (= '(1 100 2 3) (seq dll-mid)))
	(is (= '(100 1 2 3) (seq dll-head)))
	(is (= "100" (.-head dll-head)))))
	(testing "replace"
	(let [dll-mid (dll/replace dll 2 1000)
	dll-head (dll/replace dll 1 1000)
	dll-tail (dll/replace dll 3 1000)]
	(is (= '(1 1000 3) (seq dll-mid)))
	(is (= '(1000 2 3) (seq dll-head)))
	(is (= "1000" (.-head dll-head)))
	(is (= '(1 2 1000) (seq dll-tail)))
	(is (= "1000" (.-tail dll-tail)))))
	(testing "disj"
	(let [dll-mid (disj dll 2)
	dll-head (disj dll 1)
	dll-tail (disj dll 3)]
	(is (= '(1 3) (seq dll-mid)))
	(is (= '(2 3) (seq dll-head)))
	(is (= "2" (.-head dll-head)))
	(is (= '(1 2) (seq dll-tail)))
	(is (= "2" (.-tail dll-tail)))))
	(testing "get"
	(is (= 2 (get dll 2)))
	(is (= 100 (get dll :not-there 100))))
	(testing "update"
	(let [dll-upd (dll/update dll 2 + 10)]
	(is (= '(1 12 3) (seq dll-upd)))))
	(testing "first"
	(is (= 1 (first dll))))
	(testing "last"
	(is (= 3 (last dll))))
	(testing "next"
	(is (= '(2 3) (next dll))))
	(testing "peek"
	(is (= 3 (peek dll))))
	(testing "nth"
	(is (= 1 (nth dll 0)))
	(is (= 3 (nth dll 2)))
	#?(:clj (is (thrown? Exception (nth dll 1000)))))))
	(testing "range"
	(let [dll (into (dll/doubly-linked-list str) (range 1 11))]
	(is (= '(3 4) (dll/subrange dll 3 5)))
	(is (= '(3 4) (take 2 (dll/subrange dll 3))))
	(is (= '(8 9 10) (dll/subrange dll 8 1000))))))
	; Copyright (c) Dennis Heihoff. All rights reserved.

	(ns vimsical.vcs.data.dll
	"A Doubly Linked List set-like data structure implemented on top of hash-map."
	(:refer-clojure :exclude [replace update])
	#?(:clj (:require [clojure.pprint :as pprint])))


	(defprotocol PDoublyLinkedList
	(make-key [this x])
	(get-head [this])
	(get-tail [this])
	(set-head [this x])
	(set-tail [this x])
	(get-head-node [this])
	(get-tail-node [this])
	(get-node [this x])
	(get-node-by-key [this k])
	(add-before [this node-val x])
	(add-after [this node-val x])
	(get-prev [this node-val])
	(get-next [this node-val])
	(seq-from [this start-val dir])
	(replace [this node-val x])
	(subrange [this from] [this from to]))

	(defrecord Node [prev next val])

	#?(:cljs
	(extend-type Node
	IPrintWithWriter
	(-pr-writer [this writer _]
	(-write writer (str "#DoublyLinkedList/Node" (into {} this))))))

	(defn make-node [prev next val]
	(Node. prev next val))

	(defn seq*
	([m start-key next-key]
	(seq* m start-key ::none next-key))
	([m start-key stop-key next-key]
	(when-let [node (get m start-key)]
	(cons (:val node) (lazy-seq
	(when-not (= start-key stop-key)
	(seq* m (next-key node) stop-key next-key)))))))

	(defn- entry-seq [m start next-key]
	(lazy-seq
	(when-let [[_ node :as node-entry] (find m start)]
	(cons node-entry (entry-seq m (next-key node) next-key)))))

	(defn nth* [dll n not-found]
	(loop [node (.-head dll) i 0]
	(if-let [next-node (get (.-m dll) node)]
	(if (= i n)
	(:val next-node)
	(recur (:next next-node) (inc i)))
	not-found)))

	(deftype DoublyLinkedList [m head tail kfn]
	#?@(:clj
	[Object
	(toString [_]
	(str "#DoublyLinkedList" {:head head :tail tail :m m}))
	clojure.lang.Sequential
	clojure.lang.Counted
	(count [_] (count m))
	clojure.lang.Seqable
	(seq [_] (seq* m head tail :next))
	clojure.lang.Reversible
	(rseq [_] (seq* m tail head :prev))
	clojure.lang.ISeq
	(empty [_]
	(DoublyLinkedList. (empty m) nil nil kfn))
	(first [this]
	(get-head this))
	(next [this]
	(next (seq this)))
	(cons [this x]
	(if-let [tail-val (get-tail this)]
	(add-after this tail-val x)
	(set-tail this x)))
	clojure.lang.IPersistentStack
	(peek [this]
	(get-tail this))
	clojure.lang.IPersistentSet
	(equiv
	[this other]
	(and
	(= (type this) (type other))
	(= (.-m this) (.-m other))
	(= (.-head this) (.-head other))
	(= (.-tail this) (.-tail other))))
	(disjoin [_ node-val]
	(let [node-key (kfn node-val)
	{:keys [next prev]} (get m node-key)]
	(when-not (and node-val node-key)
	(throw (ex-info "Node does not exist."
	{:node-key node-key
	:node-val node-val})))
	(let [m (-> m
	(dissoc node-key)
	(cond->
	prev (clojure.core/update prev assoc :next next)
	next (clojure.core/update next assoc :prev prev)))
	head (if (= head node-key) next head)
	tail (if (= tail node-key) prev tail)]
	(DoublyLinkedList. m head tail kfn))))
	clojure.lang.ILookup
	(valAt [_ k]
	(let [node-key (kfn k)]
	(:val (.valAt m node-key nil))))
	(valAt [_ k not-found]
	(let [node-key (kfn k)]
	(or (:val (.valAt m node-key)) not-found)))]
	:cljs
	[Object
	(toString [_] (str "#DoublyLinkedList" {:head head :tail tail :m m}))
	IEquiv
	(-equiv
	[this other]
	(and
	(= (type this) (type other))
	(= (.-m this) (.-m other))
	(= (.-head this) (.-head other))
	(= (.-tail this) (.-tail other))))
	ICounted
	(-count [_] (count m))
	ISeqable
	(-seq [_] (seq* m head tail :next))
	IReversible
	(-rseq [_] (seq* m tail head :prev))
	IEmptyableCollection
	(-empty [this] (DoublyLinkedList. (empty m) nil nil kfn))
	ICollection
	(-conj
	[this x]
	(if-let [tail-val (get-tail this)]
	(add-after this tail-val x)
	(set-tail this x)))
	ISet
	(-disjoin
	[_ node-val]
	(let [node-key (kfn node-val)
	{:keys [next prev]} (get m node-key)]
	(when-not (and node-val node-key)
	(throw (ex-info "Node does not exist."
	{:node-key node-key
	:node-val node-val})))
	(let [m (-> m
	(dissoc node-key)
	(cond->
	prev (clojure.core/update prev assoc :next next)
	next (clojure.core/update next assoc :prev prev)))
	head (if (= head node-key) next head)
	tail (if (= tail node-key) prev tail)]
	(DoublyLinkedList. m head tail kfn))))
	IIndexed
	(-nth [this i] (nth this i nil))
	(-nth [this i not-found] (nth* this i not-found))
	IStack
	(-peek
	[this]
	(get-tail this))
	ILookup
	(-lookup [this x] (-lookup this x nil))
	(-lookup
	[_ x not-found]
	(let [k (kfn x)]
	(or (:val (get m k)) not-found)))
	IPrintWithWriter
	(-pr-writer
	[this writer _]
	(-write writer (str "#DoublyLinkedList" (interpose '<-> (seq this)))))])
	PDoublyLinkedList
	(make-key [_ x]
	(let [k (kfn x)]
	(when-not (get m k)
	(throw (ex-info (str "Node must exist for key " k ".")
	{:provided-value x
	:generated-key k})))
	k))
	(get-head [this]
	(:val (get-head-node this)))
	(get-tail [this]
	(:val (get-tail-node this)))
	(get-head-node [_]
	(get m head))
	(get-tail-node [_]
	(get m tail))
	(set-head [_ x]
	(let [next-head (kfn x)
	m (cond-> m
	(not (get m next-head))
	(assoc next-head (make-node nil head x)))
	tail (or tail next-head)]
	(when-not next-head
	(throw (ex-info "Head cannot be nil" {:val x})))
	(DoublyLinkedList. m next-head tail kfn)))
	(set-tail [_ x]
	(let [next-tail (kfn x)
	m (cond-> m
	(not (get m next-tail))
	(assoc next-tail (make-node tail nil x)))
	head (or head next-tail)]
	(when-not next-tail
	(throw (ex-info "Tail cannot be nil" {:val x})))
	(DoublyLinkedList. m head next-tail kfn)))
	(get-node [_ node-val]
	(when-let [k (kfn node-val)]
	(get m k)))
	(get-node-by-key [_ k]
	(get m k))
	(get-prev [this node-val]
	(let [node-key (kfn node-val)]
	(:val (get-node-by-key this (:prev (get m node-key))))))
	(get-next [this node-val]
	(let [node-key (kfn node-val)]
	(:val (get-node-by-key this (:next (get m node-key))))))
	(add-after [_ node-val x]
	(let [x-key (kfn x)
	node-key (kfn node-val)
	node-next (:next (get m node-key))]
	(when-not (and node-val node-key)
	(throw (ex-info "Node after which to insert does not exist"
	{:node node-val
	:node-key node-key
	:x x})))
	(when-let [exists (get m x-key)]
	(throw (ex-info (str "Node at key " x-key " already exists. Use assoc "
	"to replace an existing node.")
	{:key x-key
	:existing-node exists})))
	(let [m (-> m
	(assoc x-key (make-node node-key node-next x))
	(clojure.core/update node-key assoc :next x-key)
	(cond->
	node-next (clojure.core/update node-next assoc :prev x-key)))
	tail (if (= node-key tail) x-key tail)]
	(DoublyLinkedList. m head tail kfn))))
	(add-before [_ node-val x]
	(let [x-key (kfn x)
	node-key (kfn node-val)
	node-prev (:prev (get m node-key))]
	(when-not (and node-val node-key)
	(throw (ex-info "Node before which to insert does not exist"
	{:node node-val
	:node-key node-key
	:x x})))
	(when-let [exists (get m x-key)]
	(throw (ex-info (str "Node at key " x-key " already exists. Use assoc "
	"to replace an existing node.")
	{:key x-key
	:existing-node exists})))
	(let [m (-> m
	(assoc x-key (make-node node-prev node-key x))
	(clojure.core/update node-key assoc :prev x-key)
	(cond->
	node-prev (clojure.core/update node-prev assoc :next x-key)))
	head (if (= node-key head) x-key head)]
	(DoublyLinkedList. m head tail kfn))))
	(replace [_ node-val x]
	(let [x-key (kfn x)
	node-key (kfn node-val)
	{node-next :next node-prev :prev} (get m node-key)]
	(when-not (and node-val node-key)
	(throw (ex-info "Node which to replace does not exist"
	{:node node-val
	:node-key node-key
	:x x})))
	(let [m (-> m
	(dissoc node-key)
	(assoc x-key (make-node node-prev node-next x))
	(cond->
	node-prev (clojure.core/update node-prev assoc :next x-key)
	node-next (clojure.core/update node-next assoc :prev x-key)))
	head (if (= head node-key) x-key head)
	tail (if (= node-key tail) x-key tail)]
	(DoublyLinkedList. m head tail kfn))))
	(seq-from [_ start-val dir]
	{:pre [(get #{:next :prev} dir)]}
	(seq* m (kfn start-val) dir))
	(subrange [this from]
	(subrange this from (get-tail-node this)))
	(subrange [_ from-val to-val]
	(let [to-key (kfn to-val)]
	(sequence (comp (take-while (fn [[k _]] (not= to-key k)))
	(map (comp :val second)))
	(entry-seq m (kfn from-val) :next)))))

	(defn update [^DoublyLinkedList dll node-val f & args]
	(let [kfn (.-kfn dll)
	m (.-m dll)
	node-key (kfn node-val)
	cval (:val (get m node-key))]
	(when-not (and node-val node-key)
	(throw (ex-info "Node which to update does not exist"
	{:node node-val
	:node-key node-key})))
	(replace dll cval (apply f cval args))))

	(defn doubly-linked-list
	([kfn]
	(DoublyLinkedList. {} nil nil kfn))
	([kfn & vals]
	(into (DoublyLinkedList. {} nil nil kfn) vals)))

	#?(:clj (defmethod print-method DoublyLinkedList [dll w]
	(print-method (symbol "#DoublyLinkedList") w)
	(print-method (interpose '<-> (seq dll)) w)))

	;; Fixes pretty print
	#?(:clj (defmethod clojure.pprint/simple-dispatch DoublyLinkedList [o]
	((get-method pprint/simple-dispatch clojure.lang.ISeq) o)))

	#?(:clj (defmethod print-method Node [n w]
	(print-method (symbol "#DoublyLinkedList/Node") w)
	(print-method (into {} n) w)))

	(comment
	(require '[criterium.core :refer [quick-bench]])
	(let [med (vec (range 10000))
	large (vec (range 1000000))
	dll-med (apply doubly-linked-list str med)
	dll-large (apply doubly-linked-list str large)]

	;;; Medium Size

	;(quick-bench (apply doubly-linked-list str med))
	;Execution time mean : 11.010305 ms

	;(quick-bench (seq dll-med))
	;Execution time mean : 24.671025 ns

	;; subrange - small

	;(quick-bench (subrange dll-med 5000 10000))
	;Execution time mean : 2.858399 ms

	;(quick-bench (assoc dll-med 5000 1000000000000000))
	;Execution time mean : 1.511168 µs

	;;; Large Size

	;(quick-bench (apply doubly-linked-list str large))
	;Execution time mean : 2.373459 sec

	;(quick-bench (seq dll-large))
	;Execution time mean : 16.552517 ns

	;; subrange - small

	;(quick-bench (subrange dll-large 5000 10000))
	;Execution time mean : 4.663050 ms

	;; subrange - large

	;(quick-bench (subrange dll-large 500000 1000000))
	;Execution time mean : 399.820492 ms

	;(quick-bench (assoc dll-large 5000000 1000000000000000))
	;Execution time mean : 619.556069 ns
	))

	(defn dll? [x] (and x (satisfies? PDoublyLinkedList x)))