;;; Associative set
;;;
;;; (C) 2008 Gergő ÉRDI
;;; http://cactus.rulez.org/

(in-package :common-lisp-user)
(defpackage :cactus.aset
  (:use :common-lisp)
  (:export :set-from-list :aset-from-alist :defrag-alist))

(in-package :cactus.aset)

; TODO: use hashtables (mapping from rulename to hashtable repr of sets) instead of alists

(defun set-from-list (list)
  "Remove duplicates from 'list', producing a set"
  (and list (adjoin (car list) (set-from-list (cdr list)) :test #'equal)))

(defun defrag-alist (fragmented-alist &key (test #'eq))
  "Given an alist, for each key concatenate each value for that key"
  (let ((defrag-alist (mapcar #'list (set-from-list (mapcar #'car fragmented-alist)))))
    (loop for (key . value-fragment) in fragmented-alist
          for place = (assoc key defrag-alist :test test)
          do (rplacd place (append value-fragment (cdr place))))
    defrag-alist))

(defun aset-from-alist (alist)
  (mapcar #'(lambda (key-value) (rplacd key-value (set-from-list (cdr key-value))))
          alist))