;;; nixlist.el --- Miscellaneously useful functions on lists.

;;; Copyright (C) 2000, 2004, 2007 Nix <nix@esperi.org.uk>.

;; Author: Nix <nix@esperi.org.uk>
;; Created: 2000-01-06
;; Keywords: lisp
;; Version: $Revision: 1.1 $

;; This file is not part of XEmacs.

;; This library is free software; you can redistribute it and/or modify it
;; under the terms of the GNU General Public License as published by
;; the Free Software Foundation; either version 2.1, or (at your option)
;; any later version.

;; It is distributed in the hope that it will be useful, but WITHOUT
;; ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
;; or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
;; License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this library; see the file COPYING.  If not, write to the
;; Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
;; 02111-1307, USA.

;;; Commentary:

;; This file implements useful list-manipulation functions that aren't
;; already in Emacs, CL, or Elib --- yes, amazingly, there are some.

;;; Requirements:

(require 'cl)

;;; Code:

(defsubst splice (after element seq)
  "Splice ELEMENT into SEQ AFTER a given element.
Elements are compared against AFTER with `eq'.
If the element to insert AFTER is not found, the list is returned unchanged.
See also `splice-equal'."
  (let ((to-splice (memq after seq)))
    (and to-splice
         (rplacd to-splice (cons element (cdr to-splice)))))
  seq)

(defsubst splice-equal (after element seq)
  "Splice ELEMENT into SEQ AFTER a given element.
Elements are compared against AFTER with `equal'.
If the element to insert AFTER is not found, the list is returned unchanged.
See also `splice'."
  (let ((to-splice (member after seq)))
    (and to-splice
         (rplacd to-splice (cons element (cdr to-splice)))))
  seq)

(defun power-set (the-list)
  "Produce the power set of THE-LIST.
That is, produce a list whose elements are lists
consisting of all possible permutations of THE-LIST."
; Simple recursion; the power set of a list A is the power set
; of A with each of its elements in turn removed, and A itself.
(and the-list
     (remove-duplicates
      (nconc (list the-list) (mapcan #'(lambda (dead-member)
                                         (power-set (delq dead-member (copy-list the-list))))
                                     the-list)))))

(provide 'nixlist)