Class: PenguinQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/penguin_queue/version.rb,
ext/penguin_queue/penguin_queue.c

Defined Under Namespace

Classes: Node

Constant Summary collapse

VERSION = 
"0.1.3"

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Object 



95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'ext/penguin_queue/penguin_queue.c', line 95

VALUE queue_initialize(int argc, VALUE *argv, VALUE self){
  VALUE order;
  QUEUE_PREPARE(self, ptr);
  if(argc == 0)return self;
  rb_scan_args(argc, argv, "1", &order);
  if(order == ID2SYM(id_max)){
    ptr->compare_sgn = -1;
  }else if(order != ID2SYM(id_min)){
    rb_raise(rb_eArgError, "order should be :min or :max");
  }
  return self;
}

Instance Method Details

#<<(value) ⇒ Object 



285
286
287
 
# File 'ext/penguin_queue/penguin_queue.c', line 285

VALUE queue_push(VALUE self, VALUE value){
  return queue_enq_vp(self, value, value);
}

#clear ⇒ Object 



108
109
110
111
112
113
114
 
# File 'ext/penguin_queue/penguin_queue.c', line 108

VALUE queue_clear(VALUE self){
  QUEUE_PREPARE(self, ptr);
  ptr->counter = 0;
  rb_ary_clear(ptr->heap);
  rb_ary_push(ptr->heap, Qnil);
  return self;
}

#delete(node) ⇒ Object 



179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
 
# File 'ext/penguin_queue/penguin_queue.c', line 179

VALUE queue_remove_node(VALUE self, VALUE node){
  int sgn;
  long length;
  QUEUE_DECLARE_PTR(ptr);
  NODE_DECLARE_PTR(nptr);
  if(!rb_obj_is_kind_of(node, node_class))return Qnil;
  QUEUE_GET_PTR(self, ptr);
  NODE_GET_PTR(node, nptr);
  sgn = ptr->compare_sgn;
  length = RARRAY_LEN(ptr->heap);
  if(nptr->index >= length || RARRAY_AREF(ptr->heap, nptr->index) != node)return Qnil;
  RARRAY_PTR_USE(ptr->heap, heap, {
    long cmp;
    VALUE replace_node = rb_ary_pop(ptr->heap);
    NODE_PREPARE(replace_node, rptr);
    if(replace_node == node)return Qnil;
    heap[nptr->index] = replace_node;
    rptr->index = nptr->index;
    cmp = compare(rptr->priority, nptr->priority)*sgn;
    if(!cmp)cmp = compare_id(rptr->id, nptr->id);
    if(cmp > 0){
      queue_down(nptr->queue, replace_node);
    }else{
      queue_up(nptr->queue, replace_node);
    }
  });
  return Qnil;
}

#deq(*args) ⇒ Object 



329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
 
# File 'ext/penguin_queue/penguin_queue.c', line 329

VALUE queue_deq(int argc, VALUE *argv, VALUE self){
  if(argc == 0){
    VALUE node = queue_deq_node(self);
    NODE_DECLARE_PTR(nptr);
    if(node == Qnil)return Qnil;
    NODE_GET_PTR(node, nptr);
    return nptr->value;
  }else{
    VALUE nv, result;
    int i;
    long n, length;
    QUEUE_DECLARE_PTR(ptr);
    rb_scan_args(argc, argv, "1", &nv);
    n = NUM2LONG(nv);
    if(n<0)rb_raise(rb_eArgError, "negative array size");
    QUEUE_GET_PTR(self, ptr);
    length = RARRAY_LEN(ptr->heap)-1;
    if(n>length)n=length;
    result = rb_ary_new_capa(n);
    for(i=0;i<n;i++){
      VALUE node = queue_deq_node(self);
      NODE_PREPARE(node, nptr);
      rb_ary_push(result, nptr->value);
    }
    return result;
  }
}

#deq_with_priority ⇒ Object 



356
357
358
359
360
361
362
 
# File 'ext/penguin_queue/penguin_queue.c', line 356

