[instancer] templatize the priority queue, use custom type for varstore

when instantiating varstore, we need to pop a tuple like
(combined_gain, i, j), if combined gain is the same then we compare the
value of i, and then j. So we'd like to use custom type as the key when
popping from the queue. This would match fonttool's algorithm cause it
uses heappop().

4 files changed, 42 insertions, 18 deletions

diff --git a/src/graph/graph.hh b/src/graph/graph.hh
index 49424488e..2b4e1b2d3 100644
--- a/src/graph/graph.hh
+++ b/src/graph/graph.hh
@@ -566,7 +566,7 @@ struct graph_t
 
     update_distances ();
 
-    hb_priority_queue_t queue;
+    hb_priority_queue_t<int64_t> queue;
     hb_vector_t<vertex_t> &sorted_graph = vertices_scratch_;
     if (unlikely (!check_success (sorted_graph.resize (vertices_.length)))) return;
     hb_vector_t<unsigned> id_map;
@@ -1369,7 +1369,7 @@ struct graph_t
       vertices_.arrayZ[i].distance = hb_int_max (int64_t);
     vertices_.tail ().distance = 0;
 
-    hb_priority_queue_t queue;
+    hb_priority_queue_t<int64_t> queue;
     queue.insert (0, vertices_.length - 1);
 
     hb_vector_t<bool> visited;
diff --git a/src/hb-ot-var-common.hh b/src/hb-ot-var-common.hh
index 7a5227f1a..b6fe13f11 100644
--- a/src/hb-ot-var-common.hh
+++ b/src/hb-ot-var-common.hh
@@ -1938,6 +1938,35 @@ struct item_variations_t
 
   /* main algorithm ported from fonttools VarStore_optimize() method, optimize
    * varstore by default */
+
+  struct combined_gain_idx_tuple_t
+  {
+    int gain;
+    unsigned idx_1;
+    unsigned idx_2;
+
+    combined_gain_idx_tuple_t () = default;
+    combined_gain_idx_tuple_t (int gain_, unsigned i, unsigned j)
+        :gain (gain_), idx_1 (i), idx_2 (j) {}
+
+    bool operator < (const combined_gain_idx_tuple_t& o)
+    {
+      if (gain != o.gain)
+        return gain < o.gain;
+
+      if (idx_1 != o.idx_1)
+        return idx_1 < o.idx_1;
+
+      return idx_2 < o.idx_2;
+    }
+
+    bool operator <= (const combined_gain_idx_tuple_t& o)
+    {
+      if (*this < o) return true;
+      return gain == o.gain && idx_1 == o.idx_1 && idx_2 == o.idx_2;
+    }
+  };
+
   bool as_item_varstore (bool optimize=true, bool use_no_variation_idx=true)
   {
     if (!region_list) return false;
@@ -2058,7 +2087,7 @@ struct item_variations_t
 
     /* main algorithm: repeatedly pick 2 best encodings to combine, and combine
      * them */
-    hb_priority_queue_t queue;
+    hb_priority_queue_t<combined_gain_idx_tuple_t> queue;
     unsigned num_todos = encoding_objs.length;
     for (unsigned i = 0; i < num_todos; i++)
     {
@@ -2066,19 +2095,16 @@ struct item_variations_t
       {
         int combining_gain = encoding_objs.arrayZ[i].gain_from_merging (encoding_objs.arrayZ[j]);
         if (combining_gain > 0)
-        {
-          unsigned val = (i << 16) + j;
-          queue.insert (-combining_gain, val);
-        }
+          queue.insert (combined_gain_idx_tuple_t (-combining_gain, i, j), 0);
       }
     }
 
     hb_set_t removed_todo_idxes;
     while (queue)
     {
-      unsigned val = queue.pop_minimum ().second;
-      unsigned j = val & 0xFFFF;
-      unsigned i = (val >> 16) & 0xFFFF;
+      auto t = queue.pop_minimum ().first;
+      unsigned i = t.idx_1;
+      unsigned j = t.idx_2;
 
       if (removed_todo_idxes.has (i) || removed_todo_idxes.has (j))
         continue;
@@ -2119,10 +2145,7 @@ struct item_variations_t
 
         int combined_gain = combined_encoding_obj.gain_from_merging (obj);
         if (combined_gain > 0)
-        {
-          unsigned val = (idx << 16) + encoding_objs.length;
-          queue.insert (-combined_gain, val);
-        }
+          queue.insert (combined_gain_idx_tuple_t (-combined_gain, idx, encoding_objs.length), 0);
       }
 
       encoding_objs.push (std::move (combined_encoding_obj));
diff --git a/src/hb-priority-queue.hh b/src/hb-priority-queue.hh
index baac7e1e6..2c8ccbfb6 100644
--- a/src/hb-priority-queue.hh
+++ b/src/hb-priority-queue.hh
@@ -42,10 +42,11 @@
  * priority of its children. The heap is stored in an array, with the
  * children of node i stored at indices 2i + 1 and 2i + 2.
  */
+template <typename K>
 struct hb_priority_queue_t
 {
  private:
-  typedef hb_pair_t<int64_t, unsigned> item_t;
+  typedef hb_pair_t<K, unsigned> item_t;
   hb_vector_t<item_t> heap;
 
  public:
@@ -57,7 +58,7 @@ struct hb_priority_queue_t
 #ifndef HB_OPTIMIZE_SIZE
   HB_ALWAYS_INLINE
 #endif
-  void insert (int64_t priority, unsigned value)
+  void insert (K priority, unsigned value)
   {
     heap.push (item_t (priority, value));
     if (unlikely (heap.in_error ())) return;
diff --git a/src/test-priority-queue.cc b/src/test-priority-queue.cc
index e83d72c7e..67ee5ee4c 100644
--- a/src/test-priority-queue.cc
+++ b/src/test-priority-queue.cc
@@ -30,7 +30,7 @@
 static void
 test_insert ()
 {
-  hb_priority_queue_t queue;
+  hb_priority_queue_t<int64_t> queue;
   assert (queue.is_empty ());
 
   queue.insert (10, 0);
@@ -53,7 +53,7 @@ test_insert ()
 static void
 test_extract ()
 {
-  hb_priority_queue_t queue;
+  hb_priority_queue_t<int32_t> queue;
   queue.insert (0, 0);
   queue.insert (60, 6);
   queue.insert (30, 3);