Search Results

Search found 4113 results on 165 pages for 'bsp tree'.

Page 2/165 | < Previous Page | 1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >

• Implementation of Race Game Tree

  - by Mert Toka

  I build a racing game right in OpenGL using Glut, and I'm a bit lost in all the details. First of all, any suggestions as a road map would be more than great. So far what I thought is this: Tree implementation for transformations. Simulated dynamics.(*) Octree implementation for collusion detection. Actual collusion detection.(*) Modelling in Maya and export them as .OBJs. Polishing the game with GLSL or something like that for graphics quality. (*): I am not sure the order of these two. So I started with the simulated dynamics without tree, and it turned out to be a huge chaos for me. Is there any way you can think of such that could help me to build such tree to use in racing game? I thought something like this but I have no idea how to implement it. Reds are static, yellows are dynamic nodes

  Read the article

• Programmatically disclosing a node in af:tree and af:treeTable

  - by Frank Nimphius

  A common developer requirement when working with af:tree or af:treeTable components is to programmatically disclose (expand) a specific node in the tree. If the node to disclose is not a top level node, like a location in a LocationsView -> DepartmentsView -> EmployeesView hierarchy, you need to also disclose the node's parent node hierarchy for application users to see the fully expanded tree node structure. Working on ADF Code Corner sample #101, I wrote the following code lines that show a generic option for disclosing a tree node starting from a handle to the node to disclose. The use case in ADF Coder Corner sample #101 is a drag and drop operation from a table component to a tree to relocate employees to a new department. The tree node that receives the drop is a department node contained in a location. In theory the location could be part of a country and so on to indicate the depth the tree may have. Based on this structure, the code below provides a generic solution to parse the current node parent nodes and its child nodes. The drop event provided a rowKey for the tree node that received the drop. Like in af:table, the tree row key is not of type oracle.jbo.domain.Key but an implementation of java.util.List that contains the row keys. The JUCtrlHierBinding class in the ADF Binding layer that represents the ADF tree binding at runtime provides a method named findNodeByKeyPath that allows you to get a handle to the JUCtrlHierNodeBinding instance that represents a tree node in the binding layer. CollectionModel model = (CollectionModel) your_af_tree_reference.getValue(); JUCtrlHierBinding treeBinding = (JUCtrlHierBinding ) model.getWrappedData(); JUCtrlHierNodeBinding treeDropNode = treeBinding.findNodeByKeyPath(dropRowKey); To disclose the tree node, you need to create a RowKeySet, which you do using the RowKeySetImpl class. Because the RowKeySet replaces any existing row key set in the tree, all other nodes are automatically closed. RowKeySetImpl rksImpl = new RowKeySetImpl(); //the first key to add is the node that received the drop //operation (departments).            rksImpl.add(dropRowKey);    Similar, from the tree binding, the root node can be obtained. The root node is the end of all parent node iteration and therefore important. JUCtrlHierNodeBinding rootNode = treeBinding.getRootNodeBinding(); The following code obtains a reference to the hierarchy of parent nodes until the root node is found. JUCtrlHierNodeBinding dropNodeParent = treeDropNode.getParent(); //walk up the tree to expand all parent nodes while(dropNodeParent != null && dropNodeParent != rootNode){    //add the node's keyPath (remember its a List) to the row key set    rksImpl.add(dropNodeParent.getKeyPath());      dropNodeParent = dropNodeParent.getParent(); } Next, you disclose the drop node immediate child nodes as otherwise all you see is the department node. Its not quite exactly "dinner for one", but the procedure is very similar to the one handling the parent node keys ArrayList<JUCtrlHierNodeBinding> childList = (ArrayList<JUCtrlHierNodeBinding>) treeDropNode.getChildren();                     for(JUCtrlHierNodeBinding nb : childList){   rksImpl.add(nb.getKeyPath()); } Next, the row key set is defined as the disclosed row keys on the tree so when you refresh (PPR) the tree, the new disclosed state shows tree.setDisclosedRowKeys(rksImpl); AdfFacesContext.getCurrentInstance().addPartialTarget(tree.getParent()); The refresh in my use case is on the tree parent component (a layout container), which usually shows the best effect for refreshing the tree component. 

  Read the article

• Find the minimum gap between two numbers in an AVL tree

  - by user1656647

  I have a data structures homework, that in addition to the regular AVL tree functions, I have to add a function that returns the minimum gap between any two numbers in the AVL tree (the nodes in the AVL actually represent numbers.) Lets say we have the numbers (as nodes) 1 5 12 20 23 21 in the AVL tree, the function should return the minimum gap between any two numbers. In this situation it should return "1" which is |20-21| or |21-20|. It should be done in O(1). Tried to think alot about it, and I know there is a trick but just couldn't find it, I have spent hours on this. There was another task which is to find the maximum gap, which is easy, it is the difference between the minimal and maximal number.

  Read the article

• Can a binary tree or tree be always represented in a Database as 1 table and self-referencing?

  - by Jian Lin

  I didn't feel this rule before, but it seems that a binary tree or any tree (each node can have many children but children cannot point back to any parent), then this data structure can be represented as 1 table in a database, with each row having an ID for itself and a parentID that points back to the parent node. That is in fact the classical Employee - Manager diagram: one boss can have many people under him... and each person can have n people under him, etc. This is a tree structure and is represented in database books as a common example as a single table Employee.

  Read the article

• Can a binary tree or tree be always represented in a Database table as 1 table and self-referencing?

  - by Jian Lin

  I didn't feel this rule before, but it seems that a binary tree or any tree (each node can have many children but children cannot point back to any parent), then this data structure can be represented as 1 table in a database, with each row having an ID for itself and a parentID that points back to the parent node. That is in fact the classical Employee - Manager diagram: one boss can have many people under him... and each person under him can have n people under him, etc. This is a tree structure and is represented in database books as a common example as a single table Employee.

  Read the article

