2024年1月

前言

在最近的项目中经常会对C#中的数据进行排序,对于基本数据类型,其排序方式比较简单,只需要调用内置算法即可实现,但对于
自定义数据类型
以及
自定义排序规则
的情况实现起来就比较麻烦,所以在本文章中将详细介绍一下在中C#中如何对数据进行排序。

应用技术:
LINQ; Array.Sort();

1. 常规数据排序

1.1 使用Sort排序

对于系统内置数据,我们可以使用
Sort
方法直接进行排序,默认是采用正序进行排序,此处提供了三种方式:

  • 方式一:使用默认的
    Sort()
    方法直接就可以进行排序。
  • 方式二:使用
    Sort()
    方法并添加回调函数,回调函数调用数据类型
    CompareTo()
    方法。
  • 方式三:使用
    Sort()
    方法并添加回调函数,回调函数进行自定义,此处采用三目运算符写了个简单的方法。
static void test_general_sort()
{
    int[] data = { 89, 63, 48, 62, 75, 663, 45, 359, 42 };
    // 1. 方式一
    Array.Sort(data);
    // 2. 方式二
    Array.Sort(data, (x, y) => x.CompareTo(y));
    // 3. 方式三
    Array.Sort(data, (x, y) => x > y ? 1 : -1);
    print_array(data);
}

程序输出

如果是想进行逆序排序,最简单的方式就是将正序排列的数组进行一次反转即可,不然的话就是改变方法二以及方法三的回调函数输出,如下面代码所示。

static void test_general_sort_()
{
    int[] data = { 89, 63, 48, 62, 75, 663, 45, 359, 42 };
    // 1. 方式一
    Array.Sort(data);
    Array.Reverse(data);
    // 2. 方式二
    Array.Sort(data, (x, y) => y.CompareTo(x));
    // 3. 方式三
    Array.Sort(data, (x, y) => x > y ? -1 : 1);
    print_array(data);
}

程序输出

1.2 使用LINQ语句进行排序

然后我们介绍一下使用LINQ语句进行排序,LINQ是一组用于C#和Visual Basic语言的扩展。它允许编写C#或者Visual Basic代码以查询数据库相同的方式操作内存数据。在此处我们可以使用两种方式实现:

  • 方式一:使用原生的LINQ语句进行查询,此处主要通过自己写LINQ语句;
  • 方式二:使用封装好的方法
    OrderBy()
    ,该方法使用比较简单,可以直接调用对应大方法即可。
static void test_general_linq()
{
    int[] data = { 89, 63, 48, 62, 75, 663, 45, 359, 42 };
    // 1. 方式一
    IEnumerable<int> query = from d in data
                             orderby d
                             select d;
    // 2. 方式二
    query = data.OrderBy(x => x);
    print_array(query);
}

如果要项进行逆序排序,此处可以添加
descending
关键字进行设定,或者直接使用
OrderByDescending()
方法。

static void test_general_linq_()
{
    int[] data = { 89, 63, 48, 62, 75, 663, 45, 359, 42 };
    // 1. 方式一
    IEnumerable<int> query = from d in data
                             orderby d descending
                             select d;
    // 2. 方式二
    query = data.OrderByDescending(x => x);
    print_array(query);
}

1.3 多条件排序

在实际使用时,我们可能会遇到多条件排序,即第一个条件相等时时,在采用第二个条件排序,如果遇到这种情况,我们处理起来可能就比较麻烦。如下面代码所示,对于一个字符串数组,我想首先按照字符串长度进行排序,如果字符串长度相等,就按照首字母进行排序。实现方式如下所示:

static void test_general_sort_more()
{
    string[] words = { "the", "quick", "brown", "fox", "jumps", "and" };
    Array.Sort<string>(words, (x, y) =>
    {
        if (x.Length > y.Length) { return 1; }
        else if (x.Length == y.Length)
        {
            if (x.Substring(0, 1)[0] > y.Substring(0, 1)[0]) { return 1; }
            else { return -1; }
        }
        else { return -1; }
    });
    print_array(words);
}

