Hike

Hike is a library for managing identity in mutable grids with multiple, mutually independent (orthogonal) dimensions. The chief example of an application which such grids is a spreadsheet, where rows and columns can be inserted, removed and transposed. Hike provides identity for grid cells, so that data, dependencies and other properties can be attached to them. For a technical tour of its inner workings, you may want to read the relevant post on our blog.

Public API

(make-chart options) Constructs a multi-dimensional chart. If dimensions are supplied, dimensions are named after them, otherwise anonymous. Iff anonymous, their number is defined by dimensionality. The encode / decode functions convert cell origins to/from IDs (both default to identity).
(cell->id cell chart) Returns the ID for cell according to chart.
(id->cell id chart) Returns the cell for id according to chart, nil if not visible.
(slice->cells slice) Returns the cells in slice (a map containing :start and :end IDs) according to chart.
(operate chart dimension operation) Performs operation on the dimension in chart. For charts with named dimensions, dimension is a name, otherwise an index. Discards any previously undone operations.
(undo chart) Deactivates the last active operation in chart, if any.
(redo chart) Reactivates the last deactivated operation in chart, if any.
(make-transformers operation) Multimethod (dispatched on operation’s :action) for extending the operation set.

Usage

For a common 2D spreadsheet grid, we might define a chart like this:

