RLESparseResourceAllocation { public static RLESparseResourceAllocation merge(ResourceCalculator resCalc, Resource clusterResource, RLESparseResourceAllocation a, RLESparseResourceAllocation b, RLEOperator operator, long start, long end) throws PlanningException { NavigableMap<Long, Resource> cumA = a.getRangeOverlapping(start, end).getCumulative(); NavigableMap<Long, Resource> cumB = b.getRangeOverlapping(start, end).getCumulative(); NavigableMap<Long, Resource> out = merge(resCalc, clusterResource, cumA, cumB, start, end, operator); return new RLESparseResourceAllocation(out, resCalc); } RLESparseResourceAllocation(ResourceCalculator resourceCalculator);  RLESparseResourceAllocation(NavigableMap<Long, Resource> out,
      ResourceCalculator resourceCalculator); boolean addInterval(ReservationInterval reservationInterval,
      Resource totCap); boolean removeInterval(ReservationInterval reservationInterval,
      Resource totCap); Resource getCapacityAtTime(long tick); long getEarliestStartTime(); long getLatestNonNullTime(); boolean isEmpty(); @Override String toString(); Map<ReservationInterval, Resource> toIntervalMap(); NavigableMap<Long, Resource> getCumulative(); ResourceCalculator getResourceCalculator(); static RLESparseResourceAllocation merge(ResourceCalculator resCalc,
      Resource clusterResource, RLESparseResourceAllocation a,
      RLESparseResourceAllocation b, RLEOperator operator, long start, long end); RLESparseResourceAllocation getRangeOverlapping(long start, long end); void shift(long delta); Resource getMaximumPeriodicCapacity(long tick, long period); Resource getMinimumCapacityInInterval(ReservationInterval interval);  }
@Test public void testMergeAdd() throws PlanningException { TreeMap<Long, Resource> a = new TreeMap<>(); TreeMap<Long, Resource> b = new TreeMap<>(); setupArrays(a, b); RLESparseResourceAllocation rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); RLESparseResourceAllocation rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.add, 18, 45); System.out.println(out); long[] time = { 18, 20, 22, 30, 33, 40, 43, 45 }; int[] alloc = { 10, 15, 20, 25, 30, 40, 30 }; validate(out, time, alloc); }
@Test public void testMergeMin() throws PlanningException { TreeMap<Long, Resource> a = new TreeMap<>(); TreeMap<Long, Resource> b = new TreeMap<>(); setupArrays(a, b); RLESparseResourceAllocation rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); RLESparseResourceAllocation rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.min, 0, 60); System.out.println(out); long[] time = { 10, 22, 33, 40, 43, 50, 60 }; int[] alloc = { 5, 10, 15, 20, 10, 0 }; validate(out, time, alloc); }
@Test public void testMergeMax() throws PlanningException { TreeMap<Long, Resource> a = new TreeMap<>(); TreeMap<Long, Resource> b = new TreeMap<>(); setupArrays(a, b); RLESparseResourceAllocation rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); RLESparseResourceAllocation rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.max, 0, 60); System.out.println(out); long[] time = { 10, 20, 30, 40, 50, 60 }; int[] alloc = { 5, 10, 15, 20, 10 }; validate(out, time, alloc); }
@Test public void testMergeSubtract() throws PlanningException { TreeMap<Long, Resource> a = new TreeMap<>(); TreeMap<Long, Resource> b = new TreeMap<>(); setupArrays(a, b); RLESparseResourceAllocation rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); RLESparseResourceAllocation rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.subtract, 0, 60); System.out.println(out); long[] time = { 10, 11, 20, 22, 30, 33, 43, 50, 60 }; int[] alloc = { 5, 0, 5, 0, 5, 0, 10, -10 }; validate(out, time, alloc); }
@Test public void testMergesubtractTestNonNegative() throws PlanningException { TreeMap<Long, Resource> a = new TreeMap<>(); TreeMap<Long, Resource> b = new TreeMap<>(); setupArrays(a, b); RLESparseResourceAllocation rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); RLESparseResourceAllocation rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); try { RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.subtractTestNonNegative, 0, 60); fail(); } catch (PlanningException pe) { } a = new TreeMap<>(); b = new TreeMap<>(); b.put(11L, Resource.newInstance(5, 6)); rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); try { RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.subtractTestNonNegative, 0, 60); fail(); } catch (PlanningException pe) { } a.put(10L, Resource.newInstance(10, 5)); b.put(11L, Resource.newInstance(5, 6)); rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); try { RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.subtractTestNonNegative, 0, 60); fail(); } catch (PlanningException pe) { } a.put(10L, Resource.newInstance(5, 10)); b.put(11L, Resource.newInstance(6, 5)); rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); try { RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.subtractTestNonNegative, 0, 60); fail(); } catch (PlanningException pe) { } a.put(10L, Resource.newInstance(10, 6)); b.put(11L, Resource.newInstance(5, 6)); rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.subtractTestNonNegative, 0, 60); }
@Test @Ignore public void testMergeSpeed() throws PlanningException { for (int j = 0; j < 100; j++) { TreeMap<Long, Resource> a = new TreeMap<>(); TreeMap<Long, Resource> b = new TreeMap<>(); Random rand = new Random(); long startA = 0; long startB = 0; for (int i = 0; i < 1000 + rand.nextInt(9000); i++) { startA += rand.nextInt(100); startB += rand.nextInt(100); a.put(startA, Resource.newInstance(rand.nextInt(10240), rand.nextInt(10))); b.put(startB, Resource.newInstance(rand.nextInt(10240), rand.nextInt(10))); } RLESparseResourceAllocation rleA = new RLESparseResourceAllocation(a, new DefaultResourceCalculator()); RLESparseResourceAllocation rleB = new RLESparseResourceAllocation(b, new DefaultResourceCalculator()); long start = System.currentTimeMillis(); RLESparseResourceAllocation out = RLESparseResourceAllocation.merge(new DefaultResourceCalculator(), Resource.newInstance(100 * 128 * 1024, 100 * 32), rleA, rleB, RLEOperator.add, Long.MIN_VALUE, Long.MAX_VALUE); long end = System.currentTimeMillis(); System.out.println(" Took: " + (end - start) + "ms "); } }