重构一个繁琐的数据结构

    在GIX4项目的开发过程中,遇到一个比较复杂的数据结构。复杂,是因为它有许多限制条件。我的工作是在现有系统中,添加新的功能,并在过程中重构部分旧代码。

约束及需求

    以下约束是系统中已经存在的必要的约束,不可绕开这些约束而进行代码的开发。

1.项目中,有许多的实体类,都含有一种多叉树的关系和逻辑。

2.这些实体的树型关系,在运行时,只有键的关系,而没有对应的实体引用关系。     由于GIX4是数据分析软件,数据量比较大。建立关系需要的时间比较久,所以服务器端只负责给数据。这样客户端得到的数据,只是一个简单的对象集合。

3.实体集合所有的更改对象位置只能使用一个特定的操作来实现排序:void Move(Object Item, Int32 index)。     这个约束产生的主要是原因是:一:使用了CSLA作为实现分布式应用的框架,所有实体集合,都需要继承BusinessListBase。而对这个集合中的实体进行操作,经常会引起该实体的状态的改变;二:目前的OpenExpressApp框架中,要求实体直接绑定到表示层,而不能对它进行转换,如使用“ViewModel”。当然,大量的数据处理,也要求了最好不要每次都对这些数据进行转换。

4.业务上要求,实体是可以进行排序操作的。(以下称为“逻辑序号”和“逻辑排序”。)这些序号将会持久化到数据库中。

5.集合中的对象,应该按照“逻辑序号”进行排序。(以下称为“物理序号”和“物理排序”)

6.树的每一个结点的孩子结点集合,也应该是按照“逻辑序号”进行物理排序。

7.以上的操作,全部在OpenExpressApp框架中实现,而非应用层。

原有代码

    一、树的结构的定义,已经在老系统中定义并被广泛使用。属于固化因素,不可修改。定义如下:

/// <summary>
/// 树形节点
/// </summary>
public interface ITreeNode
{
    /// <summary>
    /// 所有的孩子节点
    /// </summary>
    IList<ITreeNode> ChildrenNodes { get; }
    /// <summary>
    /// 这个节点对应的父级节点
    /// </summary>
    ITreeNode ParentNode { get; set; }

    /// <summary>
    /// 当前节点的键
    /// </summary>
    object Id { get; }
    /// <summary>
    /// 父节点的键
    /// </summary>
    object Pid { get; }
}

    这个接口表示的数据结构是树的结点,但是它受到上文中第2点约束的限制:当得到一个这个接口的实例时,它的Pid有值并指示出父节点的ID值,但是同时ParentNode却可能因为没有引用到实体,而为null。同样的,虽然这个节点有许多孩子节点,但是ChildrenNodes得到的集合却有可能是空集合。

    二、实体集合对象继承自GBusinessListBase<T,C>泛型集合,对它的元素的操作只有一个:Move(C item,int index)。

接口定义

    在原有代码的基础上,我先增加了以下几个接口,目的在于先把复杂的概念清晰化:

ISimpleMovableCollection.cs