VALUE queue_deq_with_priority(VALUE self){
  VALUE node = queue_deq_node(self);
  NODE_DECLARE_PTR(nptr);
  if(node == Qnil)return Qnil;
  NODE_GET_PTR(node, nptr);
  return rb_ary_new_from_args(2, nptr->value, nptr->priority);
}

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


368
369
370
371
 
# File 'ext/penguin_queue/penguin_queue.c', line 368

VALUE queue_is_empty(VALUE self){
  QUEUE_PREPARE(self, ptr);
  return RARRAY_LEN(ptr->heap) == 1 ? Qtrue : Qfalse;
}

#enq(*args) ⇒ Object 



275
276
277
278
279
280
281
282
283
284
 
# File 'ext/penguin_queue/penguin_queue.c', line 275

VALUE queue_enq(int argc, VALUE *argv, VALUE self){
  VALUE value, opts, priority, pri  = Qundef;
  if (OPTHASH_GIVEN_P(opts)) {
    ID keyword_ids[] = {id_priority};
    rb_get_kwargs(opts, keyword_ids, 0, 1, &pri);
  }
  rb_scan_args(argc, argv, "1", &value);
  priority = (pri == Qundef) ? value : pri;
  return queue_enq_vp(self, value, priority);
}

#first ⇒ Object 



298
299
300
301
302
303
304
 
# File 'ext/penguin_queue/penguin_queue.c', line 298

VALUE queue_first(VALUE self){
  VALUE node = queue_first_node(self);
  NODE_DECLARE_PTR(nptr);
  if(node == Qnil)return Qnil;
  NODE_GET_PTR(node, nptr);
  return nptr->value;
}

#first_node ⇒ Object 



289
290
291
292
293
294
295
296
297
 
# File 'ext/penguin_queue/penguin_queue.c', line 289

VALUE queue_first_node(VALUE self){
  long length;
  QUEUE_PREPARE(self, ptr);
  length = RARRAY_LEN(ptr->heap);
  if(length == 1)return Qnil;
  RARRAY_PTR_USE(ptr->heap, heap, {
    return heap[1];
  });
}

#first_with_priority ⇒ Object 



305
306
307
308
309
310
311
 
# File 'ext/penguin_queue/penguin_queue.c', line 305

VALUE queue_first_with_priority(VALUE self){
  VALUE node = queue_first_node(self);
  NODE_DECLARE_PTR(nptr);
  if(node == Qnil)return Qnil;
  NODE_GET_PTR(node, nptr);
  return rb_ary_new_from_args(2, nptr->value, nptr->priority);
}

#inspect ⇒ Object 



381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
 
# File 'ext/penguin_queue/penguin_queue.c', line 381

VALUE queue_inspect(VALUE self){
  VALUE str = rb_str_buf_new(0);
  QUEUE_PREPARE(self, ptr);
  rb_str_buf_append(str, rb_class_name(CLASS_OF(self)));
  RB_STR_BUF_CAT(str, "{order: ");
  if(QUEUE_PTR_IS_MIN(ptr)){
    RB_STR_BUF_CAT(str, ":min");
  }else{
    RB_STR_BUF_CAT(str, ":max");
  }
  RB_STR_BUF_CAT(str, ", size: ");
  rb_str_buf_append(str, rb_inspect(queue_size(self)));
  RB_STR_BUF_CAT(str, "}");
  return str;
}

#max? ⇒ Boolean

Returns:

  • (Boolean) 


377
378
379
380
 
# File 'ext/penguin_queue/penguin_queue.c', line 377

VALUE queue_is_max(VALUE self){
  QUEUE_PREPARE(self, ptr);
  return QUEUE_PTR_IS_MIN(ptr) ? Qfalse : Qtrue;
}

#min? ⇒ Boolean

Returns:

  • (Boolean) 


373
374
375
376
 
# File 'ext/penguin_queue/penguin_queue.c', line 373

