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

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

数值算法/人工智能

开发平台：

MultiPlatform

int_set.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  int_set.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_INTSET_H
  14. #define LEDA_INTSET_H
  16. //------------------------------------------------------------------------------
  17. /* int_set: integer sets implemented by bit vectors                           */
  18. //------------------------------------------------------------------------------
  20. #include <LEDA/basic.h>
  22. #define SIZE_OF_ULONG  (8 * sizeof(unsigned long))
  24. /*{Manpage {int_set} {} {Integer Sets}}*/
  26. class int_set {
  28. /*{Mdefinition
  29. An instance $S$ of the data type $int_set$ is a subset of a fixed interval
  30. $[a..b]$ of the integers.}*/
  33.   unsigned long*  V;
  34.   int size;
  35.   int low;
  37. public:
  39. /*{Mcreation S }*/
  41. int_set(int a, int b); 
  42. /*{Mcreate creates an instance var of type $int_set$ for elements from 
  43.             $[a..b]$ and initializes it to the empty set.}*/
  45.  int_set(int n); 
  46. /*{Mcreate creates an instance var of type $int_set$ for elements from 
  47.             $[0..n-1]$ and initializes it to the empty set.}*/
  51.  int_set(const int_set&);
  52. ~int_set() { delete V; } 
  56. /*{Moperations 1.8 5 }*/
  58. void insert(int x);
  59. /*{Mop      adds $x$ to var.\
  60.      precond $ale xle b$.}*/
  62. void del(int x);
  63. /*{Mop     deletes $x$ from var.\
  64.             precond $ale xle b$.}*/
  66. int  member(int x) const;
  67. /*{Mop      returns true if $x$ in var, false otherwise.\
  68.      precond $ale xle b$.}*/
  70. void clear();
  71. /*{Mop      makes var the empty set.}*/
  73. int_set& join(const int_set& );
  74. int_set& intersect(const int_set&);
  75. int_set& complement();
  78. int_set& operator=(const int_set& S1);
  79. /*{Mbinop    assignment.}*/
  81. int_set& operator|=(const int_set&);
  82. int_set& operator&=(const int_set&);
  84. int_set  operator|(const int_set& S1);
  85. /*{Mbinop     returns the union of $S$ and $S1$}*/
  87. int_set  operator&(const int_set& S1);
  88. /*{Mbinop     returns the intersection of $S$ and $S1$}*/
  90. int_set  operator~();
  91. /*{Munop     returns the complement of $S$.}*/
  93. };
  95. inline int  int_set::member(int x)  const
  96. { int i = x-low; 
  97.   return V[i/SIZE_OF_ULONG] & (1 << (i%SIZE_OF_ULONG)); 
  98.  }
  100. inline void int_set::insert(int x) 
  101. { int i  =  x-low; 
  102.   V[i/SIZE_OF_ULONG] |= (1 << (i%SIZE_OF_ULONG)); 
  103.  }
  105. inline void int_set::del(int x)    
  106. { int i   = x-low; 
  107.   V[i/SIZE_OF_ULONG] &= ~(1 << (i%SIZE_OF_ULONG)); 
  108.  }
  110. inline int_set& int_set::operator|=(const int_set& s) { return join(s); }
  112. inline int_set& int_set::operator&=(const int_set& s) { return intersect(s); }
  115. /*{Mimplementation
  116. Integer sets are implemented by bit vectors. Operations insert, delete,
  117. member, empty, and size take constant time. clear, intersection, union 
  118. and complement take time $O(b-a+1)$.}*/
  120. #endif