维护可修改的时间片的有序列表(列表仍应有序) [英] Maintaining an ordered list of time-slices that can be modified (list should still be ordered)
问题描述
所以，我遇到一个问题，在 ArrayList 中存在特定类型的各种对象，如下所示，
So , I have a problem where there are various objects of a specific type are present in an ArrayList as present below,
...
//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);
现在，在很多情况下我可以增加或减少:
Now , there are various cases in which I can increase or decrease:
- 特定对象的开始时间
- 特定对象的结束时间
- 如果对象存在于两个或多个活动之间，则两者均为 .
例如
示例1:
如果我修改对象 h2 ，以使 h2 ( 16:30 )的开始时间减少10分钟，然后将结束时间减少 h1 的时间应减少相同，即 h1 的结束时间应为 16:20
in case I modify object h2 such that start time of h2 (16:30) is decreased by 10 mins then the end time of h1 should be decreased by the same i.e. h1 end time would be 16:20
示例2:
如果我修改对象 h2 ，以使 h2 ( 16:45 )的结束时间增加10分钟，即16:55 ，则应将对象 h3 从列表中删除，因为它完全被 h2 占据.
in case I modify object h2 such that end time of h2 (16:45) is increased by 10 mins i.e 16:55 then object h3 should be removed from the list as it is occupied completely by h2.
I/P:我总是在两个diff变量中为每个对象修改了开始时间和结束时间，但是问题是，在运行时按照上述情况修改了对象，并相应地更新了arraylist.
I/P: I always have the modified start and end time for every object in two diff variables but the problem is to modify the objects as mentioned in the cases above at runtime and update the arraylist accordingly.
推荐答案
正确的方法是使用 TreeSet 并定义 Param 的顺序.为此，您必须使 Param 实现 Comparable ，然后为 hashCode 和 equals 提供实现.
The right way to do this is to use a TreeSet and define the ordering for Param. To do this, you have to make Param implement Comparable and then provide implementations for hashCode and equals as well.
然后可以修改项目，然后浏览集合以查找前一个和后一个项目.我的解决方案假定没有重叠时间，并且也可以处理第二种情况(删除无效的时间片).
You can then modify an item and then navigate the set to find the preceding and succeeding item. My solution assumes that there aren't any overlapping times and it will handle your second case as well (removing invalid time-slices).
首先，我们需要让 Param 实现 Comparable< Param> :
First we need to have Param implement 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 中的方法找到正确的项目，然后进行修改.这是一些示例代码.
Now all the hard work is done! You can use methods from TreeSet to find the right items and then modify them. Here's some example code.
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);
运行此代码可以给我们:
Running this code gives us:
[[10, 20], [20, 30], [30, 50], [50, 60]]
[[10, 22], [22, 28], [28, 50], [50, 60]]
此代码适用于无效的时间片，并且以下示例将演示:
This code works for invalid time-slices as well as the following examples will demonstrate:
int sdiff = -20;
int ediff = 20;
输出:
[[10, 20], [20, 30], [30, 50], [50, 60]]
[[0, 50], [50, 60]]
如果您以时间段无效的方式修改了元素本身，它也将起作用:
It will also work if you have modified the element itself in such a way that its time-slice is invalid:
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 ，并在循环中运行，只要有需要修改的元素即可.循环还会检查我们是否结束于切片的中间"，如果是，它将适当地调整开始/结束时间:
This particular solution won't work if you modify an element such that it spans more than one slice. But with a slight modification, you can get it to handle those cases too. This is where using a sorted structure really helps, because it would be kind of a nightmare to do this with a list. The modification involves using a while loop instead of an if and running through the loop as long as there are elements that need to be modified. The loop also checks to see if we ended up in the "middle" of a slice and if so it adjusts the start/end time appropriately:
//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] 之类的东西呢?只要修改后的范围包含原始范围的全部或一部分，该算法就可以工作.
This algorithm won't work in the case where you, for example, change [30, 40] to be [0, 5] or [5, 15]. In this situation you end up with a space where [30, 40] used to be, and it's not clearly defined how that space should be filled up. Should [20, 30] change to [20, 40], or should [40, 50] change to [30, 50]? Or how about something like [20, 35] and [35, 50]? As long as the modified range contains all or part of the original range, this algorithm will work.
这篇关于维护可修改的时间片的有序列表(列表仍应有序)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
