Java中的稀疏矩阵/数组

Question

Java中的稀疏矩阵/数组

我正在做一个用Java编写的项目，它要求我构建一个非常大的二维稀疏数组。非常稀少，如果这有区别的话。无论如何：这个应用程序最关键的方面是时间方面的效率(假设内存负载，虽然不是无限的，允许我使用标准的二维数组-关键的范围是两个维度的数十亿)。

在数组中的kajillion单元中，将有几十万个包含一个对象的单元格。我需要能够非常快地修改单元格内容。

不管怎么说，有人知道一个特别好的图书馆吗？它必须是伯克利，LGPL或类似的许可(没有GPL，因为产品不能完全开源)。或者，如果有一种非常简单的方法来制作一个自制的稀疏数组对象，那也很好。

我在考虑MTJ，但没有听到任何关于它的质量的意见。

Answer 1

使用hashmap构建的Sparsed数组对于频繁读取的数据来说效率很低。最有效的实现使用Trie，它允许访问单个向量，其中段是分布的。Trie可以通过只执行只读的两个数组索引来计算表中是否存在一个元素，以获得存储元素的有效位置，或者知道它是否不在基础存储中。它还可以为稀疏数组的默认值提供备份存储中的默认位置，因此不需要对返回的索引进行任何测试，因为Trie保证所有可能的源索引至少映射到后备存储中的默认位置(在备份存储中经常存储零、空字符串或空对象)。有一些实现支持可快速更新的尝试，通过一个普通的“紧密()”操作来优化多个操作结束时备份存储的大小。尝试要比散列映射快得多，因为它们不需要任何复杂的散列函数，并且不需要处理读的冲突(对于Hashmap，无论是读还是写，这都需要一个循环来跳到下一个候选位置，并对它们进行测试以比较有效的源索引.)此外，JavaHashmap只能对象进行索引，并且为每个散列源索引创建一个Integer对象(每次读取都需要创建这个对象，而不仅仅是写)，因为它强调垃圾收集器的内存操作成本很高。我真的希望JRE包含一个IntegerTrieMap<Object>作为慢速HashMap<Integer，Object>或LongTrieMap<Object>的默认实现，作为更慢的HashMap<Long，Object>的默认实现.但情况仍然并非如此。你可能想知道什么是Trie？它只是一个小的整数数组(在比矩阵的整个坐标范围更小的范围内)，它允许将坐标映射到向量中的整数位置。例如，假设您想要一个只包含几个非零值的1024*1024矩阵。与其将矩阵存储在包含1024*1024个元素(超过100万)的数组中，您可能只想将其拆分为大小为16*16的子区间，而只需要64*64这样的子范围。在这种情况下，Trie索引将只包含64*64整数(4096)，并且至少有16*16个数据元素(包含默认的零，或稀疏矩阵中最常见的子范围)。用于存储值的向量将只包含一个副本，用于相互相等的子区域(其中大多数都是零的，它们将由相同的子范围表示)。所以，而不是使用类似的语法matrix[i][j]，您将使用如下语法：trie.values[trie.subrangePositions[(i&nbsp;&&nbsp;~15)&nbsp;+&nbsp;(j&nbsp;>>&nbsp;4)]&nbsp;+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((i&nbsp;&&nbsp;15)&nbsp;<<&nbsp;4)&nbsp;+&nbsp;(j&nbsp;&&nbsp;15)]使用Trie对象的访问方法可以更方便地处理。下面是一个内置在注释类中的示例(我希望它编译OK，因为它已经简化了；如果有错误需要更正，请通知我)：/** &nbsp;*&nbsp;Implement&nbsp;a&nbsp;sparse&nbsp;matrix.&nbsp;Currently&nbsp;limited&nbsp;to&nbsp;a&nbsp;static&nbsp;size &nbsp;*&nbsp;(<code>SIZE_I</code>,&nbsp;<code>SIZE_I</code>). &nbsp;*/public&nbsp;class&nbsp;DoubleTrie&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Matrix&nbsp;logical&nbsp;options&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;int&nbsp;SIZE_I&nbsp;=&nbsp;1024; &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;int&nbsp;SIZE_J&nbsp;=&nbsp;1024; &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;double&nbsp;DEFAULT_VALUE&nbsp;=&nbsp;0.0; &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Internal&nbsp;splitting&nbsp;options&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGEBITS_I&nbsp;=&nbsp;4; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGEBITS_J&nbsp;=&nbsp;4; &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Internal&nbsp;derived&nbsp;splitting&nbsp;constants&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGE_I&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;<<&nbsp;SUBRANGEBITS_I; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGE_J&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;<<&nbsp;SUBRANGEBITS_J; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGEMASK_I&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SUBRANGE_I&nbsp;-&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGEMASK_J&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SUBRANGE_J&nbsp;-&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGE_POSITIONS&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SUBRANGE_I&nbsp;*&nbsp;SUBRANGE_J; &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Internal&nbsp;derived&nbsp;default&nbsp;values&nbsp;for&nbsp;constructors&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGES_I&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(SIZE_I&nbsp;+&nbsp;SUBRANGE_I&nbsp;-&nbsp;1)&nbsp;/&nbsp;SUBRANGE_I; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGES_J&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(SIZE_J&nbsp;+&nbsp;SUBRANGE_J&nbsp;-&nbsp;1)&nbsp;/&nbsp;SUBRANGE_J; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;SUBRANGES&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SUBRANGES_I&nbsp;*&nbsp;SUBRANGES_J; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;DEFAULT_POSITIONS[]&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new&nbsp;int[SUBRANGES](0); &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;double&nbsp;DEFAULT_VALUES[]&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new&nbsp;double[SUBRANGE_POSITIONS](DEFAULT_VALUE); &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Internal&nbsp;fast&nbsp;computations&nbsp;of&nbsp;the&nbsp;splitting&nbsp;subrange&nbsp;and&nbsp;offset.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;subrangeOf( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;i,&nbsp;final&nbsp;int&nbsp;j)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(i&nbsp;>>&nbsp;SUBRANGEBITS_I)&nbsp;*&nbsp;SUBRANGE_J&nbsp;+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(j&nbsp;>>&nbsp;SUBRANGEBITS_J); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;static&nbsp;final&nbsp;int&nbsp;positionOffsetOf( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;i,&nbsp;final&nbsp;int&nbsp;j)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(i&nbsp;&&nbsp;SUBRANGEMASK_I)&nbsp;*&nbsp;MAX_J&nbsp;+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(j&nbsp;&&nbsp;SUBRANGEMASK_J); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Utility&nbsp;missing&nbsp;in&nbsp;java.lang.System&nbsp;for&nbsp;arrays&nbsp;of&nbsp;comparable &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;component&nbsp;types,&nbsp;including&nbsp;all&nbsp;native&nbsp;types&nbsp;like&nbsp;double&nbsp;here. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;int&nbsp;arraycompare( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values1,&nbsp;final&nbsp;int&nbsp;position1, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values2,&nbsp;final&nbsp;int&nbsp;position2, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;length)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(position1&nbsp;>=&nbsp;0&nbsp;&&&nbsp;position2&nbsp;>=&nbsp;0&nbsp;&&&nbsp;length&nbsp;>=&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(length--&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double&nbsp;value1,&nbsp;value2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;((value1&nbsp;=&nbsp;values1[position1&nbsp;+&nbsp;length])&nbsp;!= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(value2&nbsp;=&nbsp;values2[position2&nbsp;+&nbsp;length]))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Note:&nbsp;NaN&nbsp;values&nbsp;are&nbsp;different&nbsp;from&nbsp;everything&nbsp;including &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;all&nbsp;Nan&nbsp;values;&nbsp;they&nbsp;are&nbsp;are&nbsp;also&nbsp;neigher&nbsp;lower&nbsp;than&nbsp;nor &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;greater&nbsp;than&nbsp;everything&nbsp;including&nbsp;NaN.&nbsp;Note&nbsp;that&nbsp;the&nbsp;two &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;infinite&nbsp;values,&nbsp;as&nbsp;well&nbsp;as&nbsp;denormal&nbsp;values,&nbsp;are&nbsp;exactly &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;ordered&nbsp;and&nbsp;comparable&nbsp;with&nbsp;<,&nbsp;<=,&nbsp;==,&nbsp;>=,&nbsp;>=,&nbsp;!=.&nbsp;Note &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;that&nbsp;in&nbsp;comments&nbsp;below,&nbsp;infinite&nbsp;is&nbsp;considered&nbsp;"defined". &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(value1&nbsp;<&nbsp;value2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;-1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;defined&nbsp;<&nbsp;defined.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(value1&nbsp;>&nbsp;value2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;defined&nbsp;>&nbsp;defined.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(value1&nbsp;==&nbsp;value2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;defined&nbsp;==&nbsp;defined.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;One&nbsp;or&nbsp;both&nbsp;are&nbsp;NaN.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(value1&nbsp;==&nbsp;value1)&nbsp;/*&nbsp;Is&nbsp;not&nbsp;a&nbsp;NaN?&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;-1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;defined&nbsp;<&nbsp;NaN.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(value2&nbsp;==&nbsp;value2)&nbsp;/*&nbsp;Is&nbsp;not&nbsp;a&nbsp;NaN?&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;NaN&nbsp;>&nbsp;defined.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Otherwise,&nbsp;both&nbsp;are&nbsp;NaN:&nbsp;check&nbsp;their&nbsp;precise&nbsp;bits&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;range&nbsp;0x7FF0000000000001L..0x7FFFFFFFFFFFFFFFL &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;including&nbsp;the&nbsp;canonical&nbsp;0x7FF8000000000000L,&nbsp;or&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;range&nbsp;0xFFF0000000000001L..0xFFFFFFFFFFFFFFFFL. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Needed&nbsp;for&nbsp;sort&nbsp;stability&nbsp;only&nbsp;(NaNs&nbsp;are&nbsp;otherwise &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;unordered). &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;raw1,&nbsp;raw2; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;((raw1&nbsp;=&nbsp;Double.doubleToRawLongBits(value1))&nbsp;!= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(raw2&nbsp;=&nbsp;Double.doubleToRawLongBits(value2))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;raw1&nbsp;<&nbsp;raw2&nbsp;?&nbsp;-1&nbsp;:&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Otherwise&nbsp;the&nbsp;NaN&nbsp;are&nbsp;strictly&nbsp;equal,&nbsp;continue.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;throw&nbsp;new&nbsp;ArrayIndexOutOfBoundsException( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"The&nbsp;positions&nbsp;and&nbsp;length&nbsp;can't&nbsp;be&nbsp;negative"); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Utility&nbsp;shortcut&nbsp;for&nbsp;comparing&nbsp;ranges&nbsp;in&nbsp;the&nbsp;same&nbsp;array. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;int&nbsp;arraycompare( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;position1,&nbsp;final&nbsp;int&nbsp;position2, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;length)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;arraycompare(values,&nbsp;position1,&nbsp;values,&nbsp;position2,&nbsp;length); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Utility&nbsp;missing&nbsp;in&nbsp;java.lang.System&nbsp;for&nbsp;arrays&nbsp;of&nbsp;equalizable &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;component&nbsp;types,&nbsp;including&nbsp;all&nbsp;native&nbsp;types&nbsp;like&nbsp;double&nbsp;here. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;boolean&nbsp;arrayequals( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values1,&nbsp;final&nbsp;int&nbsp;position1, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values2,&nbsp;final&nbsp;int&nbsp;position2, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;length)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;arraycompare(values1,&nbsp;position1,&nbsp;values2,&nbsp;position2,&nbsp;length)&nbsp;== &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Utility&nbsp;shortcut&nbsp;for&nbsp;identifying&nbsp;ranges&nbsp;in&nbsp;the&nbsp;same&nbsp;array. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;boolean&nbsp;arrayequals( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;position1,&nbsp;final&nbsp;int&nbsp;position2, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;length)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;arrayequals(values,&nbsp;position1,&nbsp;values,&nbsp;position2,&nbsp;length); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Utility&nbsp;shortcut&nbsp;for&nbsp;copying&nbsp;ranges&nbsp;in&nbsp;the&nbsp;same&nbsp;array. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;void&nbsp;arraycopy( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;srcPosition,&nbsp;final&nbsp;int&nbsp;dstPosition, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;length)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arraycopy(values,&nbsp;srcPosition,&nbsp;values,&nbsp;dstPosition,&nbsp;length); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Utility&nbsp;shortcut&nbsp;for&nbsp;resizing&nbsp;an&nbsp;array,&nbsp;preserving&nbsp;values&nbsp;at&nbsp;start. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;final&nbsp;double[]&nbsp;arraysetlength( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double[]&nbsp;values, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;newLength)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;oldLength&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;values.length&nbsp;<&nbsp;newLength&nbsp;?&nbsp;values.length&nbsp;:&nbsp;newLength; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.arraycopy(values,&nbsp;0,&nbsp;values&nbsp;=&nbsp;new&nbsp;double[newLength],&nbsp;0, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;oldLength); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;values; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Internal&nbsp;instance&nbsp;members.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;double&nbsp;values[]; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;int&nbsp;subrangePositions[]; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;bool&nbsp;isSharedValues; &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;bool&nbsp;isSharedSubrangePositions; &nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Internal&nbsp;method.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;final&nbsp;reset( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;double[]&nbsp;values, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int[]&nbsp;subrangePositions)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.isSharedValues&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(this.values&nbsp;=&nbsp;values)&nbsp;==&nbsp;DEFAULT_VALUES; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.isSharedsubrangePositions&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(this.subrangePositions&nbsp;=&nbsp;subrangePositions)&nbsp;== &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DEFAULT_POSITIONS; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Reset&nbsp;the&nbsp;matrix&nbsp;to&nbsp;fill&nbsp;it&nbsp;with&nbsp;the&nbsp;same&nbsp;initial&nbsp;value. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;initialValue&nbsp;&nbsp;The&nbsp;value&nbsp;to&nbsp;set&nbsp;in&nbsp;all&nbsp;cell&nbsp;positions. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;reset(final&nbsp;double&nbsp;initialValue&nbsp;=&nbsp;DEFAULT_VALUE)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;reset( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(initialValue&nbsp;==&nbsp;DEFAULT_VALUE)&nbsp;?&nbsp;DEFAULT_VALUES&nbsp;: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new&nbsp;double[SUBRANGE_POSITIONS](initialValue), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DEFAULT_POSITIONS); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Default&nbsp;constructor,&nbsp;using&nbsp;single&nbsp;default&nbsp;value. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;initialValue&nbsp;&nbsp;Alternate&nbsp;default&nbsp;value&nbsp;to&nbsp;initialize&nbsp;all &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;positions&nbsp;in&nbsp;the&nbsp;matrix. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;DoubleTrie(final&nbsp;double&nbsp;initialValue&nbsp;=&nbsp;DEFAULT_VALUE)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.reset(initialValue); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;This&nbsp;is&nbsp;a&nbsp;useful&nbsp;preinitialized&nbsp;instance&nbsp;containing&nbsp;the &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;DEFAULT_VALUE&nbsp;in&nbsp;all&nbsp;cells. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;static&nbsp;DoubleTrie&nbsp;DEFAULT_INSTANCE&nbsp;=&nbsp;new&nbsp;DoubleTrie(); &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Copy&nbsp;constructor.&nbsp;Note&nbsp;that&nbsp;the&nbsp;source&nbsp;trie&nbsp;may&nbsp;be&nbsp;immutable &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;or&nbsp;not;&nbsp;but&nbsp;this&nbsp;constructor&nbsp;will&nbsp;create&nbsp;a&nbsp;new&nbsp;mutable&nbsp;trie &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;even&nbsp;if&nbsp;the&nbsp;new&nbsp;trie&nbsp;initially&nbsp;shares&nbsp;some&nbsp;storage&nbsp;with&nbsp;its &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;source&nbsp;when&nbsp;that&nbsp;source&nbsp;also&nbsp;uses&nbsp;shared&nbsp;storage. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;DoubleTrie(final&nbsp;DoubleTrie&nbsp;source)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.values&nbsp;=&nbsp;(this.isSharedValues&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.isSharedValues)&nbsp;? &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.values&nbsp;: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.values.clone(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.subrangePositions&nbsp;=&nbsp;(this.isSharedSubrangePositions&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.isSharedSubrangePositions)&nbsp;? &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.subrangePositions&nbsp;: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.subrangePositions.clone()); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Fast&nbsp;indexed&nbsp;getter. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;i&nbsp;&nbsp;Row&nbsp;of&nbsp;position&nbsp;to&nbsp;set&nbsp;in&nbsp;the&nbsp;matrix. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;j&nbsp;&nbsp;Column&nbsp;of&nbsp;position&nbsp;to&nbsp;set&nbsp;in&nbsp;the&nbsp;matrix. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@return&nbsp;&nbsp;&nbsp;The&nbsp;value&nbsp;stored&nbsp;in&nbsp;matrix&nbsp;at&nbsp;that&nbsp;position. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;double&nbsp;getAt(final&nbsp;int&nbsp;i,&nbsp;final&nbsp;int&nbsp;j)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;values[subrangePositions[subrangeOf(i,&nbsp;j)]&nbsp;+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;positionOffsetOf(i,&nbsp;j)]; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Fast&nbsp;indexed&nbsp;setter. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Row&nbsp;of&nbsp;position&nbsp;to&nbsp;set&nbsp;in&nbsp;the&nbsp;sparsed&nbsp;matrix. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;j&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Column&nbsp;of&nbsp;position&nbsp;to&nbsp;set&nbsp;in&nbsp;the&nbsp;sparsed&nbsp;matrix. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;value&nbsp;&nbsp;The&nbsp;value&nbsp;to&nbsp;set&nbsp;at&nbsp;this&nbsp;position. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@return&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;The&nbsp;passed&nbsp;value. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Note:&nbsp;this&nbsp;does&nbsp;not&nbsp;compact&nbsp;the&nbsp;sparsed&nbsp;matric&nbsp;after&nbsp;setting. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@see&nbsp;compact(void) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;double&nbsp;setAt(final&nbsp;int&nbsp;i,&nbsp;final&nbsp;int&nbsp;i,&nbsp;final&nbsp;double&nbsp;value)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;subrange&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;subrangeOf(i,&nbsp;j); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;positionOffset&nbsp;=&nbsp;positionOffsetOf(i,&nbsp;j); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Fast&nbsp;check&nbsp;to&nbsp;see&nbsp;if&nbsp;the&nbsp;assignment&nbsp;will&nbsp;change&nbsp;something. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;subrangePosition,&nbsp;valuePosition; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(Double.compare( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;values[valuePosition&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(subrangePosition&nbsp;=&nbsp;subrangePositions[subrange])&nbsp;+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;positionOffset], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;value)&nbsp;!=&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;So&nbsp;we'll&nbsp;need&nbsp;to&nbsp;perform&nbsp;an&nbsp;effective&nbsp;assignment&nbsp;in&nbsp;values. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Check&nbsp;if&nbsp;the&nbsp;current&nbsp;subrange&nbsp;to&nbsp;assign&nbsp;is&nbsp;shared&nbsp;of&nbsp;not. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Note&nbsp;that&nbsp;we&nbsp;also&nbsp;include&nbsp;the&nbsp;DEFAULT_VALUES&nbsp;which&nbsp;may&nbsp;be &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;shared&nbsp;by&nbsp;several&nbsp;other&nbsp;(not&nbsp;tested)&nbsp;trie&nbsp;instances, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;including&nbsp;those&nbsp;instanciated&nbsp;by&nbsp;the&nbsp;copy&nbsp;contructor.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(isSharedValues)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;values&nbsp;=&nbsp;values.clone(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;isSharedValues&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Scan&nbsp;all&nbsp;other&nbsp;subranges&nbsp;to&nbsp;check&nbsp;if&nbsp;the&nbsp;position&nbsp;in&nbsp;values &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;to&nbsp;assign&nbsp;is&nbsp;shared&nbsp;by&nbsp;another&nbsp;subrange.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;otherSubrange&nbsp;=&nbsp;subrangePositions.length; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;--otherSubrange&nbsp;>=&nbsp;0;&nbsp;)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(otherSubrange&nbsp;!=&nbsp;subrange) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;&nbsp;/*&nbsp;Ignore&nbsp;the&nbsp;target&nbsp;subrange.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Note:&nbsp;the&nbsp;following&nbsp;test&nbsp;of&nbsp;range&nbsp;is&nbsp;safe&nbsp;with&nbsp;future &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;interleaving&nbsp;of&nbsp;common&nbsp;subranges&nbsp;(TODO&nbsp;in&nbsp;compact()), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;even&nbsp;though,&nbsp;for&nbsp;now,&nbsp;subranges&nbsp;are&nbsp;sharing&nbsp;positions &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;only&nbsp;between&nbsp;their&nbsp;common&nbsp;start&nbsp;and&nbsp;end&nbsp;position,&nbsp;so&nbsp;we &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;could&nbsp;as&nbsp;well&nbsp;only&nbsp;perform&nbsp;the&nbsp;simpler&nbsp;test&nbsp;<code> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;(otherSubrangePosition&nbsp;==&nbsp;subrangePosition)</code>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;instead&nbsp;of&nbsp;testing&nbsp;the&nbsp;two&nbsp;bounds&nbsp;of&nbsp;the&nbsp;positions &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;interval&nbsp;of&nbsp;the&nbsp;other&nbsp;subrange.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;otherSubrangePosition; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;((otherSubrangePosition&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;subrangePositions[otherSubrange])&nbsp;>= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;valuePosition&nbsp;&& &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;otherSubrangePosition&nbsp;+&nbsp;SUBRANGE_POSITIONS&nbsp;< &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;valuePosition)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;The&nbsp;target&nbsp;position&nbsp;is&nbsp;shared&nbsp;by&nbsp;some&nbsp;other &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;subrange,&nbsp;we&nbsp;need&nbsp;to&nbsp;make&nbsp;it&nbsp;unique&nbsp;by&nbsp;cloning&nbsp;the &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;subrange&nbsp;to&nbsp;a&nbsp;larger&nbsp;values&nbsp;vector,&nbsp;copying&nbsp;all&nbsp;the &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;current&nbsp;subrange&nbsp;values&nbsp;at&nbsp;end&nbsp;of&nbsp;the&nbsp;new&nbsp;vector, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;before&nbsp;assigning&nbsp;the&nbsp;new&nbsp;value.&nbsp;This&nbsp;will&nbsp;require &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;changing&nbsp;the&nbsp;position&nbsp;of&nbsp;the&nbsp;current&nbsp;subrange,&nbsp;but &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;before&nbsp;doing&nbsp;that,&nbsp;we&nbsp;first&nbsp;need&nbsp;to&nbsp;check&nbsp;if&nbsp;the &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;subrangePositions&nbsp;array&nbsp;itself&nbsp;is&nbsp;also&nbsp;shared &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;between&nbsp;instances&nbsp;(including&nbsp;the&nbsp;DEFAULT_POSITIONS &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;that&nbsp;should&nbsp;be&nbsp;preserved,&nbsp;and&nbsp;possible&nbsp;arrays &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;shared&nbsp;by&nbsp;an&nbsp;external&nbsp;factory&nbsp;contructor&nbsp;whose &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;source&nbsp;trie&nbsp;was&nbsp;declared&nbsp;immutable&nbsp;in&nbsp;a&nbsp;derived &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;class).&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(isSharedSubrangePositions)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;subrangePositions&nbsp;=&nbsp;subrangePositions.clone(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;isSharedSubrangePositions&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;TODO:&nbsp;no&nbsp;attempt&nbsp;is&nbsp;made&nbsp;to&nbsp;allocate&nbsp;less&nbsp;than&nbsp;a &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;fully&nbsp;independant&nbsp;subrange,&nbsp;using&nbsp;possible &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;interleaving:&nbsp;this&nbsp;would&nbsp;require&nbsp;scanning&nbsp;all &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;other&nbsp;existing&nbsp;values&nbsp;to&nbsp;find&nbsp;a&nbsp;match&nbsp;for&nbsp;the &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;modified&nbsp;subrange&nbsp;of&nbsp;values;&nbsp;but&nbsp;this&nbsp;could &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;potentially&nbsp;leave&nbsp;positions&nbsp;(in&nbsp;the&nbsp;current&nbsp;subrange &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;of&nbsp;values)&nbsp;unreferenced&nbsp;by&nbsp;any&nbsp;subrange,&nbsp;after&nbsp;the &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;change&nbsp;of&nbsp;position&nbsp;for&nbsp;the&nbsp;current&nbsp;subrange.&nbsp;This &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;scanning&nbsp;could&nbsp;be&nbsp;prohibitively&nbsp;long&nbsp;for&nbsp;each &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;assignement,&nbsp;and&nbsp;for&nbsp;now&nbsp;it's&nbsp;assumed&nbsp;that&nbsp;compact() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;will&nbsp;be&nbsp;used&nbsp;later,&nbsp;after&nbsp;those&nbsp;assignements.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;values&nbsp;=&nbsp;setlengh( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;values, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(subrangePositions[subrange]&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;subrangePositions&nbsp;=&nbsp;values.length)&nbsp;+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SUBRANGE_POSITIONS); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;valuePosition&nbsp;=&nbsp;subrangePositions&nbsp;+&nbsp;positionOffset; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Now&nbsp;perform&nbsp;the&nbsp;effective&nbsp;assignment&nbsp;of&nbsp;the&nbsp;value.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;values[valuePosition]&nbsp;=&nbsp;value; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;value; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Compact&nbsp;the&nbsp;storage&nbsp;of&nbsp;common&nbsp;subranges. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;TODO:&nbsp;This&nbsp;is&nbsp;a&nbsp;simple&nbsp;implementation&nbsp;without&nbsp;interleaving,&nbsp;which &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;would&nbsp;offer&nbsp;a&nbsp;better&nbsp;data&nbsp;compression.&nbsp;However,&nbsp;interleaving&nbsp;with&nbsp;its &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;O(N²)&nbsp;complexity&nbsp;where&nbsp;N&nbsp;is&nbsp;the&nbsp;total&nbsp;length&nbsp;of&nbsp;values,&nbsp;should &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;be&nbsp;attempted&nbsp;only&nbsp;after&nbsp;this&nbsp;basic&nbsp;compression&nbsp;whose&nbsp;complexity&nbsp;is &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;O(n²)&nbsp;with&nbsp;n&nbsp;being&nbsp;SUBRANGE_POSITIIONS&nbsp;times&nbsp;smaller&nbsp;than&nbsp;N. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;void&nbsp;compact()&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;final&nbsp;int&nbsp;oldValuesLength&nbsp;=&nbsp;values.length; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;newValuesLength&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;oldPosition&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;oldPosition&nbsp;<&nbsp;oldValuesLength; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;oldPosition&nbsp;+=&nbsp;SUBRANGE_POSITIONS)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;oldPosition&nbsp;=&nbsp;positions[subrange]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bool&nbsp;commonSubrange&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Scan&nbsp;values&nbsp;for&nbsp;possible&nbsp;common&nbsp;subranges.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;newPosition&nbsp;=&nbsp;newValuesLength; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(newPosition&nbsp;-=&nbsp;SUBRANGE_POSITIONS)&nbsp;>=&nbsp;0;&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(arrayequals(values,&nbsp;newPosition,&nbsp;oldPosition, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SUBRANGE_POSITIONS))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;commonSubrange&nbsp;=&nbsp;true; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Update&nbsp;the&nbsp;subrangePositions|]&nbsp;with&nbsp;all&nbsp;matching &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;positions&nbsp;from&nbsp;oldPosition&nbsp;to&nbsp;newPosition.&nbsp;There&nbsp;may &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;be&nbsp;several&nbsp;index&nbsp;to&nbsp;change,&nbsp;if&nbsp;the&nbsp;trie&nbsp;has&nbsp;already &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;been&nbsp;compacted()&nbsp;before,&nbsp;and&nbsp;later&nbsp;reassigned.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(subrange&nbsp;=&nbsp;subrangePositions.length; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;--subrange&nbsp;>=&nbsp;0;&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(subrangePositions[subrange]&nbsp;==&nbsp;oldPosition) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;subrangePositions[subrange]&nbsp;=&nbsp;newPosition; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!commonSubrange)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Move&nbsp;down&nbsp;the&nbsp;non-common&nbsp;values,&nbsp;if&nbsp;some&nbsp;previous &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;subranges&nbsp;have&nbsp;been&nbsp;compressed&nbsp;when&nbsp;they&nbsp;were&nbsp;common. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!commonSubrange&nbsp;&&&nbsp;oldPosition&nbsp;!=&nbsp;newValuesLength)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arraycopy(values,&nbsp;oldPosition,&nbsp;newValuesLength, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SUBRANGE_POSITIONS); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Advance&nbsp;compressed&nbsp;values&nbsp;to&nbsp;preserve&nbsp;these&nbsp;new&nbsp;ones.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newValuesLength&nbsp;+=&nbsp;SUBRANGE_POSITIONS; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Check&nbsp;the&nbsp;number&nbsp;of&nbsp;compressed&nbsp;values.&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(newValuesLength&nbsp;<&nbsp;oldValuesLength)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;values&nbsp;=&nbsp;values.arraysetlength(newValuesLength); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;isSharedValues&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}}注意：此代码不完整，因为它处理单个矩阵大小，而它的密码器仅限于检测公共子范围，而不交叉它们。此外，根据矩阵大小，代码不确定用于将矩阵拆分为子范围(x或y坐标)的最佳宽度或高度。它只使用相同的静态子范围大小为16(这两个坐标)，但它可以方便地任何其他小功率为2(但一个非幂2将减慢int indexOf(int, int)和int offsetOf(int, int)(内部方法)，独立于两个坐标，并达到矩阵的最大宽度或高度。compact()方法应该能够确定最佳的拟合大小。如果这些拆分子范围的大小可能有所不同，则需要为这些子范围大小添加实例成员，而不是静态的。SUBRANGE_POSITIONS，并使静态方法int subrangeOf(int i, int j)和int positionOffsetOf(int i, int j)变成非静态的；以及初始化数组。DEFAULT_POSITIONS和DEFAULT_VALUES需要以不同的方式删除或重新定义。如果您想支持交错，基本上您将从将现有值除以大约相同大小的两个值开始(两者都是最小子范围大小的倍数，第一个子集可能比第二个子集多一个子区间)，然后在所有连续的位置扫描较大的子集以找到匹配的交织；然后尝试匹配这些值。然后，通过将子集分成两半(也是最小子范围大小的倍数)递归循环，然后再扫描以匹配这些子集(这将使子集的数量乘以2：您必须想知道子范围索引的加倍大小是否值得与现有值的大小相比，以查看它是否提供了有效的压缩(如果没有，您就停止了：您已经从交错压缩过程中直接找到了最佳的子范围大小)。在这种情况下，在压缩过程中，子范围大小将是可变的。但是，这段代码显示了如何分配非零值并重新分配data数组，用于额外的(非零)子范围，以及如何优化(使用compact()在使用setAt(int i, int j, double value)方法)当数据中存在可能统一的重复子范围时存储此数据，并在subrangePositions阵列。总之，TRIE的所有原则都是在这里实现的：使用单个向量而不是双索引数组(每个数组分别分配)来表示矩阵总是更快(并且在内存中更紧凑，意味着更好的局部性)。改进可见于double getAt(int, int)方法！您节省了大量的空间，但是在赋值时，重新分配新的子范围可能需要时间。因此，子范围不应该太小，否则在设置矩阵时会发生太频繁的重新分配。通过检测公共子区间，可以将初始大矩阵自动转换为更紧凑的矩阵。然后，一个典型的实现将包含一个方法，例如compact()上面。但是，如果get()访问非常快，set()非常快，如果有许多公共子范围需要压缩(例如，用它自己减去一个大的非稀疏随机填充矩阵，或者将它乘以零，那么它可能会非常慢：在这种情况下，通过实例化一个新的矩阵和删除旧的矩阵来重置Trie会更简单、更快)。公共子区域在数据中使用公共存储，因此这种共享数据必须是只读的。如果必须更改单个值而不更改矩阵的其余部分，则必须首先确保在subrangePositions索引。否则，您需要在values向量，然后将这个新子区域的位置存储到subrangePositions索引。请注意，泛型Colt库虽然非常好，但在处理稀疏矩阵时却不太好，因为它使用散列(或行压缩)技术，目前还没有实现对尝试的支持，尽管它是一个很好的优化，这两者都节省了空间。和节省时间，特别是对于最频繁的getAt()操作。甚至这里描述的用于尝试的setAt()操作也节省了大量的时间(在这里实现的方法，即设置后无需自动压缩，仍然可以根据需求和估计的时间来实现，因为压缩仍然会以时间为代价节省大量存储空间)：节省时间与子区间中单元格的数量成正比，而节省空间与每个子范围的单元格数成反比。如果要使用子范围大小，那么每个子范围的单元格数是2D矩阵中单元格总数的平方根(当使用3D矩阵时，它将是一个立方根)。Colt稀疏矩阵实现中使用的散列技术由于可能的冲突而增加了大量的存储开销和较慢的访问时间。尝试可以避免所有碰撞，然后可以保证在最坏的情况下将线性O(N)时间节省到O(1)时间，其中(N)是可能的碰撞次数(在稀疏矩阵的情况下，可能取决于矩阵中非缺省值单元的数目，即矩阵的总大小乘以与散列填充因子成正比的因子，对于非稀疏的，即全矩阵)。Colt中使用的RC(行压缩)技术离尝试更近，但这是另一个代价，这里使用的压缩技术对于最频繁的只读GET()操作具有非常慢的访问时间，而对于setAt()操作则是非常慢的压缩。此外，所使用的压缩不是正交的，与保持正交性的尝试表示不同。对于相关的查看操作，例如跨步、换位(视为基于整数循环模块操作的跨步操作)、子测距(以及一般的子选择，包括排序视图)，尝试也将保持这种正交性。我只是希望Colt将来会被更新，以便使用TRY(即TrieSparseMatrix，而不是HashSparseMatrix和RCSparseMatrix)实现另一个实现。这些想法都在本文中。trive实现(基于int->int映射)也是基于类似于Colt的HashedSparseMatrix的散列技术，即它们具有相同的不便。尝试的速度要快得多，占用一定的额外空间(但是这个空间可以被优化，甚至可以比trove和Colt更好，在一个延迟的时间内，使用对结果的矩阵/trie的最后的紧凑()离子操作)。注意：此Trie实现绑定到特定的本机类型(此处为Double)。这是自愿的，因为使用装箱类型的一般实现有很大的空间开销(而且访问时间要慢得多)。在这里，它只使用本机的双维数组，而不是泛型向量。但当然也可以为尝试导出一个通用实现.不幸的是，Java仍然不允许使用本机类型的所有优点编写真正的泛型类，除非编写多个实现(对于一个泛型对象类型或每个本机类型)，并通过类型工厂提供所有这些操作。该语言应该能够自动实例化本机实现并自动构建工厂(就目前而言，即使在Java 7中也不是这样，在这种情况下.net仍然保持其优势，适用于与本机类型一样快速的真正泛型类型)。