/** * Encode to a geohash string at a given level from a morton long */ public static final String stringEncodeFromMortonLong(long hashedVal, final int level) { // bit twiddle to geohash (since geohash is a swapped (lon/lat) encoding) hashedVal = BitUtil.flipFlop(hashedVal); StringBuilder geoHash = new StringBuilder(); short precision = 0; final short msf = (GeoPointField.BITS<<1)-5; long mask = 31L<<msf; do { geoHash.append(BASE_32[(int)((mask & hashedVal)>>>(msf-(precision*5)))]); // next 5 bits mask >>>= 5; } while (++precision < level); return geoHash.toString(); }
/** Create a HashDocSet from a list of *unique* ids */ public HashDocSet(int[] docs, int offset, int len, float inverseLoadFactor) { int tsize = Math.max(BitUtil.nextHighestPowerOfTwo(len), 1); if (tsize < len * inverseLoadFactor) { tsize <<= 1; } mask=tsize-1; table = new int[tsize]; // (for now) better then: Arrays.fill(table, EMPTY); // https://issues.apache.org/jira/browse/SOLR-390 for (int i=tsize-1; i>=0; i--) table[i]=EMPTY; int end = offset + len; for (int i=offset; i<end; i++) { put(docs[i]); } size = len; }
/** * Encode to a morton long value from a given geohash string */ public static final long mortonEncode(final String hash) { int level = 11; long b; long l = 0L; for(char c : hash.toCharArray()) { b = (long)(BASE_32_STRING.indexOf(c)); l |= (b<<((level--*5) + MORTON_OFFSET)); } return BitUtil.flipFlop(l); }
/** * Encode to a morton long value from a given geohash long value */ public static final long mortonEncode(final long geoHashLong) { final int level = (int)(geoHashLong&15); final short odd = (short)(level & 1); return BitUtil.flipFlop(((geoHashLong >>> 4) << odd) << (((12 - level) * 5) + (MORTON_OFFSET - odd))); }
/** * Computes the bounding box coordinates from a given geohash * * @param geohash Geohash of the defined cell * @return GeoRect rectangle defining the bounding box */ public static Rectangle bbox(final String geohash) { // bottom left is the coordinate GeoPoint bottomLeft = GeoPoint.fromGeohash(geohash); long ghLong = longEncode(geohash); // shift away the level ghLong >>>= 4; // deinterleave and add 1 to lat and lon to get topRight long lat = BitUtil.deinterleave(ghLong >>> 1) + 1; long lon = BitUtil.deinterleave(ghLong) + 1; GeoPoint topRight = GeoPoint.fromGeohash(BitUtil.interleave((int)lon, (int)lat) << 4 | geohash.length()); return new Rectangle(bottomLeft.lat(), topRight.lat(), bottomLeft.lon(), topRight.lon()); }
/** * Writes a long in a variable-length format. Writes between one and ten bytes. * Values are remapped by sliding the sign bit into the lsb and then encoded as an unsigned number * e.g., 0 -;> 0, -1 -;> 1, 1 -;> 2, ..., Long.MIN_VALUE -;> -1, Long.MAX_VALUE -;> -2 * Numbers with small absolute value will have a small encoding * If the numbers are known to be non-negative, use {@link #writeVLong(long)} */ public void writeZLong(long i) throws IOException { // zig-zag encoding cf. https://developers.google.com/protocol-buffers/docs/encoding?hl=en long value = BitUtil.zigZagEncode(i); while ((value & 0xFFFFFFFFFFFFFF80L) != 0L) { writeByte((byte)((value & 0x7F) | 0x80)); value >>>= 7; } writeByte((byte) (value & 0x7F)); }
public long readZLong() throws IOException { long accumulator = 0L; int i = 0; long currentByte; while (((currentByte = readByte()) & 0x80L) != 0) { accumulator |= (currentByte & 0x7F) << i; i += 7; if (i > 63) { throw new IOException("variable-length stream is too long"); } } return BitUtil.zigZagDecode(accumulator | (currentByte << i)); }
/** For testing */ public final int getRecomputedCount() { int c = 0; int end = bits.length; for (int i = 0; i < end; i++) { c += BitUtil.bitCount(bits[i]); // sum bits per byte } return c; }
/** Returns the popcount or cardinality of the union of the two sets. * Neither set is modified. */ public static long unionCount(OpenBitSet a, OpenBitSet b) { long tot = BitUtil.pop_union(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); if (a.wlen < b.wlen) { tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen); } else if (a.wlen > b.wlen) { tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen); } return tot; }
/** Returns the popcount or cardinality of "a and not b" * or "intersection(a, not(b))". * Neither set is modified. */ public static long andNotCount(OpenBitSet a, OpenBitSet b) { long tot = BitUtil.pop_andnot(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); if (a.wlen > b.wlen) { tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen); } return tot; }
/** Returns the popcount or cardinality of the exclusive-or of the two sets. * Neither set is modified. */ public static long xorCount(OpenBitSet a, OpenBitSet b) { long tot = BitUtil.pop_xor(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); if (a.wlen < b.wlen) { tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen); } else if (a.wlen > b.wlen) { tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen); } return tot; }
public VersionInfo(UpdateLog ulog, int nBuckets) { this.ulog = ulog; IndexSchema schema = ulog.uhandler.core.getLatestSchema(); versionField = getAndCheckVersionField(schema); idField = schema.getUniqueKeyField(); buckets = new VersionBucket[ BitUtil.nextHighestPowerOfTwo(nBuckets) ]; for (int i=0; i<buckets.length; i++) { buckets[i] = new VersionBucket(); } }
public VersionInfo(UpdateLog ulog, int nBuckets) { this.ulog = ulog; SolrCore core = ulog.uhandler.core; versionField = getAndCheckVersionField(core.getSchema()); idField = core.getSchema().getUniqueKeyField(); buckets = new VersionBucket[ BitUtil.nextHighestPowerOfTwo(nBuckets) ]; for (int i=0; i<buckets.length; i++) { buckets[i] = new VersionBucket(); } }
public GeoPoint resetFromGeoHash(long geohashLong) { final int level = (int)(12 - (geohashLong&15)); return this.resetFromIndexHash(BitUtil.flipFlop((geohashLong >>> 4) << ((level * 5) + 2))); }
/** * Encode lon/lat to the geohash based long format (lon/lat interleaved, 4 least significant bits = level) */ public static final long longEncode(final double lon, final double lat, final int level) { // shift to appropriate level final short msf = (short)(((12 - level) * 5) + MORTON_OFFSET); return ((BitUtil.flipFlop(GeoPointField.encodeLatLon(lat, lon)) >>> msf) << 4) | level; }
/** * Convert from a morton encoded long from a geohash encoded long */ public static long fromMorton(long morton, int level) { long mFlipped = BitUtil.flipFlop(morton); mFlipped >>>= (((GeoHashUtils.PRECISION - level) * 5) + MORTON_OFFSET); return (mFlipped << 4) | level; }
/** @return the number of set bits */ public long cardinality() { return BitUtil.pop_array(bits,0,wlen); }
/** Returns the popcount or cardinality of the intersection of the two sets. * Neither set is modified. */ public static long intersectionCount(OpenBitSet a, OpenBitSet b) { return BitUtil.pop_intersect(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen)); }
private void shift() { if ((int)word ==0) {wordShift +=32; word = word >>>32; } if ((word & 0x0000FFFF) == 0) { wordShift +=16; word >>>=16; } if ((word & 0x000000FF) == 0) { wordShift +=8; word >>>=8; } indexArray = BitUtil.bitList((byte) word); }
/** * Read a {@link BitUtil#zigZagDecode(int) zig-zag}-encoded * {@link #readVInt() variable-length} integer. * @see DataOutput#writeZInt(int) */ public int readZInt() throws IOException { return BitUtil.zigZagDecode(readVInt()); }
/** * Read a {@link BitUtil#zigZagDecode(long) zig-zag}-encoded * {@link #readVLong() variable-length} integer. Reads between one and ten * bytes. * @see DataOutput#writeZLong(long) */ public long readZLong() throws IOException { return BitUtil.zigZagDecode(readVLong(true)); }
/** * Write a {@link BitUtil#zigZagEncode(int) zig-zag}-encoded * {@link #writeVInt(int) variable-length} integer. This is typically useful * to write small signed ints and is equivalent to calling * <code>writeVInt(BitUtil.zigZagEncode(i))</code>. * @see DataInput#readZInt() */ public final void writeZInt(int i) throws IOException { writeVInt(BitUtil.zigZagEncode(i)); }
/** * Write a {@link BitUtil#zigZagEncode(long) zig-zag}-encoded * {@link #writeVLong(long) variable-length} long. Writes between one and ten * bytes. This is typically useful to write small signed ints. * @see DataInput#readZLong() */ public final void writeZLong(long i) throws IOException { writeNegativeVLong(BitUtil.zigZagEncode(i)); }
