#306

Committed 30 Apr 2024 10:01PM UTC coverage: 97.645% (-0.5%) from 98.139%

Build # #306

Build Type

push

Committed by

Commit Message

Merge pull request #555 from apache/fix_pom_xml_header

Fix pom xml header

Run Details

26865 of 27513 relevant lines covered (97.64%)

0.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.7

/src/main/java/org/apache/datasketches/hll/CouponList.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.datasketches.hll;

import static org.apache.datasketches.hll.HllUtil.EMPTY;
import static org.apache.datasketches.hll.HllUtil.LG_INIT_LIST_SIZE;
import static org.apache.datasketches.hll.HllUtil.LG_INIT_SET_SIZE;
import static org.apache.datasketches.hll.PreambleUtil.LIST_INT_ARR_START;
import static org.apache.datasketches.hll.PreambleUtil.LIST_PREINTS;
import static org.apache.datasketches.hll.PreambleUtil.extractLgK;
import static org.apache.datasketches.hll.PreambleUtil.extractListCount;
import static org.apache.datasketches.hll.PreambleUtil.extractTgtHllType;

import org.apache.datasketches.common.SketchesStateException;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;

/**
 * @author Lee Rhodes
 * @author Kevin Lang
 */
class CouponList extends AbstractCoupons {
  int lgCouponArrInts;
  int couponCount;
  int[] couponIntArr;

  private static int checkLgConfigK(final CurMode curMode, final int lgConfigK) {
    if (curMode == CurMode.SET) { assert lgConfigK > 7; }
    return lgConfigK;
  }

  /**
   * New instance constructor for LIST or SET.
   * @param lgConfigK the configured Lg K
   * @param tgtHllType the configured HLL target
   * @param curMode LIST or SET
   */
  CouponList(final int lgConfigK, final TgtHllType tgtHllType, final CurMode curMode) {
    super(checkLgConfigK(curMode, lgConfigK), tgtHllType, curMode);
    if (curMode == CurMode.LIST) {
      lgCouponArrInts = LG_INIT_LIST_SIZE;
    } else { //SET
      lgCouponArrInts = LG_INIT_SET_SIZE;
    }
    couponIntArr = new int[1 << lgCouponArrInts];
    couponCount = 0;
  }

  /**
   * Copy Constructor
   * @param that another CouponArray
   */
  CouponList(final CouponList that) {
    super(that.lgConfigK, that.tgtHllType, that.curMode);
    lgCouponArrInts = that.lgCouponArrInts;
    couponCount = that.couponCount;
    couponIntArr = that.couponIntArr.clone();
  }

  /**
   * Copy As constructor.
   * @param that another CouponList
   * @param tgtHllType the new target Hll type
   */ //also used by CouponHashSet
  CouponList(final CouponList that, final TgtHllType tgtHllType) {
    super(that.lgConfigK, tgtHllType, that.curMode);
    lgCouponArrInts = that.lgCouponArrInts;
    couponCount = that.couponCount;
    couponIntArr = that.couponIntArr.clone();
  }

  static final CouponList heapifyList(final Memory mem) {
    final int lgConfigK = extractLgK(mem);
    final TgtHllType tgtHllType = extractTgtHllType(mem);

    final CouponList list = new CouponList(lgConfigK, tgtHllType, CurMode.LIST);
    final int couponCount = extractListCount(mem);
    mem.getIntArray(LIST_INT_ARR_START, list.couponIntArr, 0, couponCount);
    list.couponCount = couponCount;
    return list;
  }

  @Override
  CouponList copy() {
    return new CouponList(this);
  }

  @Override
  CouponList copyAs(final TgtHllType tgtHllType) {
    return new CouponList(this, tgtHllType);
  }

