 (ns engine.server.rope
+  "Implementation of Ropes as per \"Ropes: an Alternative to Strings\"
+by Boehm, Hans-J; Atkinson, Russ; and Plass, Michael (December 1995), doi:10.1002/spe.4380251203."
   (:use [clojure.string :only [join]])
   (:require [clojure.zip :as zip])
-  (:import [clojure.lang IPersistentCollection ITransientCollection Seqable Counted Indexed ISeq]
+  (:import [clojure.lang Counted Indexed]
            [java.lang String IndexOutOfBoundsException]))
 
 (def *fib-seq* (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
 (def *leaf-cutoff-length* 128)
 
 (defprotocol Measurable
-  (measure [object]))
+  "Trivial protocol for things measurable.
+Default implementations are provided for nil and String; nil measures as 0
+characters, 0 lines. Strings get analyzed accordingly."
+  (measure [object] "Measure object"))
 
 (defrecord CharSequenceMeasurement [#^int length #^int lines])
 
-(defn measurement [length lines]
+(defn measurement
+  "CharSequenceMeasurement from length and lines"
+  [length lines]
   (CharSequenceMeasurement. length lines))
 
-(defn count-matches [char string]
+(defn count-matches
+  "Number of character matches in string"
+  [char string]
   (->> string (filter #(= char %)) count))
 
-(defn measure-string [string]
+(defn measure-string
+  "CharSequenceMeasurement of number of characters and newlines in string"
+  [string]
   (measurement (count string) (count-matches \newline string)))
 
 (extend-type nil

                (recur next l-index)))
            :default (throw (IndexOutOfBoundsException. (str "String index out of range: " index)))))))

(defn rope-seq [rope]
  (for [node (iterate zip/next (rope-zip rope)) :while (not (zip/end? node))]
    (zip/node node)))

(defn rope-str [rope]
  (->> (rope-seq rope) (filter string?) (reduce str)))

(defn rope-rebalance [coll] 
  (let [fold (fn [coll] (reduce rope (reverse coll)))
        fib-border (fn [limit] (->> *fib-seq* (take-while #(>= limit %)) last))]
    (loop [acc (), coll (->> (rope-seq coll) (filter string?)), max-length nil]
      (let [current (first coll), length (count current)]
        (if current
          (if (and (seq acc) (>= length max-length))

  (right [_] nil)
  (depth [_] 0))

(defprotocol Ropey
  "Rope-specific protocol for things that don't fit into general 2-3-Trees."
  (balanced? [rope]))


; necessary forward declaration
(deftype Rope [#^CharSequence left #^CharSequence right #^CharSequenceMeasurement weight #^int level])

(defn rope?
  "Is x a Rope?"
  [x]
  (instance? Rope x))

(defn weigh
  "The accumulated measurement of all children to the right, provided that Treeish-2-3 is implemented for seq.
In other words: What a new Treeish-2-3 node would weigh with seq as its left child."
  [seq]
  (if (and (satisfies? Treeish-2-3 seq) (right seq)) ; no child on the right? not required to weigh again
    (->> seq (iterate right) (take-while identity) (map measure) (map vals) (reduce #(map + %1 %2)) (apply measurement))
    (measure seq)))

(defn rope
  "New Rope that concatenates the given arguments, if any"
  ([] (Rope. nil nil (measurement 0 0) 0))
  ([seq] (Rope. seq nil (weigh seq) (inc (depth seq)))) 
  ([seq1 seq2] (Rope. seq1 seq2 (weigh seq1) (inc (max (depth seq1) (depth seq2))))))

(defn rope-zip
  "Creates Zipper structures for Ropes, starting from root"
  [root]
  (zip/zipper rope?
              (fn [node] (filter identity [(left node) (right node)]))
              (fn [node children] (apply rope children))
              root))

(defn rope-nth
  "Evaluates to character at position index in the Rope at root in O(log n) time"
  [root index]
  (loop [zipper (rope-zip root) l-index index]
    (let [node (zip/node zipper)]
      (cond (string? node) (nth node l-index)
            node
