gwnavruntime/abstractgraph/blobs/halfsquarematrix.h Source File

halfsquarematrix.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 #pragma once
8 
9 
12 
13 namespace Kaim
14 {
15 
16 template <class T>
17 class HalfSquareMatrix
18 {
19 public:
20  HalfSquareMatrix()
21  : m_buffer(nullptr)
22  , m_bufferSize(0)
23  , m_count(0)
24  {}
25 
26  HalfSquareMatrix(T* buffer, KyUInt32 bufferSize, KyUInt32 count)
27  : m_buffer(buffer)
28  , m_bufferSize(bufferSize)
29  , m_count(count)
30  {}
31 
32  T* GetValue(KyUInt32 rowIdx, KyUInt32 columnIdx) const
33  {
34  if (rowIdx < columnIdx)
35  {
36  KyUInt32 index = GetIndexInHalfMatrix(rowIdx, columnIdx);
37  return &m_buffer[index];
38  }
39  else if (rowIdx > columnIdx)
40  return GetValue(columnIdx, rowIdx); // invert column and row
41  else // if (rowIdx == columnIdx)
42  return nullptr;
43  }
44 
45 public: //internal
46 
47  // rowIdx must be strictly smaller than columnIdx
48  KyUInt32 GetIndexInHalfMatrix(KyUInt32 rowIdx, KyUInt32 columnIdx) const
49  {
50  KY_ASSERT(rowIdx < columnIdx);
51  KyUInt32 count = GetCount();
52  // index = (n*i+j) - (((i+1)^2)-(((i+1)^2)-(i+1))/2), where i is row, j is column, n is number of abstractGraphNodeCount
53  KyUInt32 fullMatrixIdx = count * rowIdx + columnIdx; // n*i+j
54  KyUInt32 rowSizedMatrixLength = rowIdx+1; // i+1
55  KyUInt32 rowSizedMatrixSize = rowSizedMatrixLength*rowSizedMatrixLength; // (i+1)*(i+1)
56  KyUInt32 rowSizedHalfMatrixSize = (rowSizedMatrixSize - rowSizedMatrixLength)/2; // (((i+1)*(i+1))-(i+1))/2
57  KyUInt32 elementToRemoveFromFullMatrix = rowSizedMatrixSize - rowSizedHalfMatrixSize; // (((i+1)*(i+1))-(((i+1)*(i+1))-(i+1))/2)
58  KyUInt32 index = fullMatrixIdx - elementToRemoveFromFullMatrix; // (n*i+j) - (((i+1)*(i+1))-(((i+1)*(i+1))-(i+1))/2)
59  return index;
60  }
61 
62  KyUInt32 GetCount() const
63  {
64  return m_count;
65  // if (m_bufferSize == 0)
66  // return 0;
67  //
68  // // quadratic formula : (1)*n*n + (-1)*n + (-size*2) = 0
69  // // discriminant : 1 - (4 * (-size*2)) //< always positive so there are 2 solutions
70  // // n = (1 +/- sqrt(1-4*(-size*2)))/2*1 //< pickup only the positive solution
71  // KyUInt32 res = (KyUInt32) (1.f + Sqrtf(1.f+8.f*((KyFloat32)m_bufferSize)));
72  // return (res >> 1);
73  }
74 
75  KyUInt32 ComputeBufferSize(KyUInt32 count) const
76  {
77  return ((count*count)-count) / 2;
78  }
79 
80 public:
81  // Here's how index of m_buffer are constructed,
82  // values given into the array are the corresponding index in m_buffer
83  //
84  // +-- Idx, m_count by m_count -----+
85  // | |
86  // V | 0 1 2 3 4 <----------------+
87  // --+------------
88  // 0 | # 0 1 2 3 T
89  // 1 | x # 4 5 6 |
90  // 2 | x x # 7 8 |
91  // 3 | x x x # 9 L___ indices in m_buffer
92  // 4 | x x x x #
93  //
94  // size of this array is (((n*n)-n) / 2) where n is m_count
95  //
96  T* m_buffer;
97  KyUInt32 m_bufferSize;
98  KyUInt32 m_count;
99 };
100 
101 }
102 
std::uint32_t KyUInt32
uint32_t
Definition: types.h:29
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17