VALUE queue_is_min(VALUE self){
  QUEUE_PREPARE(self, ptr);
  return QUEUE_PTR_IS_MIN(ptr) ? Qtrue : Qfalse;
}

#peek ⇒ Object 



298
299
300
301
302
303
304
 
# File 'ext/penguin_queue/penguin_queue.c', line 298

VALUE queue_first(VALUE self){
  VALUE node = queue_first_node(self);
  NODE_DECLARE_PTR(nptr);
  if(node == Qnil)return Qnil;
  NODE_GET_PTR(node, nptr);
  return nptr->value;
}

#poll(*args) ⇒ Object 



329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
 
# File 'ext/penguin_queue/penguin_queue.c', line 329

VALUE queue_deq(int argc, VALUE *argv, VALUE self){
  if(argc == 0){
    VALUE node = queue_deq_node(self);
    NODE_DECLARE_PTR(nptr);
    if(node == Qnil)return Qnil;
    NODE_GET_PTR(node, nptr);
    return nptr->value;
  }else{
    VALUE nv, result;
    int i;
    long n, length;
    QUEUE_DECLARE_PTR(ptr);
    rb_scan_args(argc, argv, "1", &nv);
    n = NUM2LONG(nv);
    if(n<0)rb_raise(rb_eArgError, "negative array size");
    QUEUE_GET_PTR(self, ptr);
    length = RARRAY_LEN(ptr->heap)-1;
    if(n>length)n=length;
    result = rb_ary_new_capa(n);
    for(i=0;i<n;i++){
      VALUE node = queue_deq_node(self);
      NODE_PREPARE(node, nptr);
      rb_ary_push(result, nptr->value);
    }
    return result;
  }
}

#pop(*args) ⇒ Object 



329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
 
# File 'ext/penguin_queue/penguin_queue.c', line 329

VALUE queue_deq(int argc, VALUE *argv, VALUE self){
  if(argc == 0){
    VALUE node = queue_deq_node(self);
    NODE_DECLARE_PTR(nptr);
    if(node == Qnil)return Qnil;
    NODE_GET_PTR(node, nptr);
    return nptr->value;
  }else{
    VALUE nv, result;
    int i;
    long n, length;
    QUEUE_DECLARE_PTR(ptr);
    rb_scan_args(argc, argv, "1", &nv);
    n = NUM2LONG(nv);
    if(n<0)rb_raise(rb_eArgError, "negative array size");
    QUEUE_GET_PTR(self, ptr);
    length = RARRAY_LEN(ptr->heap)-1;
    if(n>length)n=length;
    result = rb_ary_new_capa(n);
    for(i=0;i<n;i++){
      VALUE node = queue_deq_node(self);
      NODE_PREPARE(node, nptr);
      rb_ary_push(result, nptr->value);
    }
    return result;
  }
}

#push(*args) ⇒ Object 



275
276
277
278
279
280
281
282
283
284
 
# File 'ext/penguin_queue/penguin_queue.c', line 275

VALUE queue_enq(int argc, VALUE *argv, VALUE self){
  VALUE value, opts, priority, pri  = Qundef;
  if (OPTHASH_GIVEN_P(opts)) {
    ID keyword_ids[] = {id_priority};
    rb_get_kwargs(opts, keyword_ids, 0, 1, &pri);
  }
  rb_scan_args(argc, argv, "1", &value);
  priority = (pri == Qundef) ? value : pri;
  return queue_enq_vp(self, value, priority);
}

#remove(node) ⇒ Object 



179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
 
# File 'ext/penguin_queue/penguin_queue.c', line 179

