[yt-svn] commit/yt: ngoldbaum: Merged in MatthewTurk/yt (pull request #2411)

commits-noreply at bitbucket.org commits-noreply at bitbucket.org
Mon Oct 17 14:19:43 PDT 2016


1 new commit in yt:

https://bitbucket.org/yt_analysis/yt/commits/f1929d10804e/
Changeset:   f1929d10804e
Branch:      yt
User:        ngoldbaum
Date:        2016-10-17 21:19:17+00:00
Summary:     Merged in MatthewTurk/yt (pull request #2411)

Extract priority queue superclass from distance queue.
Affected #:  2 files

diff -r db097c2981cda61b07abbb087125bb03ea1006a4 -r f1929d10804e6b316a34b74293ca3c7bdebc26b4 yt/utilities/lib/distance_queue.pxd
--- a/yt/utilities/lib/distance_queue.pxd
+++ b/yt/utilities/lib/distance_queue.pxd
@@ -20,6 +20,12 @@
 from libc.stdlib cimport malloc, free
 from libc.string cimport memmove
 
+# THESE TWO STRUCTS MUST BE EQUIVALENT
+
+cdef struct ItemList:
+    np.int64_t ind
+    np.float64_t value
+
 cdef struct NeighborList:
     np.int64_t pn       # Particle number
     np.float64_t r2     # radius**2
@@ -31,9 +37,14 @@
                          bint periodicity[3],
                          np.float64_t max_dist2)
 
-cdef class DistanceQueue:
+cdef class PriorityQueue:
     cdef int maxn
     cdef int curn
+    cdef ItemList* items
+    cdef void item_reset(self)
+    cdef int item_insert(self, np.int64_t i, np.float64_t value)
+
+cdef class DistanceQueue(PriorityQueue):
     cdef np.float64_t DW[3]
     cdef bint periodicity[3]
     cdef NeighborList* neighbors # flat array

diff -r db097c2981cda61b07abbb087125bb03ea1006a4 -r f1929d10804e6b316a34b74293ca3c7bdebc26b4 yt/utilities/lib/distance_queue.pyx
--- a/yt/utilities/lib/distance_queue.pyx
+++ b/yt/utilities/lib/distance_queue.pyx
@@ -56,16 +56,68 @@
             return -1.0
     return r2
 
+cdef class PriorityQueue:
+    """This class acts as a "priority-queue."  It was extracted from the
+    DistanceQueue object so that it could serve as a general-purpose method for
+    storing the N-most "valuable" objects.  It's relatively simple, in that it
+    provides storage for a single int64 (which is usually an 'index' into an
+    external array or list) and a single float64 "value" associated with them.
+    You can insert new objects, and then if it's already at maxn objects in it,
+    it'll bump the least valuable one off the end.  Of particular note is that
+    *lower* values are considered to be *more valuable* than higher ones; this
+    is because our typical use case is to store radii.
+    """
+    def __cinit__(self, int maxn):
+        cdef int i
+        self.maxn = maxn
+        self.curn = 0
+        self.items = <ItemList *> malloc(
+            sizeof(ItemList) * self.maxn)
+
+    cdef void item_reset(self):
+        for i in range(self.maxn):
+            self.items[i].value = 1e300
+            self.items[i].ind = -1
+        self.curn = 0
+
+    cdef int item_insert(self, np.int64_t ind, np.float64_t value):
+        cdef int i, di
+        if self.curn == 0:
+            self.items[0].value = value
+            self.items[0].ind = ind
+            self.curn += 1
+            return 0
+        # Now insert in a sorted way
+        di = -1
+        for i in range(self.curn - 1, -1, -1):
+            # We are checking if i is less than us, to see if we should insert
+            # to the right (i.e., i+1).
+            if self.items[i].value < value:
+                di = i
+                break
+        # The outermost one is already too small.
+        if di == self.maxn - 1:
+            return -1
+        if (self.maxn - (di + 2)) > 0:
+            memmove(<void *> (self.items + di + 2),
+                    <void *> (self.items + di + 1),
+                    sizeof(ItemList) * (self.maxn - (di + 2)))
+        self.items[di + 1].value = value
+        self.items[di + 1].ind = ind
+        if self.curn < self.maxn:
+            self.curn += 1
+        return di + 1
+
 cdef class DistanceQueue:
     """This is a distance queue object, designed to incrementally evaluate N
     positions against a reference point.  It is initialized with the maximum
     number that are to be retained (i.e., maxn-nearest neighbors)."""
     def __cinit__(self, int maxn):
-        cdef int i
-        self.maxn = maxn
-        self.curn = 0
-        self.neighbors = <NeighborList *> malloc(
-            sizeof(NeighborList) * self.maxn)
+        if sizeof(ItemList) != sizeof(NeighborList):
+            # This should almost never, ever happen unless we do something very
+            # wrong, and must be broken at compile time.
+            raise RuntimeError
+        self.neighbors = <NeighborList *> self.items
         self.neighbor_reset()
         for i in range(3):
             self.DW[i] = 0
@@ -88,7 +140,6 @@
                             np.float64_t cpos[3]):
         # Here's a python+numpy simulator of this:
         # http://paste.yt-project.org/show/5445/
-        cdef int i, di
         cdef np.float64_t r2, r2_trunc
         if self.curn == self.maxn:
             # Truncate calculation if it's bigger than this in any dimension
@@ -99,36 +150,10 @@
         r2 = r2dist(ppos, cpos, self.DW, self.periodicity, r2_trunc)
         if r2 == -1:
             return
-        if self.curn == 0:
-            self.neighbors[0].r2 = r2
-            self.neighbors[0].pn = pn
-            self.curn += 1
-            return
-        # Now insert in a sorted way
-        di = -1
-        for i in range(self.curn - 1, -1, -1):
-            # We are checking if i is less than us, to see if we should insert
-            # to the right (i.e., i+1).
-            if self.neighbors[i].r2 < r2:
-                di = i
-                break
-        # The outermost one is already too small.
-        if di == self.maxn - 1:
-            return
-        if (self.maxn - (di + 2)) > 0:
-            memmove(<void *> (self.neighbors + di + 2),
-                    <void *> (self.neighbors + di + 1),
-                    sizeof(NeighborList) * (self.maxn - (di + 2)))
-        self.neighbors[di + 1].r2 = r2
-        self.neighbors[di + 1].pn = pn
-        if self.curn < self.maxn:
-            self.curn += 1
+        self.item_insert(pn, r2)
 
     cdef void neighbor_reset(self):
-        for i in range(self.maxn):
-            self.neighbors[i].r2 = 1e300
-            self.neighbors[i].pn = -1
-        self.curn = 0
+        self.item_reset()
 
     def find_nearest(self, np.float64_t[:] center, np.float64_t[:,:] points):
         """This function accepts a center and a set of [N,3] points, and it

Repository URL: https://bitbucket.org/yt_analysis/yt/

--

This is a commit notification from bitbucket.org. You are receiving
this because you have the service enabled, addressing the recipient of
this email.


More information about the yt-svn mailing list