Clyde学习笔记二（CoordIntMap）
CoordIntMap是一个基类为Map数据结构，是存储游戏地图场景数据的基础数据结构，在应用中一共涉及到3个类，第一个自然是CoordIntMap，另外还有Coord和Cell，Cell定义在CoordIntMap中，是一个内部类。
?
Coord用一个int来表示和存储一个2D的坐标，在存储和表示之前分别需要encode和decode。
/** * Encodes the supplied coordinates (presumed to be in [-32768, +32767]) into a single * integer. */ public static int encode (int x, int y) { return (x << 16) | (y & 0xFFFF); } /** * Extracts the x component from the specified encoded coordinate pair. */ public static int decodeX (int pair) { return pair >> 16; } /** * Extracts the y component from the specified encoded coordinate pair. */ public static int decodeY (int pair) { return (pair << 16) >> 16; }?一个int类型有4个字节，前2个字节表示x坐标，后2个字节表示y坐标。取值范围从-32768一直到 +32767。
?
对于CoordIntMap，我们可以从它的定义中看到下面这2个接口，x、y是一个2D的坐标，显然CoordIntMap是一个以x、y2D坐标为key来存取对应的int值的这样一个map结构。
/** * Retrieves the value at the specified coordinates. */ public int get (int x, int y) { ... } /** * Sets the value at the specified coordinates. * * @return the previously stored value. */ public int put (int x, int y, int value) { .... }?但是它的内部存储是通过下面这个map来实现的
protected HashMap<Coord, Cell> _cells = new HashMap<Coord, Cell>();
?
?
可以看到，对外的接口与内部的存储方式并不一致，那么它是如何来转换这两者之间的差异的呢？
我们先来看一下CoordIntMap的构造函数：
/** * Creates a new coord int map. * * @param granularity the size of the top-level cells, expressed as a power of two (e.g., * 3 for a cell size of 8 by 8). * @param empty the value indicating the absence of an entry. */ public CoordIntMap (int granularity, int empty) { _granularity = granularity; _empty = empty; initTransientFields(); }?
我们注意一下granularity这个参数，它的中文意思是粒度，在这里是2的幂指数，用来指定Cell的矩阵大小，granularity值越大，Cell内包含的元素越多，粒度越小。
Cell的构造函数：
/** * Creates a new cell. */ public Cell () { _values = new int[1 << _granularity << _granularity]; Arrays.fill(_values, _empty); }?1 << _granularity << _granularity这个表达式的数学含义是4的_granularity次方。默认_granularity=3，初始化一个8x8的数组，并且初始化成空值。
?
Cell内部是用一个一维数组来表示和存储数据的，也就是说最终的数据都是存储在下面这个数组内的。
/** The values in the cell. */ protected int[] _values;?
那么，CoordIntMap是如何通过x、y这组2D坐标映射到_values数组中的值呢？我们来看一下get方法的具体实现：
?
/** * Retrieves the value at the specified coordinates. */ public int get (int x, int y) { Cell cell = getCell(x, y); return (cell == null) ? _empty : cell.get(x & _mask, y & _mask); } /** * Returns the cell corresponding to the specified coordinates. */ protected Cell getCell (int x, int y) { _coord.set(x >> _granularity, y >> _granularity); return _cells.get(_coord); }??
首先，x、y被映射成一个Coord，然后根据这个Coord的值在内部map中找到cell，最后再从cell中得到值。这里最重要的就是对x、y的映射算法，这也是整个数据结构的核心。
?
x >> _granularity, y >> _granularity翻译成数学语言是x除以2的_granularity次方，y除以2的_granularity次方。还记得前面提到过的对Cell构造函数的解释吗？每一个Cell都是一个2的_granularity次方 x(乘)?2的_granularity次方的结构，那么这里对x、y的映射是用来计算x、y所对应的value所在的Cell的坐标。
?
在得到Cell后如何再取得最终的值呢？在理解cell.get(x & _mask, y & _mask)这个表达式之前我们先来看下CoordIntMap构造函数中的调用的initTransientFields()这个方法。
?
/** * Initializes the transient fields. */ protected void initTransientFields () { _mask = (1 << _granularity) - 1; }?这个方法用来计算mask的值，我们刚才已经看到，这个mask在我们从Cell中取值会被用到。那么，在这里的这个表达式(1 << _granularity) - 1?我们已经比较熟悉了，数学含义就是2的_granularity次方-1。如果：
?
_granularity = 2， 那么1 << _granularity) - 1 = 3， 2进制值为 11_granularity = 3， 那么1 << _granularity) - 1 = 7， 2进制值为 111...?
我们回过头再来看表达式cell.get(x & _mask, y & _mask)，分别用mask对x、y做和的位运算，其数学含义等同于分别用2的_granularity次方除x、y取余，这样其实得到了x、y映射到Cell中的坐标。
?
为了更好的理解，特意编辑了2个实例示意图，相信大家都能理解。
?
?
既然CoordIntMap它是一个Map，那么它必然要提供一个接口供调用者来遍历每一个entry。CoordIntMap对外提供了这样的一个方法，它用一个Iterator来遍历内部的数据。
?
/** * Returns a set view of the map entries. */ public Set<CoordIntEntry> coordIntEntrySet () { return new AbstractSet<CoordIntEntry>() { public Iterator<CoordIntEntry> iterator () { return new Iterator<CoordIntEntry>() { ... }; } public int size () { return _size; } }; }?
Iterator的定义：
?
public Iterator<CoordIntEntry> iterator () { return new Iterator<CoordIntEntry>() {... public CoordIntEntry next () { checkConcurrentModification(); if (_centry == null) { _centry = _cit.next(); } while (true) { int[] values = _centry.getValue().getValues(); for (; _idx < values.length; _idx++) { int value = values[_idx]; if (value != _empty) { Coord coord = _centry.getKey(); _dummy.getKey().set( (coord.x << _granularity) | (_idx & _mask), (coord.y << _granularity) | (_idx >> _granularity)); _dummy._values = values; _dummy._idx = _idx; _idx++; _count++; return _dummy; } } _centry = _cit.next(); _idx = 0; } }... protected Iterator<Entry<Coord, Cell>> _cit = _cells.entrySet().iterator(); protected Entry<Coord, Cell> _centry; protected int _idx; protected int _count; protected int _omodcount = _modcount; protected CoordIntEntry _dummy = new CoordIntEntry(); };?
?这里只截取了next方法，展示了跟前相反的操作过程，即通过内部的存储数据来取得最初的x、y的值。这里最关键的两个表达式：
(coord.x << _granularity) | (_idx & _mask)
(coord.y << _granularity) | (_idx >> _granularity)
这两个表达式分别取得x、y的值然后存储为dummy中的key，这里的key虽然也是Coord类型，但含义跟我们前边看到的那个Coord完全不同，存储的直接是x、y的值
?
/** The coordinate key. */ protected Coord _key = new Coord();
?
?如果我们跑一下下面的这段代码
?
CoordIntMap map = new CoordIntMap();map.put(5, 7, 112);map.put(1, 3, 57);map.put(8, 6, 33);Set<CoordIntEntry> set = map.coordIntEntrySet();for (CoordIntEntry entry : set) {System.out.println("key: " + entry.getKey());System.out.println("value: " + entry.getValue());}?可以预期得到的输出为key: [1, 3]
?
value: 57key: [5, 7]value: 112key: [8, 6]value: 33
?
备注：本文中涉及到的位运算及其含义
1 << _granularity << _granularity
4的_granularity次方
?
x >> _granularity, y >> _granularity
x除以2的_granularity次方，y除以2的_granularity次方
?
?
(1 << _granularity) - 1
2的_granularity次方-1
?
?
x & _mask, y & _mask
2的_granularity次方除x、y取余
?
(coord.x << _granularity) | (_idx & _mask)
coord.x乘以2的_granularity次方加上_idx除以_mask取余
?
(coord.y << _granularity) | (_idx >> _granularity)
coord.y乘以2的_granularity次方加上_idx除以2的_granularity次方取整
?
?
后记：
CoordIntMap的实现中大量使用了位运算，这样做的目的主要是为了提高效率，毕竟这是一个基础性的数据结构，特别是在处理地图场景等大数据量的时候，效率还是比较关键的。其实类似的用法我们在JDK中也能看到，比如在HashMap中，通过hashcode定位数组index的取余方法JDK中是这样实现的：
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }?在这里，当length为2的幂时，h & (length-1)等价于h % length，但是前者的效率要高于后者。怎么样，这里的length - 1和CoordIntMap中的mask是否有异曲同工之妙呢？