在上面这段代码中,我们主要是使用了
Lambda
表达式创建了一个委托函数,在这个委托函数里,我们按照排序要求,对其进行了定义,主要是对返回值的条件进行了定义,最后排序结果输出为:

Array = {the, quick, brown, fox, jumps, and}
Array = {and, fox, the, brown, jumps, quick}

不过该方式看起来实现是比较复杂的,对于大多是人来说,可能很难看懂,所以此处我们向大家展示一个比较简单的方式,就是使用LINQ语句进行多条件排序,如下面代码所示:

static void test_general_linq_more()
{
    string[] words = { "the", "quick", "brown", "fox", "jumps", "and" };
    // 1. 方式一
    IEnumerable<string> query = from word in words
                                orderby word.Length, word.Substring(0, 1)
                                select word;
    // 2. 方式二
    query = words.OrderBy(x => x.Length).ThenBy(x => x.Substring(0, 1));
    print_array(query);
}

使用LINQ语句进行排序看起来就比较简单了,上面依旧是展示了两种方式,对于多条件排序,如果使用自定义LINQ语句排序就只需要在上一个条件后增加次要条件即可;如果使用封装后的LINQ语句,就可以在
OrderBy()
增加
ThenBy()
方法添加第二个条件。如果想实现反向排序,实现方式与上文相同。

2. 自定义数据排序

下面我们进行自定义数据进行排序,如下面代码所示,我们在此处定义了一个
Person
类,并且继承了
IComparable<Person>
接口,该接口主要是用于后面调用
Sort
方法所必需的接口。

class Person : IComparable<Person>
{
    public string name { get; set; }
    public int age { get; set; }
    public int id { get; set; }

    public int CompareTo(Person? other)
    {
        if (this.age > other.age) { return 1; }
        else { return -1; }
    }
    public override string ToString()
    {
        return "(id: " + id + ", name: " + name + ", age: " + age + ")";
    }
};

2.1 使用Sort排序

对于自定义数据,我们可以使用
Sort
方法直接进行排序,默认是采用正序进行排序,此处提供了三种方式:

  • 方式一:使用默认的
    Sort()
    方法直接就可以进行排序,但是需要自定义数据继承
    IComparable<T>
    接口
  • 方式二:使用
    Sort()
    方法并添加回调函数,回调函数调用数据类型
    CompareTo()
    方法,该方法可以进行自定义。
  • 方式三:使用
    Sort()
    方法并添加回调函数,回调函数进行自定义,此处采用三目运算符写了个简单的方法,该方式无需继承继承
    IComparable<T>
    接口以及在自定义数据中添加比较函数。

代码如下所示:

static void test_person_sort()
{
    List<Person> list = new List<Person>()
    {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);

    // 1. 方式一
    list.Sort();
    // 2. 方式二
    list.Sort((x, y) => x.CompareTo(y));
    // 3. 方式三
    list.Sort((x, y) => x.age > y.age ? 1 : -1);

    print_array(list);

}

排序后结果输出为:

程序输出

如果想进行逆序排序,需要修改一下比较规则

static void test_person_sort_()
{
    List<Person> list = new List<Person>()
    {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);

    // 1. 方式一
    list.Sort((x, y) => y.CompareTo(x));
    // 2. 方式二
    list.Sort((x, y) => x.age > y.age ? -1 : 1);

    print_array(list);

}

逆序排序后的输出为

程序输出

2.2 使用LINQ语句进行排序

接下来介绍一下使用LINQ语句进行排序,LINQ是一组用于C#和Visual Basic语言的扩展。它允许编写C#或者Visual Basic代码以查询数据库相同的方式操作内存数据。在此处我们可以使用两种方式实现:

  • 方式一:使用原生的LINQ语句进行查询,此处主要通过自己写LINQ语句;在使用时要注意一点,如果自定义数据继承
    IComparable<T>
    接口,那么该数据在比较时会自动调用该数据类的比较方法进行比较,如果未继承该接口,就需要在输入时指定该数据类型使用哪种数据进行比较,如下文代码中,我们使用了
    d.age
    属性进行数据比较。
  • 方式二:使用封装好的方法
    OrderBy()
    ,该方法使用比较简单,可以直接调用对应的方法即可,注意事项跟使用原生的LINQ语句一致。