/// <summary>
/// 一个有简单Move操作的集合
/// </summary>
internal interface ISimpleMovableCollection : ICollection
{
    /// <summary>
    /// 把oldIndex上对应位置的元素移动到newIndex上去。
    /// 目的位置上的和中间的所有元素,都向oldIndex的方向移动一个位置。
    /// </summary>
    /// <param name="oldIndex"></param>
    /// <param name="newIndex"></param>
    void Move(int oldIndex, int newIndex);
    /// <summary>
    /// 把item移动到newIndex上去。
    /// 目的位置上的和中间的所有元素,都向oldIndex的方向移动一个位置。
    /// </summary>
    /// <param name="item">本集合中的某一个元素</param>
    /// <param name="newIndex"></param>
    void Move(object item, int newIndex);
}
internal interface ISimpleMovableCollection<T> : ISimpleMovableCollection
{
    /// <summary>
    /// 把item移动到newIndex上去。
    /// 目的位置上的和中间的所有元素,都向oldIndex的方向移动一个位置。
    /// </summary>
    /// <param name="item"></param>
    /// <param name="newIndex"></param>
    void Move(T item, int newIndex);
}

    接口中的Move方法的定义,主要是来自原系统中的方法:GBusinessListBase<T,C>.Move()。 ISimpleMovableCollection 这个集合不同于下面列出的其它集合,它并不继承自IList。这是因为它除了Move以外,没有任何别的排序操作。而如果继承自IList,则同时会拥有Insert,Remove等方法。这里需要注意的是,虽然IList接口有IsReadOnly属性来判断是否是一个只读的集合,但是如果这个值为false,而Move操作却可以执行的话,逻辑上是不对的。所以该集合直接继承自ICollection。

    泛型的ISimpleMovableCollection同样也没有实现ICollection<T>,原因也是因为泛型的ICollection<T>也有更改集合的操作。

    另外,我在这里定义的这些集合,都是一个泛型和一个非泛型配合。这是因为代码的实现是在OpenExpressApp框架中,而在框架中实体类的操作有时候是针对泛型实体,有时候却针对非泛型实体。所以这里只好也把非泛型版本也一起定义了。

IOrderedObject.cs
/// <summary>
/// 有逻辑排序号的对象
/// </summary>
public interface IOrderedObject
{
    /// <summary>
    /// gs 逻辑排序号
     /// LogicIndex
    /// </summary>
    int OrderNo { get; set; }

    //event EventHandler OrderNoChanged;
}

    IOrderedObject 表示一个可以被逻辑排序的实体,可以直接设置它的逻辑排序号。这个序号也是最后会被持久化到数据库的值。这样在下次从数据库中取出时,可简单的根据逻辑号进行物理排序,减少了时间消耗。

IOrderedObjectCollection.cs
/// <summary>
/// 按排序号OrderNo进行逻辑排序的对象集合
/// </summary>
/// <typeparam name="T"></typeparam>
public interface IOrderedObjectCollection : IList
{
    /// <summary>
    /// g 下一个新的对象,可以使用这个排序号
    /// </summary>
    int NextOrderNo { get; }

    /// <summary>
    /// 把指定的节点上/下移
    /// </summary>
    /// <param name="node"></param>
    /// <param name="isUp"></param>
    void MoveNode(IOrderedObject node, bool isUp);
    /// <summary>
    /// 按照OrderNo进行排序
    /// </summary>
    void SortByOrderNo();
    /// <summary>
    /// 按照物理位置把所有的OrderNo设置好。
    /// </summary>
    void SetOrderNoByIndex();
}
public interface IOrderedObjectCollection<T> : IOrderedObjectCollection, IList<T>
    where T : IOrderedObject
{ }

    IOrderedObjectCollection<T>表示一IOrderedObject的集合。它不但负责维护逻辑序号,也负责维护物理位置。需要注意的是,这个集合的定义,与树的操作是没有任何关系的。

ITreeNodeCollection.cs
/// <summary>
/// 一般的遍历类型
/// </summary>
public enum TreeNodeTravelType
{
    /// <summary>
    /// 深度优先
    /// </summary>
    DepthFirst,
    /// <summary>
    /// 广度优先
    /// </summary>
    ScopeFirst
}
/// <summary>
/// TreeNode的集合
/// 
/// 里面的元素是贫血的树节点(ITreeNode:虽然有pid,却不一定有ParentNode对象。也就是说不一定有实体引用关系……)
/// </summary>
public interface ITreeNodeCollection : IList
{
    /// <summary>
    /// 是深度排序还是广度排序
    /// </summary>
    TreeNodeTravelType SortType { get; set; }

    /// <summary>
    /// 是否集合中的TreeNode已经按照关系进行排序
    /// </summary>
    bool Sorted { get; }
    /// <summary>
    /// 是否集合中的Node都已经按照Pid关联了ParenNode和ChildrenNodes
    /// </summary>
    bool ObjectRelationsRuilt { get; }