• Inorder tree traversal in binary tree in C

  - by srk

  In the below code, I'am creating a binary tree using insert function and trying to display the inserted elements using inorder function which follows the logic of In-order traversal.When I run it, numbers are getting inserted but when I try the inorder function( input 3), the program continues for next input without displaying anything. I guess there might be a logical error.Please help me clear it. Thanks in advance... #include<stdio.h> #include<stdlib.h> int i; typedef struct ll { int data; struct ll *left; struct ll *right; } node; node *root1=NULL; // the root node void insert(node *root,int n) { if(root==NULL) //for the first(root) node { root=(node *)malloc(sizeof(node)); root->data=n; root->right=NULL; root->left=NULL; } else { if(n<(root->data)) { root->left=(node *)malloc(sizeof(node)); insert(root->left,n); } else if(n>(root->data)) { root->right=(node *)malloc(sizeof(node)); insert(root->right,n); } else { root->data=n; } } } void inorder(node *root) { if(root!=NULL) { inorder(root->left); printf("%d ",root->data); inorder(root->right); } } main() { int n,choice=1; while(choice!=0) { printf("Enter choice--- 1 for insert, 3 for inorder and 0 for exit\n"); scanf("%d",&choice); switch(choice) { case 1: printf("Enter number to be inserted\n"); scanf("%d",&n); insert(root1,n); break; case 3: inorder(root1); break; default: break; } } }

  Read the article

• AVL tree in C language

  - by I_S_W

  Hey all; i am currently doing a project that requires the use of AVL trees , the insert function i wrote for the avl does not seem to be working , it works for 3 or 4 nodes at maximum ; i would really appreciate your help The attempt is below enter code here Tree insert(Tree t,char name[80],int num) { if(t==NULL) { t=(Tree)malloc(sizeof(struct node)); if(t!=NULL) { strcpy(t->name,name); t->num=num; t->left=NULL; t->right=NULL; t->height=0; } } else if(strcmp(name,t->name)<0) { t->left=insert(t->left,name,num); if((height(t->left)-height(t->right))==2) if(strcmp(name,t->left->name)<0) { t=s_rotate_left(t);} else{ t=d_rotate_left(t);} } else if(strcmp(name,t-name)0) { t-right=insert(t-right,name,num); if((height(t-right)-height(t-left))==2) if(strcmp(name,t-right-name)0){ t=s_rotate_right(t); } else{ t=d_rotate_right(t);} } t-height=max(height(t-left),height(t-right))+1; return t; }

  Read the article

• New to AVL tree implementation.

  - by nn

  I am writing a sliding window compression algorithm (LZ77) that searches for phrases in a "moving" dictionary. So far I have written a BST where each node is stored in an array and it's index in the array is also the value of the starting position in the window itself. I am now looking at transforming the BST to an AVL tree. I am a little confused at the sample implementations I have seen. Some only appear to store the balance factors whereas others store the height of each tree. Are there any performance advantage/disadvantages of storing the height and/or balance factor for each node? Apologies if this is a very simple question, but I'm still not visualizing how I want to restructure my BST to implement height balancing. Thanks.

  Read the article

• Convert a binary tree to linked list, breadth first, constant storage/destructive

  - by Merlyn Morgan-Graham

  This is not homework, and I don't need to answer it, but now I have become obsessed :) The problem is: Design an algorithm to destructively flatten a binary tree to a linked list, breadth-first. Okay, easy enough. Just build a queue, and do what you have to. That was the warm-up. Now, implement it with constant storage (recursion, if you can figure out an answer using it, is logarithmic storage, not constant). I found a solution to this problem on the Internet about a year back, but now I've forgotten it, and I want to know :) The trick, as far as I remember, involved using the tree to implement the queue, taking advantage of the destructive nature of the algorithm. When you are linking the list, you are also pushing an item into the queue. Each time I try to solve this, I lose nodes (such as each time I link the next node/add to the queue), I require extra storage, or I can't figure out the convoluted method I need to get back to a node that has the pointer I need. Even the link to that original article/post would be useful to me :) Google is giving me no joy. Edit: Jérémie pointed out that there is a fairly simple (and well known answer) if you have a parent pointer. While I now think he is correct about the original solution containing a parent pointer, I really wanted to solve the problem without it :) The refined requirements use this definition for the node: struct tree_node { int value; tree_node* left; tree_node* right; };

  Read the article

• How to functionally generate a tree breadth-first. (With Haskell)

  - by Dennetik

  Say I have the following Haskell tree type, where "State" is a simple wrapper: data Tree a = Branch (State a) [Tree a] | Leaf (State a) deriving (Eq, Show) I also have a function "expand :: Tree a - Tree a" which takes a leaf node, and expands it into a branch, or takes a branch and returns it unaltered. This tree type represents an N-ary search-tree. Searching depth-first is a waste, as the search-space is obviously infinite, as I can easily keep on expanding the search-space with the use of expand on all the tree's leaf nodes, and the chances of accidentally missing the goal-state is huge... thus the only solution is a breadth-first search, implemented pretty decent over here, which will find the solution if it's there. What I want to generate, though, is the tree traversed up to finding the solution. This is a problem because I only know how to do this depth-first, which could be done by simply called the "expand" function again and again upon the first child node... until a goal-state is found. (This would really not generate anything other then a really uncomfortable list.) Could anyone give me any hints on how to do this (or an entire algorithm), or a verdict on whether or not it's possible with a decent complexity? (Or any sources on this, because I found rather few.)

  Read the article

• The "Ruby" way of doing an n-ary tree

  - by sardaukar

  I'm writing a Ruby script and would like to use a n-ary tree data structure. Is there a good implementation that is available as source code? Thanks.

  Read the article

