How to increment several numeric keys of a hash-table

Question

Q: How to programmatically increment several numeric keys of a hash-table.

Background:

I am working on a modificion of speedbar to support the concept of speedbar-get-marked-files -- speedbar -- mark/unmark directories/files -- `speedbar-get-marked-files` I have setup a hash-table that consists of buffer line numbers for the keys, and the values are absolute filenames or directories.

When clicking on a + sign to expand directories, speedbar inserts additional files and directories underneath the expanded node. It is at this point that the hash-table needs to be modified, since puthash replaces existing entries. Programmatically, I already know how many new lines will be inserted.

Example:

A buffer contains 9 lines (in this case all directories), with a corresponding hash-table.

1  "/usr/"
2  "/usr/bin"
3  "/usr/include"
4  "/usr/lib"
5  "/usr/libexec"
6  "/usr/local"
7  "/usr/man"
8  "/usr/sbin"
9  "/usr/share"

We click on the expandable directory /usr/lib and programmatically we know that 8 new directories and 27 new files will be inserted. Therefore, a total of 35 new lines will be added underneath line 4 -- the previous hash-table entries of 5, 6, 7, 8 and 9 all need to be renumbered by adding 35 to each one. The new hash-table should become:

1  "/usr/"
2  "/usr/bin"
3  "/usr/include"
4  "/usr/lib"
40  "/usr/libexec"
41  "/usr/local"
42  "/usr/man"
43  "/usr/sbin"
44  "/usr/share"

Answer 1

If you know the top index, and you know that the indices are consecutive it might be more efficient to loop over those specific indices:

(let ((table #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data
                           (1 "/usr/" 2 "/usr/bin" 3 "/usr/include" 4 "/usr/lib" 5 "/usr/libexec"
                              6 "/usr/local" 7 "/usr/man" 8 "/usr/sbin" 9 "/usr/share")))
      (lo 5)
      (hi 9)
      (inc 35))
  (if (cl-plusp inc)
      (cl-loop for i from hi downto lo
               do (puthash (+ i inc) (gethash i table) table))
    (cl-loop for i from lo upto hi
             do (puthash (+ i inc) (gethash i table) table))))
 ;; assuming 5..34 are set later

Answer 2

As npostavs said, it would probably make more sense to use another datastructure, perhaps a B-tree or some other kind of tree, where you wouldn't need to do massive insert / remove operations. Below, however, is a simple example of how one can go about doing this while still using a hash-table:

(let ((example (make-hash-table))
      (offset 5)
      (increment 3))
  (cl-loop for i below 10 do (puthash i (format "value: %d" i) example))
  (cl-loop for k being the hash-keys of example using (hash-values v) do
           (message "before %s => %s" k v))
  (cl-loop for (k . v) in
           (cl-loop for k being the hash-keys of example using (hash-values v)
                    when (> k offset) do
                    (remhash k example)
                    and collect (cons k v))
           do (puthash (+ k increment) v example))
  (cl-loop for k being the hash-keys of example using (hash-values v) do
           (message "after %s => %s" k v)))

;; before 0 => value: 0
;; before 1 => value: 1
;; before 2 => value: 2
;; before 3 => value: 3
;; before 4 => value: 4
;; before 5 => value: 5
;; before 6 => value: 6
;; before 7 => value: 7
;; before 8 => value: 8
;; before 9 => value: 9

;; after 0 => value: 0
;; after 1 => value: 1
;; after 2 => value: 2
;; after 3 => value: 3
;; after 4 => value: 4
;; after 5 => value: 5
;; after 12 => value: 9
;; after 11 => value: 8
;; after 10 => value: 7
;; after 9 => value: 6

---

Note that there's a caveat: if you increase the key in the same loop, you may accidentally overwrite the value with higher key value.

Answer 3

(let* ((current-line (line-number-at-pos))
       (increment 35)
       (copied-line-to-node-table (copy-hash-table speedbar-line-to-node-table))
       (copied-node-to-line-table (copy-hash-table speedbar-node-to-line-table)))
  (maphash
    (lambda (line filename)
      (when (> line current-line)
        (puthash (+ line increment) filename speedbar-line-to-node-table)))
    copied-line-to-node-table)
  (maphash
    (lambda (filename line)
      (when (> line current-line)
        (puthash filename (+ line increment) speedbar-node-to-line-table)))
    copied-node-to-line-table))