API tools faq
paste
Guest User

Untitled

a guest
Dec 16th, 2011
68
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.50 KB | None | 0 0
raw download clone embed print report
  1. #include "Ordered2DSet.h"
  2.  
  3. Ordered2DSet::Ordered2DSet() {
  4. root =0;
  5. }
  6.  
  7.  
  8. Ordered2DSet::Ordered2DSet(const Ordered2DSet& orig) {
  9. root = new Node;
  10. if (orig.root!= 0)
  11. copy (orig.root, root);
  12. else
  13. root=0;
  14. }
  15. Ordered2DSet::~Ordered2DSet() {
  16. clear_all (root);
  17. root=0;
  18. }
  19. void Ordered2DSet::copy (Ordered2DSet *a, Ordered2DSet *b){
  20. Node *p[2*n+1];
  21.  
  22. if (a !=0){
  23. for (int i=0; i < a->RAmount; i++){
  24. b->massiv[i].key = a->massiv[i].key;
  25. }
  26. if ( (a->children!=0)){
  27. p[0] = new Node;
  28. p[1] = new Node;
  29. }
  30. else{
  31. p[0]=0;
  32. p[1]=0;
  33. }
  34. for(int i=1;i<2*n;i++){
  35. if ((a->RAmount >=i+1) && (a->children!=0))
  36. p[i+1]= new Node;
  37. else p[i+1]=0;
  38. }
  39. b->children = p[0];
  40. for(int i=1;i<2*n+1;i++){
  41. b->massiv[i].p = p[i];
  42. }
  43. if (a->RAmount >= 1)
  44. {
  45. copy (a->children, p[0]);
  46. copy (a->massiv[0].p, p[1]);
  47. }
  48. for(int i=1;i<2*n;i++){
  49. if (a->RAmount >=i+1) copy (a->massiv[i].p, p[i+1]);
  50. }
  51. }
  52. }
  53.  
  54. void Ordered2DSet::Add (const Node key){
  55. bool grow;
  56. BNT u;
  57. Node *bufer_root;
  58. search_add_key (key, root, grow, u);
  59. if (grow == true)
  60. {
  61. bufer_root = root;
  62. root = new Node;
  63. root->children = 0;
  64. for (int i=0;i<2*n+1;i++){
  65. root->massiv[i].p =0;
  66. }
  67. root->RAmount = 1;
  68. root->children = bufer_root;
  69. root->massiv[0] = u;
  70.  
  71. }
  72. }
  73.  
  74. void Ordered2DSet::search_add_key (const Node k, Node *a, bool& grow, BNT& m) {
  75. int i, L, R;
  76. Node *b;
  77. BNT u;
  78. if (a==0){
  79. grow = true;
  80. m.key=k;
  81. m.p =0;
  82. }
  83. else{
  84. L=0;
  85. R=a->RAmount;
  86. while (L<R){
  87. i = (L+R)/2;
  88. if ((bolshe(a->massiv[i].key,k)==0)&&(bolshe(a->massiv[i].key,k)==-1))
  89. L = i+1;
  90. else
  91. R=i;
  92. }
  93. R = R-1;
  94. if ((R>=0) && (bolshe(a->massiv[R].key,k) ==0)){
  95. grow=false;}
  96. else{
  97. if (R==-1){
  98. search_add_key(key,v, a->children, grow, u);
  99. }
  100. else
  101. search_add_key(key,v, a->massiv[R].p, grow, u);
  102. if (grow==true){
  103. if (a->RAmount<2*n){
  104. grow= false;
  105. a->RAmount++;
  106. for (i=a->RAmount-1;i>=R+2;i--)
  107. a->massiv[i] =a->massiv[i-1];
  108. a->massiv[R+1]=u;
  109. }
  110. else{
  111. b=new Node;
  112. b->children=0;
  113. for(int c=0;c<2*n+1;c++){
  114. b->massiv[c].p=0;
  115. }
  116. if (R<=(n-1)){
  117. if (R==(n-1))
  118. m=u;
  119. else{
  120. m=a->massiv[n-1];
  121. for (i=n-1; i>=R+n-1; i--)
  122. a->massiv[i]=a->massiv[i-1];
  123. a->massiv[R+1]=u;
  124. }
  125. for (i=0; i<=n; i++)
  126. b->massiv[i] = a->massiv[i+n];
  127.  
  128. }
  129. else{
  130. R=R-n;
  131. m=a->massiv[n];
  132. for (i=0; i<=R-1; i++)
  133. b->massiv[i] = a->massiv[i+n+1];
  134. b->massiv[R]=u;
  135. for (i=R+1; i<=n-1; i++)
  136. b->massiv[i] = a->massiv[i+n];
  137. }
  138. a->RAmount = n;
  139. b->RAmount = n;
  140. //a->massiv[b->RAmount-1]-> b->massiv[b->RAmount-1]->parent=b;
  141. b->children = m.p;
  142. m.p=b;
  143. }
  144. }
  145. }
  146. }
  147. }
  148.  
  149.  
  150. bool Ordered2DSet::Search (const Point k){
  151. return (search_key (k, root));
  152. }
  153.  
  154. bool Ordered2DSet::search_key (const Point k,const Node *a)const{
  155. int i, L, R;
  156. if (a==0){
  157. return (false);
  158. }
  159. else{
  160. L = 0;
  161. R = a->RAmount;
  162. while (L < R){
  163. i = (L+R)/2;
  164. if ((bolshe(a->massiv[i].key, k)==0)&&(bolshe(a->massiv[i].key, k)==-1))
  165. L = i+1;
  166. else
  167. R = i;
  168. }
  169. R = R-1;
  170. if ((R >= 0) && (bolshe(a->massiv[R].key,k)==0)
  171. return (true);
  172. else
  173. if (R == -1)
  174. return search_key (k,a->children);
  175. else
  176. return search_key (k,a->massiv[R].p);
  177. }
  178. }
  179.  
  180.  
  181. void Ordered2DSet::Delete (const Point k){
  182. bool smallsize;
  183. Node *bufer_root;
  184. delete_key (k, root, smallsize);
  185. if (smallsize==true){
  186. if (root->RAmount == 0){
  187. bufer_root = root;
  188. root = bufer_root->children;
  189. bufer_root=0;
  190. }
  191. }
  192. }
  193.  
  194.  
  195. void Ordered2DSet::delete_key (const Point k, Node *a, bool& smallsize){
  196. int i, L, R;
  197. Node *q;
  198. if (a==0)
  199. smallsize=false;
  200. else{
  201. L=0;
  202. R=a->RAmount;
  203. while (L < R){
  204. i = (L+R)/2;
  205. if (bolshe(a->massiv[i].key, k)==-1)
  206. L = i+1;
  207. else R = i;
  208. }
  209. if (R == 0)
  210. q = a->children;
  211. else
  212. q = a->massiv[R-1].p;
  213. if ((R <= a->RAmount-1) && (bolshe(a->massiv[R].key,k==0)){
  214. if (q==0){
  215. a->RAmount--;
  216. smallsize = (a->RAmount < n);
  217. for (i=R; i<a->RAmount; i++)
  218. a->massiv[i] = a->massiv[i+1];
  219. }
  220. else{
  221. del(R, a, q, smallsize);
  222. if (smallsize==true)
  223. fusion (a, q, R-1, smallsize);
  224. }
  225. }
  226. else{
  227. delete_key (k, q, smallsize);
  228. if (smallsize == true)
  229. fusion (a, q, R-1, smallsize);
  230. }
  231. }
  232. }
  233.  
  234.  
  235. void Ordered2DSet::del (int R, Node *a, Node *q, bool& smallsize){
  236. Node *b;
  237. b = q->massiv[q->RAmount-1].p;
  238. if (b !=0){
  239. del (R, a, b, smallsize);
  240. if (smallsize==true)
  241. fusion (q, b, q->RAmount-1, smallsize);
  242. }
  243. else{
  244. q->massiv[q->RAmount-1].p = a->massiv[R].p;
  245. a->massiv[R] = q->massiv[q->RAmount-1];
  246. q->RAmount--;
  247. smallsize = (q->RAmount < n);
  248. }
  249. }
  250.  
  251.  
  252. void Ordered2DSet::fusion (Node *father, Node *son, int R, bool& smallsize)
  253. {
  254. Node *b;
  255. int i, k, RAb, RAfather;
  256. RAfather = father->RAmount;
  257. if (R < RAfather-1){
  258. R++;
  259. b = father->massiv[R].p;
  260. RAb = b->RAmount;
  261. k = (RAb-n+1)/2;
  262. son->massiv[n-1] = father->massiv[R];
  263. son->massiv[n-1].p = b->children;
  264. if (k > 0){
  265. for (i=0; i <= k-1; i++)
  266. son->massiv[i+n] = b->massiv[i];
  267. father->massiv[R] = b->massiv[k];
  268. father->massiv[R].p = b;
  269. b->children = b->massiv[k].p;
  270. RAb = RAb-k-1;
  271. for (i=0; i < RAb; i++)
  272. b->massiv[i] = b->massiv[i+k+1];
  273. b->RAmount = RAb;
  274. son->RAmount = n-1+(k+1);
  275. smallsize = false;
  276. }
  277. else{
  278. for (i=0; i < n; i++)
  279. son->massiv[i+n] = b->massiv[i];
  280. for (i=R; i < RAfather-1; i++)
  281. father->massiv[i] = father->massiv[i+1];
  282. son->RAmount = 2*n;
  283. father->RAmount--;
  284. smallsize = (father->RAmount < n);
  285. b=0;
  286. }
  287. }
  288. else{
  289. if (R == 0)
  290. b = father->children;
  291. else
  292. b = father->massiv[R-1].p;
  293. RAb = b->RAmount+1;
  294. k = (RAb-n)/2;
  295. if (k > 0){
  296. son->massiv[k] = son->massiv[0];
  297. son->massiv[k-1] = father->massiv[R];
  298. son->massiv[k-1].p = son->children;
  299. RAb = RAb-k-1;
  300. son->children = b->massiv[RAb].p;
  301. father->massiv[R] = b->massiv[RAb];
  302. father->massiv[R].p = son;
  303. b->RAmount--;
  304. son->RAmount = n-1+k;
  305. smallsize = false;
  306. }
  307. else{
  308. b->massiv[RAb-1] = father->massiv[R];
  309. b->massiv[RAb-1].p = son->children;
  310. b->massiv[RAb] = son->massiv[0];
  311. b->RAmount = 2*n;
  312. father->RAmount--;
  313. smallsize = (father->RAmount < n);
  314. son=0;
  315. }
  316. }
  317. }
  318.  
  319.  
  320.  
  321. int Ordered2DSet::Amount() const{
  322. return amount_allkey(root, 0);
  323. }
  324.  
  325.  
  326. int Ordered2DSet::amount_allkey(Node *a,int b)const{
  327. int i;
  328. if (a!=0){
  329. for (i=0; i<a->RAmount; i++)
  330. b++;
  331. b=b+amount_allkey(a->children,0);
  332. for (i=0; i<a->RAmount; i++)
  333. b=b+amount_allkey(a->massiv[i].p,0);
  334. }
  335. return b;
  336. }
  337.  
  338. void Ordered2DSet::Clear (){
  339. clear_all (root);
  340. root=0;
  341.  
  342. }
  343.  
  344.  
  345. void Ordered2DSet::clear_all (Node *a){
  346. Node *p[2*n+1];
  347. if (a!=0){
  348. if (a->RAmount >=1){
  349. p[0] = a->children;
  350. p[1] = a->massiv[0].p;
  351. }
  352. else{
  353. p[0]=0;
  354. p[1]=0;
  355. }
  356. for(int i=1;i<2*n;i++){
  357. if (a->RAmount >= i+1)
  358. p[i+1]=a->massiv[i].p;
  359. else
  360. p[i+1]=0;
  361. }
  362. a=0;
  363. for(int i=0;i<2*n+1;i++) clear_all(p[i]);
  364. }
  365. }
  366.  
  367.  
  368.  
  369.  
  370. void Ordered2DSet::Print (){
  371. print_b_tree (root, 0);
  372. }
  373.  
  374.  
  375. void Ordered2DSet::print_b_tree (Node *a, int level){
  376. int i;
  377. if (a != NULL){
  378. for (i=0; i<level; i++)
  379. cout << "---";
  380. for (i=0; i<a->RAmount; i++)
  381. {
  382. cout << a->massiv[i].key;
  383. if (i != a->RAmount-1)
  384. cout << ", ";
  385. }
  386. cout << endl;
  387. print_b_tree (a->children, level+1);
  388. for (i=0; i<a->RAmount; i++)
  389. print_b_tree (a->massiv[i].p, level+1);
  390. }
  391. }
  392.  
  393.  
  394. ostream& operator<<(ostream& out, const Point& k)
  395. {out<<"(";
  396. out<<k.x;
  397. out<<" , ";
  398. out<<k.y;
  399. out<<")";
  400. return out;
  401. };
  402. istream& operator>>(istream& in, Point& k){
  403. in>>k.x;
  404. in>>k.y;
  405. return in;
  406. };
  407.  
  408. int bolshe(Point a, Point b)
  409. {if(a.x>b.x) return 1;
  410. if(a.x==b.x) {if(a.y>b.y) return 1;if(a.y==b.y) return 0;if(a.y<b.y) return -1;}
  411. if(a.x<b.x) return -1;
  412. };
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!