  @Override
  HllSketchImpl couponUpdate(final int coupon) {
    final int len = 1 << lgCouponArrInts;
    for (int i = 0; i < len; i++) { //search for empty slot
      final int couponAtIdx = couponIntArr[i];
      if (couponAtIdx == EMPTY) {
        couponIntArr[i] = coupon; //update
        couponCount++;
        if (couponCount >= len) { //array full
          if (lgConfigK < 8) {
            return promoteHeapListOrSetToHll(this); //oooFlag = false
          }
          return promoteHeapListToSet(this); //oooFlag = true
        }
        return this;
      }
      //cell not empty
      if (couponAtIdx == coupon) {
        return this; //duplicate
      }
      //cell not empty & not a duplicate, continue
    } //end for
    throw new SketchesStateException("Array invalid: no empties & no duplicates");
  }

  @Override
  int getCompactSerializationBytes() {
    return getMemDataStart() + (couponCount << 2);
  }

  @Override
  int getCouponCount() {
    return couponCount;
  }

  @Override
  int[] getCouponIntArr() {
    return couponIntArr;
  }

  @Override
  int getLgCouponArrInts() {
    return lgCouponArrInts;
  }

  @Override
  int getMemDataStart() {
    return LIST_INT_ARR_START;
  }

  @Override
  Memory getMemory() {
    return null;
  }

  @Override
  int getPreInts() {
    return LIST_PREINTS;
  }

  @Override
  WritableMemory getWritableMemory() {
    return null;
  }

  @Override
  boolean isCompact() {
    return false;
  }

  @Override
  boolean isMemory() {
    return false;
  }

  @Override
  boolean isOffHeap() {
    return false;
  }

  @Override
  boolean isSameResource(final Memory mem) {
    return false;
  }

  @Override
  PairIterator iterator() {
    return new IntArrayPairIterator(couponIntArr, lgConfigK);
  }

  @Override
  void mergeTo(final HllSketch that) {
    final int arrLen = couponIntArr.length;
    for (int i = 0; i < arrLen; i++) {
      final int pair = couponIntArr[i];
      if (pair == 0) { continue; }
      that.couponUpdate(pair);
    }
  }

  @Override
  CouponList reset() {
    return new CouponList(lgConfigK, tgtHllType, CurMode.LIST);
  }

  static final HllSketchImpl promoteHeapListToSet(final CouponList list) {
    final int couponCount = list.couponCount;
    final int[] arr = list.couponIntArr;
    final CouponHashSet chSet = new CouponHashSet(list.lgConfigK, list.tgtHllType);
    for (int i = 0; i < couponCount; i++) {
      chSet.couponUpdate(arr[i]);
    }
    return chSet;
  }

