3 Replies - 1085 Views - Last Post: 20 May 2016 - 11:37 AM

#1 zerophase  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 88
  • Joined: 07-May 13

Implementing binary tree that can handle long longs?

Posted 19 May 2016 - 09:09 PM

I'm working on some code that parses xml generated by our documentation software, and generates classes for use with Unreal 4. The documentation software has bubbles connecting different dialogues and game concepts with branching paths. So far, paths from each dialogue box only have 2 branches.

How the xml is organized is there's a portion that lists each node in each subsection and the type of node with an IdRef such as:

<Node IdRef="0x0100000100000075" Type="Dialogue">
     <Node IdRef="0x0100000100000096" Type="DialogueFragment"/>
     <Node IdRef="0x010000010000009B" Type="Connection"/>
     <Node IdRef="0x0100000300000196" Type="Connection"/>
     <Node IdRef="0x0100000300000197" Type="DialogueFragment"/>
</Node>



Then each node of type Connection lists, which node goes to which DialogueFragment. So, I'm rebuilding the binary trees from the documentation in C++, so I can print out each dialogue in the appropriate order and eventually generate files from it.

The only snag I've hit is building the binary tree correctly. I figured since each node has to go in a particular spot I'd need to breadth first search(Once I get it working I'll play around with other searches) through the binary tree being built and drop the node off at the appropriate place based on the Connection. The problem I'm having is saving the IdRef to vectors for the current route and visited nodes because they're huge long long numbers. Once I have the data structure down correctly, for the tree I'll rewrite it keeping those long longs as char * or strings.

One big issue I see with this approach is those vectors will have to be huge, if the index represents the source node and the value represents the target node.

Anyone know of any strategies I could for making the visited and route vectors a more reasonable size? How could I go about representing the long longs as ints? (Not all of the numbers are powers of 2)

Is This A Good Question/Topic? 0
  • +

Replies To: Implementing binary tree that can handle long longs?

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5929
  • View blog
  • Posts: 20,274
  • Joined: 05-May 12

Re: Implementing binary tree that can handle long longs?

Posted 20 May 2016 - 04:14 AM

Sounds like a perfect place to make use of a hashing.

But you could just be lazy and use the standard library's std::map that on the surface looks like a hash table, but is usually implemented with a tree.
Was This Post Helpful? 1
  • +
  • -

#3 zerophase  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 88
  • Joined: 07-May 13

Re: Implementing binary tree that can handle long longs?

Posted 20 May 2016 - 11:19 AM

Thanks, have any suggested hash algorithms to consider?

I guess I could rewrite the whole thing to just use a map and find.

By the way can you move this to the help forum. Just realized I posted in general discussion.
Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is offline

  • member icon

Reputation: 5344
  • View blog
  • Posts: 16,679
  • Joined: 25-December 09

Re: Implementing binary tree that can handle long longs?

Posted 20 May 2016 - 11:37 AM

Quote

guess I could rewrite the whole thing to just use a map and find.

But don't forget that there can't be duplicate keys. You may want to consider std::multimap if you want duplicate keys. Also you can create your own hash function to use with std::multimap if you so desire.

Jim
Was This Post Helpful? 2
  • +
  • -

Page 1 of 1