static void test_person_linq()
{
    List<Person> list = new List<Person>()
            {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);
    // 1. 方式一
    IEnumerable<Person> query = from d in list
                                orderby d.age
                                select d;
    // 2. 方式二
    query = list.OrderBy(x => x.age);
    print_array(query);
}

如果想进行逆序排序,只需要添加
descending
关键字进行设定,或者直接使用
OrderByDescending()
方法。

static void test_person_linq_()
{
    List<Person> list = new List<Person>()
            {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);
    // 1. 方式一
    IEnumerable<Person> query = from d in list
                                orderby d.age descending
                                select d;
    // 2. 方式二
    query = list.OrderByDescending(x => x.age);
    print_array(query);
}

2.3 多条件排序

在实际使用时,我们可能会遇到多条件排序,即第一个条件相等时时,在采用第二个条件排序,如果遇到这种情况,我们处理起来可能就比较麻烦,对于自定义数据,如果我们在定义数据时继承
IComparable<T>
接口,并在接口方法中自定义排序要求即可。在下面中我们提供了一种使用
Sort()
接口并利用委托函数定义比较规则来实现数据排序,代码如下所示:

static void test_person_sort_more()
{
    List<Person> list = new List<Person>()
            {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);
    list.Sort((x, y) => {
        if (x.age > y.age) { return 1; }
        else if (x.age == y.age)
        {
            if (x.id > y.id) { return 1; }
            else { return -1; }
        }
        else { return -1; }
    });

    print_array(list);

}

如果想进行逆序排序,只需要修改一下相关的比较条件即可,逆序排序代码如下所示:

static void test_person_sort_more_()
{
    List<Person> list = new List<Person>()
            {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);
    list.Sort((x, y) => {
        if (y.age > x.age) { return 1; }
        else if (y.age == x.age)
        {
            if (y.id > x.id) { return 1; }
            else { return -1; }
        }
        else { return -1; }
    });

    print_array(list);
}

通过上面代码我们可以看出使用除了可以使用
Sort()
接口是比较复杂的,其中的比较过程需要我们自己定义。下面我们将介绍使用LINQ语言进行多条件排序,当我们使用原生的LINQ语句时,在进行自定义数据比较时,需要声明所选择的对象的属性,并且按照先后顺序进行排序即可;如果使用封装后的LINQ语句,可以使用
OrderBy()
以及
ThenBy()
分别指定条件,在添加条件时,要生命比较的对象属性。代码如下所示:

static void test_person_linq_more()
{
    List<Person> list = new List<Person>()
            {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);
    // 1. 方式一
    IEnumerable<Person> query = from d in list
                                orderby d.age, d.id
                                select d;
    // 2. 方式二
    query = list.OrderBy(x => x.age).ThenBy(x => x.id);
    print_array(query);
}

如果想进行逆序排序,对于原生LINQ语句,在条件后添加
descending
即可,对于封装后的LINQ语句,

static void test_person_linq_more_()
{
    List<Person> list = new List<Person>()
            {
                new Person(){name="a",age=15,id=1 },
                new Person(){name="b",age=12,id=2 },
                new Person(){name="c",age=14,id=3 },
                new Person(){name="d",age=12,id=4 },
                new Person(){name="e",age=14,id=5 },
                new Person(){name="f",age=12,id=6 },
                new Person(){name="g",age=15,id=7 },
            };
    print_array(list);

    // 1. 方式一
    IEnumerable<Person> query = from d in list
                                orderby d.age descending, d.id descending
                                select d;
    // 2. 方式二
    query = list.OrderByDescending(x => x.age).ThenByDescending(x => x.id);
    print_array(query);
}

自定义数据排序后,程序运行最后输出为:

程序输出

自定义数据逆序排序后,程序运行最后输出为:

程序输出

3. 多维数据排序

