参考
鬼谷子2-99问题
题目：
一天，鬼谷子随意从2-99中选取了两个数。
他把这两个数的和告诉了庞涓，把这两个数的乘积告诉了孙膑，但孙膑和庞涓彼此不知到对方得到的数。
第二天，庞涓很有自信的对孙膑说：虽然我不知到这两个数是什麽，但我知道你一定也不知道。
随后，孙膑说：那我知道了。
过一会儿，庞涓说：那我也知道了。
问：这两个数是多少？
答案：
4 13
下面通过代码遍历的方式验证答案：
-
首先用代码遍历出所有可能的答案，记为集合totalList（题目说从2-99选两个数分别给两个人，没明确说两个人的数会不会重复，这里先暂且设定是可以重复的）：
static class Result{ int num1; int num2; public Result(int num1, int num2) { this.num1 = num1; this.num2 = num2; } public int getNum1() { return num1; } public int getNum2() { return num2; } public int getSum(){ return num1 + num2; } public int getProduct() { return num1 * num2; } @Override public String toString() { return "("+num1+" "+num2+")"; } } public static void main(String[] args) { test(); } private static int START = 2; private static int END = 99; private static ArrayList<Result> totalList = new ArrayList<>();// private static void test() { // for(int i = START; i <=END; i++) { for (int j = i; j <=END; j++) { totalList.add(new Result(i,j)); } } System.out.println("总共组合:"+totalList.size()+"\n"+totalList); }打印如下，有4851中组合（这里也可以通过排列组合公式计算，从2至99的98个数中取两个=98*97/2=4753，再加上98个重复的组合（2 2，3 3，…，98 98，99 99），即得4851）：
总共组合:4851 [(2 2), (2 3), (2 4), (2 5), (2 6), (2 7), (2 8), (2 9), (2 10), (2 11), (2 12), (2 13), (2 14), (2 15), (2 16), (2 17), (2 18), (2 19), (2 20), (2 21), (2 22), (2 23), (2 24), (2 25), (2 26), (2 27), (2 28), (2 29), (2 30), (2 31), (2 32), (2 33), (2 34), (2 35), (2 36), (2 37), (2 38), (2 39), (2 40), (2 41), (2 42), (2 43), (2 44), (2 45), (2 46), (2 47), (2 48), (2 49), (2 50), (2 51), (2 52), (2 53), (2 54), (2 55), (2 56), (2 57), (2 58), (2 59), (2 60), (2 61), (2 62), (2 63), (2 64), (2 65), (2 66), (2 67), (2 68), (2 69), (2 70), (2 71), (2 72), (2 73), (2 74), (2 75), (2 76), (2 77), (2 78), (2 79), (2 80), (2 81), (2 82), (2 83), (2 84), (2 85), (2 86), (2 87), (2 88), (2 89), (2 90), (2 91), (2 92), (2 93), (2 94), (2 95), (2 96), (2 97), (2 98), (2 99), ...省略 (92 92), (92 93), (92 94), (92 95), (92 96), (92 97), (92 98), (92 99), (93 93), (93 94), (93 95), (93 96), (93 97), (93 98), (93 99), (94 94), (94 95), (94 96), (94 97), (94 98), (94 99), (95 95), (95 96), (95 97), (95 98), (95 99), (96 96), (96 97), (96 98), (96 99), (97 97), (97 98), (97 99), (98 98), (98 99), (99 99)] -
条件1：庞涓（知道和的人）说：我不知道这两个数是什么
由此条件可知，庞涓所拿到的和能拆分成多种组合，这样他才会不确定是多种组合中的哪一个，即该和有多组解，可以把这个多组解记为集合A1——multiResultOfSum，可以用代码遍历得出：
ArrayList<Result> multiResultOfSum = getMultiResultOfSum(totalList); System.out.println("其和有多组解的组合有"+multiResultOfSum.size()+"\n"+multiResultOfSum); private static ArrayList<Result> getMultiResultOfSum(ArrayList<Result> totalList) { ArrayList<Result> list = new ArrayList(); for (Result item:totalList) { int sum = item.getNum1() + item.getNum2(); if(splitSum(sum).size() > 1 ){// 多组解 list.add(item); } } return list; } /** * 拆解和，返回所有可能的组合 * @param sum * @return */ private static ArrayList splitSum(int sum) { ArrayList<Result> list = new ArrayList(); for (Result item:totalList) { if((item.getNum1()+item.getNum2()) == sum){ list.add(item); } } return list; }打印如下，即由“和有多组解”可推测实际组合是下面的4847种之一（其实这里也可以直接推测，因为只需要排除四种组合（最大最小边界：2 2，2 3，98 99，99 99），其他的和都都能拆成多组解）：
其和有多组解的组合有4847 [(2 4), (2 5), (2 6), (2 7), (2 8), (2 9), (2 10), (2 11), (2 12), (2 13), (2 14), (2 15), (2 16), (2 17), (2 18), (2 19), (2 20), (2 21), (2 22), (2 23), (2 24), (2 25), (2 26), (2 27), (2 28), (2 29), (2 30), (2 31), (2 32), (2 33), (2 34), (2 35), (2 36), (2 37), (2 38), (2 39), (2 40), (2 41), (2 42), (2 43), (2 44), (2 45), (2 46), (2 47), (2 48), (2 49), (2 50), (2 51), (2 52), (2 53), (2 54), (2 55), (2 56), (2 57), (2 58), (2 59), (2 60), (2 61), (2 62), (2 63), (2 64), (2 65), (2 66), (2 67), (2 68), (2 69), (2 70), (2 71), (2 72), (2 73), (2 74), (2 75), (2 76), (2 77), (2 78), (2 79), (2 80), (2 81), (2 82), (2 83), (2 84), (2 85), (2 86), (2 87), (2 88), (2 89), (2 90), (2 91), (2 92), (2 93), (2 94), (2 95), (2 96), (2 97), (2 98), (2 99), ...省略 (92 92), (92 93), (92 94), (92 95), (92 96), (92 97), (92 98), (92 99), (93 93), (93 94), (93 95), (93 96), (93 97), (93 98), (93 99), (94 94), (94 95), (94 96), (94 97), (94 98), (94 99), (95 95), (95 96), (95 97), (95 98), (95 99), (96 96), (96 97), (96 98), (96 99), (97 97), (97 98), (97 99), (98 98)] -
条件2：庞涓（知道和的人）继续说：但我知道你一定也不知道
首先与上一步类似，由“你（知道积的人）一定不知道”，可知该积能拆分成多种组合，即该积有多组解，可以把这个多组解记为集合A2——multiResultOfProduct，可以用代码遍历得出：
ArrayList<Result> multiResultOfProduct = getMultiResultOfProduct(totalList); System.out.println("其乘积有多组解的组合有"+multiResultOfProduct.size()+"\n"+multiResultOfProduct); private static ArrayList<Result> getMultiResultOfProduct(ArrayList<Result> totalList) { ArrayList<Result> list = new ArrayList(); for (Result item:totalList) {//总共组合:4851 int product = item.getNum1() * item.getNum2(); if(splitProduct(product).size() > 1){ // 多组解--3076 list.add(item); } } return list; } /** * 拆解积，返回所有可能的组合 * @param product * @return */ private static ArrayList splitProduct(int product) { ArrayList<Result> list = new ArrayList(); for (Result item:totalList) { if((item.getNum1()*item.getNum2()) == product){ list.add(item); } } return list; }打印如下，即由“积有多组解”可推测实际组合是下面的3076种之一（这一步也可以从另一个方向——是否是质数相乘等等来计算，这里就不展开了）：
其乘积有多组解的组合有3076 [(2 6), (2 8), (2 9), (2 10), (2 12), (2 14), (2 15), (2 16), (2 18), (2 20), (2 21), (2 22), (2 24), (2 25), (2 26), (2 27), (2 28), (2 30), (2 32), (2 33), (2 34), (2 35), (2 36), (2 38), (2 39), (2 40), (2 42), (2 44), (2 45), (2 46), (2 48), (2 49), (2 50), (2 51), (2 52), (2 54), (2 55), (2 56), (2 57), (2 58), (2 60), (2 62), (2 63), (2 64), (2 65), (2 66), (2 68), (2 69), (2 70), (2 72), (2 74), (2 75), (2 76), (2 77), (2 78), (2 80), (2 81), (2 82), (2 84), (2 85), (2 86), (2 87), (2 88), (2 90), (2 91), (2 92), (2 93), (2 94), (2 95), (2 96), (2 98), (2 99), ...省略 (72 72), (72 75), (72 76), (72 77), (72 80), (72 84), (72 85), (72 88), (72 90), (72 91), (72 92), (72 95), (72 98), (72 99), (75 76), (75 78), (75 84), (75 96), (76 80), (76 85), (76 90), (77 78), (77 80), (77 81), (77 84), (77 90), (77 96), (78 80), (78 84), (78 98), (80 81), (80 84), (80 90), (80 99), (81 88), (84 84), (84 88), (84 91), (88 90)]接下来的理解比较关键，同样还是这句话：庞涓（知道和的人）说我知道你一定也不知道，即 知道和的人 断定 知道积的人 一定不能从积直接推测出实际组合（所以肯定不能是两个质数相乘），那么他是如何能这么断言的？ 想象一个场景：庞涓看了看自己手上的和，眉头一皱，心想：这和能拆成的组合多了去了，我怎么知道原来的两个数是什么啊！然后再仔细分析一下后，发现手上的和所能拆成的几种组合中，每一种组合的积 都不能直接反推出组合，换句话说，和所拆解的每一种组合的积 都能再分解成多种组合（也就是积有多组解），可以考虑这样一种过滤方式：在A1——multiResultOfSum的基础上，遍历它的每一种组合，对一种组合（m,n）求和后，把和拆分成多组解，如果这个多组解的每一个组合都包含在A2——multiResultOfProduct之中（即组合的积有多组解），才认为组合（m,n）符合条件，将满足条件的组合集合记为A3，相应的代码如下：
// ArrayList<Result> A3 = getA3(multiResultOfSum, multiResultOfProduct); System.out.println("A3---其和所能拆解成的组合都包含于A2---"+A3.size()+"\n"+A3); private static ArrayList<Result> getA3(ArrayList<Result> multiResultOfSum, ArrayList<Result> multiResultOfProduct) { ArrayList<Result> list = new ArrayList(); for (Result item:multiResultOfSum) { int sum = item.getNum1() + item.getNum2(); ArrayList<Result> splitOfSum = splitSum(sum); // if(multiResultOfProduct.containsAll(splitOfSum)){ list.add(item); } } return list; }打印如下，即由条件1和条件2可推测实际组合是下面的145种之一：
A3---其和所能拆解成的组合都包含于A2---145 [(2 9), (2 15), (2 21), (2 25), (2 27), (2 33), (2 35), (2 39), (2 45), (2 51), (3 8), (3 14), (3 20), (3 24), (3 26), (3 32), (3 34), (3 38), (3 44), (3 50), (4 7), (4 13), (4 19), (4 23), (4 25), (4 31), (4 33), (4 37), (4 43), (4 49), (5 6), (5 12), (5 18), (5 22), (5 24), (5 30), (5 32), (5 36), (5 42), (5 48), (6 11), (6 17), (6 21), (6 23), (6 29), (6 31), (6 35), (6 41), (6 47), (7 10), (7 16), (7 20), (7 22), (7 28), (7 30), (7 34), (7 40), (7 46), (8 9), (8 15), (8 19), (8 21), (8 27), (8 29), (8 33), (8 39), (8 45), (9 14), (9 18), (9 20), (9 26), (9 28), (9 32), (9 38), (9 44), (10 13), (10 17), (10 19), (10 25), (10 27), (10 31), (10 37), (10 43), (11 12), (11 16), (11 18), (11 24), (11 26), (11 30), (11 36), (11 42), (12 15), (12 17), (12 23), (12 25), (12 29), (12 35), (12 41), (13 14), (13 16), (13 22), (13 24), (13 28), (13 34), (13 40), (14 15), (14 21), (14 23), (14 27), (14 33), (14 39), (15 20), (15 22), (15 26), (15 32), (15 38), (16 19), (16 21), (16 25), (16 31), (16 37), (17 18), (17 20), (17 24), (17 30), (17 36), (18 19), (18 23), (18 29), (18 35), (19 22), (19 28), (19 34), (20 21), (20 27), (20 33), (21 26), (21 32), (22 25), (22 31), (23 24), (23 30), (24 29), (25 28), (26 27)] -
条件3：孙膑（知道积的人）说：那我知道了。
首先明确一点，孙膑在获知条件1和条件2后，自行推导出了A1、A2和A3。
然后他看了看自己手上的积，就说自己知道了鬼谷子所选的两个数是什么，那么他是如何能断定的？可以先假设一种场景：孙膑在得知A3 以及手上的积的情况下，把积套入A3中的145种组合，看看有哪个组合相乘后能够得到自己手上的积，此时，如果他发现有多个组合相乘符合条件的话必然会一脸懵逼 无法从积倒推出真正的两个数，但是，实际情况是孙膑并没有一脸懵逼，而是淡定的倒推出了鬼谷子所选的两个数，说明他**必然是只能从145个组合中找出唯一一种相乘得到自己手上的积！**所以可以尝试遍历A3，找出其中积唯一的组合，代码如下：
ArrayList<Result> A4 = getA4(A3); System.out.println("A4---"+A4.size()+"\n"+A4); private static ArrayList<Result> getA4(ArrayList<Result> a3) { ArrayList<Result> list = new ArrayList(); //MySparseArray:可以认为是int作为key的Map，即HashMap<Integer, ArrayList<Result>> MySparseArray<ArrayList<Result>> mySparseArray = new MySparseArray<>(); for (Result item : a3) {//遍历A3 int product = item.getProduct(); ArrayList<Result> listOfProduct = mySparseArray.get(product); if(listOfProduct == null){ listOfProduct = new ArrayList(); } listOfProduct.add(item); mySparseArray.put(product, listOfProduct);//以乘积作为key存放 乘积相同的组合 } for (int i = 0; i < mySparseArray.size(); i++) {//遍历乘积及其对应的 组合list ArrayList<Result> results = mySparseArray.valueAt(i); System.out.println(mySparseArray.keyAt(i)+"---"+results); if(results.size() == 1 ){//找到积只有唯一解的组合，并记录 list.add(results.get(0)); } } return list; }各个乘积及其对应的组合打印如下，排除乘积有多组解的情况后，最后找到86个有唯一解的组合并记为A4（到这里，知道自己手上的积是哪个数的孙膑已经能从明确的积找到对应的组合了，但是处于上帝视角在上方俯瞰的我们并不知道孙膑的积是哪个数，所以此时对于我们来说仍然有86种可能性）：
18---[(2 9)] 24---[(3 8)] 28---[(4 7)] 30---[(2 15), (5 6)] 42---[(2 21), (3 14)] 50---[(2 25)] 52---[(4 13)] 54---[(2 27)] 60---[(3 20), (5 12)] 66---[(2 33), (6 11)] 70---[(2 35), (7 10)] 72---[(3 24), (8 9)] 76---[(4 19)] 78---[(2 39), (3 26)] 90---[(2 45), (5 18)] 92---[(4 23)] 96---[(3 32)] 100---[(4 25)] 102---[(2 51), (3 34), (6 17)] 110---[(5 22)] 112---[(7 16)] 114---[(3 38)] 120---[(5 24), (8 15)] 124---[(4 31)] 126---[(6 21), (9 14)] 130---[(10 13)] 132---[(3 44), (4 33), (11 12)] 138---[(6 23)] 140---[(7 20)] 148---[(4 37)] 150---[(3 50), (5 30)] 152---[(8 19)] 154---[(7 22)] 160---[(5 32)] 162---[(9 18)] 168---[(8 21)] 170---[(10 17)] 172---[(4 43)] 174---[(6 29)] 176---[(11 16)] 180---[(5 36), (9 20), (12 15)] 182---[(13 14)] 186---[(6 31)] 190---[(10 19)] 196---[(4 49), (7 28)] 198---[(11 18)] 204---[(12 17)] 208---[(13 16)] 210---[(5 42), (6 35), (7 30), (14 15)] 216---[(8 27)] 232---[(8 29)] 234---[(9 26)] 238---[(7 34)] 240---[(5 48)] 246---[(6 41)] 250---[(10 25)] 252---[(9 28)] 264---[(8 33), (11 24)] 270---[(10 27)] 276---[(12 23)] 280---[(7 40)] 282---[(6 47)] 286---[(11 26), (13 22)] 288---[(9 32)] 294---[(14 21)] 300---[(12 25), (15 20)] 304---[(16 19)] 306---[(17 18)] 310---[(10 31)] 312---[(8 39), (13 24)] 322---[(7 46), (14 23)] 330---[(11 30), (15 22)] 336---[(16 21)] 340---[(17 20)] 342---[(9 38), (18 19)] 348---[(12 29)] 360---[(8 45)] 364---[(13 28)] 370---[(10 37)] 378---[(14 27)] 390---[(15 26)] 396---[(9 44), (11 36)] 400---[(16 25)] 408---[(17 24)] 414---[(18 23)] 418---[(19 22)] 420---[(12 35), (20 21)] 430---[(10 43)] 442---[(13 34)] 462---[(11 42), (14 33)] 480---[(15 32)] 492---[(12 41)] 496---[(16 31)] 510---[(17 30)] 520---[(13 40)] 522---[(18 29)] 532---[(19 28)] 540---[(20 27)] 546---[(14 39), (21 26)] 550---[(22 25)] 552---[(23 24)] 570---[(15 38)] 592---[(16 37)] 612---[(17 36)] 630---[(18 35)] 646---[(19 34)] 660---[(20 33)] 672---[(21 32)] 682---[(22 31)] 690---[(23 30)] 696---[(24 29)] 700---[(25 28)] 702---[(26 27)] A4---86 [(2 9), (3 8), (4 7), (2 25), (4 13), (2 27), (4 19), (4 23), (3 32), (4 25), (5 22), (7 16), (3 38), (4 31), (10 13), (6 23), (7 20), (4 37), (8 19), (7 22), (5 32), (9 18), (8 21), (10 17), (4 43), (6 29), (11 16), (13 14), (6 31), (10 19), (11 18), (12 17), (13 16), (8 27), (8 29), (9 26), (7 34), (5 48), (6 41), (10 25), (9 28), (10 27), (12 23), (7 40), (6 47), (9 32), (14 21), (16 19), (17 18), (10 31), (16 21), (17 20), (12 29), (8 45), (13 28), (10 37), (14 27), (15 26), (16 25), (17 24), (18 23), (19 22), (10 43), (13 34), (15 32), (12 41), (16 31), (17 30), (13 40), (18 29), (19 28), (20 27), (22 25), (23 24), (15 38), (16 37), (17 36), (18 35), (19 34), (20 33), (21 32), (22 31), (23 30), (24 29), (25 28), (26 27)] -
条件4:庞涓（知道和的人）说：那我也知道了
庞涓由前面的三个条件，也能推导出A1、A2、A3和A4，同时庞涓手上还有一个确定的和，然后他是如何确定鬼谷子选的两个数到底是哪个组合的？与上一步场景类似：庞涓也看了看手上的和，然后他把“和”套入A4，只找到了其中唯一一种组合相加能够得到手上的和，代码也与上一步类似，遍历A4，以和作为key存放 “和相同的组合List” ：
ArrayList<Result> A5 = getA5(A4);
System.out.println("A5---"+A5.size()+"\n"+A5);
private static ArrayList<Result> getA5(ArrayList<Result> a4) {
ArrayList<Result> list = new ArrayList();
HashMap<Integer, ArrayList<Result>> map = new HashMap<>();
for (Result item : a4) {
int sum = item.getNum1() + item.getNum2();
ArrayList<Result> listOfSum = map.get(sum);
if(listOfSum == null){
listOfSum = new ArrayList();
}
listOfSum.add(item);
map.put(sum, listOfSum);
}
map.forEach(new BiConsumer<Integer, ArrayList<Result>>() {
@Override
public void accept(Integer integer, ArrayList<Result> results) {
System.out.println(integer+"---"+results);
if(results.size() == 1 ){
list.add(results.get(0));
}
}
});
return list;
}
打印如下，86种组合中，和有唯一解的情况只有一种，就是17对应的[(4 13)]，这也就是真正的组合 鬼谷子所选的两个数：4和13 ！
17---[(4 13)]
35---[(3 32), (4 31), (6 29), (8 27), (9 26), (10 25), (12 23), (14 21), (16 19), (17 18)]
37---[(5 32), (6 31), (8 29), (9 28), (10 27), (16 21), (17 20)]
53---[(5 48), (6 47), (8 45), (10 43), (12 41), (13 40), (15 38), (16 37), (17 36), (18 35), (19 34), (20 33), (21 32), (22 31), (23 30), (24 29), (25 28), (26 27)]
23---[(4 19), (7 16), (10 13)]
41---[(3 38), (4 37), (7 34), (9 32), (10 31), (12 29), (13 28), (14 27), (15 26), (16 25), (17 24), (18 23), (19 22)]
11---[(2 9), (3 8), (4 7)]
27---[(2 25), (4 23), (5 22), (7 20), (8 19), (9 18), (10 17), (11 16), (13 14)]
29---[(2 27), (4 25), (6 23), (7 22), (8 21), (10 19), (11 18), (12 17), (13 16)]
47---[(4 43), (6 41), (7 40), (10 37), (13 34), (15 32), (16 31), (17 30), (18 29), (19 28), (20 27), (22 25), (23 24)]
A5---1
[(4 13)]
附：
-
MySparseArray：
import java.lang.reflect.Array; public class MySparseArray<E> implements Cloneable { private static final Object DELETED = new Object(); private boolean mGarbage = false; private int[] mKeys; private Object[] mValues; private int mSize; /** * Creates a new MySparseArray containing no mappings. */ public MySparseArray() { this(10); } /** * Creates a new MySparseArray containing no mappings that will not * require any additional memory allocation to store the specified * number of mappings. If you supply an initial capacity of 0, the * sparse array will be initialized with a light-weight representation * not requiring any additional array allocations. */ public MySparseArray(int initialCapacity) { if (initialCapacity == 0) { mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else { // mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mValues = new Object[initialCapacity]; mKeys = new int[mValues.length]; } mSize = 0; } @Override @SuppressWarnings("unchecked") public MySparseArray<E> clone() { MySparseArray<E> clone = null; try { clone = (MySparseArray<E>) super.clone(); clone.mKeys = mKeys.clone(); clone.mValues = mValues.clone(); } catch (CloneNotSupportedException cnse) { /* ignore */ } return clone; } /** * Gets the Object mapped from the specified key, or <code>null</code> * if no such mapping has been made. */ public E get(int key) { return get(key, null); } /** * Gets the Object mapped from the specified key, or the specified Object * if no such mapping has been made. */ @SuppressWarnings("unchecked") public E get(int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { return (E) mValues[i]; } } /** * Removes the mapping from the specified key, if there was any. */ public void delete(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } } /** * @hide * Removes the mapping from the specified key, if there was any, returning the old value. */ public E removeReturnOld(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { final E old = (E) mValues[i]; mValues[i] = DELETED; mGarbage = true; return old; } } return null; } /** * Alias for {@link #delete(int)}. */ public void remove(int key) { delete(key); } /** * Removes the mapping at the specified index. * * <p>For indices outside of the range <code>0...size()-1</code>, * the behavior is undefined.</p> */ public void removeAt(int index) { if (mValues[index] != DELETED) { mValues[index] = DELETED; mGarbage = true; } } /** * Remove a range of mappings as a batch. * * @param index Index to begin at * @param size Number of mappings to remove * * <p>For indices outside of the range <code>0...size()-1</code>, * the behavior is undefined.</p> */ public void removeAtRange(int index, int size) { final int end = Math.min(mSize, index + size); for (int i = index; i < end; i++) { removeAt(i); } } private void gc() { // Log.e("MySparseArray", "gc start with " + mSize); int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i < n; i++) { Object val = values[i]; if (val != DELETED) { if (i != o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } mGarbage = false; mSize = o; // Log.e("MySparseArray", "gc end with " + mSize); } /** * Adds a mapping from the specified key to the specified value, * replacing the previous mapping from the specified key if there * was one. */ public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] = value; } else { i = ~i; if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) { gc(); // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } mKeys = insert(mKeys, mSize, i, key); mValues = insert(mValues, mSize, i, value); mSize++; } } public static int[] insert(int[] array, int currentSize, int index, int element) { assert currentSize <= array.length; if (currentSize + 1 <= array.length) { System.arraycopy(array, index, array, index + 1, currentSize - index); array[index] = element; return array; } int[] newArray = new int[growSize(currentSize)]; System.arraycopy(array, 0, newArray, 0, index); newArray[index] = element; System.arraycopy(array, index, newArray, index + 1, array.length - index); return newArray; } public static <T> T[] insert(T[] array, int currentSize, int index, T element) { assert currentSize <= array.length; if (currentSize + 1 <= array.length) { System.arraycopy(array, index, array, index + 1, currentSize - index); array[index] = element; return array; } @SuppressWarnings("unchecked") T[] newArray = newUnpaddedArray((Class<T>)array.getClass().getComponentType(), growSize(currentSize)); System.arraycopy(array, 0, newArray, 0, index); newArray[index] = element; System.arraycopy(array, index, newArray, index + 1, array.length - index); return newArray; } public static <T> T[] newUnpaddedArray(Class<T> clazz, int minLen) { // return (T[])VMRuntime.getRuntime().newUnpaddedArray(clazz, minLen); return (T[])Array.newInstance(clazz,minLen); } public static int growSize(int currentSize) { return currentSize <= 4 ? 8 : currentSize * 2; } /** * Returns the number of key-value mappings that this MySparseArray * currently stores. */ public int size() { if (mGarbage) { gc(); } return mSize; } /** * Given an index in the range <code>0...size()-1</code>, returns * the key from the <code>index</code>th key-value mapping that this * MySparseArray stores. * * <p>The keys corresponding to indices in ascending order are guaranteed to * be in ascending order, e.g., <code>keyAt(0)</code> will return the * smallest key and <code>keyAt(size()-1)</code> will return the largest * key.</p> * * <p>For indices outside of the range <code>0...size()-1</code>, * the behavior is undefined.</p> */ public int keyAt(int index) { if (mGarbage) { gc(); } return mKeys[index]; } /** * Given an index in the range <code>0...size()-1</code>, returns * the value from the <code>index</code>th key-value mapping that this * MySparseArray stores. * * <p>The values corresponding to indices in ascending order are guaranteed * to be associated with keys in ascending order, e.g., * <code>valueAt(0)</code> will return the value associated with the * smallest key and <code>valueAt(size()-1)</code> will return the value * associated with the largest key.</p> * * <p>For indices outside of the range <code>0...size()-1</code>, * the behavior is undefined.</p> */ @SuppressWarnings("unchecked") public E valueAt(int index) { if (mGarbage) { gc(); } return (E) mValues[index]; } /** * Given an index in the range <code>0...size()-1</code>, sets a new * value for the <code>index</code>th key-value mapping that this * MySparseArray stores. * * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined.</p> */ public void setValueAt(int index, E value) { if (mGarbage) { gc(); } mValues[index] = value; } /** * Returns the index for which {@link #keyAt} would return the * specified key, or a negative number if the specified * key is not mapped. */ public int indexOfKey(int key) { if (mGarbage) { gc(); } return ContainerHelpers.binarySearch(mKeys, mSize, key); } /** * Returns an index for which {@link #valueAt} would return the * specified key, or a negative number if no keys map to the * specified value. * <p>Beware that this is a linear search, unlike lookups by key, * and that multiple keys can map to the same value and this will * find only one of them. * <p>Note also that unlike most collections' {@code indexOf} methods, * this method compares values using {@code ==} rather than {@code equals}. */ public int indexOfValue(E value) { if (mGarbage) { gc(); } for (int i = 0; i < mSize; i++) { if (mValues[i] == value) { return i; } } return -1; } /** * Returns an index for which {@link #valueAt} would return the * specified key, or a negative number if no keys map to the * specified value. * <p>Beware that this is a linear search, unlike lookups by key, * and that multiple keys can map to the same value and this will * find only one of them. * <p>Note also that this method uses {@code equals} unlike {@code indexOfValue}. * @hide */ public int indexOfValueByValue(E value) { if (mGarbage) { gc(); } for (int i = 0; i < mSize; i++) { if (value == null) { if (mValues[i] == null) { return i; } } else { if (value.equals(mValues[i])) { return i; } } } return -1; } /** * Removes all key-value mappings from this MySparseArray. */ public void clear() { int n = mSize; Object[] values = mValues; for (int i = 0; i < n; i++) { values[i] = null; } mSize = 0; mGarbage = false; } /** * Puts a key/value pair into the array, optimizing for the case where * the key is greater than all existing keys in the array. */ // public void append(int key, E value) { // if (mSize != 0 && key <= mKeys[mSize - 1]) { // put(key, value); // return; // } // // if (mGarbage && mSize >= mKeys.length) { // gc(); // } // // mKeys = GrowingArrayUtils.append(mKeys, mSize, key); // mValues = GrowingArrayUtils.append(mValues, mSize, value); // mSize++; // } /** * {@inheritDoc} * * <p>This implementation composes a string by iterating over its mappings. If * this map contains itself as a value, the string "(this Map)" * will appear in its place. */ @Override public String toString() { if (size() <= 0) { return "{}"; } StringBuilder buffer = new StringBuilder(mSize * 28); buffer.append('{'); for (int i=0; i<mSize; i++) { if (i > 0) { buffer.append(", "); } int key = keyAt(i); buffer.append(key); buffer.append('='); Object value = valueAt(i); if (value != this) { buffer.append(value); } else { buffer.append("(this Map)"); } } buffer.append('}'); return buffer.toString(); } } class EmptyArray { private EmptyArray() {} public static final boolean[] BOOLEAN = new boolean[0]; public static final byte[] BYTE = new byte[0]; public static final char[] CHAR = new char[0]; public static final double[] DOUBLE = new double[0]; public static final float[] FLOAT = new float[0]; public static final int[] INT = new int[0]; public static final long[] LONG = new long[0]; public static final Class<?>[] CLASS = new Class[0]; public static final Object[] OBJECT = new Object[0]; public static final String[] STRING = new String[0]; public static final Throwable[] THROWABLE = new Throwable[0]; public static final StackTraceElement[] STACK_TRACE_ELEMENT = new StackTraceElement[0]; public static final java.lang.reflect.Type[] TYPE = new java.lang.reflect.Type[0]; public static final java.lang.reflect.TypeVariable[] TYPE_VARIABLE = new java.lang.reflect.TypeVariable[0]; } class ContainerHelpers { // This is Arrays.binarySearch(), but doesn't do any argument validation. static int binarySearch(int[] array, int size, int value) { int lo = 0; int hi = size - 1; while (lo <= hi) { final int mid = (lo + hi) >>> 1; final int midVal = array[mid]; if (midVal < value) { lo = mid + 1; } else if (midVal > value) { hi = mid - 1; } else { return mid; // value found } } return ~lo; // value not present } static int binarySearch(long[] array, int size, long value) { int lo = 0; int hi = size - 1; while (lo <= hi) { final int mid = (lo + hi) >>> 1; final long midVal = array[mid]; if (midVal < value) { lo = mid + 1; } else if (midVal > value) { hi = mid - 1; } else { return mid; // value found } } return ~lo; // value not present } }