joda-collection 之 Grid解析

joda-collection官网说明了是提供jdk和guava之外的collection操作，所以提供了Grid操作；
Grid顾名思义就是网格的意思，也就是有个(x,y)坐标确定一个元素；

如何引入

现在基本都是采用maven构建方式，在需要的项目pom中添加依赖：

<dependency>
  <groupId>org.joda</groupId>
  <artifactId>joda-collect</artifactId>
  <version>0.7</version>
</dependency>

源码解析

继承关系

• Grid定义为接口，AbstractGrid为实现该接口的抽象类
• DenseGrid，ImmutableGrid（抽象类），SparseGrid均实现了AbstractGrid抽象类
• DenseImmutableGrid，EmptyGrid，SingletonGrid，SparseImmutableGrid实现了Immutable抽象类
• 其中AbstractGrid，DenseImmutableGrid，EmptyGrid，SingletonGrid和SparseImmutableGrid为包访问权限

看代码

ImmutableGrid的copyOf方法

该方法为从grid获取到具有immutable的grid

public static <R> ImmutableGrid<R> copyOf(Grid<R> grid) {
    if (grid == null) {
        throw new IllegalArgumentException("Grid must not be null");
    }
    if (grid instanceof ImmutableGrid) {
        return (ImmutableGrid<R>) grid;
    }
    validateCounts(grid.rowCount(), grid.columnCount
    if (grid.size() == 0) {
        return new EmptyGrid<R>(grid.rowCount(), grid.columnCount());
    }
    if (grid.size() == 1) {
        Cell<R> cell = grid.cells().iterator().next();
        return new SingletonGrid<R>(grid.rowCount(), grid.columnCount(), cell);
    }
    if (grid.size() >= (grid.rowCount() * grid.columnCount() / 2)) {
        return DenseImmutableGrid.create(grid);
    }
    return new SparseImmutableGrid<R>(grid);
}

• 如果grid为空的，那么返回EmptyGrid；其实返回这个用处不大，本来就是个immutable的，不能往里插数据
• 如果grid所持有的对象个数为1，那么返回的是SingletonGrid；
• 如果grid所持有的对象个数大于等于grid总大小的一般，就用DenseImmutableGrid（非稀疏的不可变grid），否则返回的是SparseImmutableGrid（稀疏的不可变grid）

关于稀疏（dense）grid和非稀疏(sparse)grid

两者的区别在于存储的方式不同：dense采用的的数组的方式存储信息，而sparse采用SortedSet<Cell<V>>来作为存储结构；下边先介绍Cell是什么玩意

Cell接口是Grid的一个内部接口，MutableCell和ImmutableCell采用相同的存储结构且都实现AbstractCell抽象类，存储结构为row，column，value

接下来看看SparseGrid的实现

    private final int rowCount;
    private final int columnCount;
    private final SortedSet<Cell<V>> cells;
    public static <R> SparseGrid<R> create(int rowCount, int columnCount) {
        return new SparseGrid<R>(rowCount, columnCount, new TreeSet<Cell<R>>(AbstractCell.<R>comparator()));
    }

首先，通过SortedSet来存储，在creat方法中可以看到，实际采用的是SortedSet的实现类TreeSet来存储；然后存储总行数和总列数；为什么不直接声明为TreeSet来存储呢，主要是为了扩展性考虑，面向接口编程嘛；对于稀疏的采用Set来存储而不是数组，可以节省存储空间

AbstractCell实现了Comparator接口，利用row和column来进行排序；

cell(int row, int column)方法来获取指定的cell

@Override
public Cell<V> cell(int row, int column) {
    if (exists(row, column)) {
        SortedSet<Cell<V>> tail = cells.tailSet(finder(row, column));
        if (tail.size() > 0) {
            Cell<V> cell = tail.first();
            if (cell.getRow() == row && cell.getColumn() == column) {
                return cell;
            }
        }
    }
    return null;
}

@Override
public boolean exists(int row, int column) {
    return row >= 0 && row < rowCount() && column >= 0 && column < columnCount();
}

通过SortedSet来查询具体的cell；

再来看看DenseGrid

private final int rowCount;
private final int columnCount;
private int size;
private final V[] values;

从代码里看出，采用的是数组的存储方式，因为当数据比较稠密的时候，浪费的空间的少量的，这种方式相比较SparseGrid，效率会高，实现比较简单；

public static <V> DenseGrid<V> create(int rowCount, int columnCount) {
    return new DenseGrid<V>(rowCount, columnCount);
}
private DenseGrid(int rowCount, int columnCount) {
    validateCounts(rowCount, columnCount);
    this.rowCount = rowCount;
    this.columnCount = columnCount;
    this.values = (V[]) new Object[rowCount * columnCount];
}

代码里可以看出来，最开始构造方法就已经分配了最大容量的数组；

@Override
public V get(int row, int column) {
    if (exists(row, column)) {
        return values[row * columnCount + column];
    }
    return null;
}

@Override
public Cell<V> cell(int row, int column) {
    V value = get(row, column);
    return (value != null ? ImmutableCell.of(row, column, value) : null);
}

从get的代码可以看出来，就是简单的数组下标定位，效率非常高；其他一些需要get的操作都是通过数组下标的方式来做的，例如public List<V> column(int column)和public List<V> row(int row)等方法；

总结下，稀疏Grid和非稀疏Grid最大的区别就是以时间换空间还是以空间换时间的问题；通过不同的存储结构来实现；

---

总结

• 从Grid的源码分析来看，执行效率还是不错的
• Grid的使用场景还是有一些的，比如一些业务场景中的需要多个map来实现的业务逻辑，可以考虑Grid的实现方式，看看哪种实现方式更方便及效率更高；