• Spanning-tree setup with incompatible switches

  - by wfaulk

  I have a set of eight HP ProCurve 2910al-48G Ethernet switches at my datacenter that are set up in a star topology with no physical loops. I want to partially mesh the switches for redundancy and manage the loops with a spanning-tree protocol. However, our connection to the datacenter is provided by two uplinks, each to a Cisco 3750. The datacenter's switches are handling the redundant connection using PVST spanning-tree, which is a Cisco-proprietary spanning-tree implementation that my HP switches do not support. It appears that my switches are not participating in the datacenter's spanning-tree domain, but are blindly passing the BPDUs between the two switchports on my side, which enables the datacenter's switches to recognize the loop and put one of the uplinks into the Blocking state. This is somewhat supposition, but I can confirm that, while my switches say that both of the uplink ports are forwarding, only one is passing any real quantity of data. (I am assuming that I cannot get the datacenter to move away from PVST. I don't know that I'd want them to make that significant of a change anyway.) The datacenter has also sent me this output from their switches (which I have expurgated of any identifiable info): 3750G-1#sh spanning-tree vlan nnn VLAN0nnn Spanning tree enabled protocol ieee Root ID Priority 10 Address 00d0.0114.xxxx Cost 4 Port 5 (GigabitEthernet1/0/5) Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Bridge ID Priority 32mmm (priority 32768 sys-id-ext nnn) Address 0018.73d3.yyyy Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Aging Time 300 sec Interface Role Sts Cost Prio.Nbr Type ------------------- ---- --- --------- -------- -------------------------------- Gi1/0/5 Root FWD 4 128.5 P2p Gi1/0/6 Altn BLK 4 128.6 P2p Gi1/0/8 Altn BLK 4 128.8 P2p and: 3750G-2#sh spanning-tree vlan nnn VLAN0nnn Spanning tree enabled protocol ieee Root ID Priority 10 Address 00d0.0114.xxxx Cost 4 Port 6 (GigabitEthernet1/0/6) Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Bridge ID Priority 32mmm (priority 32768 sys-id-ext nnn) Address 000f.f71e.zzzz Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Aging Time 300 sec Interface Role Sts Cost Prio.Nbr Type ------------------- ---- --- --------- -------- -------------------------------- Gi1/0/1 Desg FWD 4 128.1 P2p Gi1/0/5 Altn BLK 4 128.5 P2p Gi1/0/6 Root FWD 4 128.6 P2p Gi1/0/8 Desg FWD 4 128.8 P2p The uplinks to my switches are on Gi1/0/8 on both of their switches. The uplink ports are configured with a single tagged VLAN. I am also using a number of other tagged VLANs in my switch infrastructure. And, to be clear, I am passing the tagged VLAN I'm receiving from the datacenter to other ports on other switches in my infrastructure. My question is: how do I configure my switches so that I can use a spanning tree protocol inside my switch infrastructure without breaking the datacenter's spanning tree that I cannot participate in?

  Read the article

