File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\jenkins\model\lazy\SortedIntList.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.Arrays;
28
29 /**
30 * {@code ArrayList&lt;Integer>} that uses {@code int} for storage.
31 *
32 * Plus a number of binary-search related methods that assume the array is sorted in the ascending order.
33 *
34 * @author Kohsuke Kawaguchi
35 */
36 class SortedIntList extends AbstractList<Integer> {
37 private int[] data;
38 private int size;
39
40 public SortedIntList(int capacity) {
41 this.data = new int[capacity];
42 this.size = 0;
43 }
44
45 /**
46 * Internal copy constructor.
47 */
48 public SortedIntList(SortedIntList that) {
49 this.data = new int[that.size+8];
50 System.arraycopy(that.data, 0, this.data, 0,
51 that.size);
52 this.size = that.size;
53 }
54
55 /**
56 * Binary search to find the position of the given string.
57 *
58 * @return
59 * -(insertionPoint+1) if the exact string isn't found.
60 * That is, -1 means the probe would be inserted at the very beginning.
61 */
62 public int find(int probe) {
63 return binarySearch(data, 0, size, probe);
64 }
65
66 @Override
67 public boolean contains(Object o) {
68 return o instanceof Integer && contains(((Integer)o).intValue());
69 }
70
71 public boolean contains(int i) {
72 return find(i)>=0;
73 }
74
75 @Override
76 public Integer get(int index) {
77 if (size<=index) throw new IndexOutOfBoundsException();
78 return data[index];
79 }
80
81 @Override
82 public int size() {
83 return size;
84 }
85
86 @Override
87 public boolean add(Integer i) {
88 return add(i.intValue());
89 }
90
91 public boolean add(int i) {
92 ensureCapacity(size+1);
93 data[size++] = i;
94 return true;
95 }
96
97 private void ensureCapacity(int i) {
98 if (data.length<i) {
99 int[] r = new int[Math.max(data.length*2,i)];
100 System.arraycopy(data,0,r,0,size);
101 data = r;
102 }
103 }
104
105 /**
106 * Finds the index of the entry lower than v.
107 */
108 public int lower(int v) {
109 return Boundary.LOWER.apply(find(v));
110 }
111
112 /**
113 * Finds the index of the entry greater than v.
114 */
115 public int higher(int v) {
116 return Boundary.HIGHER.apply(find(v));
117 }
118
119 /**
120 * Finds the index of the entry lower or equal to v.
121 */
122 public int floor(int v) {
123 return Boundary.FLOOR.apply(find(v));
124 }
125
126 /**
127 * Finds the index of the entry greater or equal to v.
128 */
129 public int ceil(int v) {
130 return Boundary.CEIL.apply(find(v));
131 }
132
133 public boolean isInRange(int idx) {
134 return 0<=idx && idx<size;
135 }
136
137 public void sort() {
138 Arrays.sort(data,0,size);
139 }
140
141 public void copyInto(int[] dest) {
142 System.arraycopy(data,0,dest,0,size);
143 }
144
145 public void removeValue(int n) {
146 int idx = find(n);
147 if (idx<0) return;
148 System.arraycopy(data,idx+1,data,idx,size-(idx+1));
149 size--;
150 }
151
152 /**
153 * Switch to {@code java.util.Arrays.binarySearch} when we depend on Java6.
154 */
155 private static int binarySearch(int[] a, int start, int end, int key) {
156 int lo = start, hi = end-1; // search range is [lo,hi]
157
158 // invariant lo<=hi
159 while (lo <= hi) {
160 int pivot = (lo + hi)/2;
161 int v = a[pivot];
162
163 if (v < key) // needs to search upper half
164 lo = pivot+1;
165 else if (v > key) // needs to search lower half
166 hi = pivot-1;
167 else // eureka!
168 return pivot;
169 }
170 return -(lo + 1); // insertion point
171 }
172 }
173