在实际应用中,我们可能还会使用到多维数据,例如对于二维数据,我们在排序时可能会按照第二维数据的第一个数据作为主要排序关键字,第二数据作为第二个关键字进行排序,当遇到这种情况时,我们可以直接使用LINQ语句进行排序,如下面代码所示,我们定义了一个二维数组,类似于将一系列点数据存放到数组中,然后我们可以参考上文中自定义数据排序方法,书写排序代码:

static void test_array_sort()
{
    List<List<int>> list = new List<List<int>>() {
                new List<int>{ 1, 9 } ,
                new List<int>{ 6, 6 } ,
                new List<int>{ 1, 4 } ,
                new List<int>{ 6, 2 } ,
                new List<int>{ 1, 6 } ,
                new List<int>{ 7, 2 } ,
                new List<int>{ 1, 2 } ,
                new List<int>{ 3, 5 }
            };
    print_array(list);
    // 1. 方式一
    IEnumerable<List<int>> query = from d in list
                                   orderby d[0], d[1]
                                   select d;
    // 2. 方式二
    query = list.OrderBy(x => x[0]).ThenBy(x => x[1]);
    print_array(query);
}

排序后结果输出为:

程序输出

4. 总结

以上就是给大家带来的C#常用排序方式一些实现方式,希望大家在日常使用中能够用到。

Android的部分图片编辑应用中需要对图片进行移动、缩放和旋转,这些变化都依赖于触摸手势实现,而本文主要阐述移动、缩放和旋转手势的简单实现。

一、移动

首先需要从触摸事件(
MotionEvent
)中获取每个手指(
Pointer
)的坐标,随后计算这些坐标的中心(重心)位置,那么本次触摸事件与前一次触摸事件的中心距离就是手势的移动距离:

// calc center coordinates
float centerX = 0;
float centerY = 0;
for (int index = 0; index < pointerCount; index++) {
    centerX += event.getX(index);
    centerY += event.getY(index);
}
centerX /= pointerCount;
centerY /= pointerCount;

// calc translation
float translateX = centerX - mPrevCenterX;
float translateY = centerY - mPrevCenterY;

mPrevCenterX = centerX;
mPrevCenterY = centerY;

二、缩放

同样手势缩放也需要计算触摸事件的中心,其次计算每一个手指坐标与中心的距离,然后计算这些距离的平均值,那么本次触摸事件平均中心距离与上一次触摸事件的比值就是本次手势的缩放比例:

// omit calc center coordinates

// calc mean distance
double sumDistance = 0;
for (int index = 0; index < pointerCount; index++) {
    float vx = event.getX(index) - centerX;
    float vy = event.getY(index) - centerY;

    // calc distance to center coordinates
    sumDistance += Math.sqrt(vx * vx + vy * vy);
}
float meanDistance = (float) (sumDistance / pointerCount);

// calc scale
float scale = mPrevMeanDistance < 1e-5 ? 1 : meanDistance / mPrevMeanDistance;

mPrevMeanDistance = meanDistance;

三、旋转

手势旋转同样需要计算触摸事件的中心,然后计算中心到每一个手指坐标的向量,计算每一个手指向量相对于上一次触摸事件中对应的手指向量的旋转角度,最后计算这些旋转角度的平均值,这个平均值就是本次手势的旋转角度:

// omit calc center coordinates

// calc rotate degrees
double sumRotateDegrees = 0;
for (int index = 0; index < pointerCount; index++) {
    float vx = event.getX(index) - centerX;
    float vy = event.getY(index) - centerY

    // calc angle between vectors
    int pointerId = event.getPointerId(index);
    sumRotateDegrees = Math.toDegrees(angleBetweenVectors(mPrevVx[pointerId], mPrevVy[pointerId], vx, vy));

    mPrevVx[pointerId] = vx;
    mPrevVy[pointerId] = vy;
}
float rotateDegrees = (float) (sumRotateDegrees / pointerCount);

两个向量叉乘公式:
\(\boldsymbol v_1*\boldsymbol v_2=\sin\alpha|\boldsymbol v_1||\boldsymbol v_2|=v_{x1}*v_{y2}-v_{y1}*v_{x2}\)
,那么两个向量之间的夹角:

\[\begin{flalign*}
&\alpha=arcsin(\frac{\boldsymbol v_1*\boldsymbol v_2}{|\boldsymbol v_1||\boldsymbol v_2|})&
\end{flalign*}
\]

private static double cross(float vx1, float vy1, float vx2, float vy2) {
    return vx1 * vy2 - vy1 * vx2;
}

private static double angleBetweenVectors(float vx1, float vy1, float vx2, float vy2) {
    double dist1 = Math.sqrt(vx1 * vx1 + vy1 * vy1);
    double dist2 = Math.sqrt(vx2 * vx2 + vy2 * vy2);

    if (dist1 < 1e-5 || dist2 < 1e-5) {
        return 0;
    }
    return Math.asin(cross(vx1, vy1, vx2, vy2) / dist1 / dist2);
}

不管是移动、缩放和旋转都需要保证本次触摸事件手指数量与上一次相等,如果不相等计算出来的值则跳动较大。

四、完整示例

本文的完整示例放在
github仓库
中,主要实现了图片的移动、旋转和缩放效果:

参考各家代码,用Rust实现了线段树和懒标记。

由于使用了泛型,很多操作都要用闭包自定义实现。

看代码。

// 线段树定义
pub struct SegmentTree<T: Clone>
{
    pub data: Vec<T>,
    tree: Vec<Option<T>>,
    marker: Vec<T>,                               //懒标记。
    query_op: Box<dyn Fn(T, T) -> T>, //查询时,对所有查询元素做的操作。比如加法,就是求区间的所有元素的和。
    marker_marker_op: Box<dyn Fn(T, T) -> T>, //marker加到marker上时,对marker的操作。通常我们要marker[i] += p; 来更新标记,但是泛型实现不了,并且考虑到有些用户有别的需求,所以用闭包包装。
    marker_t_op: Box<dyn Fn(T, T) -> T>, //marker应用到T时,对T的操作。考虑到有些用户有别的需求,所以用闭包包装。
    marker_mul_usize: Box<dyn Fn(T, usize) -> T>, //marker乘usize的方法。这个没法通过要求满足Mul trait自动实现。由于使用了泛型,连乘法都要交给闭包实现。。。
}

impl<T: Clone + Default + Copy + PartialEq> SegmentTree<T> {
    pub fn new(
        data: Vec<T>,
        query_op: Box<dyn Fn(T, T) -> T>,
        marker_marker_op: Box<dyn Fn(T, T) -> T>,
        marker_t_op: Box<dyn Fn(T, T) -> T>,
        marker_mul_usize: Box<dyn Fn(T, usize) -> T>,
    ) -> Self {
        let data_len = data.len();
        let mut tr = Self {
            data,
            marker: vec![T::default(); 4 * data_len], //四倍原数据大小
            tree: vec![None; 4 * data_len],           //四倍原数据大小
            query_op,
            marker_marker_op,
            marker_t_op,
            marker_mul_usize,
        };
        tr.build();
        tr
    }

