java - 维护可以修改的时间片的有序列表(列表仍应排序)

Question

所以，我遇到一个问题，ArrayList 中存在特定类型的各种对象，如下所示，

...
//Class definition
class Params
{
  long startTimeMillis;
  long endTimeMillis;
  String currentState;

 .. correponding getters and setters are present here ..
}
....

ArrayList<Params> activities=new ArrayList<>();

Params h1= new Params();        
h1.setStartTimeMillis(1435939200000L);//"16:00"
h1.setEndTimeMillis(1435941000000L);//"16:30"
h1.setCurrentState("C");

Params h2= new Params();        
h2.setStartTimeMillis(1435941000000L);//"16:30"
h2.setEndTimeMillis(1435941900000L);//"16:45"
h2.setCurrentState("B");

Params h3= new Params();        
h3.setStartTimeMillis(1435941900000L);//"16:45"
h3.setEndTimeMillis(1435942500000L);//"16:55"
h3.setCurrentState("A");

Params h4= new Params();        
h4.setStartTimeMillis(1435942500000L);//"16:55"
h4.setEndTimeMillis(1435942800000L);//"17:00"
h4.setCurrentState("B");

Params h5= new Params();        
h5.setStartTimeMillis(1435942800000L);//"17:00"
h5.setEndTimeMillis(1435943400000L);//"17:10"
h5.setCurrentState("C");

activities.add(h1);
activities.add(h2);
activities.add(h3);
activities.add(h4);
activities.add(h5);

现在，有多种情况我可以增加或减少:

• 特定对象的开始时间
• 特定对象的结束时间
• 如果对象出现在两个或多个 Activity 之间，则两者都是。

例如

示例1:

如果我修改对象 h2 ，使 h2 的开始时间 (16:30) 减少 10 分钟，然后结束时间h1 的值应减少相同的值，即 h1 结束时间将为 16:20

示例2:

如果我修改对象 h2 ，使 h2 的结束时间 (16:45) 增加 10 分钟，即 16:55 那么对象 h3 应从列表中删除，因为它已被 h2 完全占用。

I/P:我总是在两个 diff 变量中修改每个对象的开始和结束时间，但问题是在运行时修改上述情况中提到的对象并相应地更新数组列表。

Answer 1

正确的方法是使用 TreeSet并定义 Param 的排序。为此，您必须创建 Param实现Comparable然后提供 hashCode 的实现和equals以及。

然后，您可以修改某个项目，然后导航该集合以查找前一个和后一个项目。我的解决方案假设没有任何重叠时间，并且它也会处理您的第二种情况(删除无效的时间片)。

首先我们需要 Param实现Comparable<Param> :

public class Param implements Comparable<Param> {

    //Public just for demo purposes and brevity
    public int start;
    public int end;

    public Param(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Param o) {
        //Needs to be consistent with equals!!
        int result = this.start - o.start;
        if(result == 0) {
            result = (this.end - this.start) - (o.end - o.start);
        }

        return result;
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + start;
        result = 31 * result + end;  
        return result;
    }

    @Override
    public boolean equals(Object o) {
        ... // null check, reference check etc.
        Param p = (Param) o;
        return this.start == p.start && this.end == p.end;
    }
}

现在所有的辛苦工作都完成了!您可以使用 TreeSet 中的方法找到正确的项目然后修改它们。这是一些示例代码。

  NavigableSet<Param> pset = new TreeSet<Param>();

  Param p1 = new Param(10, 20);
  Param p2 = new Param(20, 30);
  Param p3 = new Param(30, 50);
  Param p4 = new Param(50, 60);

  pset.add(p1);
  pset.add(p2);
  pset.add(p3);
  pset.add(p4);

  System.out.println(pset);      

  int sdiff = -2;
  int ediff = 2;      

  //Find the item we want, as well as the preceding and succeeding items
  Param p = pset.floor(new Param(20, 30));      
  Param lower = pset.lower(p);
  Param higher = pset.higher(p);      

  //Remove the item from the set and modify it
  pset.remove(p);
  p.start += sdiff;
  p.end += ediff;      

  //Add only if it is valid
  if(p.start < p.end) {
      pset.add(p);    
  }      

  //If we have a preceding item
  if(lower != null) {
      //Remove, modify, and add back to set
      pset.remove(lower);
      lower.end += sdiff;
      if(lower.start < lower.end) {
          pset.add(lower);
      }    
  }

  //Same case as lower
  if(higher != null) {
      pset.remove(higher);
      higher.start += ediff;          
      if(higher.start < higher.end) {
          pset.add(higher);
      }    
  }

  System.out.println(pset);