  //Promotional move of coupons to an HllSketch from either List or Set.
  //called by CouponHashSet.couponUpdate()
  //called by CouponList.couponUpdate()
  static final HllSketchImpl promoteHeapListOrSetToHll(final CouponList src) {
    final HllArray tgtHllArr = HllArray.newHeapHll(src.lgConfigK, src.tgtHllType);
    final PairIterator srcItr = src.iterator();
    tgtHllArr.putKxQ0(1 << src.lgConfigK);
    while (srcItr.nextValid()) {
      tgtHllArr.couponUpdate(srcItr.getPair());
    }
    tgtHllArr.putHipAccum(src.getEstimate());

    tgtHllArr.putOutOfOrder(false);
    return tgtHllArr;
  }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19
20	package org.apache.datasketches.hll;
21
22	import static org.apache.datasketches.hll.HllUtil.EMPTY;
23	import static org.apache.datasketches.hll.HllUtil.LG_INIT_LIST_SIZE;
24	import static org.apache.datasketches.hll.HllUtil.LG_INIT_SET_SIZE;
25	import static org.apache.datasketches.hll.PreambleUtil.LIST_INT_ARR_START;
26	import static org.apache.datasketches.hll.PreambleUtil.LIST_PREINTS;
27	import static org.apache.datasketches.hll.PreambleUtil.extractLgK;
28	import static org.apache.datasketches.hll.PreambleUtil.extractListCount;
29	import static org.apache.datasketches.hll.PreambleUtil.extractTgtHllType;
30
31	import org.apache.datasketches.common.SketchesStateException;
32	import org.apache.datasketches.memory.Memory;
33	import org.apache.datasketches.memory.WritableMemory;
34
35	/**
36	* @author Lee Rhodes
37	* @author Kevin Lang
38	*/
39	class CouponList extends AbstractCoupons {	1✔
40	int lgCouponArrInts;
41	int couponCount;
42	int[] couponIntArr;
43
44	private static int checkLgConfigK(final CurMode curMode, final int lgConfigK) {
45	if (curMode == CurMode.SET) { assert lgConfigK > 7; }	1✔
46	return lgConfigK;	1✔
47	}
48
49	/**
50	* New instance constructor for LIST or SET.
51	* @param lgConfigK the configured Lg K
52	* @param tgtHllType the configured HLL target
53	* @param curMode LIST or SET
54	*/
55	CouponList(final int lgConfigK, final TgtHllType tgtHllType, final CurMode curMode) {
56	super(checkLgConfigK(curMode, lgConfigK), tgtHllType, curMode);	1✔
57	if (curMode == CurMode.LIST) {	1✔
58	lgCouponArrInts = LG_INIT_LIST_SIZE;	1✔
59	} else { //SET
60	lgCouponArrInts = LG_INIT_SET_SIZE;	1✔
61	}
62	couponIntArr = new int[1 << lgCouponArrInts];	1✔
63	couponCount = 0;	1✔
64	}	1✔
65
66	/**
67	* Copy Constructor
68	* @param that another CouponArray
69	*/
70	CouponList(final CouponList that) {
71	super(that.lgConfigK, that.tgtHllType, that.curMode);	1✔
72	lgCouponArrInts = that.lgCouponArrInts;	1✔
73	couponCount = that.couponCount;	1✔
74	couponIntArr = that.couponIntArr.clone();	1✔
75	}	1✔
76
77	/**
78	* Copy As constructor.
79	* @param that another CouponList
80	* @param tgtHllType the new target Hll type
81	*/ //also used by CouponHashSet
82	CouponList(final CouponList that, final TgtHllType tgtHllType) {
83	super(that.lgConfigK, tgtHllType, that.curMode);	1✔
84	lgCouponArrInts = that.lgCouponArrInts;	1✔
85	couponCount = that.couponCount;	1✔
86	couponIntArr = that.couponIntArr.clone();	1✔
87	}	1✔
88
89	static final CouponList heapifyList(final Memory mem) {
90	final int lgConfigK = extractLgK(mem);	1✔
91	final TgtHllType tgtHllType = extractTgtHllType(mem);	1✔
92
93	final CouponList list = new CouponList(lgConfigK, tgtHllType, CurMode.LIST);	1✔
94	final int couponCount = extractListCount(mem);	1✔
95	mem.getIntArray(LIST_INT_ARR_START, list.couponIntArr, 0, couponCount);	1✔
96	list.couponCount = couponCount;	1✔
97	return list;	1✔
98	}
99
100	@Override
101	CouponList copy() {
102	return new CouponList(this);	1✔
103	}
104
105	@Override
106	CouponList copyAs(final TgtHllType tgtHllType) {
107	return new CouponList(this, tgtHllType);	1✔
108	}
109
110	@Override
111	HllSketchImpl couponUpdate(final int coupon) {
112	final int len = 1 << lgCouponArrInts;	1✔
113	for (int i = 0; i < len; i++) { //search for empty slot	1✔
114	final int couponAtIdx = couponIntArr[i];	1✔
115	if (couponAtIdx == EMPTY) {	1✔
116	couponIntArr[i] = coupon; //update	1✔
117	couponCount++;	1✔
118	if (couponCount >= len) { //array full	1✔
119	if (lgConfigK < 8) {	1✔
120	return promoteHeapListOrSetToHll(this); //oooFlag = false	1✔
121	}
122	return promoteHeapListToSet(this); //oooFlag = true	1✔
123	}
124	return this;	1✔
125	}
126	//cell not empty
127	if (couponAtIdx == coupon) {	1✔
128	return this; //duplicate	1✔
129	}
130	//cell not empty & not a duplicate, continue
131	} //end for
132	throw new SketchesStateException("Array invalid: no empties & no duplicates");	×
133	}
134
135	@Override
136	int getCompactSerializationBytes() {
137	return getMemDataStart() + (couponCount << 2);	1✔
138	}
139
140	@Override
141	int getCouponCount() {
142	return couponCount;	1✔
143	}
144
145	@Override
146	int[] getCouponIntArr() {
147	return couponIntArr;	1✔
148	}
149
150	@Override
151	int getLgCouponArrInts() {
152	return lgCouponArrInts;	1✔
153	}
154
155	@Override
156	int getMemDataStart() {
157	return LIST_INT_ARR_START;	1✔
158	}
159
160	@Override
161	Memory getMemory() {
162	return null;	1✔
163	}
164
165	@Override
166	int getPreInts() {
167	return LIST_PREINTS;	1✔
168	}
169
170	@Override
171	WritableMemory getWritableMemory() {
172	return null;	1✔
173	}
174
175	@Override
176	boolean isCompact() {
177	return false;	1✔
178	}
179
180	@Override
181	boolean isMemory() {
182	return false;	1✔
183	}
184
185	@Override
186	boolean isOffHeap() {
187	return false;	1✔
188	}
189
190	@Override
191	boolean isSameResource(final Memory mem) {
192	return false;	1✔
193	}
194
195	@Override
196	PairIterator iterator() {
197	return new IntArrayPairIterator(couponIntArr, lgConfigK);	1✔
198	}
199
200	@Override
201	void mergeTo(final HllSketch that) {
202	final int arrLen = couponIntArr.length;	1✔
203	for (int i = 0; i < arrLen; i++) {	1✔
204	final int pair = couponIntArr[i];	1✔
205	if (pair == 0) { continue; }	1✔
206	that.couponUpdate(pair);	1✔
207	}
208	}	1✔
209
210	@Override
211	CouponList reset() {
212	return new CouponList(lgConfigK, tgtHllType, CurMode.LIST);	1✔
213	}
214
215	static final HllSketchImpl promoteHeapListToSet(final CouponList list) {
216	final int couponCount = list.couponCount;	1✔
217	final int[] arr = list.couponIntArr;	1✔
218	final CouponHashSet chSet = new CouponHashSet(list.lgConfigK, list.tgtHllType);	1✔
219	for (int i = 0; i < couponCount; i++) {	1✔
220	chSet.couponUpdate(arr[i]);	1✔
221	}
222	return chSet;	1✔
223	}
224
225	//Promotional move of coupons to an HllSketch from either List or Set.
226	//called by CouponHashSet.couponUpdate()
227	//called by CouponList.couponUpdate()
228	static final HllSketchImpl promoteHeapListOrSetToHll(final CouponList src) {
229	final HllArray tgtHllArr = HllArray.newHeapHll(src.lgConfigK, src.tgtHllType);	1✔
230	final PairIterator srcItr = src.iterator();	1✔
231	tgtHllArr.putKxQ0(1 << src.lgConfigK);	1✔
232	while (srcItr.nextValid()) {	1✔
233	tgtHllArr.couponUpdate(srcItr.getPair());	1✔
234	}
235	tgtHllArr.putHipAccum(src.getEstimate());	1✔
236
237	tgtHllArr.putOutOfOrder(false);	1✔
238	return tgtHllArr;	1✔
239	}
240
241	}

apache / datasketches-java / #306

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous