1 /*
2 *_________________________________________________________________________*
3 * POEMS: PARALLELIZABLE OPEN SOURCE EFFICIENT MULTIBODY SOFTWARE *
4 * DESCRIPTION: SEE READ-ME *
5 * FILE NAME: SystemProcessor.h *
6 * AUTHORS: See Author List *
7 * GRANTS: See Grants List *
8 * COPYRIGHT: (C) 2005 by Authors as listed in Author's List *
9 * LICENSE: Please see License Agreement *
10 * DOWNLOAD: Free at www.rpi.edu/~anderk5 *
11 * ADMINISTRATOR: Prof. Kurt Anderson *
12 * Computational Dynamics Lab *
13 * Rensselaer Polytechnic Institute *
14 * 110 8th St. Troy NY 12180 *
15 * CONTACT: anderk5@rpi.edu *
16 *_________________________________________________________________________*/
17
18 #ifndef _SYS_PROCESSOR_H_
19 #define _SYS_PROCESSOR_H_
20 #include "poemslist.h"
21 #include "poemstree.h"
22 #include "POEMSChain.h"
23 #include <stdio.h>
24 bool mydebug = 1;
25
26 struct POEMSNode {
27 List<POEMSNode> joints;
28 List<bool> taken;
29 int idNumber;
30 bool visited;
31
~POEMSNodePOEMSNode32 ~POEMSNode(){
33 for(int i = 0; i < taken.GetNumElements(); i++)
34 {
35 delete taken(i);
36 }
37 };
38 };
39
40 //*************************************************************************
41 class SystemProcessor{
42 private:
43 Tree nodes;
44 // List<POEMSNode> forDeletion;
45 List<POEMSChain> headsOfSystems;
46 List<List<int> > ringsInSystem;
47 POEMSNode * findSingleLink(TreeNode * aNode);
48 POEMSChain * AddNewChain(POEMSNode * currentNode);
49 bool setLinkVisited(POEMSNode * firstNode, POEMSNode * secondNode);
50 public:
51 SystemProcessor(void);
52
~SystemProcessor(void)53 ~SystemProcessor(void) {
54 headsOfSystems.DeleteValues();
55 for(int i = 0; i < ringsInSystem.GetNumElements(); i++)
56 {
57 for(int k = 0; k < ringsInSystem(i)->GetNumElements(); i++)
58 {
59 delete (*ringsInSystem(i))(k);
60 }
61 }
62 };
63 void processArray(int** joints, int njoint);
64 List<POEMSChain> * getSystemData();
65 int getNumberOfHeadChains();
66 };
67
68 //*************************************************************************
SystemProcessor(void)69 SystemProcessor::SystemProcessor(void){
70 }
71
72 //*************************************************************************
processArray(int ** joints,int njoint)73 void SystemProcessor::processArray(int** joints, int njoint)
74 {
75 if (mydebug) printf ("what is here njoint: %d \n", njoint);
76 bool * false_var; //holds the value false; needed because a constant cannot be put into a list; the list requires a
77 if (mydebug) cout<< "the size of false_var:"<< sizeof(false_var) <<endl; //reference.
78 for(int i = 0; i < njoint; i++) //go through all the joint..
79 {
80 if (mydebug) printf ("what is here joints: %d \n", joints[i][0]);
81 if(!nodes.Find(joints[i][0])) //if the first node in the pair is not found in the storage tree
82 {
83 POEMSNode * newNode = new POEMSNode; //make a new node
84 // forDeletion.Append(newNode);
85 newNode->idNumber = joints[i][0];//set its ID to the value
86 newNode->visited = false;//set it to be unvisited
87 nodes.Insert(joints[i][0], joints[i][0], (void *) newNode);//and add it to the tree storage structure
88 }
89 if(!nodes.Find(joints[i][1])) //repeat process for the other half of each link
90 {
91 POEMSNode * newNode = new POEMSNode;
92 // forDeletion.Append(newNode);
93 newNode->idNumber = joints[i][1];
94 newNode->visited = false;
95 nodes.Insert(joints[i][1], joints[i][1], (void *) newNode);
96 }
97 POEMSNode * firstNode = (POEMSNode *)nodes.Find(joints[i][0]); //now that we are sure both nodes exist,
98 POEMSNode * secondNode = (POEMSNode *)nodes.Find(joints[i][1]); //we can get both of them out of the tree
99 firstNode->joints.Append(secondNode); //and add the link from the first to the second...
100 false_var = new bool;
101 *false_var = false; //make a new false boolean to note that the link between these two
102 firstNode->taken.Append(false_var); //has not already been taken, and append it to the taken list
103 secondNode->joints.Append(firstNode); //repeat process for link from second node to first
104 false_var = new bool;
105 *false_var = false;
106 secondNode->taken.Append(false_var);
107 }
108
109 TreeNode * temp = nodes.GetRoot(); //get the root node of the node storage tree
110 if (mydebug) cout<< "what is size of TreeNode * temp:"<< sizeof(temp) <<endl;
111 POEMSNode * currentNode;
112
113 do
114 {
115 currentNode = findSingleLink(temp); //find the start of the next available chain go and check!!
116 if (mydebug) cout<< "what is size of currentNode:"<< sizeof(currentNode) <<endl;
117 if(currentNode != NULL)
118 {
119 headsOfSystems.Append(AddNewChain(currentNode));//and add it to the headsOfSystems list of chains
120 }
121 }
122 while(currentNode != NULL); //repeat this until all chains have been added
123 }
124
125 //*************************************************************************
AddNewChain(POEMSNode * currentNode)126 POEMSChain * SystemProcessor::AddNewChain(POEMSNode * currentNode){
127 if(currentNode == NULL) //Termination condition; if the currentNode is null, then return null
128 {
129 return NULL;
130 }
131 int * tmp;
132 POEMSNode * nextNode = NULL; //nextNode stores the proposed next node to add to the chain. this will be checked to make sure no backtracking is occuring before being assigned as the current node.
133 POEMSChain * newChain = new POEMSChain; //make a new POEMSChain object. This will be the object returned
134
135 if(currentNode->joints.GetNumElements() == 0) //if we have no joints from this node, then the whole chain is only one node. Add this node to the chain and return it; mark node as visited for future reference
136 {
137 currentNode->visited = true;
138 tmp = new int;
139 *tmp = currentNode->idNumber;
140 newChain->listOfNodes.Append(tmp);
141 return newChain;
142 }
143 while(currentNode->joints.GetNumElements() <= 2) //we go until we get to a node that branches, or both branches have already been taken both branches can already be taken if a loop with no spurs is found in the input data
144 {
145 currentNode->visited = true;
146 tmp = new int;
147 *tmp = currentNode->idNumber;
148 newChain->listOfNodes.Append(tmp); //append the current node to the chain & mark as visited
149 //cout << "Appending node " << currentNode->idNumber << " to chain" << endl;
150 nextNode = currentNode->joints.GetHeadElement()->value; //the next node is the first or second value stored in the joints array
151 //of the current node. We get the first value...
152 if(!setLinkVisited(currentNode, nextNode)) //...and see if it points back to where we came from. If it does...
153 { //either way, we set this link as visited
154 if(currentNode->joints.GetNumElements() == 1) //if it does, then if that is the only link to this node, we're done with the chain, so append the chain to the list and return the newly created chain
155 {
156 //headsOfSystems.Append(newChain);
157 return newChain;
158 }
159 nextNode = currentNode->joints.GetHeadElement()->next->value;//follow the other link if there is one, so we go down the chain
160 if(!setLinkVisited(currentNode, nextNode)) //mark link as followed, so we know not to backtrack
161 {
162 // headsOfSystems.Append(newChain);
163 return newChain; //This condition, where no branches have occurred but both joints have already
164 //been taken can only occur in a loop with no spurs; add this loop to the
165 //system (currently added as a chain for consistency), and return.
166 }
167 }
168 currentNode = nextNode; //set the current node to be the next node in the chain
169 }
170 currentNode->visited = true;
171 tmp = new int;
172 *tmp = currentNode->idNumber;
173 newChain->listOfNodes.Append(tmp); //append the last node before branch (node shared jointly with branch chains)
174 //re-mark as visited, just to make sure
175 ListElement<POEMSNode> * tempNode = currentNode->joints.GetHeadElement(); //go through all of the joints, one at a time that branch
176 POEMSChain * tempChain = NULL; //temporary variable to hold data
177 while(tempNode != NULL) //when we have followed all joints, stop
178 {
179 if(setLinkVisited(tempNode->value, currentNode)) //dont backtrack, or create closed loops
180 {
181 tempChain = AddNewChain(tempNode->value); //Add a new chain created out of the next node down that link
182 tempChain->parentChain = newChain; //set the parent to be this chain
183 newChain->childChains.Append(tempChain); //append the chain to this chain's list of child chains
184 }
185 tempNode = tempNode->next; //go to process the next chain
186 }
187 //headsOfSystems.Append(newChain); //append this chain to the system list
188 return newChain;
189 }
190
191 //*************************************************************************
findSingleLink(TreeNode * aNode)192 POEMSNode * SystemProcessor::findSingleLink(TreeNode * aNode)
193 //This function takes the root of a search tree containing POEMSNodes and returns a POEMSNode corresponding to the start of a chain in the
194 //system. It finds a node that has not been visited before, and only has one link; this node will be used as the head of the chain.
195 {
196 if(aNode == NULL)
197 {
198 return NULL;
199 }
200 POEMSNode * returnVal = (POEMSNode *)aNode->GetAuxData(); //get the poemsnode data out of the treenode
201 if (mydebug) cout<< "what is size of returnVal:"<< sizeof(returnVal) <<endl;
202 POEMSNode * detectLoneLoops = NULL; //is used to handle a loop that has no protruding chains
203 if(returnVal->visited == false)
204 {
205 detectLoneLoops = returnVal; //if we find any node that has not been visited yet, save it
206 }
207 if(returnVal->joints.GetNumElements() == 1 && returnVal->visited == false)//see if it has one element and hasnt been visited already
208 {
209 return returnVal; //return the node is it meets this criteria
210 }
211 returnVal = findSingleLink(aNode->Left()); //otherwise, check the left subtree
212 if(returnVal == NULL) //and if we find nothing...
213 {
214 returnVal = findSingleLink(aNode->Right()); //check the right subtree
215 }
216 if(returnVal == NULL) //if we could not find any chains
217 {
218 returnVal = detectLoneLoops; //see if we found any nodes at all that havent been processed
219 }
220 if (mydebug) cout<< "value returnVal=====:"<< returnVal <<endl;
221 //currently returnVal is NULL, so no new chain added,means one chain only.
222 return returnVal;//return what we find (will be NULL if no new chains are found)
223
224 }
225
226 //*************************************************************************
setLinkVisited(POEMSNode * firstNode,POEMSNode * secondNode)227 bool SystemProcessor::setLinkVisited(POEMSNode * firstNode, POEMSNode * secondNode)
228 //setLinkVisited sets the joints between these two nodes as visited. If they are already visited, it returns false. Otherwise, it sets
229 //them as visited and returns true. This function is used to see whether a certain path has been taken already in the graph structure.
230 //If it has been, then we need to know so we dont follow it again; this prevents infinite recursion when there is a loop, and prevents
231 //backtracking up a chain that has already been made. The list of booleans denoting if a link has been visited is called 'taken' and is
232 //part of the POEMSNode struct. The list is the same size as the list of pointers to other nodes, and stores the boolean visited/unvisited
233 //value for that particular link. Because each link is represented twice, (once at each node in the link), both of the boolean values need
234 //to be set in the event that the link has to be set as visited.
235 {
236 //cout << "Checking link between nodes " << firstNode->idNumber << " and " << secondNode->idNumber << "... ";
237 ListElement<POEMSNode> * tmp = firstNode->joints.GetHeadElement(); //get the head element of the list of pointers for node 1
238 ListElement<bool> * tmp2 = firstNode->taken.GetHeadElement(); //get the head element of the list of bool isVisited flags for node 1
239 while(tmp->value != NULL || tmp2->value != NULL) //go through untill we reach the end of the lists
240 {
241 if(tmp->value == secondNode) //if we find the link to the other node
242 {
243 if(*(tmp2->value) == true) //if the link has already been visited
244 {
245 //cout << "visited already" << endl;
246 return false; //return false to indicate that the link has been visited before this attempt
247 }
248 else //otherwise, visit it
249 {
250 *tmp2->value = true;
251 }
252 break;
253 }
254 tmp = tmp->next; //go check next link
255 tmp2 = tmp2->next;
256 }
257
258 tmp = secondNode->joints.GetHeadElement(); //now, if the link was unvisited, we need to go set the other node's list such that
259 //it also knows this link is being visited
260 tmp2 = secondNode->taken.GetHeadElement();
261 while(tmp->value != NULL || tmp2->value != NULL) //go through the list
262 {
263 if(tmp->value == firstNode) //if we find the link
264 {
265 if(*(tmp2->value) == true) //and it has already been visited, then signal an error; this shouldnt ever happen
266 {
267 cout << "Error in parsing structure! Should never reach this condition! \n" <<
268 "Record of visited joints out of synch between two adjacent nodes.\n";
269 return false;
270 }
271 else
272 {
273 *tmp2->value = true; //set the appropriate value to true to indicate this link has been visited
274 }
275 break;
276 }
277 tmp = tmp->next;
278 tmp2 = tmp2->next;
279 }
280 //cout << "not visited" << endl;
281 return true; //return true to indicate that this is the first time the link has been visited
282 }
283
284 //*************************************************************************
getSystemData(void)285 List<POEMSChain> * SystemProcessor::getSystemData(void) //Gets the list of POEMSChains that comprise the system. Might eventually only
286 //return chains linked to the reference plane, but currently returns every chain
287 //in the system.
288 {
289 return &headsOfSystems;
290 }
291
292 //*************************************************************************
getNumberOfHeadChains(void)293 int SystemProcessor::getNumberOfHeadChains(void) //This function isnt implemented yet, and might be taken out entirely; this was a holdover
294 //from when I intended to return an array of chain pointers, rather than a list of chains
295 //It will probably be deleted once I finish figuring out exactly what needs to be returned
296 {
297 return 0;
298 }
299 #endif
300