An ND array in a 1D array

I want to represent a binary tree, quad tree, oct tree etc. as one generic tree structure that can be used for any.

I've got a 1D array, that holds the children of a tree data structure.
The tree has the number of dimensions associated with it.

The number of children it has is:2^Dimensions since i'm divining things in two, for each dimension.

What i'm doing with the tree is dividing up an ND space into equil parts. i.e. for 2D space i'd need 4 chidren etc.
The trouble i'm having is when i come to work out the upper and lower bounds of each child (given the upper and lower bounds of the parent).

I need a way of knowing, for a given dimension (e.g. X,Y,Z...) in a given child (indexed in trhe 1D array), what the upper and lower bounds would be for this child

Thanks for any help, i'm really stuck with this and i need a solution pretty soon.

Sorry for the dodgy explanation, here's what i did with 3 dimensions, which may or may not help:

Code:

---

for(int i=0;i<2;i++)
          {
                  for(int j=0;j<2;j++)
                  {
                          for(int k=0;k<2;k++)
                          {
                                 
                                  //Setup boundaries
                          m_pChildren[i][j][k]->m_pLowBounds[0] = (byte)(m_pLowBounds[0] + i * ((m_pHighBounds[0] - m_pLowBounds[0])/2.0f));
                          m_pChildren[i][j][k]->m_pHighBounds[0] = (byte)(m_pLowBounds[0] + (1+i) * ((m_pHighBounds[0] - m_pLowBounds[0])/2.0f));
                                 
                          m_pChildren[i][j][k]->m_pLowBounds[1] = (byte)(m_pLowBounds[1] + (j * ((m_pHighBounds[1] - m_pLowBounds[1])/2.0f)));
                          m_pChildren[i][j][k]->m_pHighBounds[1] = (byte)(m_pLowBounds[1] + (1+j) * ((m_pHighBounds[1] - m_pLowBounds[1])/2.0f));
                                 
                          m_pChildren[i][j][k]->m_pLowBounds[2] = (byte)(m_pLowBounds[2] + k * ((m_pHighBounds[2] - m_pLowBounds[2])/2.0f));
                          m_pChildren[i][j][k]->m_pHighBounds[2] = (byte)(m_pLowBounds[2] + (1+k) * ((m_pHighBounds[2] - m_pLowBounds[2])/2.0f));
                          }
                  }
          }

---

Cracked it!
Basically i recursivly split the 1D array, remember whether i chose the left or the right each time, that dictates which branch i'm going down in terms of upper and lower bounds.

Code:

---

for(UINT i=0;i < (UINT)(1 << m_iDimensions);i++)
        {
                m_pChildren[i] = new CColourSpaceTree(m_iDepth+1,m_iDimensions);
               
                //Recursivly divide the 1D array, remembering which side we chose each time
                UINT Low = 0;
                UINT High = 1<<m_iDimensions;
                UINT Mid;
                UINT LowValue;
               
                for(UINT j=0;j<m_iDimensions;j++)
                {
                        Mid = ((High-Low)>>1)+Low;
                        if(i <= Mid)
                        {
                                LowValue = 0;
                                High = Mid;
                        }
                        else
                        {
                                LowValue = 1;
                                Low = Mid;
                        }
                    m_pChildren[i]->m_pLowBounds[j] = m_pLowBounds[j] + LowValue * ((m_pHighBounds[j] - m_pLowBounds[j])/2.0f);
                    m_pChildren[i]->m_pHighBounds[j] = m_pLowBounds[j] + (LowValue + 1) * ((m_pHighBounds[j] - m_pLowBounds[j])/2.0f);
 
                        m_pChildren[i]->m_pParent = this;
                }
        }

---

Hmm, doesn't quite work, if anyone can see what i'm doing wrong, or can provide an answer i'd greatly appreciate it.

One thing you could do is to use a trick with templates, in recursion

template <int DIM,int D>

where DIM is the dimension count and D is the current dimension. In the function you call itself with the template parameters <DIM, D-1>. Make sure the function inlines, and Low, High and Mid will be calculated at compiletime. Then have partial template specialization (this requires a compiler that can do this, if you have msvc6 then theres a tecnique to this anyway which I have posted in the c++ forum, just search for partial template specialisation) with parameters <DIM, 0> to terminate the recursion.
Btw,
Mid = ((High-Low)>>1)+Low;
is the same as
Mid = ((High+Low)>>1);

That's a very neat idea, thanks.

I managed to solve the problem anyway though. I don't think i'll use that template method this time since i want to be able to vary high and low on the top level tree, plus i don't have long until this is due in.

Definatly something to think about for another time though. :thumb::thumb: