bidirindex.org

Contents

• Namespace: thi.ng.dstruct.bidirindex
  • Protocols
  • Implementation
    • MonotonicBidirIndex
    • CustomBidirIndex
  • Constructors
  • ID generators
  • Indexing operations & helper functions
  • Complete namespace definition

Namespace: thi.ng.dstruct.bidirindex

This namespace provides bi-directional index implementations between values to IDs and vice versa.

Protocols

(defprotocol PIndex
  (index [_ item]
    "Attempts to find item in index and adds it to index if not found.
    Returns 2-elem vector of [updated-index item-id].")
  (unindex [_ item]
    "Attempts to remove item from index. Does nothing if item can't be
    found. Returns updated index.")
  (reindex [_ old new]
    "Attempts to re-associate the ID of old item with new item. Does
    nothing if old item can't be found. Returns update index."))

Implementation

The PIndex implementations below each consists of two hash maps to create the 2-way mapping:

• v->id - maps indexed items to their respective ID
• id->v - provides reverse mapping from ID to index value (uses sorted-map)

Since the indices are implemented as defrecord, both fields can be accessed via their respective keywords.

MonotonicBidirIndex

(defrecord MonotonicBidirIndex [v->id id->v next]
  PIndex
  (index
      [_ item]
    (let [id (get v->id item)]
      (if id
        [_ id]
        [(MonotonicBidirIndex.
          (assoc v->id item next)
          (assoc id->v next item)
          (inc next))
         next])))
  (unindex
      [_ item]
    (let [id (get v->id item)]
      (if id
        (MonotonicBidirIndex.
         (dissoc v->id item)
         (dissoc id->v id)
         next)
        _)))
  (reindex
      [_ item newitem]
    (let [id (get v->id item)]
      (if id
        (MonotonicBidirIndex.
         (-> v->id (dissoc item) (assoc newitem id))
         (assoc id->v id newitem)
         next)
        _))))

CustomBidirIndex

IDs for this implementation are generated via an user supplied function which is called for every new item to be indexed. The default implementation provides a monotonically increasing counter generator.

(defrecord CustomBidirIndex [v->id id->v id-gen]
  PIndex
  (index
      [_ item]
    (let [id (get v->id item)]
      (if id
        [_ id]
        (let [id (id-gen item)]
          [(CustomBidirIndex.
            (assoc v->id item id)
            (assoc id->v id item)
            id-gen)
           id]))))
  (unindex
      [_ item]
    (let [id (get v->id item)]
      (if id
        (CustomBidirIndex.
         (dissoc v->id item)
         (dissoc id->v id)
         id-gen)
        _)))
  (reindex
      [_ item newitem]
    (let [id (get v->id item)]
      (if id
        (CustomBidirIndex.
         (-> v->id (dissoc item) (assoc newitem id))
         (assoc id->v id newitem)
         id-gen)
        _))))

Constructors

(defn monotonic-index
  ([] (monotonic-index 0))
  ([start] (MonotonicBidirIndex. (hash-map) (sorted-map) start))
  ([start items] (reduce #(first (index %1 %2)) (monotonic-index start) items)))

(defn custom-index
  ([] (custom-index (counter)))
  ([id-gen] (CustomBidirIndex. (hash-map) (sorted-map) id-gen))
  ([id-gen items] (reduce #(first (index %1 %2)) (custom-index id-gen) items)))

ID generators

(defn counter
  ([] (counter 0))
  ([start] (let [id (volatile! (dec start))] (fn [_] (vswap! id inc)))))

Indexing operations & helper functions

(defn index-coll
  [idx coll]
  (reduce
   (fn [[idx ids] v]
     (let [[idx id] (index idx v)]
       [idx (conj ids id)]))
   [idx []] coll))

(defn index-attribs
  ([idx attribs]
   (index-attribs idx monotonic-index attribs))
  ([idx ctor attribs]
   (reduce-kv
    (fn [[attr aids] id v]
      (let [[idx ids] (index-coll (or (get attr id) (ctor)) v)]
        [(assoc attr id idx) (assoc aids id ids)]))
    [idx {}] attribs)))

(defn attrib-values
  [idx ids] (mapv (:id->v idx) ids))

Complete namespace definition

(ns thi.ng.dstruct.bidirindex)

<<protos>>

<<impl>>

<<idgen>>

<<ctors>>

<<ops>>