    /// <summary>
    /// 重新建立ParenNode和ChildrenNodes关联
    /// </summary>
    void RebuildObjectRelations();
    /// <summary>
    /// 保证建立了ParenNode和ChildrenNodes关联
    /// </summary>
    void EnsureObjectRelations();

    /// <summary>
    /// 按照SortType进行排序
    /// </summary>
    void SortByTree();
    /// <summary>
    /// 保证已经排序
    /// </summary>
    void EnsureSorted();

    /// <summary>
    /// 把指定的节点升/降级
    /// </summary>
    /// <param name="node"></param>
    /// <param name="isUp"></param>
    void ChangeNodeLevel(ITreeNode node, bool isUp);
    /// <summary>
    /// 以指定的节点为位置标准,添加一个新的节点。
    /// </summary>
    /// <param name="targetNode">作为位置标准的节点</param>
    /// <param name="insertAsChild">新的节点是否是targetNode的孩子节点。(如果不是,就算兄弟/同级节点。)</param>
    /// <param name="createAsChild">
    /// 如果是添加兄弟节点,true表示放在targetNode的前面,false则表示放在后面。
    /// 如果是添加孩子节点,true表示新的节点作为第一个孩子,false表示作为第后一个绩点
    /// </param>
    /// <returns></returns>
    ITreeNode CreateNode(ITreeNode targetNode, bool createAsChild, bool beforeFirst);
    /// <summary>
    /// 把指定的节点和它所有的子节点都加入集合中。
    /// </summary>
    /// <param name="node"></param>
    void AddNode(ITreeNode node, bool recursivlyAddChildren);

    /// <summary>
    /// 在列表中查找前一个兄弟节点
    /// </summary>
    /// <param name="node"></param>
    /// <returns></returns>
    ITreeNode FindPrevSibling(ITreeNode node);
    /// <summary>
    /// 在列表中查找后一个兄弟节点
    /// </summary>
    /// <param name="node"></param>
    /// <returns></returns>
    ITreeNode FindNextSibling(ITreeNode node);
    /// <summary>
    /// 查找所有根节点(没有父亲的节点)
    /// </summary>
    /// <returns></returns>
    ITreeNode[] FindRoots();
}
public interface ITreeNodeCollection<T> : ITreeNodeCollection, IList<T>
    where T : ITreeNode
{
}

    ITreeNodeCollection<T>集合是ITreeNode的集合。类似IOrderedObjectCollection<T>,这里也与IOrderedObject没任何关系。

    这个集合中的每一个ITreeNode,都可以在这个集合中找到它的所有的关系节点。在集合里面寻找,是因为ITreeNode.ParentNode和ITreeNode.ChildrenNodes并不一定会有实体引用。 看到方法FindRoots,大家应该想到,这个集合中并不一定只包含一棵树。

IOrderedTreeNodeCollection.cs
/// <summary>
/// 一个元素集合
/// 
/// 整合两套不同的模式:ITreeNodeCollection和IOrderedObjectCollection
/// </summary>
public interface IOrderedTreeNodeCollection :
    ITreeNodeCollection,
    IOrderedObjectCollection,
    IList
{
    /// <summary>
    /// 按照树的顺序重新给OrderNo赋值
    /// 这里对每个根节点使用深度遍历设置OrderNo。
    /// </summary>
    void SetOrderNoByTree();
    /// <summary>
    /// 保证 逻辑Index、物理Index 相等。
    /// 并且和树的递归顺序是一样的
    /// </summary>
    void EnsureIndices();
}
public interface IOrderedTreeNodeCollection<T> :
    IOrderedTreeNodeCollection,
    ITreeNodeCollection<T>,
    IOrderedObjectCollection<T>,
    IList<T>
    where T : IOrderedObject, ITreeNode
{
}

    IOrderedTreeNodeCollection<T>才是系统中要应用到的集合。集合中的元素一定是同时实现了IOrderedObject和ITreeNode接口。所以我们可以根据树来设计逻辑序号:SetOrderNoByTree。也有了操作:EnsureIndices。

