             [cmr.system-int-test.utils.search-util :as search]
             [cmr.system-int-test.utils.index-util :as index]
             [cmr.system-int-test.data2.collection :as dc]
+            [cmr.common.concepts :as concepts]
             [cmr.system-int-test.data2.core :as d2c]
             [cmr.search.services.parameters.parameter-validation :as pm]))
 
 (def prov1-collection-count 10)
+(def prov1-deleted-collection-count 3)
 (def prov2-collection-count 15)
 
 (def collection-count (+ prov2-collection-count prov1-collection-count))
 
+(def revision-count (+ (* 2 prov1-collection-count)
+                       prov2-collection-count
+                       (* 2 prov1-deleted-collection-count)))
+
+
+
 (defn create-collections
   "Set up the fixtures for tests."
   []
-  (dotimes [n prov1-collection-count]
-    (d2c/ingest "PROV1" (dc/collection)))
-  (dotimes [n prov2-collection-count]
-    (d2c/ingest "PROV2" (dc/collection)))
-  (index/wait-until-indexed))
+  (let [prov1-colls (doall (for [n (range prov1-collection-count)
+                                 :let [coll-r1 (d2c/ingest "PROV1" (dc/collection))]]
+                             [coll-r1
+                              (d2c/ingest "PROV1" (dissoc coll-r1 :revision-id))]))
+        prov1-deleted-colls (doall (for [n (range prov1-deleted-collection-count)
+                                         :let [coll-r1 (d2c/ingest "PROV1" (dc/collection))]]
+                                     (do
+                                       (ingest/delete-concept (d2c/item->concept coll-r1))
+                                       [coll-r1 (assoc coll-r1 :deleted true
+                                                       :revision-id 2)])))
+
+        prov2-colls (doall (for [n (range prov2-collection-count)]
+                             (d2c/ingest "PROV2" (dc/collection))))]
+    (index/wait-until-indexed)
+
+    (flatten (concat prov1-colls prov1-deleted-colls prov2-colls))))
+
 
 (use-fixtures :each (ingest/reset-fixture {"provguid1" "PROV1" "provguid2" "PROV2"}))
 
-(deftest search-with-page-size-and-page-num
+(deftest search-with-page-size
   (create-collections)
+
   (testing "Exceeded page depth (page-num * page-size)"
     (let [page-size 10
           page-num 1000000000]

  (are [hits params]
       (= hits (:hits (search/find-refs :collection params)))
       collection-count {}
       0 {:provider "NONE"}
       prov1-collection-count {:provider "PROV1"}
       prov2-collection-count {:provider "PROV2"}))

(deftest search-with-page-num
  (let [provider-id "PROV1"

            {:keys [status errors]} resp]
        (is (= 400 status))
        (is (re-matches #"The paging depth \(page_num \* page_size\) of \[\d*?\] exceeds the limit of \d*?.*?"
                        (first errors))))))

  (testing "Search with page_size."
    (let [{:keys [refs]} (search/find-refs :collection {:page_size 5})]
      (is (= 5 (count refs)))))
  (testing "Search with large page_size."
    (let [{:keys [refs]} (search/find-refs :collection {:page_size 100})]
      (is (= collection-count (count refs)))))
  (testing "all revision page size"
    (let [{:keys [refs]} (search/find-refs :collection {:page_size 5 :all-revisions true})]
      (is (= 5 (count refs)))))
  (testing "page_size less than zero."
    (let [resp (search/find-refs :collection {:page_size -1})
          {:keys [status errors]} resp]
