index-except.clj

(ns cljclass)

;; Various ways to solve the problem of transforming a vector to a vector of indices starting at zero, but
;; using an index of -1 for items for which (pred item) is true.
;; E.g. (index-except odd? [1 4 18 7 9 2 4 3]) => [-1 0 1 -1 -1 2 3 -1]

;; NB:
;; This is not the same as assigning indices and replacing the elements for which pred is true with -1.
;; E.g. (index-except odd? [1 2 3]) => [-1 0 -1] and not [-1 1 -1]. 


;; 1. mutating solution
(defn index-except [pred s]
  (let [i (atom -1)]
    (vec
     (for [item s]
       (if (pred item)
         -1
         (swap! i inc))))))


;; 2. recursion growing the stack
(defn index-except-recur [pred s i]
  (when (seq s)
    (let [p (pred (first s))]
      (cons (if p -1 i)
            (index-except-recur pred
                                (rest s)
                                (if p i (inc i)))))))

(defn index-except [pred s]
  (vec (index-except-recur pred s 0)))


;; 3. recursion with lazy-seq (doesn't grow the stack)
(defn index-except-recur [pred s i]
  (when (seq s)
    (let [p (pred (first s))]
      (cons (if p -1 i)
            (lazy-seq
             (index-except-recur pred
                                 (rest s)
                                 (if p i (inc i))))))))

(defn index-except [pred s]
  (vec (index-except-recur pred s 0)))


;; 4. optimized tail recursion (doesn't grow the stack)
(defn index-except-recur [pred s i acc]
  (if (empty? s)
    acc
    (let [p (pred (first s))]
      (recur pred
             (rest s)
             (if p i (inc i))
             (conj acc (if p -1 i))))))

(defn index-except [pred s]
  (index-except-recur pred s 0 []))


;; 5. optimized tail recursion (doesn't grow the stack) with no helper function
(defn index-except [pred s]
  (loop [pred pred s s i 0 acc []]
    (if (empty? s)
      acc
      (let [p (pred (first s))]
        (recur pred
               (rest s)
               (if p i (inc i))
               (conj acc (if p -1 i)))))))


;; 6. using the reduce function instead of recursion
(defn index-except [pred s]
  (let [f (fn [[acc i] item]
            (let [p (pred item)]
              [(conj acc (if p -1 i))
               (if p i (inc i))]))]
    (first (reduce f [[] 0] s))))


;; 7. using the iterate function instead of recursion
(defn index-except [pred s]
  (let [f (fn [[acc i s]]
            (let [p (pred (first s))]
              [(conj acc (if p -1 i))
               (if p i (inc i))
               (rest s)]))]
    (-> (iterate f [[] 0 s])
        (nth (count s))
        first)))


;; 8. crazy, inefficient solution with map-indexed and a hash map
(defn index-except [pred s]
  (let [m (->> s
               (map-indexed #(do [%1 %2]))
               (remove (fn [[_ v]] (pred v)))
               (map-indexed #(do [(first %2) %1]))
               (into {}))]

    (vec
     (take (count s)
           (map #(m % -1) (range))))))


;; using reductions to manage state like reduce would, but lazily.
;; the state is a pair: "value to return/produce" and "index for the next matching element".
;; I always forget the (rest ...) part: (reductions f acc coll) always starts with just acc, which is usually junk.
(defn index-except [pred coll]
  (map first
       (rest (reductions (fn [[_ i] x]
                           (if (pred x)
                             [-1 i]
                             [i (inc i)]))
                         [nil 0], coll))))