period timeline
initial period : period {start, end}
- 50 - 65
- 85 - 90
- 0 - 20
- 80 - 85
- 70 - 100
- 15 - 40
- 5 - 30
- 50 - 55
- 0 - 40
- 50 - 65
- 70 - 100
4 steps of algorithm
(sort, change, remove and integrate)
1. sort periods
ทำการจัดเรียง periods ใหม่ทั้งหมด โดยจัดเรียงตาม period start จากน้อยไปหามาก
ถ้า period start มีค่าเท่ากัน ให้จัดเรียงตาม period end จากน้อยไปหามาก
before
- 50 - 65
- 85 - 90
- 0 - 20
- 80 - 85
- 70 - 100
- 15 - 40
- 5 - 30
- 50 - 55
- 0 - 20
- 5 - 30
- 15 - 40
- 50 - 55
- 50 - 65
- 70 - 100
- 80 - 85
- 85 - 90
private void sortPeriods() {
periodList = new ArrayList<>(periodSet);
Collections.sort(periodList, new Comparator<Period>() {
@Override
public int compare(Period period1, Period period2) {
if (period1.getStart() == period2.getStart()) {
return (int) (period1.getEnd() - period2.getEnd());
}
return (int) (period1.getStart() - period2.getStart());
}
});
}
2. change overlapในกรณีที่ period start ปัจจุบัน มีค่าน้อยกว่า period end ของตัวก่อนหน้า
ให้ทำการเปลี่ยน period start นั้น ให้มีค่าเท่ากันกับ period end ของตัวก่อนหน้า
before
- 0 - 20
- 5 - 30 (20 - 30)
- 15 - 40 (30 - 40)
- 50 - 55
- 50 - 65 (55 - 65)
- 70 - 100
- 80 - 85 (100 - 85)
- 85 - 90
- 0 - 20
- 20 - 30
- 30 - 40
- 50 - 55
- 55 - 65
- 70 - 100
- 100 - 85
- 85 - 90
private void changeOverlap() {
if (periodList.size() > 1) {
for (int i = 1; i < periodList.size(); i++) {
Period before = periodList.get(i - 1);
Period current = periodList.get(i);
if (current.getStart() < before.getEnd()) {
current.setStart(before.getEnd());
}
}
}
}
3. remove incorrect / sub periodทำการลบ period ที่มีค่าไม่ถูกต้องออกไป เช่น
period ที่มี start มากกว่าหรือเท่ากับ end หรือ
period นั้น เป็น sub period ของ period อื่นๆ
before
- 0 - 20
- 20 - 30
- 30 - 40
- 50 - 55
- 55 - 65
- 70 - 100
- 100 - 85 incorrect (100 > 85 or start > end)
- 85 - 90 sub period (70 - 100)
- 0 - 20
- 20 - 30
- 30 - 40
- 50 - 55
- 55 - 65
- 70 - 100
private void removeIncorrect() {
if (periodList.size() > 1) {
for (int i = 1; i < periodList.size(); i++) {
Period periodI = periodList.get(i);
for (int j = i + 1; j < periodList.size(); j++) {
Period periodJ = periodList.get(j);
if(isIncorrect(periodJ) || isSubPeriod(periodJ, periodI)){
periodList.remove(periodJ);
}
}
}
}
}
private boolean isIncorrect(Period period){
return period.getStart() >= period.getEnd();
}
private boolean isSubPeriod(Period period1, Period period2){
return period1.getStart() >= period2.getStart() && period1.getEnd() <= period2.getEnd();
}
4. integrate periodsทำการยุบรวม period ที่เหลือให้เป็น period เดียวกัน
before
- 0 - 20 (1)
- 20 - 30 (1)
- 30 - 40 (1)
- 50 - 55 (2)
- 55 - 65 (2)
- 70 - 100 (3)
- 0 - 40
- 50 - 65
- 70 - 100
private void integratePeriods() {
if (periodList.size() > 1) {
for (int i = 1; i < periodList.size(); i++) {
Period before = periodList.get(i - 1);
Period current = periodList.get(i);
if (current.getStart() == before.getEnd()) {
current.setStart(before.getStart());
periodList.remove(before);
i--;
}
}
}
}
success!
full code
Period.java
full code
Period.java
package com.blogspot.na5cent.learning.integrateperiodalgorthm;
/**
*
* @author recrow
*/
public class Period {
private long start;
private long end;
public Period(long start, long end) {
this.start = start;
this.end = end;
}
public long getStart() {
return start;
}
public void setStart(long start) {
this.start = start;
}
public long getEnd() {
return end;
}
public void setEnd(long end) {
this.end = end;
}
@Override
public int hashCode() {
int hash = 7;
hash = 47 * hash + (int) (this.start ^ (this.start >>> 32));
hash = 47 * hash + (int) (this.end ^ (this.end >>> 32));
return hash;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Period other = (Period) obj;
if (this.start != other.start) {
return false;
}
if (this.end != other.end) {
return false;
}
return true;
}
}
PeriodIntegrator.java
package com.blogspot.na5cent.learning.integrateperiodalgorthm;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
*
* @author redcrow
*/
public class PeriodIntegrator {
private Set<Period> periodSet;
private List<Period> periodList;
public PeriodIntegrator() {
periodSet = new HashSet<>();
}
public PeriodIntegrator addPeriod(Period period) {
periodSet.add(period);
return this;
}
public PeriodIntegrator addAllPeriods(List<Period> periodList){
periodSet.addAll(periodList);
return this;
}
private void sortPeriods() {
periodList = new ArrayList<>(periodSet);
showPeriods("initial periods", periodList);
Collections.sort(periodList, new Comparator<Period>() {
@Override
public int compare(Period period1, Period period2) {
if (period1.getStart() == period2.getStart()) {
return (int) (period1.getEnd() - period2.getEnd());
}
return (int) (period1.getStart() - period2.getStart());
}
});
showPeriods("step 1 >> sort periods", periodList);
}
private void changeOverlap() {
if (periodList.size() > 1) {
for (int i = 1; i < periodList.size(); i++) {
Period before = periodList.get(i - 1);
Period current = periodList.get(i);
if (current.getStart() < before.getEnd()) {
current.setStart(before.getEnd());
}
}
}
showPeriods("step 2 >> change overlap", periodList);
}
private void removeIncorrect() {
if (periodList.size() > 1) {
for (int i = 1; i < periodList.size(); i++) {
Period periodI = periodList.get(i);
for (int j = i + 1; j < periodList.size(); j++) {
Period periodJ = periodList.get(j);
if(isIncorrect(periodJ) || isSubPeriod(periodJ, periodI)){
periodList.remove(periodJ);
}
}
}
}
showPeriods("step 3 >> remove incorrect", periodList);
}
private boolean isIncorrect(Period period){
return period.getStart() >= period.getEnd();
}
private boolean isSubPeriod(Period period1, Period period2){
return period1.getStart() >= period2.getStart() && period1.getEnd() <= period2.getEnd();
}
private void showPeriods(String operationName, List<Period> periodList) {
System.out.println("");
System.out.println(operationName);
System.out.println("-------------------------------------------------");
for (Period period : periodList) {
System.out.println("period {" + period.getStart() + ", " + period.getEnd() + "}");
}
}
private void integratePeriods() {
if (periodList.size() > 1) {
for (int i = 1; i < periodList.size(); i++) {
Period before = periodList.get(i - 1);
Period current = periodList.get(i);
if (current.getStart() == before.getEnd()) {
current.setStart(before.getStart());
periodList.remove(before);
i--;
}
}
}
showPeriods("step 4 >> integrate periods", periodList);
}
public List<Period> integrate() {
sortPeriods();
changeOverlap();
removeIncorrect();
integratePeriods();
return periodList;
}
}
IntegratePeriodAlgorthm.java
package com.blogspot.na5cent.learning.integrateperiodalgorthm;
/**
*
* @author redcrow
*/
public class IntegratePeriodAlgorthm {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
new PeriodIntegrator()
.addPeriod(new Period(5, 30))
.addPeriod(new Period(15, 40))
.addPeriod(new Period(50, 65))
.addPeriod(new Period(50, 55))
.addPeriod(new Period(0, 20))
.addPeriod(new Period(70, 100))
.addPeriod(new Period(80, 85))
.addPeriod(new Period(85, 90))
.integrate();
}
}
run code
ไม่มีความคิดเห็น:
แสดงความคิดเห็น