部分实现代码

    首先,有树的遍历操作,自然先实现这个。这里使用两个静态方法对已经建立关系的树进行遍历,一个深度遍历使用栈,一个广度遍历使用队列。代码就不贴了,太占空间。

    下面这个GBusinessTreeListBase<T,T>类,继承自原来的GBusinessListBase<T, C>类。考虑到继承层次过深对性能的影响,所以在这个类中直接全部实现了前面的所有接口。但是却是逻辑分离的。先看代码:

    注意到,前面的接口,继承层次是这样的:

    但是GBusinessTreeListBase<T,T>类在实现全部接口时,逻辑上,可以简单理解为以下形式:

    其中,箭头方向,即是逻辑中的继承方向,也是实现中的依赖方向。在GBusinessTreeListBase<T,T>中每一个接口实现的Region中,都可以看成是一个简单的类。只不过是把它们整合到了一个类里。如下:

ISimpleMovableCollection<C> 实现:

IOrderedObjectCollection<C> 实现:

ITreeNodeCollection<C> 实现:

IOrderedTreeNodeCollection<C> 实现:

后话

    细心的读者可能会发现:IOrderedObjectCollection<T>实现中的的MoveNode方法调用了IOrderedTreeNodeCollection<T>实现中的MoveNode方法;本应该出来在ITreeNodeCollection<T>实现中CreateNode方法,却被放在了IOrderedObjectCollection<T>实现。

    谁能说出这是为什么吗?这还算是单向依赖的吗?:)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Modeng的专栏

Javascript数组系列三之你不了解的迭代2

今天我们来继续 Javascript 数组系列的文章,上文 《Javascript数组系列二之迭代方法1》 我们说到一些数组的迭代方法,我们在开发项目实战的过程...

14930
来自专栏JackeyGao的博客

关于Python的20个面试题

Python 是一个高级、解释型、交互式和面向对象的脚本语言. Python 语言设计具有高度可读性的, 使用一些常见的英语词组和其他语言常用的标点符号组成的语...

16410
来自专栏大闲人柴毛毛

Java8新特性——StreamAPI(一)

1. 流的基本概念 1.1 什么是流? 流是Java8引入的全新概念,它用来处理集合中的数据,暂且可以把它理解为一种高级集合。 众所周知,集合操作非常麻烦,若...

36690
来自专栏风口上的猪的文章

.NET面试题系列[10] - IEnumerable的派生类

IEnumerable分为两个版本:泛型的和非泛型的。IEnumerable只有一个方法GetEnumerator。如果你只需要数据而不打算修改它,不打算为集合...

12420
来自专栏JAVA高级架构

JAVA基础面试总结

1.00 什么时候使用基于接口编程? 基于接口编程、Fascade层等等抽象封装都是有开发和维护的代价的,是否使用归根结底还是要看团队人员的分工情况, 技术方...

35080
来自专栏LhWorld哥陪你聊算法

【Scala篇】--Scala中Trait、模式匹配、样例类、Actor模型

Scala Trait(特征) 相当于 Java 的接口,实际上它比接口还功能强大。

9720
来自专栏Java Web

《编写高质量代码》学习笔记(2)

写着写着发现简书提醒我文章接近字数极限,建议我换一篇写了。 ---- 建议52:推荐使用String直接量赋值 一般对象都是通过new关键字生成的,但是Str...

36940
来自专栏飞雪无情的博客

从Java到Golang快速入门

Golang从09年发布,中间经历了多个版本的演进,已经渐渐趋于成熟,并且出现了很多优秀的开源项目,比如我们熟知的docker,etcd,kubernetes等...

12330
来自专栏nnngu

经典Java面试题收集

2、访问修饰符public,private,protected,以及不写(默认)时的区别?

40980
来自专栏程序员互动联盟

【编程基础】聊聊C语言-兵马未动粮草先行(1)

上一篇我们讲的聊聊C语言-我的地盘我做主,相信大家对变量的存储类型和变量的作用域有了一定的了解。现在我们马上公布上期的答案如下: #include<stdio....

33880

扫码关注云+社区

领取腾讯云代金券