VALUE queue_remove_node(VALUE self, VALUE node){
  int sgn;
  long length;
  QUEUE_DECLARE_PTR(ptr);
  NODE_DECLARE_PTR(nptr);
  if(!rb_obj_is_kind_of(node, node_class))return Qnil;
  QUEUE_GET_PTR(self, ptr);
  NODE_GET_PTR(node, nptr);
  sgn = ptr->compare_sgn;
  length = RARRAY_LEN(ptr->heap);
  if(nptr->index >= length || RARRAY_AREF(ptr->heap, nptr->index) != node)return Qnil;
  RARRAY_PTR_USE(ptr->heap, heap, {
    long cmp;
    VALUE replace_node = rb_ary_pop(ptr->heap);
    NODE_PREPARE(replace_node, rptr);
    if(replace_node == node)return Qnil;
    heap[nptr->index] = replace_node;
    rptr->index = nptr->index;
    cmp = compare(rptr->priority, nptr->priority)*sgn;
    if(!cmp)cmp = compare_id(rptr->id, nptr->id);
    if(cmp > 0){
      queue_down(nptr->queue, replace_node);
    }else{
      queue_up(nptr->queue, replace_node);
    }
  });
  return Qnil;
}

#shift(*args) ⇒ Object 



329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
 
# File 'ext/penguin_queue/penguin_queue.c', line 329

VALUE queue_deq(int argc, VALUE *argv, VALUE self){
  if(argc == 0){
    VALUE node = queue_deq_node(self);
    NODE_DECLARE_PTR(nptr);
    if(node == Qnil)return Qnil;
    NODE_GET_PTR(node, nptr);
    return nptr->value;
  }else{
    VALUE nv, result;
    int i;
    long n, length;
    QUEUE_DECLARE_PTR(ptr);
    rb_scan_args(argc, argv, "1", &nv);
    n = NUM2LONG(nv);
    if(n<0)rb_raise(rb_eArgError, "negative array size");
    QUEUE_GET_PTR(self, ptr);
    length = RARRAY_LEN(ptr->heap)-1;
    if(n>length)n=length;
    result = rb_ary_new_capa(n);
    for(i=0;i<n;i++){
      VALUE node = queue_deq_node(self);
      NODE_PREPARE(node, nptr);
      rb_ary_push(result, nptr->value);
    }
    return result;
  }
}

#size ⇒ Object 



364
365
366
367
 
# File 'ext/penguin_queue/penguin_queue.c', line 364

VALUE queue_size(VALUE self){
  QUEUE_PREPARE(self, ptr);
  return LONG2FIX(RARRAY_LEN(ptr->heap)-1);
}

#to_s ⇒ Object 



381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
 
# File 'ext/penguin_queue/penguin_queue.c', line 381

VALUE queue_inspect(VALUE self){
  VALUE str = rb_str_buf_new(0);
  QUEUE_PREPARE(self, ptr);
  rb_str_buf_append(str, rb_class_name(CLASS_OF(self)));
  RB_STR_BUF_CAT(str, "{order: ");
  if(QUEUE_PTR_IS_MIN(ptr)){
    RB_STR_BUF_CAT(str, ":min");
  }else{
    RB_STR_BUF_CAT(str, ":max");
  }
  RB_STR_BUF_CAT(str, ", size: ");
  rb_str_buf_append(str, rb_inspect(queue_size(self)));
  RB_STR_BUF_CAT(str, "}");
  return str;
}

#top ⇒ Object 



298
299
300
301
302
303
304
 
# File 'ext/penguin_queue/penguin_queue.c', line 298

VALUE queue_first(VALUE self){
  VALUE node = queue_first_node(self);
  NODE_DECLARE_PTR(nptr);
  if(node == Qnil)return Qnil;
  NODE_GET_PTR(node, nptr);
  return nptr->value;
}

#unshift(*args) ⇒ Object 



275
276
277
278
279
280
281
282
283
284
 
# File 'ext/penguin_queue/penguin_queue.c', line 275

VALUE queue_enq(int argc, VALUE *argv, VALUE self){
  VALUE value, opts, priority, pri  = Qundef;
  if (OPTHASH_GIVEN_P(opts)) {
    ID keyword_ids[] = {id_priority};
    rb_get_kwargs(opts, keyword_ids, 0, 1, &pri);
  }
  rb_scan_args(argc, argv, "1", &value);
  priority = (pri == Qundef) ? value : pri;
  return queue_enq_vp(self, value, priority);
}