Class: CPriorityQueue

Inherits:
Object show all
Defined in:
ext/amp/priority_queue/priority_queue.c

Overview

A Priority Queue implementation

A priority queue is a queue, where each element (the key) has an assigned priority. It is possible to efficently decrease priorities and to efficently look up and remove the key with the smallest priority.

This datastructure is used in different algorithms. The standard algorithm used to introduce priority queues is dijkstra’s shortest path algorithm.

The priority queue includes the Enumerable module.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Object

Create a new, empty PriorityQueue



494
495
496
497
498
499
 
# File 'ext/amp/priority_queue/priority_queue.c', line 494

static
VALUE pq_init(VALUE self) {
  rb_iv_set(self, "@__node_by_object__", rb_hash_new());

  return self;
}

Instance Method Details

#[](object) ⇒ Object

Return the priority of a key or nil if the key is not in the queue.

q = PriorityQueue.new
(0..10).each do | i | q[i.to_s] = i end
q["5"] #=> 5
q[5] #=> nil



717
718
719
720
721
722
723
724
725
726
727
 
# File 'ext/amp/priority_queue/priority_queue.c', line 717

static
VALUE pq_get_priority(VALUE self, VALUE object) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");

  VALUE node_pointer = rb_hash_aref(hash, object);
  
  if (NIL_P(node_pointer))
    return Qnil;
  else
    return (VALUE) (((priority_node*) NUM2ULONG(node_pointer))->priority);
}

#[]=(object, priority) ⇒ Object

change_priority(key, priority)

push(key, priority)

Set the priority of a key.

q = PriorityQueue.new
q["car"] = 50
q["train"] = 50
q["bike"] = 10
q.min #=> ["bike", 10]
q["car"] = 0
q.min #=> ["car", 0]



691
692
693
694
695
696
697
698
699
700
701
702
703
704
 
# File 'ext/amp/priority_queue/priority_queue.c', line 691

static
VALUE pq_change_priority(VALUE self, VALUE object, VALUE priority) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");
  priority_queue* q = get_pq_from_value(self);

  VALUE node = rb_hash_aref(hash, object);
  if (NIL_P(node)) {
    pq_push(self, object, priority);
  } else {
    priority_queue_change_priority(q, (priority_node*) NUM2ULONG(node), priority);
  }

  return self;
}

#change_priority(object, priority) ⇒ Object

change_priority(key, priority)

push(key, priority)

Set the priority of a key.

q = PriorityQueue.new
q["car"] = 50
q["train"] = 50
q["bike"] = 10
q.min #=> ["bike", 10]
q["car"] = 0
q.min #=> ["car", 0]



691
692
693
694
695
696
697
698
699
700
701
702
703
704
 
# File 'ext/amp/priority_queue/priority_queue.c', line 691

static
VALUE pq_change_priority(VALUE self, VALUE object, VALUE priority) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");
  priority_queue* q = get_pq_from_value(self);

  VALUE node = rb_hash_aref(hash, object);
  if (NIL_P(node)) {
    pq_push(self, object, priority);
  } else {
    priority_queue_change_priority(q, (priority_node*) NUM2ULONG(node), priority);
  }

  return self;
}

#delete(key) ⇒ Array #delete(key) ⇒ nil

Delete a key from the priority queue. Returns nil when the key was not in the queue and [key, priority] otherwise.

q = PriorityQueue.new
(0..10).each do | i | q[i.to_s] = i end
q.delete(5)                               #=> ["5", 5]
q.delete(5)                               #=> nil

Overloads:

  • #delete(key) ⇒ Array

    Returns:

  • #delete(key) ⇒ nil

    Returns:

    • (nil) 


777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
 
# File 'ext/amp/priority_queue/priority_queue.c', line 777

static
VALUE pq_delete(VALUE self, VALUE object) {
  priority_queue* q = get_pq_from_value(self);

  VALUE hash = rb_iv_get(self, "@__node_by_object__");

  VALUE node_pointer = rb_hash_aref(hash, object);  
  
  if (NIL_P(node_pointer))
    return Qnil;
  else {
    priority_node* n = (priority_node*) NUM2ULONG(node_pointer);
    VALUE object = n->object;
    VALUE priority = n->priority;
    priority_queue_delete(q, n);
    rb_hash_delete(hash, object);
    priority_node_free(n);
    return rb_ary_new3(2, object, priority);
  }
}

#delete_min ⇒ Array

Delete key with minimal priority and return [key, priority]

q = PriorityQueue.new
q["a"] = 1
q["b"] = 0
q.delete_min #=> ["b", 0]
q.delete_min #=> ["a", 1]
q.delete_min #=> nil

Returns:



