Changeset 3974
- Timestamp:
- 2016-05-30T17:28:04-07:00 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/f4grobner/pair-queue.lisp
r3972 r3974 90 90 polynomials is selected.")) 91 91 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. 99 100 and START is the first position beyond the elements which form a 100 101 partial 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 self105 (setf pq (make-priority-queue106 :element-type 'critical-pair107 :element-key #'(lambda (pair) (funcall pair-key-fn (critical-pair-first pair) (critical-pair-second pair)))108 :test pair-order-fn))109 102 ;; Add critical pairs for polynomials in POLY-LIST 110 111 112 113 114 115 (dolist (pair b)116 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))))) 117 110 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 self124 (format stream "PAIR-KEY-FN=~A PAIR-ORDER-FN=~A PQ=~A"125 pair-key-fn pair-order-fn pq))))126 111 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 self132 (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 self139 (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 self146 (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 self153 (priority-queue-empty-p pq))))154
Note:
See TracChangeset
for help on using the changeset viewer.