首先,什么是Table,可以理解为前端使用的html table组件,它具有行头,列头,以及具体的数据.即描述有多少行,多少列,在行为X,列为Y的二维格子中所对应的值是多少.
在使用google guava组件同时,也在讨论其组件的一些局限性,比如它的不变性,对序列化支持的不友好等.
其中table就是一个例子,作为一个表格组件的后端对应数据结构,其自带的table实现完全不能满足实际的需要.其大部分实现都是不可变的,即意味着必须要使用类似builder的模式来进行创建,一旦创建好之后,就不能再次修改.那么,作为一个实际可用的table实现,它需要哪些特性呢.以下例出我们所需要的要求:
1. 查找 按行,按列,快速定位
2. 快速迭代,按行,按列,支持稀疏迭代
3. 泛型支持(通用化)
4. 支持排序
5. 行,列动态增长,削减
6. 反序列化支持(json)
也就是说,我们期望像使用java的集合一样,创建出相应的数据之后,一直都是可变的,并且可以随意地进行传递,然后再任意地进行处理.无论按行,按列,都能够很好地使用.
本篇即描述了如何实现这样一个table组件,以及它最终的效果.
已实现的github地址:https://github.com/flym/array-tree-table
1 选择存储方式
在标准的Table实现中,存储即如何来对相应的数据进行存储.数据指在行,列相交的格子中所存储的内容.按照与展现相同的处理方式,其有2种实现方式.分别为map存储和数组存储.
map存储,即采用Map<R,Map<C,V>>的实现方式,即双重map.以行(或列)作为第一个key,然后列作为第2个key,这样来描述整个表格结构.同时,在进行查找时,先通过行找到第一个map,再通过列找到相应的值.
缺点1,如果要基于列作为查找起始点,就很难,可能需要遍列整个map来实现.
缺点2,在序列化时,由于map序列化的原因,其会输出相应的key值,导致输出的json太大.比如 {key1:{c1:v1,c2:v2}}这样的处理方式
数组存储,采用V[][]的二维数组实现方式.其中这里的下标存储的是行或列在实现存储中的下标值,即需要一个额外的行,列下标转换对象.在查找时,先通过转换表查找到相应的下标,再通过下标直接进行定位即可.
如果是先列,后行的方式,也不存在问题,因为都是通过转换表来处理下标问题,无非就是数组下标处理.
缺点1,需要额外的行,列转换表.
在本实现当中,主要考虑到序列化问题,采用了二维数组来实现相应的存储,同时采用TreeMap来存储相应的下标映射.为什么使用TreeMap,是为了后续的排序作准备.
2 按行,按列,稀疏迭代
从之前的存储上,我们已经具有用于表示数据的二维数组,以及分别表示行和列的下标定义器.相应的结构可以如下所示:
/** 位置信息,存储当前下标 */
private TreeMap<R, Integer> rowIndex;
private TreeMap<C, Integer> columnIndex;
/** 实际存储的值 */
private V[][] innerV;
按行迭代
首先通过rowIndex获取到相应的下标.如果不存在,则表示没有此行,获取到行之后,再到innerV直接获取到该行的数据,后面直接迭代一维数据即可.迭代时跳过null数据即可.
搂列迭代
通过columnIndex获取到相应的下标,然后通过rowIndex.size快速判定行的长度,然后每次访问数据即可,类似v[0][x],v[1][x]这样的访问顺序.
稀疏迭代
所谓稀疏,即如一个100行*100列的数据,其实际的存储理可能才几百个,因为中间大量的空单元.为了处理这种情况,我们可以采取一个单独的位图来对有位置的格子进行记录,当相应的数据被设置时,即在相应的位图中进行记录即可.全程可以采用如下的数据来进行表示:
/** 存储的位置信息 */
private long[] bits;
private transient BitSet bitsSet;
上面的bits数组实际上为bitSet中原始的long型数组字段.在实现内部实现时采用bitSet与之相对应.
3 泛型化
从上面的定义可知,在处理时我们实际上已经采用R,C,V来分别表示行,列以及单元值信息.
4 支持排序
一般来讲,使用表格地方,除了界面上使用直接按原来的默认输出之外,在进行表格数据组织时,都是需要对行或对列进行排序.即行,列的顺序是有排序要求的.比如,按月的数据都必须按照自然月的顺序进行排序,而统计类的则按照统计指标进行处理.因此,在这个表格当中,我们使用了额外的排序器.
排序器用于控制行,列的位置,实际上最终反映到值上面就是相应的下标位.首先,使用TreeMap的rowIndex,让行的顺序是支持排序的,其值信息(即下标位),是实际按照innerV的下标位一一对应,即keySet的迭代顺序就是下标的顺序.如第一个key的下标位为0,其在行的顺序中也是第一位的.
因为排序,自然即会使用到指定的排序器,因此我们需要定义相应的行排序器,列排序器.如下代码所示:
private transient Comparator<? super R> rowComparator; private transient Comparator<? super C> columnComparator;
通过以上的排序器,在初始化rowIndex和columnIndex时,即传递相应的排序器即可,即这里我们在初始化TreeMap时使用带排序器的构造函数.
5 行列的动态增长和削减
当插入一个新行时(或者是一个新的rowKey),就会实际上在相应的数据中增加一个新的行.这里就会涉及到行的变量,主要涉及到行的定位和数据的迁移.
行定位,首先是通过rowIndex定位到新行应该存储的位置.这里我们使用的treeMap,其基于navigableMap特性,通过tailMap方法可以找到比插入rowKey更大的subMap,并且通过相应的firstEntry可以找到当前rowKey应该被插入的下标位.其值就是当前rowKey应该放的行数.其相应的代码描述可以如下所示:
NavigableMap<R, Integer> tailMap = rowIndex.tailMap(rowKey, false);
Integer putIndex = tailMap.isEmpty() ? rowSize : tailMap.firstEntry().getValue();
位置确定即有2种可能,要么比之前rowIndex的数据都大,那么当前值就放到最后一位.否则就放到原来比插入值更大的值的位置上,原来的数据被迁移.比如rowKey分别为 a b d,其中d的下标为2,那么插入rowKey为c时,则c的下标为原来d的下标位2,而d的下标位则变更为3,并进行数据迁移.
数据迁移,则需要根据行和列的不同分别进行处理.如果是行,则通过system.arrayCopy直接以相应的putIndex位分别将前面部分和后面部分copy至新的数组中即可.
如果是列,则需要每一行都进行迁移,在具体迁移时可以进行一些空间上的处理.如指定的行原来只在第0位存储了数据,如果要迁移下标位2以上的数据,则此行可以进行跳过,即不需要迁移.
与增长相对应的则是行列的消减,即由于delete的原因,导致某一行(列)的数据都被删除完毕,则该行(列)就应该从相应的数据中被移除掉.在处理时,采取与增长相对应的逆操作即可.
整个与数据处理的代码可以由下面的方法签名来描述:
/** 增长行,同时迁移之前相应的下标位 */
private Integer _incRow(R rowKey) {}
/** 减少行, 迁移相应的下标位 */
private void _decRow(R rowKey, int rowIdx) {}
/** 将指定的数组增长至指定位数 */
private V[] _incArray(V[] vv, int size) {}
/** 增长列,同时迁移相应的下标位 */
private Integer _incColumn(C columnKey) {}
/** 减少列,迁移下标位 */
private void _decColumn(C columnKey, int columnIdx) {}
有一点麻烦的就是,由于之前我们采用了bits来描述位图信息,因此在整个处理中,我们还需要处理bits信息.即在整个处理中,要处理3个数据, xIndex下标数据,innerV值信息,以及bits位图信息.
6 序列化和反序列化
由上面的元素定义可知,由于都是采用了基本对象和集合,因此在进行序列化时不需要作任何的处理,相应的json序列化框架都可以正常的序列化.惟一需要处理即是反序列化信息.
类型信息的确定
由于在反序列化时,默认情况下对象的创建即是其默认的构建函数,因此在内部相应的类型信息都需要由外部传入,并且在初始化时正确使用相应的类型来描述相应的对象信息.即对于innerV对象,我们不能在进行创建时使用Object类型来代替,也不能在直接new V[][]这样的语法.为解决此问题,定义了3个类型信息来分别描述相应的行,列,值类型.如下所示:
private Class<R> rowClass;
private Class<C> columnClass;
private Class<V> valueClass;
同时,分别定义了无参构造函数和有参构造,分别用于传入相应的类型信息来确定值信息.
因为,传入了类型信息,在进行相应数据的构造时,就可以采用类型信息来正确的创建起数据元素.如innerV就可以采用Array.newInstance 这样的方式来进行对象创建,只需要传入相应的类型即可.
行,列排序器的确定
与类型信息确定相一致,在创建内部的treeMap时,反序列化器也一般即调用相应的无参构建,这样就不能采用内部使用的排序器了.这里需要修改其对于字段值的初始化或者是反序列化处理方式.首先,与类型相一致,这里采用了用于创建排序器的类型器,用于最终创建起排序器.相应的代码如下所示:
private Class<Comparator<R>> rowComparatorClass;
private Class<Comparator<C>> columnComparatorClass;
在确定了排序器的类,就可以使用class.newInstance使用默认构造器来创建排序器.通常来说,排序器也是采用无参构造函数来初始化的.
正确的序列化过程和反序列化过程
因为要正确地创建起rowIndex,我们需要保证先提到相应的rowClass和相应的rowComparatorClass.这里就需要保证在反序列化时先处理前面的信息,得到相应的数据后再来处理此类.根据json流式地反序列化处理方式,我们可以参考在序列化时提供指定的顺序,让其生成的json中数据的排列是有顺序的,这样在反序列化时就可以通过先后顺序保证前面的class类先进行处理了.
在fastjson中,可以使用JSONField传递ordinal数据来影响顺序;在jackson中,可以使用JsonPropertyOrder来确定顺序.
调整对象的初始化
有了以上的信息,在不同的json框架中,我们都可以通过提供对应类型的deserializer来实现定制的反序列化.其目的还是在于正确地创建起相应的字段实例,相应的实例可以参考源码中的ArrayTreeTableDeserializer来进行了解.
7 框架无关性
在整个实现中,虽然我们在ArrayTreeTable上加了一些注解,但并不表示在实际使用时就必须与相应的框架进行绑定.按照java的注解处理协议,如果在当前系统中读取注解时,如果相应的注解不能正确地被解析或实例化,则会忽略此注解.
可以这样认为,如果你使用jackson,那么在类中fastjson的注解,在使用时可以忽略,就相当于它不存在一样.
结论
本实现专注于很好地实现一个table组件,对于一些性能上的指标没有经过测试,针对于一个自实现table的开发方向.并且经过相应的测试用例(ArrayTreeTableTest),至少正确地使用在项目中是没有任何问题的.
源码开放,可以任意进行修改和使用.
访问地址:https://github.com/flym/array-tree-table
转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/201606200002.html