    #[inline]
    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index)
    }

    #[inline]
    pub fn len(&self) -> usize {
        self.data.len()
    }

    #[inline]
    fn left_child(index: usize) -> usize {
        2 * index + 1
    }

    #[inline]
    fn right_child(index: usize) -> usize {
        2 * index + 2
    }

    #[inline]
    fn build(&mut self) {
        self.build_segment_tree(0, 0, self.data.len() - 1);
    }

    // 递归Build
    fn build_segment_tree(&mut self, tree_index: usize, left: usize, right: usize) {
        if left == right {
            self.tree[tree_index] = Some(self.data[left]);
            return;
        }
        let left_tree_index = Self::left_child(tree_index);
        let right_tree_index = Self::right_child(tree_index);
        let mid = (right - left) / 2 + left;
        self.build_segment_tree(left_tree_index, left, mid);
        self.build_segment_tree(right_tree_index, mid + 1, right);
        // 左右子树数据处理方式
        if let Some(l) = self.tree[left_tree_index] {
            if let Some(r) = self.tree[right_tree_index] {
                self.tree[tree_index] = Some((self.query_op)(l, r))
            }
        }
    }

    // 返回对线段树的全部元素做query_op操作的结果
    #[inline]
    pub fn query_all(&mut self) -> T {
        self.recursion_query(0, self.data.len() - 1, 0, 0, self.data.len() - 1)
    }

    // 返回对线段树的[l..r]范围全部元素做query_op操作的结果
    pub fn query(&mut self, l: usize, r: usize) -> Result<T, &'static str> {
        if l > self.data.len() || r > self.data.len() || l > r {
            return Err("索引错误");
        }
        if l == r {
            return Ok(self.data[l]);
        }
        Ok(self.recursion_query(l, r, 0, 0, self.data.len() - 1))
    }

    // 在index表示的[current_left,current_right]范围中查询[l..r]值
    fn recursion_query(
        &mut self,
        l: usize,
        r: usize,
        index: usize,
        current_left: usize,
        current_right: usize,
    ) -> T {
        if l > current_right || r < current_left {
            return T::default();
        }
        if l == current_left && r == current_right {
            if let Some(d) = self.tree[index] {
                if l == r {
                    self.data[l] = d;
                }
                return d;
            }
            return T::default();
        }
        self.push_down(index, current_right - current_left + 1);
        let mid = current_left + (current_right - current_left) / 2;
        if l >= mid + 1 {
            return self.recursion_query(l, r, Self::right_child(index), mid + 1, current_right);
        } else if r <= mid {
            return self.recursion_query(l, r, Self::left_child(index), current_left, mid);
        }
        let l_res = self.recursion_query(l, mid, Self::left_child(index), current_left, mid);
        let r_res =
            self.recursion_query(mid + 1, r, Self::right_child(index), mid + 1, current_right);
        (self.query_op)(l_res, r_res)
    }

    // 更新index为val
    pub fn set(&mut self, index: usize, val: T) -> Result<(), &'static str> {
        if index >= self.data.len() {
            return Err("索引超过线段树长度");
        }
        // 更新数据
        self.data[index] = val;
        // 递归更新树
        self.recursion_set(0, 0, self.data.len() - 1, index, val);
        Ok(())
    }

    // 递归更新树
    fn recursion_set(&mut self, index_tree: usize, l: usize, r: usize, index: usize, val: T) {
        if l == r {
            self.tree[index_tree] = Some(val);
            return;
        }
        let mid = l + (r - l) / 2;
        let left_child = Self::left_child(index_tree);
        let right_child = Self::right_child(index_tree);
        if index >= mid + 1 {
            self.recursion_set(right_child, mid + 1, r, index, val);
        } else {
            self.recursion_set(left_child, l, mid, index, val);
        }
        // 左右子树数据求和
        if let Some(l_d) = self.tree[left_child] {
            if let Some(r_d) = self.tree[right_child] {
                self.tree[index_tree] = Some((self.query_op)(l_d, r_d));
            }
        }
    }

    // 应用所有懒标记到data数组上
    #[inline]
    pub fn apply_marker_all(&mut self) {
        self.apply_marker_lr(0, self.data.len() - 1);
    }

    // 应用懒标记到[l:r]数据范围
    #[inline]
    pub fn apply_marker_lr(&mut self, l: usize, r: usize) {
        self.apply_marker(l, r, 0, 0, self.data.len() - 1);
    }

    fn apply_marker(
        &mut self,
        l: usize,
        r: usize,
        index: usize,
        current_l: usize,
        current_r: usize,
    ) {
        if current_l > r || current_r < l || r >= self.data.len() {
            return; // 区间无交集
        } else {
            // 与目标区间有交集,但不包含于其中
            if current_l == current_r {
                if let Some(d) = self.tree[index] {
                    self.data[current_l] = d;
                }
                return;
            }
            let mid = (current_l + current_r) / 2;
            self.push_down(index, current_r - current_l + 1);
            self.apply_marker(l, r, Self::left_child(index), current_l, mid); // 递归地往下寻找
            self.apply_marker(l, r, Self::right_child(index), mid + 1, current_r);
            self.tree[index] = Some((self.query_op)(
                self.tree[Self::left_child(index)].unwrap(),
                self.tree[Self::right_child(index)].unwrap(),
            ));
            // 根据子节点更新当前节点的值
        }
    }
    #[inline]
    pub fn update_interval(&mut self, l: usize, r: usize, delta: T) {
        self.update(l, r, delta, 0, 0, self.data.len() - 1);
    }

    // 传递marker到下级
    fn push_down(&mut self, index: usize, len: usize) {
        self.marker[Self::left_child(index)] =
            (self.marker_marker_op)(self.marker[index], self.marker[Self::left_child(index)]); // 标记向下传递
        self.marker[Self::right_child(index)] =
            (self.marker_marker_op)(self.marker[index], self.marker[Self::right_child(index)]);
        if self.tree[Self::left_child(index)].is_some() {
            self.tree[Self::left_child(index)] = Some((self.marker_t_op)(
                (self.marker_mul_usize)(self.marker[index], len - (len / 2)),
                self.tree[Self::left_child(index)].unwrap(),
            ));
        }
        if self.tree[Self::right_child(index)].is_some() {
            self.tree[Self::right_child(index)] = Some((self.marker_t_op)(
                (self.marker_mul_usize)(self.marker[index], len / 2),
                self.tree[Self::right_child(index)].unwrap(),
            ));
        }
        self.marker[index] = T::default(); // 清除标记
    }

    fn update(
        &mut self,
        l: usize,
        r: usize,
        delta: T,
        index: usize,
        current_l: usize,
        current_r: usize,
    ) {
        if current_l > r || current_r < l {
            return; // 区间无交集
        } else if current_l >= l && current_r <= r {
            // 当前节点对应的区间包含在目标区间中
            if self.tree[index].is_some() {
                // 更新当前区间的值
                self.tree[index] = Some((self.query_op)(
                    self.tree[index].unwrap(),
                    (self.marker_mul_usize)(delta, current_r - current_l + 1),
                ));
            }
            // 如果不是叶子节点
            if current_r > current_l {
                // 给当前区间打上标记
                self.marker[index] = (self.marker_marker_op)(delta, self.marker[index]);
            }
        } else {
            // 与目标区间有交集,但不包含于其中
            let mid = (current_l + current_r) / 2;
            self.push_down(index, current_r - current_l + 1);
            self.update(l, r, delta, Self::left_child(index), current_l, mid); // 递归地往下寻找
            self.update(l, r, delta, Self::right_child(index), mid + 1, current_r);
            self.tree[index] = Some((self.query_op)(
                self.tree[Self::left_child(index)].unwrap(),
                self.tree[Self::right_child(index)].unwrap(),
            )); // 根据子节点更新当前节点的值
        }
    }
}