(require '[hike.core :as hike])

(def spreadsheet-chart (hike/make-chart {:dimensions [:row :column]}))

Then, we can start asking for cell identities:

(def id-1 (hike/cell->id [3 4] spreadsheet-chart))
(def id-2 (hike/cell->id [13 14] spreadsheet-chart))

(map #(hike/id->cell % spreadsheet-chart) [id-1 id-2])

([3 4] [13 14])

Hike supports three actions as grid operations out of the box: insertion (:insert :count cells at :index), removal (:remove :count consecutive cells starting at :index) and transposition (:transpose :count consecutive cells starting at :index :offset positions to the right – a negative :offset meaning to the left).

Insertion

Let’s insert 3 new consecutive rows, with the first new one at position 10:

(as-> spreadsheet-chart $
  (hike/operate $ :row {:action :insert :index 10 :count 3})
  (map #(hike/id->cell % $) [id-1 id-2]))

([3 4] [16 14])

Notice how the cell corresponding to id-1 wasn’t affected, but the one for id-2 was moved 3 positions down. Thus, the slice between them has grown:

{:before (-> {:start id-1 :end id-2}
	     (hike/slice->cells spreadsheet-chart)
	     count)
 :after  (as-> spreadsheet-chart $
	   (hike/operate $ :row {:action :insert :index 10 :count 3})
	   (hike/slice->cells {:start id-1 :end id-2} $)
	   (count $))}

{:before 121, :after 154}

Removal

Let’s remove 3 consecutive columns starting from position 10:

(as-> spreadsheet-chart $
  (hike/operate $ :column {:action :remove :index 10 :count 3})
  (map #(hike/id->cell % $) [id-1 id-2]))

([3 4] [13 11])

Notice that, again, the cell corresponding to id-1 wasn’t affected, but the one for id-2 was moved 3 positions to the left. Thus, the slice between them has shrunk:

{:before (-> {:start id-1 :end id-2}
	     (hike/slice->cells spreadsheet-chart)
	     count)
 :after  (as-> spreadsheet-chart $
	   (hike/operate $ :column {:action :remove :index 10 :count 3})
	   (hike/slice->cells {:start id-1 :end id-2} $)
	   (count $))}

{:before 121, :after 88}

Transposition

Let’s transpose 3 consecutive rows, starting from position 2, one position up (notice the negative :offset value)

(as-> spreadsheet-chart $
  (hike/operate $ :row {:action :transpose :index 2 :count 3 :offset -1})
  (map #(hike/id->cell % $) [id-1 id-2]))

([2 4] [13 14])

Notice that, this time, the cell corresponding to id-2 wasn’t affected, whereas the one for id-1 was indeed moved one position up (as it belonged to the rows being transposed). Thus, the slice between them has grown:

{:before (-> {:start id-1 :end id-2}
	     (hike/slice->cells spreadsheet-chart)
	     count)
 :after  (as-> spreadsheet-chart $
	   (hike/operate $ :row {:action :transpose :index 2 :count 3 :offset -1})
	   (hike/slice->cells {:start id-1 :end id-2} $)
	   (count $))}

{:before 121, :after 132}

Undo/redo

Hike supports linear undo/redo, the scheme most popular among end-user applications. What this means is that we can at any time undo the last active operation. Any undone operation may be redone (i.e. re-activated), provided that no other operations have been applied since the undo. In other words, every new operation truncates history of operations that were undone at the time of its introduction. Let’s see it in action (observing the position of id-2 during a simple chain of undos and redos):

(loop [chart  (-> spreadsheet-chart
		  (hike/operate :row {:action :insert :index 10 :count 3})
		  (hike/operate :column {:action :remove :index 10 :count 3}))
       ;; notice the extraneous third undo (nop)
       ops    [hike/undo hike/undo hike/undo hike/redo hike/redo]
       result [(hike/id->cell id-2 chart)]]
  (if-not (seq ops) result
	  (let [new-chart ((first ops) chart)]
	    (recur new-chart
		   (rest ops)
		   (conj result (hike/id->cell id-2 new-chart))))))

[[16 11] [16 14] [13 14] [13 14] [16 14] [16 11]]

Extraneous undos (when there no more active operations) and redos (when there have been no undos since the last operation) have no effect.

Extensibility

Hike supports extension of its operation set. To add a new operation, you have to define a method for the make-transformers multimethod. Its input is a map with no requirements but a unique dispatch (:action) value. The method should return a map of two functions:

(descend pos & [bypass])) Returns the old position of the cell at position pos after the operation. If it was just inserted, return nil, unless the optional bypass direction (either :min or :max) is specified. In this case, return the position of the nearest available cell in that direction before the operation is performed.
(ascend pos & [bypass])) Returns the new position of the cell that was at position pos before the operation. If it was just removed, return nil, unless the optional bypass direction (either :min or :max) is specified. In this case, return the position of the nearest available cell in that direction after the operation is performed.

For example, suppose we want to define an operation which creates a double of every cell along a dimension (to create, for example, a column on the right of each column in a spreadsheet). We can define such an operation by writing something like this:

(defmethod hike/make-transformers :interpose [_op]
  {:descend (fn [pos & [bypass]]
	      (if (even? pos) (/ pos 2)
		  (get {:min (dec pos)
			:max (inc pos)}
		       bypass)))
   :ascend  (fn [pos & _] (* pos 2))})

We can now see the new operation in action:

(as-> spreadsheet-chart $
  (hike/operate $ :column {:action :interpose})
  (map #(hike/id->cell % $) [id-1 id-2]))

([3 8] [13 28])

Of course, if we ask for the position of a cell created by the operation after we undo it, we get nil:

(let [interposed (hike/operate spreadsheet-chart :column {:action :interpose})]
  (hike/id->cell (hike/cell->id [3 3] interposed)
	         (hike/undo interposed)))

nil

For other cells, we get their old position as usual:

(let [interposed (hike/operate spreadsheet-chart :column {:action :interpose})]
  (hike/id->cell (hike/cell->id [3 4] interposed)
	         (hike/undo interposed)))

[3 2]

Custom IDs

Hike’s ID generation is fully customizable. If we examine an ID from the previous examples, we can see its default representation:

id-1

([0 3] [0 4])

which is a sequence of pairs, one for each dimension. Every pair consists of a nonnegative (natural) integer and an integer, in that order. When constructing a chart, we can specify our own encode and decode functions, which should translate between this and any other (still unique!) ID representation we need.

To see where this feature might be useful, consider a spreadsheet’s sheets. Each sheet hosts its own grid, but cells may contain references to cells/slices from other grids, so they have to share the space of possible ID values. To do that, we have to attach additional, differentiating data to IDs that might otherwise be identical across different grids. Grids aren’t just another dimension, since we expect them to be independent from each other (e.g. if we remove some rows from a grid, we don’t expect other grids to change). With that in mind, we can create a chart for a specific sheet’s grid:

(letfn [(make-sheet-chart [sheet-id]
	  (hike/make-chart {:dimensions [:row :column]
			    :encode     #(assoc {:sheet sheet-id} :grid-id %)
			    :decode     :grid-id}))]
  (let [chart (make-sheet-chart 1)
	id    (hike/cell->id [1 2] chart)]
    [id (hike/id->cell id chart)]))

[{:sheet 1, :grid-id ([0 1] [0 2])} [1 2]]

This way, the encoder attaches the sheet’s ID to make the generated ID globally unique, while the decoder in the referenced sheet’s chart picks the grid ID to return the cell position.

Another use of custom ID generation is some requirement imposed on the type/form of the IDs, e.g. them being byte arrays:

(let [chart (hike/make-chart {:dimensions [:row :column]
			      :encode     #(-> % pr-str .getBytes)
			      :decode     #(-> % String. clojure.edn/read-string)})
      id    (hike/cell->id [1 2] chart)]
  [(bytes? id) (hike/id->cell id chart)])

[true [1 2]]

pixelated-noise/hike