pr_queue_k.h
上传用户:chinafayin
上传日期:2022-04-05
资源大小:153k
文件大小:4k
源码类别:

并行计算

开发平台:

Visual C++

  1. //----------------------------------------------------------------------
  2. // File: pr_queue_k.h
  3. // Programmer: Sunil Arya and David Mount
  4. // Description: Include file for priority queue with k items.
  5. // Last modified: 01/04/05 (Version 1.0)
  6. //----------------------------------------------------------------------
  7. // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
  8. // David Mount.  All Rights Reserved.
  9. // 
  10. // This software and related documentation is part of the Approximate
  11. // Nearest Neighbor Library (ANN).  This software is provided under
  12. // the provisions of the Lesser GNU Public License (LGPL).  See the
  13. // file ../ReadMe.txt for further information.
  14. // 
  15. // The University of Maryland (U.M.) and the authors make no
  16. // representations about the suitability or fitness of this software for
  17. // any purpose.  It is provided "as is" without express or implied
  18. // warranty.
  19. //----------------------------------------------------------------------
  20. // History:
  21. // Revision 0.1  03/04/98
  22. // Initial release
  23. //----------------------------------------------------------------------
  24. #ifndef PR_QUEUE_K_H
  25. #define PR_QUEUE_K_H
  26. #include "../ANNx.h" // all ANN includes
  27. #include "../ANNperf.h" // performance evaluation
  28. //----------------------------------------------------------------------
  29. // Basic types
  30. //----------------------------------------------------------------------
  31. typedef ANNdist PQKkey; // key field is distance
  32. typedef int PQKinfo; // info field is int
  33. //----------------------------------------------------------------------
  34. // Constants
  35. // The NULL key value is used to initialize the priority queue, and
  36. // so it should be larger than any valid distance, so that it will
  37. // be replaced as legal distance values are inserted.  The NULL
  38. // info value must be a nonvalid array index, we use ANN_NULL_IDX,
  39. // which is guaranteed to be negative.
  40. //----------------------------------------------------------------------
  41. const PQKkey PQ_NULL_KEY  =  ANN_DIST_INF; // nonexistent key value
  42. const PQKinfo PQ_NULL_INFO =  ANN_NULL_IDX; // nonexistent info value
  43. //----------------------------------------------------------------------
  44. // ANNmin_k
  45. // An ANNmin_k structure is one which maintains the smallest
  46. // k values (of type PQKkey) and associated information (of type
  47. // PQKinfo).  The special info and key values PQ_NULL_INFO and
  48. // PQ_NULL_KEY means that thise entry is empty.
  49. //
  50. // It is currently implemented using an array with k items.
  51. // Items are stored in increasing sorted order, and insertions
  52. // are made through standard insertion sort.  (This is quite
  53. // inefficient, but current applications call for small values
  54. // of k and relatively few insertions.)
  55. //
  56. // Note that the list contains k+1 entries, but the last entry
  57. // is used as a simple placeholder and is otherwise ignored.
  58. //----------------------------------------------------------------------
  59. class ANNmin_k {
  60. struct mk_node { // node in min_k structure
  61. PQKkey key; // key value
  62. PQKinfo info; // info field (user defined)
  63. };
  64. int k; // max number of keys to store
  65. int n; // number of keys currently active
  66. mk_node *mk; // the list itself
  67. public:
  68. ANNmin_k(int max) // constructor (given max size)
  69. {
  70. n = 0; // initially no items
  71. k = max; // maximum number of items
  72. mk = new mk_node[max+1]; // sorted array of keys
  73. }
  74. ~ANNmin_k() // destructor
  75. { delete [] mk; }
  76. PQKkey ANNmin_key() // return minimum key
  77. { return (n > 0 ? mk[0].key : PQ_NULL_KEY); }
  78. PQKkey max_key() // return maximum key
  79. { return (n == k ? mk[k-1].key : PQ_NULL_KEY); }
  80. PQKkey ith_smallest_key(int i) // ith smallest key (i in [0..n-1])
  81. { return (i < n ? mk[i].key : PQ_NULL_KEY); }
  82. PQKinfo ith_smallest_info(int i) // info for ith smallest (i in [0..n-1])
  83. { return (i < n ? mk[i].info : PQ_NULL_INFO); }
  84. inline void insert( // insert item (inlined for speed)
  85. PQKkey kv, // key value
  86. PQKinfo inf) // item info
  87. {
  88. register int i;
  89. // slide larger values up
  90. for (i = n; i > 0; i--) {
  91. if (mk[i-1].key > kv)
  92. mk[i] = mk[i-1];
  93. else
  94. break;
  95. }
  96. mk[i].key = kv; // store element here
  97. mk[i].info = inf;
  98. if (n < k) n++; // increment number of items
  99. ANN_FLOP(k-i+1) // increment floating ops
  100. }
  101. };
  102. #endif