fn main() {
    let mut tr: SegmentTree<i32> = SegmentTree::new(
        vec![1, 3, 4, 0, 0, 4, 5, 0],
        Box::new(|a, b| a + b),
        Box::new(|a, b| a + b),
        Box::new(|a, b| a + b),
        Box::new(|a, b| a * (b as i32)),
    );
    let _ = tr.set(1, 2); //点更新,即把data[1]设为2
    tr.update_interval(0, 2, -1); //区间更新,即[0:2]每个元素减1
    tr.update_interval(1, 3, 2); //区间更新,即[1:3]每个元素加2
    tr.apply_marker_all(); //应用全部marker到data数组
    println!("{}", tr.query_all()); //输出19,即全部元素的和
    println!("{:?}", tr.data); //输出[0, 3, 5, 2, 0, 4, 5, 0]
}

做一道题验证一下这个线段树的正确性,直接看我写的
1589. 所有排列中的最大和题解
即可(虽然这道题用差分数组最快,但是作为线段树验证还是很方便的)。

1.前言

大家好,我是 BNTang,今天给大家介绍一下 Flutter 的开发环境搭建。在之前我已经将 Dart 的基本语法给大家介绍了,所以今天就不再介绍 Dart 的基本语法了,直接进入 Flutter 的开发环境搭建。

2.安装 Java SDK

