File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\jenkins\model\lazy\SortedList.java.html

1 /*
2 * The MIT License
3 *
4 * Copyright (c) 2012, CloudBees, Inc.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 * THE SOFTWARE.
23 */
24 package jenkins.model.lazy;
25
26 import java.util.AbstractList;
27 import java.util.ArrayList;
28 import java.util.Collections;
29 import java.util.List;
30
31 /**
32 * {@link List} decorator that provides a number of binary-search related methods
33 * by assuming that the array is sorted in the ascending order.
34 *
35 * @author Kohsuke Kawaguchi
36 */
37 class SortedList<T extends Comparable<T>> extends AbstractList<T> {
38 private List<T> data;
39
40 public SortedList(List<T> data) {
41 this.data = new ArrayList<T>(data);
42 assert isSorted();
43 }
44
45 /**
46 * Binary search to find the position of the given string.
47 *
48 * @return
49 * -(insertionPoint+1) if the exact string isn't found.
50 * That is, -1 means the probe would be inserted at the very beginning.
51 */
52 public int find(T probe) {
53 return Collections.binarySearch(data, probe);
54 }
55
56 @Override
57 public boolean contains(Object o) {
58 return find((T)o)>=0;
59 }
60
61 public T get(int idx) {
62 return data.get(idx);
63 }
64
65 @Override
66 public int size() {
67 return data.size();
68 }
69
70 @Override
71 public T remove(int index) {
72 return data.remove(index);
73 }
74
75 @Override
76 public boolean remove(Object o) {
77 return data.remove(o);
78 }
79
80 /**
81 * Finds the index of the entry lower than v.
82 *
83 * @return
84 * return value will be in the [-1,size) range
85 */
86 public int lower(T v) {
87 return Boundary.LOWER.apply(find(v));
88 }
89
90 /**
91 * Finds the index of the entry greater than v.
92 *
93 * @return
94 * return value will be in the [0,size] range
95 */
96 public int higher(T v) {
97 return Boundary.HIGHER.apply(find(v));
98 }
99
100 /**
101 * Finds the index of the entry lower or equal to v.
102 *
103 * @return
104 * return value will be in the [-1,size) range
105 */
106 public int floor(T v) {
107 return Boundary.FLOOR.apply(find(v));
108 }
109
110 /**
111 * Finds the index of the entry greater or equal to v.
112 *
113 * @return
114 * return value will be in the [0,size] range
115 */
116 public int ceil(T v) {
117 return Boundary.CEIL.apply(find(v));
118 }
119
120 public boolean isInRange(int idx) {
121 return 0<=idx && idx<data.size();
122 }
123
124 private boolean isSorted() {
125 for (int i = 1; i < data.size(); i++) {
126 if (data.get(i).compareTo(data.get(i - 1)) < 0) {
127 return false;
128 }
129 }
130 return true;
131 }
132
133 }
134