diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/ModifiedBulletX/ModifiedBulletX/Collision/CollisionDispatch/UnionFind.cs | 151 |
1 files changed, 0 insertions, 151 deletions
diff --git a/libraries/ModifiedBulletX/ModifiedBulletX/Collision/CollisionDispatch/UnionFind.cs b/libraries/ModifiedBulletX/ModifiedBulletX/Collision/CollisionDispatch/UnionFind.cs deleted file mode 100644 index 3c7daea..0000000 --- a/libraries/ModifiedBulletX/ModifiedBulletX/Collision/CollisionDispatch/UnionFind.cs +++ /dev/null | |||
@@ -1,151 +0,0 @@ | |||
1 | /* | ||
2 | Bullet for XNA Copyright (c) 2003-2007 Vsevolod Klementjev http://www.codeplex.com/xnadevru | ||
3 | Bullet original C++ version Copyright (c) 2003-2007 Erwin Coumans http://bulletphysics.com | ||
4 | |||
5 | This software is provided 'as-is', without any express or implied | ||
6 | warranty. In no event will the authors be held liable for any damages | ||
7 | arising from the use of this software. | ||
8 | |||
9 | Permission is granted to anyone to use this software for any purpose, | ||
10 | including commercial applications, and to alter it and redistribute it | ||
11 | freely, subject to the following restrictions: | ||
12 | |||
13 | 1. The origin of this software must not be misrepresented; you must not | ||
14 | claim that you wrote the original software. If you use this software | ||
15 | in a product, an acknowledgment in the product documentation would be | ||
16 | appreciated but is not required. | ||
17 | 2. Altered source versions must be plainly marked as such, and must not be | ||
18 | misrepresented as being the original software. | ||
19 | 3. This notice may not be removed or altered from any source distribution. | ||
20 | */ | ||
21 | |||
22 | using System; | ||
23 | using System.Collections.Generic; | ||
24 | using System.Text; | ||
25 | |||
26 | namespace XnaDevRu.BulletX | ||
27 | { | ||
28 | public class UnionFind : IDisposable | ||
29 | { | ||
30 | private List<Element> _elements = new List<Element>(); | ||
31 | |||
32 | public int ElementCount | ||
33 | { | ||
34 | get { return _elements.Count; } | ||
35 | } | ||
36 | |||
37 | public void SortIslands() | ||
38 | { | ||
39 | for (int i = 0; i < _elements.Count; i++) | ||
40 | { | ||
41 | _elements[i].ID = Find(i); | ||
42 | _elements[i].Size = i; | ||
43 | } | ||
44 | |||
45 | _elements.Sort(Sort); | ||
46 | } | ||
47 | |||
48 | private static int Sort(Element x, Element y) | ||
49 | { | ||
50 | if (x.ID < y.ID) return -1; | ||
51 | //else if (x.ID > y.ID) return 1; | ||
52 | else return 0; | ||
53 | } | ||
54 | |||
55 | public void Reset(int number) | ||
56 | { | ||
57 | Allocate(number); | ||
58 | |||
59 | for (int i = 0; i < number; i++) | ||
60 | { | ||
61 | Element element = new Element(); | ||
62 | element.ID = i; | ||
63 | element.Size = 1; | ||
64 | _elements.Insert(i, element); | ||
65 | } | ||
66 | } | ||
67 | |||
68 | public bool IsRoot(int index) | ||
69 | { | ||
70 | return (_elements[index].Size == index); | ||
71 | } | ||
72 | |||
73 | public Element this[int index] | ||
74 | { | ||
75 | get { return _elements[index]; } | ||
76 | } | ||
77 | |||
78 | public void Allocate(int number) | ||
79 | { | ||
80 | //Does nothing | ||
81 | _elements = new List<Element>(number); | ||
82 | } | ||
83 | |||
84 | public bool Find(int i, int j) | ||
85 | { | ||
86 | return (Find(i) == Find(j)); | ||
87 | } | ||
88 | |||
89 | public int Find(int i) | ||
90 | { | ||
91 | while (i != _elements[i].ID) | ||
92 | { | ||
93 | //Element element = _elements[i]; | ||
94 | //element.ID = _elements[_elements[i].ID].ID; | ||
95 | _elements[i].ID = _elements[_elements[i].ID].ID; | ||
96 | i = _elements[i].ID; | ||
97 | } | ||
98 | |||
99 | return i; | ||
100 | } | ||
101 | |||
102 | public void Unite(int p, int q) | ||
103 | { | ||
104 | int i = Find(p), j = Find(q); | ||
105 | if (i == j) | ||
106 | return; | ||
107 | |||
108 | //weighted quick union, this keeps the 'trees' balanced, and keeps performance of unite O( log(n) ) | ||
109 | //if (_elements[i].Size < _elements[j].Size) | ||
110 | //{ | ||
111 | // Element element = _elements[i]; | ||
112 | // element.ID = j; | ||
113 | // _elements[i] = element; | ||
114 | |||
115 | // element = _elements[j]; | ||
116 | // element.Size += _elements[i].Size; | ||
117 | // _elements[j] = element; | ||
118 | //} | ||
119 | //else | ||
120 | //{ | ||
121 | // Element element = _elements[j]; | ||
122 | // element.ID = i; | ||
123 | // _elements[j] = element; | ||
124 | |||
125 | // element = _elements[i]; | ||
126 | // element.Size += _elements[j].Size; | ||
127 | // _elements[i] = element; | ||
128 | //} | ||
129 | _elements[i].ID = j; | ||
130 | _elements[j].Size += _elements[i].Size; | ||
131 | } | ||
132 | |||
133 | #region IDisposable Members | ||
134 | |||
135 | public void Dispose() | ||
136 | { | ||
137 | _elements.Clear(); | ||
138 | } | ||
139 | |||
140 | #endregion | ||
141 | } | ||
142 | |||
143 | public class Element | ||
144 | { | ||
145 | private int _id; | ||
146 | private int _size; | ||
147 | |||
148 | public int ID { get { return _id; } set { _id = value; } } | ||
149 | public int Size { get { return _size; } set { _size = value; } } | ||
150 | } | ||
151 | } \ No newline at end of file | ||