Java SDK 下载地址:
https://www.oracle.com/cn/java/technologies/downloads/#jdk17-windows

配置环境变量:

img

如上其实就是将 Java SDK 的 bin 目录添加到环境变量中,这样我们就可以在任意目录下使用 Java 命令了。

如果对安装 Java SDK 有疑问的话,可以参考我之前写的一篇文章:
『Java』Java 环境搭建

配置完毕了之后,我们可以在命令行中输入
java -version
来查看 Java SDK 的版本:

3.安装 Flutter SDK

Flutter SDK 下载地址:
https://docs.flutter.dev/get-started/install/windows/desktop?tab=download

下载完成之后,解压到任意目录下,然后将 Flutter SDK 的 bin 目录添加到环境变量中:

4.安装 Android Studio

Android Studio 下载地址:
https://developer.android.com/studio?hl=zh-cn

除了这种方式还可以通过
Toolbox App
来安装 Android Studio:

如果是通过链接的方式下载的,就自行双击安装包运行起来,一顿 Next,如果出现了如下界面,就点击 Cancel 取消:

选择 Custom,点击 Next:

接受许可:

静静的等待安装完毕即可。

!!!推荐从官网下载,先不用 Toolbox App,2023-12-31 16:17:46 经过测试,Toolbox App 安装的 Android Studio 也是可以的。所以大家可以根据自己的喜好来选择。

5.配置 Android Studio

5.1.安装 Flutter 插件和 Dart 插件

5.2.其它配置

6.用 Android Studio 创建一个 Flutter 项目

配置一下 Flutter SDK:

然后点击 Next:

原生平台开发语言我这里 Android language 与 IOS language 分别选择比较老的 Java 与 O C

点击 create 创建项目即可。

如下是我创建第一个 Flutter 的基本配置参考即可:

6.1.安装设备管理器

点击 start 按钮即可,如果你运行起来发现比较小,你可以参考我下面推荐的配置,单独运行一个窗口来展示设备:

然后将设备管理器停了,在重新运行效果如下:

6.2.运行第一个 Flutter 项目

设备管理器安装好了之后,并且运行过之后,编辑器工具栏的 run 按钮就可以点击了,点击一下运行我们的 Flutter 项目,如下图:

耐心等待运行起来即可,第一次运行需要点时间:

闭坑指南

[!] Network resources X A network error occurred while checking “https://github.com/“:信号灯超时时间已到


flutter doctor
过程中出现将以下全部复制粘贴
C:\Windows\System32\drivers\etc\hosts
里面保存:

192.30.253.113    github.com
 
192.30.252.131 github.com
 
185.31.16.185 github.global.ssl.fastly.net
 
74.125.237.1 dl-ssl.google.com
 
173.194.127.200 groups.google.com
 
192.30.252.131 github.com
185.31.16.185 github.global.ssl.fastly.net
 
74.125.128.95 ajax.googleapis.com

192.30.255.112  github.com git
185.31.16.184 github.global.ssl.fastly.net 
192.30.253.112    github.com 
192.30.253.119    gist.github.com
151.101.184.133    assets-cdn.github.com
151.101.184.133    raw.githubusercontent.com
151.101.184.133    gist.githubusercontent.com
151.101.184.133    cloud.githubusercontent.com
151.101.184.133    camo.githubusercontent.com
151.101.184.133    avatars0.githubusercontent.com
151.101.184.133    avatars1.githubusercontent.com
151.101.184.133    avatars2.githubusercontent.com
151.101.184.133    avatars3.githubusercontent.com
151.101.184.133    avatars4.githubusercontent.com
151.101.184.133    avatars5.githubusercontent.com
151.101.184.133    avatars6.githubusercontent.com
151.101.184.133    avatars7.githubusercontent.com
151.101.184.133    avatars8.githubusercontent.com

再次运行
flutter doctor -v
:

Visual Studio - develop for Windows

Visual Studio not installed; this is necessary for Windows development:未安装Visual Studio;这是Windows开发所必需的。

安装地址:
https://visualstudio.microsoft.com/zh-hans/downloads/

End