close Warning: Can't synchronize with repository "(default)" (The repository directory has changed, you should resynchronize the repository with: trac-admin $ENV repository resync '(default)'). Look in the Trac log for more information.

Changeset 3974 for branches


Ignore:
Timestamp:
2016-05-30T17:28:04-07:00 (8 years ago)
Author:
Marek Rychlik
Message:

* empty log message *

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/f4grobner/pair-queue.lisp

    r3972 r3974  
    9090polynomials is selected."))
    9191
    92 (defclass critical-pair-queue (selection-strategy)
    93   ((pq :initform nil :initarg :pq :accessor pq :type priority-queue))
    94   (:documentation "Represents the priority queue of critical pairs. It is a subclass
    95 of SELECTION-STRATEGY."))
    96 
    97 (defmethod initialize-instance :after ((self critical-pair-queue) &key (poly-list nil) (start 1))
    98   "Initializes the priority queue SELF of critical pairs, where POLY-LIST is the initial list of polynomials.
     92(defun make-critical-pair-queue (&key pair-key-fn pair-order-fn (poly-list nil) (start 1)
     93                                 &aux (pq (make-priority-queue
     94                                           :element-type 'critical-pair
     95                                           :element-key #'(lambda (pair) (funcall pair-key-fn
     96                                                                                  (critical-pair-first pair)
     97                                                                                  (critical-pair-second pair)))
     98                                           :test pair-order-fn)))
     99  "Makes a priority queue for critical pairs. The argument POLY-LIST should the initial list of polynomials.
    99100and START is the first position beyond the elements which form a
    100101partial Grobner basis, i.e. satisfy the Buchberger criterion."
    101   (with-accessors ((pair-key-fn pair-key-fn)
    102                    (pair-order-fn pair-order-fn)
    103                    (pq pq))
    104       self
    105     (setf pq (make-priority-queue
    106                 :element-type 'critical-pair
    107                 :element-key #'(lambda (pair) (funcall pair-key-fn (critical-pair-first pair) (critical-pair-second pair)))
    108                 :test pair-order-fn))
    109102    ;; Add critical pairs for polynomials in POLY-LIST
    110     (let* ((s (1- (length poly-list)))
    111            (b (nconc (makelist (make-instance 'critical-pair :first (elt poly-list i) :second (elt poly-list j))
    112                                (i 0 (1- start)) (j start s))
    113                      (makelist (make-instance 'critical-pair :first (elt poly-list i) :second (elt poly-list j))
    114                                (i start (1- s)) (j (1+ i) s)))))
    115       (dolist (pair b)
    116         (priority-queue-insert pq pair)))))
     103  (let* ((s (1- (length poly-list)))
     104         (b (nconc (makelist (make-instance 'critical-pair :first (elt poly-list i) :second (elt poly-list j))
     105                             (i 0 (1- start)) (j start s))
     106                   (makelist (make-instance 'critical-pair :first (elt poly-list i) :second (elt poly-list j))
     107                             (i start (1- s)) (j (1+ i) s)))))
     108    (dolist (pair b pq)
     109      (priority-queue-insert pq pair)))))
    117110
    118 (defmethod print-object ((self critical-pair-queue) stream)
    119   (print-unreadable-object (self stream :type t :identity t)
    120     (with-accessors ((pair-key-fn pair-key-fn)
    121                      (pair-order-fn pair-order-fn)
    122                      (pq pq))
    123         self
    124       (format stream "PAIR-KEY-FN=~A PAIR-ORDER-FN=~A PQ=~A"
    125               pair-key-fn pair-order-fn pq))))
    126111
    127 (defgeneric enqueue (self object)
    128   (:documentation "Insert an object OBJECT into a queue SELF.")
    129   (:method ((self critical-pair-queue) (pair critical-pair))
    130     (with-slots (pq)
    131         self
    132       (priority-queue-insert pq pair))))
    133 
    134 (defgeneric dequeue (self)
    135   (:documentation "Remove an object from a queue SELF. Returns the removed object.")
    136   (:method ((self critical-pair-queue))
    137     (with-slots (pq)
    138         self
    139       (priority-queue-remove pq))))
    140 
    141 (defgeneric queue-size (self)
    142   (:documentation "Returns the number of elements in the queue SELF.")
    143   (:method ((self critical-pair-queue))
    144     (with-slots (pq)
    145         self
    146       (priority-queue-size pq))))
    147 
    148 (defgeneric queue-empty-p (self)
    149   (:documentation "Returns T if the queue SELF is empty, NIL otherwise.")
    150   (:method ((self critical-pair-queue))
    151     (with-slots (pq)
    152         self
    153       (priority-queue-empty-p pq))))
    154 
Note: See TracChangeset for help on using the changeset viewer.