开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
b_queue.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：3k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

b_queue.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  b_queue.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_BQUEUE_H
  14. #define LEDA_BQUEUE_H
  16. //------------------------------------------------------------------------------
  17. // bounded queues
  18. //------------------------------------------------------------------------------
  20. #include <LEDA/basic.h>
  22. /*{Manpage {b_queue} {E} {Bounded Queues}}*/
  24. template<class E> 
  26. class b_queue  
  27. {
  28. /*{Mdefinition
  29. An instance $Q$ of the parameterized data type name is a queue
  30. (see section ref{Queues}) of bounded size.}*/
  33. E* first;     // first element of array
  34. E* stop;      // one position behind last element of array
  35. E* start;     // current start of queue (wraps around)
  36. E* end;       // one position behind end of queue (wraps around)
  38. public:
  40. /*{Mcreation Q}*/
  43. b_queue(int n) 
  44. {
  45. #if !defined(LEDA_CHECKING_OFF)
  46.   if (n<1) error_handler(88,"_b_queue: bad size");
  47. #endif
  48.   first = new E[n];
  49.   if (first==0) error_handler(88,"_b_queue: out of memory");
  50.   stop  = first+n;
  51.   start = end = first; 
  52. }
  54. /*{Mcreate creates an instance var of type name that can hold up to $n$ 
  55.            elements.  var is initialized with the empty queue.}*/
  58. virtual ~b_queue() { delete [] first; }
  60. /*{Moperations 2 5}*/
  62. E top() const
  63. {
  64. #if !defined(LEDA_CHECKING_OFF)
  65.   if (start==end) error_handler(88, "_b_queue empty");
  66. #endif
  67.   return *start;
  68. }
  70. /*{Mop  returns the front element of var.\
  71.          precond $Q$ is not empty.}*/
  74. E pop()
  75. {
  76. #if !defined(LEDA_CHECKING_OFF)
  77.  if (start==end) error_handler(88, "_b_queue underflow");
  78. #endif
  79.   E x = *start++;
  80.   if (start == stop) start = first;
  81.   return x;
  82. }
  84. /*{Mop  deletes and returns the front element of var.\
  85.          precond $Q$ is not empty.}*/
  87. void append(E& x)
  88. { *end++ = x;
  89.   if (end == stop) end = first;
  90. #if !defined(LEDA_CHECKING_OFF)
  91.   if (start==end) error_handler(88, "_b_queue overflow");
  92. #endif
  93. }
  95. /*{Mop   appends $x$ to the rear end of var.\
  96.   precond $Q$.size()$ < n$.}*/
  99. void clear() { start = end = first; }
  100. /*{Mop    makes var the empty queue.}*/
  103. int size() const 
  104. { int s = end-start;
  105.   return (s<0) ?  (stop-first+s) : s;
  106. }
  107. /*{Mop    returns the size of var.}*/
  110. bool empty() const { return (size()==0) ? true : false; }
  111. /*{Mop    returns true if var is empty, false otherwise.}*/
  114. };
  117. /*{Mimplementation
  118. Bounded queues are implemented by circular arrays. All operations take 
  119. time $O(1)$. The space requirement is $O(n)$.}*/
  121. #endif