| [9102] | 1 | ///
|
|---|
| 2 | /// This file is part of ILNumerics Community Edition.
|
|---|
| 3 | ///
|
|---|
| 4 | /// ILNumerics Community Edition - high performance computing for applications.
|
|---|
| 5 | /// Copyright (C) 2006 - 2012 Haymo Kutschbach, http://ilnumerics.net
|
|---|
| 6 | ///
|
|---|
| 7 | /// ILNumerics Community Edition is free software: you can redistribute it and/or modify
|
|---|
| 8 | /// it under the terms of the GNU General Public License version 3 as published by
|
|---|
| 9 | /// the Free Software Foundation.
|
|---|
| 10 | ///
|
|---|
| 11 | /// ILNumerics Community Edition is distributed in the hope that it will be useful,
|
|---|
| 12 | /// but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|---|
| 13 | /// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|---|
| 14 | /// GNU General Public License for more details.
|
|---|
| 15 | ///
|
|---|
| 16 | /// You should have received a copy of the GNU General Public License
|
|---|
| 17 | /// along with ILNumerics Community Edition. See the file License.txt in the root
|
|---|
| 18 | /// of your distribution package. If not, see <http://www.gnu.org/licenses/>.
|
|---|
| 19 | ///
|
|---|
| 20 | /// In addition this software uses the following components and/or licenses:
|
|---|
| 21 | ///
|
|---|
| 22 | /// =================================================================================
|
|---|
| 23 | /// The Open Toolkit Library License
|
|---|
| 24 | ///
|
|---|
| 25 | /// Copyright (c) 2006 - 2009 the Open Toolkit library.
|
|---|
| 26 | ///
|
|---|
| 27 | /// Permission is hereby granted, free of charge, to any person obtaining a copy
|
|---|
| 28 | /// of this software and associated documentation files (the "Software"), to deal
|
|---|
| 29 | /// in the Software without restriction, including without limitation the rights to
|
|---|
| 30 | /// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
|
|---|
| 31 | /// the Software, and to permit persons to whom the Software is furnished to do
|
|---|
| 32 | /// so, subject to the following conditions:
|
|---|
| 33 | ///
|
|---|
| 34 | /// The above copyright notice and this permission notice shall be included in all
|
|---|
| 35 | /// copies or substantial portions of the Software.
|
|---|
| 36 | ///
|
|---|
| 37 | /// =================================================================================
|
|---|
| 38 | ///
|
|---|
| 39 |
|
|---|
| 40 | using System;
|
|---|
| 41 | using System.Collections.Generic;
|
|---|
| 42 | using System.Linq;
|
|---|
| 43 | using System.Text;
|
|---|
| 44 | using keytype = System.Int32;
|
|---|
| 45 |
|
|---|
| 46 | namespace ILNumerics.Data {
|
|---|
| 47 | /// <summary>
|
|---|
| 48 | /// incomplete BTree implementation (it lags of a remove method)
|
|---|
| 49 | /// </summary>
|
|---|
| 50 | /// <typeparam name="T">value element type</typeparam>
|
|---|
| 51 | public class ILBTree<T> {
|
|---|
| 52 |
|
|---|
| 53 | //private static readonly int ORDER = 4; // max number of childs
|
|---|
| 54 | //private static readonly int MAX_KEYS = 3; // uneven ! (order - 1)
|
|---|
| 55 | //private static readonly int MIN_CHILDS = 2;
|
|---|
| 56 | //private static readonly int MIN_KEYS = 1; // uneven ! (order / 2 - 1)
|
|---|
| 57 | private static int m_order = 24;
|
|---|
| 58 | public static int ORDER {
|
|---|
| 59 | get { return m_order; }
|
|---|
| 60 | set {
|
|---|
| 61 | if (value / 2 * 2 != value) {
|
|---|
| 62 | value++;
|
|---|
| 63 | }
|
|---|
| 64 | m_order = value;
|
|---|
| 65 | MAX_KEYS = value -1;
|
|---|
| 66 | MIN_KEYS = value / 2 - 1;
|
|---|
| 67 | }
|
|---|
| 68 | } // max number of childs
|
|---|
| 69 |
|
|---|
| 70 | public static int MAX_KEYS = 15; // uneven ! (order - 1)
|
|---|
| 71 | public static int MIN_KEYS = 7; // uneven ! (order / 2 - 1)
|
|---|
| 72 | public static int DEFAULT_LIST_CAPACITY = 8;
|
|---|
| 73 |
|
|---|
| 74 | private int m_nodeCount = 0;
|
|---|
| 75 | private int m_levelCount = 1;
|
|---|
| 76 |
|
|---|
| 77 | private nodetype m_root;
|
|---|
| 78 |
|
|---|
| 79 | //private class itemtype {
|
|---|
| 80 | // public keytype Key;
|
|---|
| 81 | // public List<T> Values;
|
|---|
| 82 | // //private itemtype () {
|
|---|
| 83 | // // Key = -1;
|
|---|
| 84 | // // Values = new LinkedList<T>();
|
|---|
| 85 | // //}
|
|---|
| 86 | // public itemtype (keytype key, T value) {
|
|---|
| 87 | // Key = key;
|
|---|
| 88 | // Values = new List<T>(8);
|
|---|
| 89 | // Values.Add(value);
|
|---|
| 90 | // }
|
|---|
| 91 | // public override string ToString() {
|
|---|
| 92 | // return String.Format("K:{0} Count:{1}",Key,Values.Count);
|
|---|
| 93 | // }
|
|---|
| 94 | //}
|
|---|
| 95 | private class nodetype {
|
|---|
| 96 | //public itemtype[] Items;
|
|---|
| 97 | public int[] Keys;
|
|---|
| 98 | public List<T>[] Values;
|
|---|
| 99 | public nodetype[] Childs;
|
|---|
| 100 | /// <summary>
|
|---|
| 101 | /// number of keys in the node
|
|---|
| 102 | /// </summary>
|
|---|
| 103 | public int Count;
|
|---|
| 104 |
|
|---|
| 105 | public nodetype() {
|
|---|
| 106 | Count = 0;
|
|---|
| 107 | //Items = new itemtype[ MAX_KEYS ];
|
|---|
| 108 | Keys = new int[MAX_KEYS];
|
|---|
| 109 | Values = new List<T>[MAX_KEYS];
|
|---|
| 110 | Childs = new nodetype[ MAX_KEYS + 1 ];
|
|---|
| 111 | }
|
|---|
| 112 | public override string ToString() {
|
|---|
| 113 | string itemDesc = "---";
|
|---|
| 114 | if (Count > 0) {
|
|---|
| 115 | itemDesc = String.Format("{0} - {1}",Keys[0],Keys[Count-1]);
|
|---|
| 116 | }
|
|---|
| 117 | return String.Format("{0} Items:[{1}]",Count,itemDesc);
|
|---|
| 118 | }
|
|---|
| 119 |
|
|---|
| 120 | }
|
|---|
| 121 |
|
|---|
| 122 | #region constructor
|
|---|
| 123 | public ILBTree() {
|
|---|
| 124 | m_root = new nodetype();
|
|---|
| 125 | m_nodeCount = 1;
|
|---|
| 126 | }
|
|---|
| 127 | #endregion
|
|---|
| 128 |
|
|---|
| 129 | #region public interface
|
|---|
| 130 |
|
|---|
| 131 | public int NodeCount {
|
|---|
| 132 | get { return m_nodeCount; }
|
|---|
| 133 | }
|
|---|
| 134 | public int LevelCount {
|
|---|
| 135 | get { return m_levelCount; }
|
|---|
| 136 | }
|
|---|
| 137 |
|
|---|
| 138 |
|
|---|
| 139 | public void Add(keytype key, T value) {
|
|---|
| 140 | if (m_root.Count >= MAX_KEYS) {
|
|---|
| 141 | nodetype newright = new nodetype();
|
|---|
| 142 | keytype upkey;
|
|---|
| 143 | List<T> upval;
|
|---|
| 144 | SplitNode(m_root,newright, out upkey, out upval);
|
|---|
| 145 | nodetype newRoot = new nodetype();
|
|---|
| 146 | newRoot.Childs[0] = m_root;
|
|---|
| 147 | newRoot.Childs[1] = newright;
|
|---|
| 148 | newRoot.Keys[0] = upkey;
|
|---|
| 149 | newRoot.Values[0] = upval;
|
|---|
| 150 | newRoot.Count = 1;
|
|---|
| 151 | m_root = newRoot;
|
|---|
| 152 | m_nodeCount += 2;
|
|---|
| 153 | m_levelCount++;
|
|---|
| 154 | }
|
|---|
| 155 | AddValue(key, value, m_root);
|
|---|
| 156 | }
|
|---|
| 157 | #endregion
|
|---|
| 158 |
|
|---|
| 159 | #region private helpers
|
|---|
| 160 | /// <summary>
|
|---|
| 161 | /// is the key contained in curNode ?
|
|---|
| 162 | /// </summary>
|
|---|
| 163 | /// <param name="curNode"></param>
|
|---|
| 164 | /// <param name="key"></param>
|
|---|
| 165 | /// <param name="location"></param>
|
|---|
| 166 | /// <returns></returns>
|
|---|
| 167 | private unsafe static bool SearchNode(nodetype curNode, keytype key, ref int location) {
|
|---|
| 168 | int loc = 0, max = curNode.Count; int[] curNodeKeys = curNode.Keys;
|
|---|
| 169 | for (; loc < max; loc++) {
|
|---|
| 170 | int curKey = curNodeKeys[loc];
|
|---|
| 171 | if (curKey == key) {
|
|---|
| 172 | location = loc;
|
|---|
| 173 | return true;
|
|---|
| 174 | } else if (curKey > key) {
|
|---|
| 175 | location = loc;
|
|---|
| 176 | return false;
|
|---|
| 177 | }
|
|---|
| 178 | }
|
|---|
| 179 | location = loc;
|
|---|
| 180 | return false;
|
|---|
| 181 |
|
|---|
| 182 | //int loc = 0, max = curNode.Count;
|
|---|
| 183 | //foreach (keytype curKey in curNode.Keys) {
|
|---|
| 184 | // if (curKey == key) {
|
|---|
| 185 | // location = loc;
|
|---|
| 186 | // return true;
|
|---|
| 187 | // } else if (curKey > key) {
|
|---|
| 188 | // location = loc;
|
|---|
| 189 | // return false;
|
|---|
| 190 | // }
|
|---|
| 191 | // if (++loc >= max) break;
|
|---|
| 192 | //}
|
|---|
| 193 | //location = loc;
|
|---|
| 194 | //return false;
|
|---|
| 195 |
|
|---|
| 196 | //int loc = curNode.Count - 1;
|
|---|
| 197 | //fixed (int* keys = curNode.Keys) {
|
|---|
| 198 | // int* curKey = keys + loc;
|
|---|
| 199 | // do {
|
|---|
| 200 | // if (*curKey == key) {
|
|---|
| 201 | // location = loc;
|
|---|
| 202 | // return true;
|
|---|
| 203 | // } else if (*curKey < key) {
|
|---|
| 204 | // location = ++loc;
|
|---|
| 205 | // return false;
|
|---|
| 206 | // }
|
|---|
| 207 | // curKey--;
|
|---|
| 208 | // } while (loc --> 0);
|
|---|
| 209 | //}
|
|---|
| 210 | //location = 0;
|
|---|
| 211 | //return false;
|
|---|
| 212 | }
|
|---|
| 213 | private void AddValue(keytype key, T value, nodetype curNode) {
|
|---|
| 214 | System.Diagnostics.Debug.Assert(curNode.Count < MAX_KEYS);
|
|---|
| 215 | while (true) {
|
|---|
| 216 | // search node (inlined from func)
|
|---|
| 217 | short max = (short)curNode.Count;
|
|---|
| 218 | short location = 0;
|
|---|
| 219 | int[] curNodeKeys = curNode.Keys;
|
|---|
| 220 | for (; location < max; location++) {
|
|---|
| 221 | int curKey = curNodeKeys[location];
|
|---|
| 222 | if (curKey == key) {
|
|---|
| 223 | curNode.Values[location].Add(value);
|
|---|
| 224 | return;
|
|---|
| 225 | }
|
|---|
| 226 | if (curKey > key) {
|
|---|
| 227 | break;
|
|---|
| 228 | }
|
|---|
| 229 | }
|
|---|
| 230 | nodetype childNode = curNode.Childs[location];
|
|---|
| 231 | if (childNode == null) {
|
|---|
| 232 | // insert right here
|
|---|
| 233 | var newVals = new List<T>(8);
|
|---|
| 234 | newVals.Add(value);
|
|---|
| 235 | InsertItemIntoNode(curNode,key,newVals,location,null);
|
|---|
| 236 | break;
|
|---|
| 237 | } else {
|
|---|
| 238 | // check if the child is filled up allready
|
|---|
| 239 | if (childNode.Count >= MAX_KEYS) {
|
|---|
| 240 | nodetype newRightChild = new nodetype();
|
|---|
| 241 | int upkey;
|
|---|
| 242 | List<T> upval;
|
|---|
| 243 | SplitNode(childNode, newRightChild, out upkey, out upval);
|
|---|
| 244 | m_nodeCount++;
|
|---|
| 245 | InsertItemIntoNode(curNode,upkey, upval, location, newRightChild); // cur node should always have space left!
|
|---|
| 246 | // in which subtree to go?
|
|---|
| 247 | if (key == upkey) {
|
|---|
| 248 | curNode.Values[location].Add(value);
|
|---|
| 249 | return;
|
|---|
| 250 | }
|
|---|
| 251 | if (key > upkey)
|
|---|
| 252 | location++;
|
|---|
| 253 | }
|
|---|
| 254 | //AddValue(key, value, curNode.Childs[location]);
|
|---|
| 255 | curNode = curNode.Childs[location];
|
|---|
| 256 | }
|
|---|
| 257 | }
|
|---|
| 258 | }
|
|---|
| 259 |
|
|---|
| 260 | //private void AddValue(keytype key, T value, nodetype curNode) {
|
|---|
| 261 | // System.Diagnostics.Debug.Assert(curNode.Count < MAX_KEYS);
|
|---|
| 262 | // int location;
|
|---|
| 263 | // if (SearchNode(curNode, key, out location)) {
|
|---|
| 264 | // curNode.Values[location].Add(value);
|
|---|
| 265 | // } else {
|
|---|
| 266 | // nodetype childNode = curNode.Childs[location];
|
|---|
| 267 | // if (childNode == null) {
|
|---|
| 268 | // // insert right here
|
|---|
| 269 | // var newVals = new List<T>(8);
|
|---|
| 270 | // newVals.Add(value);
|
|---|
| 271 | // InsertItemIntoNode(curNode,key,newVals,location,null);
|
|---|
| 272 | // } else {
|
|---|
| 273 | // // check if the child is filled up allready
|
|---|
| 274 | // if (childNode.Count >= MAX_KEYS) {
|
|---|
| 275 | // nodetype newRightChild = new nodetype();
|
|---|
| 276 | // int upkey;
|
|---|
| 277 | // List<T> upval;
|
|---|
| 278 | // SplitNode(childNode, newRightChild, out upkey, out upval);
|
|---|
| 279 | // m_nodeCount++;
|
|---|
| 280 | // InsertItemIntoNode(curNode,upkey, upval, location, newRightChild); // cur node should always have space left!
|
|---|
| 281 | // // in which subtree to go?
|
|---|
| 282 | // if (key == upkey) {
|
|---|
| 283 | // curNode.Values[location].Add(value);
|
|---|
| 284 | // return;
|
|---|
| 285 | // }
|
|---|
| 286 | // if (key > upkey)
|
|---|
| 287 | // location++;
|
|---|
| 288 | // }
|
|---|
| 289 | // AddValue(key, value, curNode.Childs[location]);
|
|---|
| 290 | // }
|
|---|
| 291 | // }
|
|---|
| 292 | //}
|
|---|
| 293 |
|
|---|
| 294 | #region break
|
|---|
| 295 | #endregion
|
|---|
| 296 |
|
|---|
| 297 | //private void AddValue(keytype key, T value, nodetype curNode, ref itemtype upcomingItem, ref nodetype rightchild) {
|
|---|
| 298 | // if (curNode == null) {
|
|---|
| 299 | // // we came from a leaf! let the parent handle the insertion
|
|---|
| 300 | // upcomingItem = new itemtype(key,value);
|
|---|
| 301 | // rightchild = null;
|
|---|
| 302 | // return;
|
|---|
| 303 | // }
|
|---|
| 304 | // System.Diagnostics.Debug.Assert(curNode.Count < MAX_KEYS);
|
|---|
| 305 | // int location;
|
|---|
| 306 | // if (SearchNode(curNode, key, out location)) {
|
|---|
| 307 | // curNode.Items[location].Values.AddFirst(value);
|
|---|
| 308 | // upcomingItem = null;
|
|---|
| 309 | // } else {
|
|---|
| 310 | // nodetype childNode = curNode.Childs[location];
|
|---|
| 311 | // if (childNode.Count >= MAX_KEYS) {
|
|---|
| 312 | // nodetype newRightChild = new nodetype();
|
|---|
| 313 | // itemtype newUpItem;
|
|---|
| 314 | // SplitNode(childNode, newRightChild, out newUpItem);
|
|---|
| 315 | // InsertItemIntoNode(curNode,newUpItem,location,newRightChild); // cur node should always have space left!
|
|---|
| 316 | // // in which subtree to go?
|
|---|
| 317 | // if (key > newUpItem.Key)
|
|---|
| 318 | // location++;
|
|---|
| 319 | // if (key == newUpItem.Key) {
|
|---|
| 320 | // curNode.Items[location].Values.AddFirst(value);
|
|---|
| 321 | // upcomingItem = null;
|
|---|
| 322 | // return;
|
|---|
| 323 | // }
|
|---|
| 324 | // }
|
|---|
| 325 | // // location = index of child/ insertion point
|
|---|
| 326 | // AddValue(key, value, curNode.Childs[location], ref upcomingItem, ref rightchild);
|
|---|
| 327 | // // handle upcoming node
|
|---|
| 328 | // if (upcomingItem != null) {
|
|---|
| 329 | // if (curNode.Count < MAX_KEYS) {
|
|---|
| 330 | // // insert right here
|
|---|
| 331 | // InsertItemIntoNode(curNode, upcomingItem, location, rightchild);
|
|---|
| 332 | // upcomingItem = null;
|
|---|
| 333 | // } else {
|
|---|
| 334 | // // split the node and move median up
|
|---|
| 335 | // SplitNode(curNode, upcomingItem, location, ref upcomingItem, ref rightchild);
|
|---|
| 336 | // }
|
|---|
| 337 | // }
|
|---|
| 338 | // }
|
|---|
| 339 | //}
|
|---|
| 340 |
|
|---|
| 341 | private void SplitNode(nodetype curNode, nodetype newRight, out keytype upKey, out List<T> upval) {
|
|---|
| 342 | System.Diagnostics.Debug.Assert(Math.Round(curNode.Count / 2.0) != curNode.Count / 2.0);
|
|---|
| 343 | System.Diagnostics.Debug.Assert(curNode.Count == (MIN_KEYS * 2 + 1));
|
|---|
| 344 | System.Diagnostics.Debug.Assert(curNode.Count == MAX_KEYS);
|
|---|
| 345 | System.Diagnostics.Debug.Assert(newRight != null && newRight.Childs != null && newRight.Keys != null);
|
|---|
| 346 | System.Diagnostics.Debug.Assert(newRight.Childs.Length == ORDER && newRight.Keys.Length == MAX_KEYS && newRight.Values.Length == MAX_KEYS);
|
|---|
| 347 | for (int i = MIN_KEYS + 1, ni = 0; ni < MIN_KEYS; ni++, i++) {
|
|---|
| 348 | newRight.Keys[ni] = curNode.Keys[i];
|
|---|
| 349 | newRight.Values[ni] = curNode.Values[i];
|
|---|
| 350 | newRight.Childs[ni+1] = curNode.Childs[i+1];
|
|---|
| 351 | // clear old data
|
|---|
| 352 | curNode.Keys[i] = -1;
|
|---|
| 353 | curNode.Values[i] = null;
|
|---|
| 354 | curNode.Childs[i+1] = null;
|
|---|
| 355 | }
|
|---|
| 356 | curNode.Count = MIN_KEYS;
|
|---|
| 357 | newRight.Count = MIN_KEYS;
|
|---|
| 358 | newRight.Childs[0] = curNode.Childs[MIN_KEYS + 1];
|
|---|
| 359 | upKey = curNode.Keys[MIN_KEYS];
|
|---|
| 360 | upval = curNode.Values[MIN_KEYS];
|
|---|
| 361 | // clear old data
|
|---|
| 362 | curNode.Keys[MIN_KEYS] = -1;
|
|---|
| 363 | curNode.Values[MIN_KEYS] = null;
|
|---|
| 364 | curNode.Childs[MIN_KEYS + 1] = null;
|
|---|
| 365 | }
|
|---|
| 366 |
|
|---|
| 367 | //private void SplitNode(nodetype curNode, itemtype newItem, int location, ref itemtype upcomingItem, ref nodetype upcomingrightnode) {
|
|---|
| 368 | // var newnode = new nodetype();
|
|---|
| 369 | // if (location <= MIN_KEYS) {
|
|---|
| 370 | // // copy right node
|
|---|
| 371 | // for (int ci = MIN_KEYS, ni = 0; ci < MAX_KEYS; ci++, ni++ ) {
|
|---|
| 372 | // newnode.Items[ni] = curNode.Items[ci];
|
|---|
| 373 | // newnode.Childs[ni+1] = curNode.Childs[ci];
|
|---|
| 374 | // }
|
|---|
| 375 | // // copy curNode
|
|---|
| 376 | // for (int ci = MIN_KEYS; ci --> location; ) {
|
|---|
| 377 | // curNode.Items[ci+1] = curNode.Items[ci];
|
|---|
| 378 | // curNode.Childs[ci+1] = curNode.Childs[ci];
|
|---|
| 379 | // }
|
|---|
| 380 | // curNode.Count = MIN_KEYS + 1;
|
|---|
| 381 | // newnode.Count = MAX_KEYS - MIN_KEYS;
|
|---|
| 382 | // // insert new item
|
|---|
| 383 | // curNode.Items[location] = newItem;
|
|---|
| 384 | // curNode.Childs[location] = upcomingrightnode;
|
|---|
| 385 | // newnode.Childs[0] = curNode.Childs[MIN_KEYS];
|
|---|
| 386 | // // give the median back upwards
|
|---|
| 387 | // upcomingItem = curNode.Items[MIN_KEYS];
|
|---|
| 388 | // upcomingrightnode = newnode;
|
|---|
| 389 | // } else {
|
|---|
| 390 | // // copy right node -> up to insert location
|
|---|
| 391 | // int i = MIN_KEYS, ni = 0;
|
|---|
| 392 | // for (; i < location; i++, ni++) {
|
|---|
| 393 | // newnode.Items[ni] = curNode.Items[i];
|
|---|
| 394 | // newnode.Childs[ni+1] = curNode.Childs[i];
|
|---|
| 395 | // }
|
|---|
| 396 | // // insert new item
|
|---|
| 397 | // newnode.Items[ni] = newItem;
|
|---|
| 398 | // newnode.Childs[ni++] = upcomingrightnode;
|
|---|
| 399 | // // copy rest of node to right side
|
|---|
| 400 | // for (; i < curNode.Count; i++, ni++) {
|
|---|
| 401 | // newnode.Items[ni] = curNode.Items[i];
|
|---|
| 402 | // newnode.Childs[ni+1] = curNode.Childs[i];
|
|---|
| 403 | // }
|
|---|
| 404 | // // update curNode
|
|---|
| 405 | // curNode.Count = MIN_KEYS + 1;
|
|---|
| 406 | // newnode.Count = ni;
|
|---|
| 407 | // newnode.Childs[0] = curNode.Childs[MIN_KEYS + 1];
|
|---|
| 408 | // upcomingItem = curNode.Items[MIN_KEYS + 1];
|
|---|
| 409 | // upcomingrightnode = newnode;
|
|---|
| 410 | // }
|
|---|
| 411 | // m_nodeCount++;
|
|---|
| 412 | //}
|
|---|
| 413 |
|
|---|
| 414 | private void InsertItemIntoNode(nodetype curNode, keytype newKey,List<T> newvalue, int location, nodetype rigthchild) {
|
|---|
| 415 | int a = curNode.Count;
|
|---|
| 416 | for (; a --> location; ) {
|
|---|
| 417 | curNode.Keys[a+1] = curNode.Keys[a];
|
|---|
| 418 | curNode.Values[a+1] = curNode.Values[a];
|
|---|
| 419 | curNode.Childs[a+2] = curNode.Childs[a+1];
|
|---|
| 420 | }
|
|---|
| 421 | // insert a new linked list at freed position
|
|---|
| 422 | curNode.Keys[location] = newKey;
|
|---|
| 423 | curNode.Values[location] = newvalue;
|
|---|
| 424 | curNode.Childs[location+1] = rigthchild;
|
|---|
| 425 | curNode.Count++;
|
|---|
| 426 | }
|
|---|
| 427 |
|
|---|
| 428 | #endregion
|
|---|
| 429 |
|
|---|
| 430 | }
|
|---|
| 431 | }
|
|---|