605
606
607
608
609
610
611
612
613
614
615
616
617
618
 
# File 'ext/amp/priority_queue/priority_queue.c', line 605

static
VALUE pq_delete_min(VALUE self) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");
  priority_queue* q = get_pq_from_value(self);

  priority_node* n = priority_queue_delete_min(q);

  if (n) {
    rb_hash_delete(hash, n->object); // TODO: Maybe we have a problem here with garbage collection of n->object?
    return rb_ary_new3(2, n->object, n->priority);  
  } else {
    return Qnil;
  }
}

#delete_min_return_key ⇒ Object

Delete key with minimal priority and return the key

q = PriorityQueue.new
q["a"] = 1
q["b"] = 0
q.delete_min_return_key #=> "b"
q.delete_min_return_key #=> "a"
q.delete_min_return_key #=> nil



632
633
634
635
636
637
638
639
640
641
642
643
644
645
 
# File 'ext/amp/priority_queue/priority_queue.c', line 632

static
VALUE pq_delete_min_return_key(VALUE self) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");
  priority_queue* q = get_pq_from_value(self);

  priority_node* n = priority_queue_delete_min(q);

  if (n) {
    rb_hash_delete(hash, n->object); // TODO: Maybe we have a problem here with garbage collection of n->object?
    return n->object;  
  } else {
    return Qnil;
  }
}

#delete_min_return_priority ⇒ Object

Delete key with minimal priority and return the priority value

q = PriorityQueue.new
q["a"] = 1
q["b"] = 0
q.delete_min_return_priority #=> 0
q.delete_min_return_priority #=> 1
q.delete_min_return_priority #=> nil



660
661
662
663
664
665
666
667
668
669
670
671
672
673
 
# File 'ext/amp/priority_queue/priority_queue.c', line 660

static
VALUE pq_delete_min_return_priority(VALUE self) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");
  priority_queue* q = get_pq_from_value(self);

  priority_node* n = priority_queue_delete_min(q);

  if (n) {
    rb_hash_delete(hash, n->object); // TODO: Maybe we have a problem here with garbage collection of n->object?
    return n->priority;  
  } else {
    return Qnil;
  }
}

#each ⇒ Object

Call the given block with each [key, priority] pair in the queue

Beware: Changing the queue in the block may lead to unwanted behaviour and even infinite loops.



869
870
871
872
873
874
 
# File 'ext/amp/priority_queue/priority_queue.c', line 869

static
VALUE pq_each(VALUE self) {
  priority_queue* q = get_pq_from_value(self);
  priority_queue_each(q, &pq_each_helper, NULL);
  return self;
}

#empty? ⇒ Boolean

Returns true if the array is empty, false otherwise.

Returns:



852
853
854
855
856
 
# File 'ext/amp/priority_queue/priority_queue.c', line 852

static
VALUE pq_empty(VALUE self) {
  priority_queue* q = get_pq_from_value(self);
  return priority_queue_empty(q) ? Qtrue : Qfalse;
}

#has_key?(key) ⇒ Boolean

Return false if the key is not in the queue, true otherwise.

q = PriorityQueue.new
(0..10).each do | i | q[i.to_s] = i end
q.has_key("5") #=> true
q.has_key(5)   #=> false

Returns:



740
741
742
743
744
745
746
747
 
# File 'ext/amp/priority_queue/priority_queue.c', line 740

static
VALUE pq_has_key(VALUE self, VALUE object) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");

  VALUE node_pointer = rb_hash_aref(hash, object);
  
  return NIL_P(node_pointer) ? Qfalse : Qtrue;
}

#initialize_copy(orig) ⇒ Object 



881
882
883
884
885
886
887
888
889
 
# File 'ext/amp/priority_queue/priority_queue.c', line 881

static
VALUE pq_initialize_copy(VALUE copy, VALUE orig) {
  if (copy == orig)
    return copy;

  rb_iterate(rb_each, orig, pq_insert_node, copy);
  
  return copy;
}

#inspect ⇒ Object

Returns a string representation of the priority queue.



894
895
896
897
898
899
900
901
902
 
# File 'ext/amp/priority_queue/priority_queue.c', line 894

static
VALUE pq_inspect(VALUE self) {  
  VALUE result = rb_str_new2("<PriorityQueue: ");
  rb_str_concat(result,
      rb_funcall(rb_funcall(self, rb_intern("to_a"), 0),
	rb_intern("inspect"), 0));
  rb_str_concat(result, rb_str_new2(">"));
  return result;
}

#length ⇒ Fixnum

Returns the number of elements of the queue.

q = PriorityQueue.new
q.length #=> 0
q[0] = 1
q.length #=> 1

Returns:



758
759
760
761
762
763
 
# File 'ext/amp/priority_queue/priority_queue.c', line 758

static
VALUE pq_length(VALUE self) {
  priority_queue* q = get_pq_from_value(self);

  return INT2NUM(q->length);
}

#min ⇒ Array

Return the pair [object, priority] with minimal priority or nil when the queue is empty.

q = PriorityQueue.new
q["a"] = 10
q["b"] = 20
q.min          #=> ["a", 10]
q.delete_min   #=> ["a", 10]
q.min          #=> ["b", 20]
q.delete_min   #=> ["b", 20]
q.min          #=> nil

Returns:



532
533
534
535
536
537
538
539
540
541
 
# File 'ext/amp/priority_queue/priority_queue.c', line 532

static
VALUE pq_min(VALUE self) {
  priority_queue* q = get_pq_from_value(self);

  priority_node* n = priority_queue_min(q);
  if (n)
    return rb_ary_new3(2, n->object, n->priority);
  else
    return Qnil;
}

#min_key ⇒ Object

Return the key that has the minimal priority or nil when the queue is empty.

q = PriorityQueue.new
q["a"] = 10
q["b"] = 20
q.min_key      #=> "a"
q.delete_min   #=> ["a", 10]
q.min_key      #=> "b"
q.delete_min   #=> ["b", 20]
q.min_key      #=> nil

Returns:



557
558
559
560
561
562
563
564
565
566
 
# File 'ext/amp/priority_queue/priority_queue.c', line 557

static
VALUE pq_min_key(VALUE self) {
  priority_queue* q = get_pq_from_value(self);

  priority_node* n = priority_queue_min(q);
  if (n)
    return n->object;
  else
    return Qnil;
}

#min_priority ⇒ Object

Return the minimal priority or nil when the queue is empty.

q = PriorityQueue.new
q["a"] = 10
q["b"] = 20
q.min_priority #=> 10
q.delete_min   #=> ["a", 10]
q.min_priority #=> 20
q.delete_min   #=> ["b", 20]
q.min_priority #=> nil



582
583
584
585
586
587
588
589
590
591
 
# File 'ext/amp/priority_queue/priority_queue.c', line 582

static
VALUE pq_min_priority(VALUE self) {
  priority_queue* q = get_pq_from_value(self);

  priority_node* n = priority_queue_min(q);
  if (n)
    return n->priority;
  else
    return Qnil;
}

#priority(object) ⇒ Object

Return the priority of a key or nil if the key is not in the queue.

q = PriorityQueue.new
(0..10).each do | i | q[i.to_s] = i end
q["5"] #=> 5
q[5] #=> nil



717
718
719
720
721
722
723
724
725
726
727
 
# File 'ext/amp/priority_queue/priority_queue.c', line 717

static
VALUE pq_get_priority(VALUE self, VALUE object) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");

  VALUE node_pointer = rb_hash_aref(hash, object);
  
  if (NIL_P(node_pointer))
    return Qnil;
  else
    return (VALUE) (((priority_node*) NUM2ULONG(node_pointer))->priority);
}

#push(object, priority) ⇒ Object

change_priority(key, priority)

push(key, priority)

Set the priority of a key.

q = PriorityQueue.new
q["car"] = 50
q["train"] = 50
q["bike"] = 10
q.min #=> ["bike", 10]
q["car"] = 0
q.min #=> ["car", 0]



691
692
693
694
695
696
697
698
699
700
701
702
703
704
 
# File 'ext/amp/priority_queue/priority_queue.c', line 691

static
VALUE pq_change_priority(VALUE self, VALUE object, VALUE priority) {
  VALUE hash = rb_iv_get(self, "@__node_by_object__");
  priority_queue* q = get_pq_from_value(self);

  VALUE node = rb_hash_aref(hash, object);
  if (NIL_P(node)) {
    pq_push(self, object, priority);
  } else {
    priority_queue_change_priority(q, (priority_node*) NUM2ULONG(node), priority);
  }

  return self;
}

#to_dot ⇒ Object

Print a priority queue as a dot-graph. The output can be fed to dot from the vizgraph suite to create a tree depicting the internal datastructure.

(I’m not proud of this function ;-( )



833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
 
# File 'ext/amp/priority_queue/priority_queue.c', line 833

static
VALUE pq_to_dot(VALUE self) {
  priority_queue* q = get_pq_from_value(self);

  VALUE result_string = rb_str_new2("digraph fibonacci_heap {\n");
  if (q->rootlist) {
    priority_node* n1 = q->rootlist;
    do {    
      pq_node2dot(result_string, n1, 1);
      n1 = n1->right;
    } while(n1 != q->rootlist);
  }
  rb_str_cat2(result_string, "}\n");
  return result_string;
}