运行这段代码给我们:

[[10, 20], [20, 30], [30, 50], [50, 60]]
[[10, 22], [22, 28], [28, 50], [50, 60]]

此代码适用于无效的时间片，以下示例将演示:

int sdiff = -20;
int ediff = 20; 

输出:

[[10, 20], [20, 30], [30, 50], [50, 60]]
[[0, 50], [50, 60]]

如果您修改了元素本身，使其时间片无效，它也将起作用:

int sdiff = 5;
int ediff = -5;      

Param p = pset.floor(new Param(10, 20));

给我们:

[[10, 20], [20, 30], [30, 50], [50, 60]]
[[15, 30], [30, 50], [50, 60]]

还有:

int sdiff = 5;
int ediff = -10;      

Param p = pset.floor(new Param(10, 20));

给我们:

[[10, 20], [20, 30], [30, 50], [50, 60]]
[[10, 30], [30, 50], [50, 60]]

如果您修改一个元素使其跨越多个切片，则此特定解决方案将不起作用。但通过稍加修改，您也可以让它处理这些情况。这就是使用排序结构真正有用的地方，因为使用列表来执行此操作将是一场噩梦。修改涉及使用 while循环而不是 if只要有需要修改的元素就循环运行。该循环还会检查我们是否最终位于切片的“中间”，如果是，则适当调整开始/结束时间:

//As long as we have elements to modify
while(lower != null) {
    Param nextLower = null;

    //Remove, modify, and add back to set if valid
    pset.remove(lower);
    lower.end += sdiff;

    if(lower.start < lower.end) {
        //The modified slice is valid, so add it back
        pset.add(lower);                   
    } else if(lower.start > lower.end) {
        //The modified slice is not valid and so we're not
        //going to add it. But it looks like we might have
        //encroached on the space of the slice that precedes
        //"lower" (at least; we may have extended past even
        //more, possibly all the way up to and past the
        //beginning)
        nextLower = pset.lower(p);
        if(nextLower != null && p.start == nextLower.start) {
            //It looks like we took up the space of the preceding
            //slice exactly (i.e., we are flush against it) and
            //so we don't need to do anything.
            nextLower = null;
        } else if(nextLower != null) {
            //It looks like we took up the space of the preceding
            //slice and then some. Let's adjust sdiff to reflect
            //that.
            sdiff = p.start - nextLower.end;                  
        }                            
    }

    lower = nextLower;
}

  //Similar to lower
  while(higher != null) {
      Param nextHigher = null;

      pset.remove(higher);
      higher.start += ediff;

      //Need to check for the additional case where the modified element's
      //end time could supersede a "higher" element's end time.
      if(higher.start < higher.end && higher.end > p.end) {
          pset.add(higher);              
      } else if(higher.start > higher.end || higher.end <= p.end) {
          nextHigher = pset.higher(p);
          if(nextHigher != null && p.end == nextHigher.start) {
              nextHigher = null;
          } else if(nextHigher != null) {
              ediff = p.end - nextHigher.start;                  
          }
      }

      higher = nextHigher;
  }

例如，当您更改 [30, 40] 时，此算法将不起作用。成为[0, 5]或[5, 15] 。在这种情况下，您最终会得到一个空格，其中 [30, 40]过去是这样，并且没有明确定义如何填充该空间。应该[20, 30]更改为 [20, 40] ，或者应该[40, 50]更改为 [30, 50] ？或者像 [20, 35] 这样的东西怎么样？和[35, 50] ？只要修改后的范围包含原始范围的全部或部分，该算法就有效。