• HPET for x86 BSP (how to build it for WCE8)

  - by Werner Willemsens

  Originally posted on: http://geekswithblogs.net/WernerWillemsens/archive/2014/08/02/157895.aspx"I needed a timer". That is how we started a few blogs ago our series about APIC and ACPI. Well, here it is. HPET (High Precision Event Timer) was introduced by Intel in early 2000 to: Replace old style Intel 8253 (1981!) and 8254 timers Support more accurate timers that could be used for multimedia purposes. Hence Microsoft and Intel sometimes refers to HPET as Multimedia timers. An HPET chip consists of a 64-bit up-counter (main counter) counting at a frequency of at least 10 MHz, and a set of (at least three, up to 256) comparators. These comparators are 32- or 64-bit wide. The HPET is discoverable via ACPI. The HPET circuit in recent Intel platforms is integrated into the SouthBridge chip (e.g. 82801) All HPET timers should support one-shot interrupt programming, while optionally they can support periodic interrupts. In most Intel SouthBridges I worked with, there are three HPET timers. TIMER0 supports both one-shot and periodic mode, while TIMER1 and TIMER2 are one-shot only. Each HPET timer can generate interrupts, both in old-style PIC mode and in APIC mode. However in PIC mode, interrupts cannot freely be chosen. Typically IRQ11 is available and cannot be shared with any other interrupt! Which makes the HPET in PIC mode virtually unusable. In APIC mode however more IRQs are available and can be shared with other interrupt generating devices. (Check the datasheet of your SouthBridge) Because of this higher level of freedom, I created the APIC BSP (see previous posts). The HPET driver code that I present you here uses this APIC mode. Hpet.reg [HKEY_LOCAL_MACHINE\Drivers\BuiltIn\Hpet] "Dll"="Hpet.dll" "Prefix"="HPT" "Order"=dword:10 "IsrDll"="giisr.dll" "IsrHandler"="ISRHandler" "Priority256"=dword:50 Because HPET does not reside on the PCI bus, but can be found through ACPI as a memory mapped device, you don't need to specify the "Class", "SubClass", "ProgIF" and other PCI related registry keys that you typically find for PCI devices. If a driver needs to run its internal thread(s) at a certain priority level, by convention in Windows CE you add the "Priority256" registry key. Through this key you can easily play with the driver's thread priority for better response and timer accuracy. See later. Hpet.cpp (Hpet.dll) This cpp file contains the complete HPET driver code. The file is part of a folder that you typically integrate in your BSP (\src\drivers\Hpet). It is written as sample (example) code, you most likely want to change this code to your specific needs. There are two sets of #define's that I use to control how the driver works. _TRIGGER_EVENT or _TRIGGER_SEMAPHORE: _TRIGGER_EVENT will let your driver trigger a Windows CE Event when the timer expires, _TRIGGER_SEMAPHORE will trigger a Windows CE counting Semaphore. The latter guarantees that no events get lost in case your application cannot always process the triggers fast enough. _TIMER0 or _TIMER2: both timers will trigger an event or semaphore periodically. _TIMER0 will use a periodic HPET timer interrupt, while _TIMER2 will reprogram a one-shot HPET timer after each interrupt. The one-shot approach is interesting if the frequency you wish to generate is not an even multiple of the HPET main counter frequency. The sample code uses an algorithm to generate a more correct frequency over a longer period (by reducing rounding errors). _TIMER1 is not used in the sample source code. HPT_Init() will locate the HPET I/O memory space, setup the HPET counter (_TIMER0 or _TIMER2) and install the Interrupt Service Thread (IST). Upon timer expiration, the IST will run and on its turn will generate a Windows CE Event or Semaphore. In case of _TIMER2 a new one-shot comparator value is calculated and set for the timer. The IRQ of the HPET timers are programmed to IRQ22, but you can choose typically from 20-23. The TIMERn_INT_ROUT_CAP bits in the TIMn_CONF register will tell you what IRQs you can choose from. HPT_IOControl() can be used to set a new HPET counter frequency (actually you configure the counter timeout value in microseconds), start and stop the timer, and request the current HPET counter value. The latter is interesting because the Windows CE QueryPerformanceCounter() and QueryPerformanceFrequency() APIs implement the same functionality, albeit based on other counter implementations. HpetDrvIst() contains the IST code. DWORD WINAPI HpetDrvIst(LPVOID lpArg) { psHpetDeviceContext pHwContext = (psHpetDeviceContext)lpArg; DWORD mainCount = READDWORD(pHwContext->g_hpet_va, GenCapIDReg + 4); // Main Counter Tick period (fempto sec 10E-15) DWORD i = 0; while (1) { WaitForSingleObject(pHwContext->g_isrEvent, INFINITE); #if defined(_TRIGGER_SEMAPHORE) LONG p = 0; BOOL b = ReleaseSemaphore(pHwContext->g_triggerEvent, 1, &p); #elif defined(_TRIGGER_EVENT) BOOL b = SetEvent(pHwContext->g_triggerEvent); #else #pragma error("Unknown TRIGGER") #endif #if defined(_TIMER0) DWORD currentCount = READDWORD(pHwContext->g_hpet_va, MainCounterReg); DWORD comparator = READDWORD(pHwContext->g_hpet_va, Tim0_ComparatorReg + 0); SETBIT(pHwContext->g_hpet_va, GenIntStaReg, 0); // clear interrupt on HPET level InterruptDone(pHwContext->g_sysIntr); // clear interrupt on OS level _LOGMSG(ZONE_INTERRUPT, (L"%s: HpetDrvIst 0 %06d %08X %08X", pHwContext->g_id, i++, currentCount, comparator)); #elif defined(_TIMER2) DWORD currentCount = READDWORD(pHwContext->g_hpet_va, MainCounterReg); DWORD previousComparator = READDWORD(pHwContext->g_hpet_va, Tim2_ComparatorReg + 0); pHwContext->g_counter2.QuadPart += pHwContext->g_comparator.QuadPart; // increment virtual counter (higher accuracy) DWORD comparator = (DWORD)(pHwContext->g_counter2.QuadPart >> 8); // "round" to real value WRITEDWORD(pHwContext->g_hpet_va, Tim2_ComparatorReg + 0, comparator); SETBIT(pHwContext->g_hpet_va, GenIntStaReg, 2); // clear interrupt on HPET level InterruptDone(pHwContext->g_sysIntr); // clear interrupt on OS level _LOGMSG(ZONE_INTERRUPT, (L"%s: HpetDrvIst 2 %06d %08X %08X (%08X)", pHwContext->g_id, i++, currentCount, comparator, comparator - previousComparator)); #else #pragma error("Unknown TIMER") #endif } return 1; } The following figure shows how the HPET hardware interrupt via ISR -> IST is translated in a Windows CE Event or Semaphore by the HPET driver. The Event or Semaphore can be used to trigger a Windows CE application. HpetTest.cpp (HpetTest.exe)This cpp file contains sample source how to use the HPET driver from an application. The file is part of a separate (smart device) VS2013 solution. It contains code to measure the generated Event/Semaphore times by means of GetSystemTime() and QueryPerformanceCounter() and QueryPerformanceFrequency() APIs. HPET evaluation If you scan the internet about HPET, you'll find many remarks about buggy HPET implementations and bad performance. Unfortunately that is true. I tested the HPET driver on an Intel ICH7M SBC (release date 2008). When a HPET timer expires on the ICH7M, an interrupt indeed is generated, but right after you clear the interrupt, a few more unwanted interrupts (too soon!) occur as well. I tested and debugged it for a loooong time, but I couldn't get it to work. I concluded ICH7M's HPET is buggy Intel hardware. I tested the HPET driver successfully on a more recent NM10 SBC (release date 2013). With the NM10 chipset however, I am not fully convinced about the timer's frequency accuracy. In the long run - on average - all is fine, but occasionally I experienced upto 20 microseconds delays (which were immediately compensated on the next interrupt). Of course, this was all measured by software, but I still experienced the occasional delay when both the HPET driver IST thread as the application thread ran at CeSetThreadPriority(1). If it is not the hardware, only the kernel can cause this delay. But Windows CE is an RTOS and I have never experienced such long delays with previous versions of Windows CE. I tested and developed this on WCE8, I am not heavily experienced with it yet. Internet forum threads however mention inaccurate HPET timer implementations as well. At this moment I haven't figured out what is going on here. Useful references: http://www.intel.com/content/dam/www/public/us/en/documents/technical-specifications/software-developers-hpet-spec-1-0a.pdf http://en.wikipedia.org/wiki/High_Precision_Event_Timer http://wiki.osdev.org/HPET Windows CE BSP source file package for HPET in MyBsp Note that this source code is "As Is". It is still under development and I cannot (and never will) guarantee the correctness of the code. Use it as a guide for your own HPET integration.

  Read the article

• What is the difference between an Abstract Syntax Tree and a Concrete Syntax Tree?

  - by Jason Baker

  I've been reading a bit about how interpreters/compilers work, and one area where I'm getting confused is the difference between an AST and a CST. My understanding is that the parser makes a CST, hands it to the semantic analyzer which turns it into an AST. However, my understanding is that the semantic analyzer simply ensures that rules are followed. I don't really understand why it would actually make any changes to make it abstract rather than concrete. Is there something that I'm missing about the semantic analyzer, or is the difference between an AST and CST somewhat artificial?

  Read the article

• Token Suffix Tree Tutorial

  - by Bart J

  Can someone please point to tutorials on - "Token Suffix Trees". Google, gives only links to research papers that are already using them! :( Thanks in advance.

  Read the article

• Deletion procedure for a Binary Search Tree

  - by Metz

  Consider the deletion procedure on a BST, when the node to delete has two children. Let's say i always replace it with the node holding the minimum key in its right subtree. The question is: is this procedure commutative? That is, deleting x and then y has the same result than deleting first y and then x? I think the answer is no, but i can't find a counterexample, nor figure out any valid reasoning. EDIT: Maybe i've got to be clearer. Consider the transplant(node x, node y) procedure: it replace x with y (and its subtree). So, if i want to delete a node (say x) which has two children i replace it with the node holding the minimum key in its right subtree: y = minimum(x.right) transplant(y, y.right) // extracts the minimum (it doesn't have left child) y.right = x.right y.left = x.left transplant(x,y) The question was how to prove the procedure above is not commutative.

  Read the article

• Return parent of node in Binary Tree

  - by user188995

  I'm writing a code to return the parent of any node, but I'm getting stuck. I don't want to use any predefined ADTs. //Assume that nodes are represented by numbers from 1...n where 1=root and even //nos.=left child and odd nos=right child. public int parent(Node node){ if (node % 2 == 0){ if (root.left==node) return root; else return parent(root.left); } //same case for right } But this program is not working and giving wrong results. My basic algorithm is that the program starts from the root checks if it is on left or on the right. If it's the child or if the node that was queried else, recurses it with the child.

  Read the article

• Problems in Binary Search Tree

  - by user2782324

  This is my first ever trial at implementing the BST, and I am unable to get it done. Please help The problem is that When I delete the node if the node is in the right subtree from the root or if its a right child in the left subtree, then it works fine. But if the node is in the left subtree from root and its any left child, then it does not get deleted. Can someone show me what mistake am I doing?? the markedNode here gets allocated to the parent node of the node to be deleted. the minValueNode here gets allocated to a node whose left value child is the smallest value and it will be used to replace the value to be deleted. package DataStructures; class Node { int value; Node rightNode; Node leftNode; } class BST { Node rootOfTree = null; public void insertintoBST(int value) { Node markedNode = rootOfTree; if (rootOfTree == null) { Node newNode = new Node(); newNode.value = value; rootOfTree = newNode; newNode.rightNode = null; newNode.leftNode = null; } else { while (true) { if (value >= markedNode.value) { if (markedNode.rightNode != null) { markedNode = markedNode.rightNode; } else { Node newNode = new Node(); newNode.value = value; markedNode.rightNode = newNode; newNode.rightNode = null; newNode.leftNode = null; break; } } if (value < markedNode.value) { if (markedNode.leftNode != null) { markedNode = markedNode.leftNode; } else { Node newNode = new Node(); newNode.value = value; markedNode.leftNode = newNode; newNode.rightNode = null; newNode.leftNode = null; break; } } } } } public void searchBST(int value) { Node markedNode = rootOfTree; if (rootOfTree == null) { System.out.println("Element Not Found"); } else { while (true) { if (value > markedNode.value) { if (markedNode.rightNode != null) { markedNode = markedNode.rightNode; } else { System.out.println("Element Not Found"); break; } } if (value < markedNode.value) { if (markedNode.leftNode != null) { markedNode = markedNode.leftNode; } else { System.out.println("Element Not Found"); break; } } if (value == markedNode.value) { System.out.println("Element Found"); break; } } } } public void deleteFromBST(int value) { Node markedNode = rootOfTree; Node minValueNode = null; if (rootOfTree == null) { System.out.println("Element Not Found"); return; } if (rootOfTree.value == value) { if (rootOfTree.leftNode == null && rootOfTree.rightNode == null) { rootOfTree = null; return; } else if (rootOfTree.leftNode == null ^ rootOfTree.rightNode == null) { if (rootOfTree.rightNode != null) { rootOfTree = rootOfTree.rightNode; return; } else { rootOfTree = rootOfTree.leftNode; return; } } else { minValueNode = rootOfTree.rightNode; if (minValueNode.leftNode == null) { rootOfTree.rightNode.leftNode = rootOfTree.leftNode; rootOfTree = rootOfTree.rightNode; } else { while (true) { if (minValueNode.leftNode.leftNode != null) { minValueNode = minValueNode.leftNode; } else { break; } } // Minvalue to the left of minvalue node rootOfTree.value = minValueNode.leftNode.value; // The value has been swapped if (minValueNode.leftNode.leftNode == null && minValueNode.leftNode.rightNode == null) { minValueNode.leftNode = null; } else { if (minValueNode.leftNode.leftNode != null) { minValueNode.leftNode = minValueNode.leftNode.leftNode; } else { minValueNode.leftNode = minValueNode.leftNode.rightNode; } // Minvalue deleted } } } } else { while (true) { if (value > markedNode.value) { if (markedNode.rightNode != null) { if (markedNode.rightNode.value == value) { break; } else { markedNode = markedNode.rightNode; } } else { System.out.println("Element Not Found"); return; } } if (value < markedNode.value) { if (markedNode.leftNode != null) { if (markedNode.leftNode.value == value) { break; } else { markedNode = markedNode.leftNode; } } else { System.out.println("Element Not Found"); return; } } } // Parent of the required element found // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// if (markedNode.rightNode != null) { if (markedNode.rightNode.value == value) { if (markedNode.rightNode.rightNode == null && markedNode.rightNode.leftNode == null) { markedNode.rightNode = null; return; } else if (markedNode.rightNode.rightNode == null ^ markedNode.rightNode.leftNode == null) { if (markedNode.rightNode.rightNode != null) { markedNode.rightNode = markedNode.rightNode.rightNode; return; } else { markedNode.rightNode = markedNode.rightNode.leftNode; return; } } else { if (markedNode.rightNode.value == value) { minValueNode = markedNode.rightNode.rightNode; } else { minValueNode = markedNode.leftNode.rightNode; } if (minValueNode.leftNode == null) { // MinNode has no left value markedNode.rightNode = minValueNode; return; } else { while (true) { if (minValueNode.leftNode.leftNode != null) { minValueNode = minValueNode.leftNode; } else { break; } } // Minvalue to the left of minvalue node if (markedNode.leftNode != null) { if (markedNode.leftNode.value == value) { markedNode.leftNode.value = minValueNode.leftNode.value; } } if (markedNode.rightNode != null) { if (markedNode.rightNode.value == value) { markedNode.rightNode.value = minValueNode.leftNode.value; } } // MarkedNode exchanged if (minValueNode.leftNode.leftNode == null && minValueNode.leftNode.rightNode == null) { minValueNode.leftNode = null; } else { if (minValueNode.leftNode.leftNode != null) { minValueNode.leftNode = minValueNode.leftNode.leftNode; } else { minValueNode.leftNode = minValueNode.leftNode.rightNode; } // Minvalue deleted } } } // //////////////////////////////////////////////////////////////////////////////////////////////////////////////// if (markedNode.leftNode != null) { if (markedNode.leftNode.value == value) { if (markedNode.leftNode.rightNode == null && markedNode.leftNode.leftNode == null) { markedNode.leftNode = null; return; } else if (markedNode.leftNode.rightNode == null ^ markedNode.leftNode.leftNode == null) { if (markedNode.leftNode.rightNode != null) { markedNode.leftNode = markedNode.leftNode.rightNode; return; } else { markedNode.leftNode = markedNode.leftNode.leftNode; return; } } else { if (markedNode.rightNode.value == value) { minValueNode = markedNode.rightNode.rightNode; } else { minValueNode = markedNode.leftNode.rightNode; } if (minValueNode.leftNode == null) { // MinNode has no left value markedNode.leftNode = minValueNode; return; } else { while (true) { if (minValueNode.leftNode.leftNode != null) { minValueNode = minValueNode.leftNode; } else { break; } } // Minvalue to the left of minvalue node if (markedNode.leftNode != null) { if (markedNode.leftNode.value == value) { markedNode.leftNode.value = minValueNode.leftNode.value; } } if (markedNode.rightNode != null) { if (markedNode.rightNode.value == value) { markedNode.rightNode.value = minValueNode.leftNode.value; } } // MarkedNode exchanged if (minValueNode.leftNode.leftNode == null && minValueNode.leftNode.rightNode == null) { minValueNode.leftNode = null; } else { if (minValueNode.leftNode.leftNode != null) { minValueNode.leftNode = minValueNode.leftNode.leftNode; } else { minValueNode.leftNode = minValueNode.leftNode.rightNode; } // Minvalue deleted } } } } // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// } } } } } } public class BSTImplementation { public static void main(String[] args) { BST newBst = new BST(); newBst.insertintoBST(19); newBst.insertintoBST(13); newBst.insertintoBST(10); newBst.insertintoBST(20); newBst.insertintoBST(5); newBst.insertintoBST(23); newBst.insertintoBST(28); newBst.insertintoBST(16); newBst.insertintoBST(27); newBst.insertintoBST(9); newBst.insertintoBST(4); newBst.insertintoBST(22); newBst.insertintoBST(17); newBst.insertintoBST(30); newBst.insertintoBST(40); newBst.deleteFromBST(5); newBst.deleteFromBST(4); newBst.deleteFromBST(9); newBst.deleteFromBST(10); newBst.deleteFromBST(13); newBst.deleteFromBST(16); newBst.deleteFromBST(17); newBst.searchBST(5); newBst.searchBST(4); newBst.searchBST(9); newBst.searchBST(10); newBst.searchBST(13); newBst.searchBST(16); newBst.searchBST(17); System.out.println(); newBst.deleteFromBST(20); newBst.deleteFromBST(23); newBst.deleteFromBST(27); newBst.deleteFromBST(28); newBst.deleteFromBST(30); newBst.deleteFromBST(40); newBst.searchBST(20); newBst.searchBST(23); newBst.searchBST(27); newBst.searchBST(28); newBst.searchBST(30); newBst.searchBST(40); } }

  Read the article

• Experience the new Bootloader of CE7 VirtualPC BSP - Display Resolution Override

  - by Kate Moss' Open Space

  The CE 7 (aka. Windows Embedded Compact) provides many new features, a new VirtualPC is one of them and as a replacement of Device Emulator in CE 6.   The bootloader of VPC BSP utilize a new introduced framework in CE7, the BLDR (not the BIOSLOADER!) It provides many rich and advanced feature, I will introduce more detail in my future posts. Today, I am going to introduce a basic usage: setting the display resolution. One of the benefit os using the BLDR is it provides interactive user interface, no DOS enviroment required, so user can change the setting on the console. It is especially useful on VPC: if you are not using Win7, edit a file in VHD could take some effort! In the Boot menu, you can select [5] Display Settings. There are a couples of sub menu allow you to change resolution, bpp and etc. As it is very straight forward, I won't go through each option except to the Option [3] "Change Viewable Display Region". The resolution it provides depends on the BIOS (VPC is a PC compatible device), and the minimum resolution it provides is 640x480. But what if user need smaller resolution or any non-standard resolution for whatever reason, it comes the use of "Change Viewable Display Region". User can use it to create a reduced display region. e.g. 240x320 on 640x480 screen. Also you can alter the platform\virtualpc\src\boot\bldr\config.c to add a non-standard resolution (e.g. 480x272) to displayMode array. Another solution in case of you don't want to rebuilt and replace bootloader is to alter SaveVGAArgs in platform\common\src\x86\common\io\ioctl.c to overwrite cxDisplayScreen and cyDisplayScreen setting to whatever resolution you want.

  Read the article

• Pathfinding and BSP with Box2D

  - by Amplify91

  I'm looking into implementing AI in my 2D side-scrolling platformer, and I'm looking into using algorithms such as A*. For many kinds of pathfinding, we need some sort of grid or systems of nodes or polygon areas. My problem is that I am using Box2d for physics and I am not sure how best to create a structure that my AI can use besides placing individual nodes manually (something I really want to avoid) and using some sort of steering behavior. My level design is tile-based with each tile being about half of the height/width of my main character. The tiles are not all square (some are sloped). I'd like to have a system that can see what the terrain looks like for pathfinding and also keep track of the positions of other actors such as enemies. I'd like to avoid directly placing any nodes into my level design except for possible endpoints or goals. This question is related: How do you do AI path following within a 2d physics engine like farseer/box2d?, but it doesn't specify what kind of structure I could use instead of a list of nodes. I'm looking for some kind of grid or type of BSP that I can query for algorithms like A*.

  Read the article

• Problem with building tree bottom up

  - by Esmond

  Hi, I have problems building a binary tree from the bottom up. THe input of the tree would be internal nodes of the trees with the children of this node being the leaves of the eventual tree. So initially if the tree is empty the root would be the first internal node. Afterwards, The next internal node to be added would be the new root(NR), with the old root(OR) being one of the child of NR. And so on. The problem i have is that whenever i add a NR, the children of the OR seems to be lost when i do a inOrder traversal. This is proven to be the case when i do a getSize() call which returns the same number of nodes before and after addNode(Tree,Node) Any help with resolving this problem is appreciated edited with the inclusion of node class code. both tree and node classes have the addChild methods because i'm not very sure where to put them for it to be appropriated. any comments on this would be appreciated too. The code is as follows: import java.util.*; public class Tree { Node root; int size; public Tree() { root = null; } public Tree(Node root) { this.root = root; } public static void setChild(Node parent, Node child, double weight) throws ItemNotFoundException { if (parent.child1 != null && parent.child2 != null) { throw new ItemNotFoundException("This Node already has 2 children"); } else if (parent.child1 != null) { parent.child2 = child; child.parent = parent; parent.c2Weight = weight; } else { parent.child1 = child; child.parent = parent; parent.c1Weight = weight; } } public static void setChild1(Node parent, Node child) { parent.child1 = child; child.parent = parent; } public static void setChild2(Node parent, Node child) { parent.child2 = child; child.parent = parent; } public static Tree addNode(Tree tree, Node node) throws ItemNotFoundException { Tree tree1; if (tree.root == null) { tree.root = node; } else if (tree.root.getSeq().equals(node.getChild1().getSeq()) || tree.root.getSeq().equals(node.getChild2().getSeq())) { Node oldRoot = tree.root; oldRoot.setParent(node); tree.root = node; } else { //form a disjoint tree and merge the 2 trees tree1 = new Tree(node); tree = mergeTree(tree, tree1); } System.out.print("addNode2 = "); if(tree.root != null ) { Tree.inOrder(tree.root); } System.out.println(); return tree; } public static Tree mergeTree(Tree tree, Tree tree1) { String root = "root"; Node node = new Node(root); tree.root.setParent(node); tree1.root.setParent(node); tree.root = node; return tree; } public static int getSize(Node root) { if (root != null) { return 1 + getSize(root.child1) + getSize(root.child2); } else { return 0; } } public static boolean isEmpty(Tree Tree) { return Tree.root == null; } public static void inOrder(Node root) { if (root != null) { inOrder(root.child1); System.out.print(root.sequence + " "); inOrder(root.child2); } } } public class Node { Node child1; Node child2; Node parent; double c1Weight; double c2Weight; String sequence; boolean isInternal; public Node(String seq) { sequence = seq; child1 = null; c1Weight = 0; child2 = null; c2Weight = 0; parent = null; isInternal = false; } public boolean hasChild() { if (this.child1 == null && this.child2 == null) { this.isInternal = false; return isInternal; } else { this.isInternal = true; return isInternal; } } public String getSeq() throws ItemNotFoundException { if (this.sequence == null) { throw new ItemNotFoundException("No such node"); } else { return this.sequence; } } public void setChild(Node child, double weight) throws ItemNotFoundException { if (this.child1 != null && this.child2 != null) { throw new ItemNotFoundException("This Node already has 2 children"); } else if (this.child1 != null) { this.child2 = child; this.c2Weight = weight; } else { this.child1 = child; this.c1Weight = weight; } } public static void setChild1(Node parent, Node child) { parent.child1 = child; child.parent = parent; } public static void setChild2(Node parent, Node child) { parent.child2 = child; child.parent = parent; } public void setParent(Node parent){ this.parent = parent; } public Node getParent() throws ItemNotFoundException { if (this.parent == null) { throw new ItemNotFoundException("This Node has no parent"); } else { return this.parent; } } public Node getChild1() throws ItemNotFoundException { if (this.child1 == null) { throw new ItemNotFoundException("There is no child1"); } else { return this.child1; } } public Node getChild2() throws ItemNotFoundException { if (this.child2 == null) { throw new ItemNotFoundException("There is no child2"); } else { return this.child2; } } }

  Read the article

• Behaviour tree code example?

  - by jokoon

  http://altdevblogaday.org/2011/02/24/introduction-to-behavior-trees/ Obviously the most interesting article I found on this website. What do you think about it ? It lacks some code example, don't you know any ? I also read that state machines are not very flexible compared to behaviour trees... On top of that I'm not sure if there is a true link between state machines and the state pattern... is there ?

  Read the article

• How to procedurally (create) grow an artistic (2D) tree in real-time (L-System?).

  - by lalan

  Recently I programmed an L-system module, It got me interested further. I am a Plants vs Zombies junkie as well, really liked the concept of Tree of Wisdom. Would love to create similar procedural art just for fun and learn more. Question: How should I approach the process of creating an artistic tree (2d perhaps with fixed camera/perspective) dynamically? Ideally I would like to start with a plant (only a stem with a leaf) and grow it dynamically using some influence (input/user action) over its structure. These influences may result in different type of branching, curves in branches, its spread, location of fruits, color of flowers, etc. Want it to be really full of life/spirit. :) Plants vs Zombies: Tree of wisdom It would be great to dynamically grow a similar tree, but with lot more variation and animations happening. My Background: Student / Programmer, have used few game engines (Ogre3d, cocos2d, unity). Haven't really programmed directly using openGL, trying to fix that :). I am ready to spend considerable time, Please let me know about the APIs? and how would an expert like you would take on this problem? Why 2D? I think it's easier to solve the problem only considering 2 dimensions. Artistic inspirations: Only the tree, with fruits and leaves, without the shrubs at the bottom The large tree (visible branches, green leaves, flowers, fruits, etc) on the left, behind monkey. PixelJunk's Eden (Art style inspiration). Procedurally Generated Apple Tree using Fractals Please let me know if it was easy for you to understand the question, I may elaborate further. I hope a discussion of various approach would be helpful for everyone. You guys are awesome.

  Read the article

• Upgrade tree to 1.6?

  - by Pureferret

  I'm trying to upgrade my version of tree to 1.6 on ubuntu 12.04. I've d'loaded, ran make and make install in the terminal using the sudo command. ~/tree-1.6.0$ sudo make make: Nothing to be done for `all'. I've already run sudo make here ~/tree-1.6.0$ sudo make install install -d /usr/bin install -d /usr/man/man1 if [ -e tree ]; then \ install -s tree /usr/bin/tree; \ fi install doc/tree.1 /usr/man/man1/tree.1 What's this output though? It's not updated. I've checked the man page, and -du doesn't work. How am I supposed to update tree if not via the terminal?

  Read the article

• Configure spanning tree from HP to Cisco hardware

  - by Tim Brigham

  I have three switches I'd like to configure in a loop - a Cisco stack (3750s) and two HP 2900 series. Each is connected to the next with a 10 gig backplane of one form or another. How do I configure the spanning tree on these systems to make this function correctly? From the documents I've looked at it looks like I need to set both sets of hardware to use MST mode but I'm not sure past that point. The trunking, etc is all set up as needed. HP Switch 1 A4 connected to Cisco 1/0/1. HP Switch 2 B2 connected to Cisco 2/0/1. HP Switch 1 A2 connected to HP Switch 2 A1. HP Switch 1 show spanning-tree Multiple Spanning Tree (MST) Information STP Enabled : Yes Force Version : MSTP-operation IST Mapped VLANs : 1-4094 Switch MAC Address : 0021f7-126580 Switch Priority : 32768 Max Age : 20 Max Hops : 20 Forward Delay : 15 Topology Change Count : 352,485 Time Since Last Change : 2 secs CST Root MAC Address : 0018ba-c74268 CST Root Priority : 1 CST Root Path Cost : 200000 CST Root Port : 1 IST Regional Root MAC Address : 0021f7-126580 IST Regional Root Priority : 32768 IST Regional Root Path Cost : 0 IST Remaining Hops : 20 Root Guard Ports : TCN Guard Ports : BPDU Protected Ports : BPDU Filtered Ports : PVST Protected Ports : PVST Filtered Ports : | Prio | Designated Hello Port Type | Cost rity State | Bridge Time PtP Edge ----- --------- + --------- ---- ---------- + ------------- ---- --- ---- ... A1 | Auto 128 Disabled | A2 10GbE-CX4 | 2000 128 Forwarding | 0021f7-126580 2 Yes No A3 10GbE-CX4 | Auto 128 Disabled | A4 10GbE-SR | 2000 128 Forwarding | 0021f7-126580 2 Yes No HP Switch 2 show spanning-tree Multiple Spanning Tree (MST) Information STP Enabled : Yes Force Version : MSTP-operation IST Mapped VLANs : 1-4094 Switch MAC Address : 0024a8-cd6000 Switch Priority : 32768 Max Age : 20 Max Hops : 20 Forward Delay : 15 Topology Change Count : 19,623 Time Since Last Change : 32 secs CST Root MAC Address : 0018ba-c74268 CST Root Priority : 1 CST Root Path Cost : 202000 CST Root Port : A1 IST Regional Root MAC Address : 0024a8-cd6000 IST Regional Root Priority : 32768 IST Regional Root Path Cost : 0 IST Remaining Hops : 20 Root Guard Ports : TCN Guard Ports : BPDU Protected Ports : BPDU Filtered Ports : PVST Protected Ports : PVST Filtered Ports : | Prio | Designated Hello Port Type | Cost rity State | Bridge Time PtP Edge ----- --------- + --------- ---- ---------- + ------------- ---- --- ---- ... A1 10GbE-CX4 | 2000 128 Forwarding | 0021f7-126580 2 Yes No A2 10GbE-CX4 | Auto 128 Disabled | B1 SFP+SR | 2000 128 Blocking | a44c11-a67c80 2 Yes No B2 | Auto 128 Disabled | Cisco Stack 1 show spanning-tree ... (additional VLANs) VLAN0100 Spanning tree enabled protocol ieee Root ID Priority 1 Address 0018.bac7.426e Cost 2 Port 107 (TenGigabitEthernet2/1/1) Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Bridge ID Priority 32868 (priority 32768 sys-id-ext 100) Address a44c.11a6.7c80 Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Aging Time 300 sec Interface Role Sts Cost Prio.Nbr Type ------------------- ---- --- --------- -------- -------------------------------- Te1/1/1 Desg FWD 2 128.53 P2p Te2/1/1 Root FWD 2 128.107 P2p

  Read the article

< Previous Page | 1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >