Skip to content

Commit 0e3187f

Browse files
jbgijbgi
authored
Add a Hash Array Mapped Trie
* Copied hamt from personal repo * Created show instances. Fixed BitSet.xor * Fixing overflow on BitSet longs. Adding tests * BitSet properties test * More BitSetProperties tests * Added remaining BitSet properties required * Moved hamt to String to the Show class * Clean up hamt test print lines * Updated after Gen/Arbitrary changes * Changed BitSet method name for creation from a long value * Fixed BitSet.asString * Added javadoc for HAMT * Added javadoc for HAMT * More tests on BitSet * Added more tests and minor refactoring for BitSet * Fixed BitSet.takeUpper * Fixed HAMT issue * Deleted BitSetTest * Fixed find and set. Added folds for HAMT * Properties and ad hoc tests for HAMT properties * Added Seq insert and filter * Added count population (CTPOP) from the paper for a bit set * Minor clean-up, remove dead-code. * improve BitSet#range performance (use bitwise operations) * remove unnecessary lambda
1 parent f56fa23 commit 0e3187f

13 files changed

Lines changed: 921 additions & 3 deletions

File tree

‎core/src/main/java/fj/Equal.java‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
import static fj.Function.curry;
44

55
import fj.data.*;
6+
import fj.data.hamt.BitSet;
67
import fj.data.hlist.HList;
78
import fj.data.vector.V2;
89
import fj.data.vector.V3;
@@ -104,6 +105,8 @@ public static <A> Equal<A> anyEqual() {
104105
*/
105106
public static final Equal<Boolean> booleanEqual = anyEqual();
106107

108+
public static final Equal<BitSet> bitSetSequal = Equal.equal(bs1 -> bs2 -> bs1.longValue() == bs2.longValue());
109+
107110
/**
108111
* An equal instance for the <code>byte</code> type.
109112
*/

‎core/src/main/java/fj/Show.java‎

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
11
package fj;
22

33
import fj.data.*;
4+
import fj.data.hamt.BitSet;
5+
import fj.data.hamt.HashArrayMappedTrie;
46
import fj.data.fingertrees.FingerTree;
5-
import fj.data.fingertrees.Node;
67
import fj.data.hlist.HList;
78
import fj.data.vector.V2;
89
import fj.data.vector.V3;
@@ -315,7 +316,7 @@ public static <V, A> Show<fj.data.fingertrees.Digit<V, A>> digitShow(final Show<
315316
});
316317
}
317318

318-
public static <V, A> Show<Node<V, A>> nodeShow(final Show<V> sv, final Show<A> sa) {
319+
public static <V, A> Show<fj.data.fingertrees.Node<V, A>> nodeShow(final Show<V> sv, final Show<A> sa) {
319320
return show(n -> {
320321
final String s = n.match(
321322
n2 -> "Node2(" + n2.measure() + " -> " + v2Show(sa).showS(n2.toVector()) + ")",
@@ -701,4 +702,21 @@ public static <A> Show<Stream<A>> unlineShow(final Show<A> sa) {
701702
public static <E, L extends HList<L>> Show<HList.HCons<E, L>> HListShow(final Show<E> e, final Show<L> l) {
702703
return show(c -> fromString("HList(").append(e.show(c.head())).append(l.show(c.tail())).append(fromString(")")));
703704
}
705+
706+
public static <K, V> Show<fj.data.hamt.Node<K, V>> hamtNodeShow(Show<K> sk, Show<V> sv) {
707+
F<fj.data.hamt.Node<K, V>, String> f = n -> n.match(p -> p2Show(sk, sv).showS(p), h -> hamtShow(sk, sv).showS(h));
708+
return Show.showS(f);
709+
}
710+
711+
public static <K, V> Show<HashArrayMappedTrie<K, V>> hamtShow(Show<K> sk, Show<V> sv) {
712+
return Show.showS(hamt ->
713+
"HashArrayMappedTrie(" + Show.bitSetShow.showS(hamt.getBitSet()) +
714+
", " + Show.seqShow(Show.hamtNodeShow(sk, sv)).showS(hamt.getSeq()) + ")"
715+
);
716+
}
717+
718+
public static final Show<BitSet> bitSetShow = Show.showS(
719+
bs -> "BitSet(" + bs.asString() + ")"
720+
);
721+
704722
}

‎core/src/main/java/fj/data/Seq.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -275,6 +275,18 @@ public boolean isEmpty() {
275275
return ftree.isEmpty();
276276
}
277277

278+
/**
279+
* Inserts the element at the given index. This is an O(log(n)) operation.
280+
*
281+
* @param index The index of the element to return.
282+
* @return The sequence with the element inserted at the given index,
283+
* or throws an error if the index is out of bounds.
284+
*/
285+
public Seq<A> insert(int index, A a) {
286+
final P2<Seq<A>, Seq<A>> p = split(index);
287+
return p._1().append(single(a)).append(p._2());
288+
}
289+
278290
/**
279291
* Checks if this sequence is not empty.
280292
*
@@ -370,6 +382,11 @@ public <B> B foldRight(final F2<A, B, B> f, final B z) {
370382
return ftree.foldRight(f, z);
371383
}
372384

385+
386+
public Seq<A> filter(F<A, Boolean> f) {
387+
return foldLeft((acc, a) -> f.f(a) ? acc.snoc(a) : acc, empty());
388+
}
389+
373390
@Override
374391
public int hashCode() {
375392
return Hash.seqHash(Hash.<A>anyHash()).hash(this);

‎core/src/main/java/fj/data/hamt/BitSet.java‎

Lines changed: 204 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,204 @@
1+
package fj.data.hamt;
2+
3+
import fj.Equal;
4+
import fj.F2;
5+
import fj.Monoid;
6+
import fj.Show;
7+
import fj.data.List;
8+
import fj.data.Stream;
9+
10+
/**
11+
* A sequence of bits representing a value. The most significant bit (the
12+
* bit with the highest value) is the leftmost bit and has the highest index.
13+
* For example, the BitSet("1011") represents the decimal number 11 and has
14+
* indices [3, 0] inclusive where the bit with the lowest value has the lowest
15+
* index and is the rightmost bit.
16+
*
17+
* Created by maperr on 31/05/2016.
18+
*/
19+
public final class BitSet {
20+
21+
public static final int TRUE_BIT = 1;
22+
public static final int FALSE_BIT = 0;
23+
public static final BitSet EMPTY = new BitSet(FALSE_BIT);
24+
25+
public static final long BASE_LONG = 1L;
26+
public static final int MAX_BIT_SIZE = Long.SIZE;
27+
public static final int MAX_BIT_INDEX = Long.SIZE - 1;
28+
29+
private final long value;
30+
31+
private BitSet(final long l) {
32+
value = l;
33+
}
34+
35+
public static BitSet empty() {
36+
return EMPTY;
37+
}
38+
39+
public static BitSet longBitSet(final long l) {
40+
return new BitSet(l);
41+
}
42+
43+
public static BitSet listBitSet(final List<Boolean> list) {
44+
final int n = list.length();
45+
if (n > MAX_BIT_SIZE) {
46+
throw new IllegalArgumentException("Does not support lists greater than " + MAX_BIT_SIZE + " bits, actual size is " + n);
47+
}
48+
long result = 0;
49+
for (Boolean b: list) {
50+
result = (result << 1) | toInt(b);
51+
}
52+
return longBitSet(result);
53+
}
54+
55+
public static BitSet streamBitSet(final Stream<Boolean> s) {
56+
return listBitSet(s.toList());
57+
}
58+
59+
public static BitSet stringBitSet(final String s) {
60+
return streamBitSet(Stream.fromString(s).map(BitSet::toBoolean));
61+
}
62+
63+
public boolean isSet(final int index) {
64+
return (value & (BASE_LONG << index)) != 0;
65+
}
66+
67+
public boolean isEmpty() {
68+
return value == 0;
69+
}
70+
71+
public BitSet set(final int index) {
72+
return longBitSet(value | (BASE_LONG << index));
73+
}
74+
75+
public BitSet set(final int index, boolean b) {
76+
return b ? set(index) : clear(index);
77+
}
78+
79+
public BitSet clear(final int index) {
80+
return longBitSet(value & ~(BASE_LONG << index));
81+
}
82+
83+
public long longValue() {
84+
return value;
85+
}
86+
87+
public BitSet and(final BitSet bs) {
88+
return longBitSet(value & bs.longValue());
89+
}
90+
91+
public BitSet or(final BitSet bs) {
92+
return longBitSet(value | bs.longValue());
93+
}
94+
95+
public BitSet shiftRight(final int n) {
96+
return longBitSet(value >> n);
97+
}
98+
99+
public BitSet shiftLeft(final int n) {
100+
return longBitSet(value << n);
101+
}
102+
103+
public int bitsUsed() {
104+
return toStream().length();
105+
}
106+
107+
public int bitsOn() {
108+
return toStream().foldLeft((acc, b) -> acc + (b ? 1 : 0), 0);
109+
}
110+
111+
/**
112+
* Returns a stream of boolean where the head is the most significant bit
113+
* (the bit with the largest value)
114+
*/
115+
public Stream<Boolean> toStream() {
116+
return Stream.fromString(Long.toBinaryString(value)).map(BitSet::toBoolean).dropWhile(b -> !b);
117+
}
118+
119+
@Override
120+
public String toString() {
121+
return Show.bitSetShow.showS(this);
122+
}
123+
124+
@Override
125+
public boolean equals(Object obj) {
126+
return Equal.equals0(BitSet.class, this, obj, Equal.bitSetSequal);
127+
}
128+
129+
public int bitsToRight(final int index) {
130+
if (index >= MAX_BIT_SIZE) {
131+
throw new IllegalArgumentException("Does not support an index " +
132+
"greater than or equal to " + MAX_BIT_SIZE + " bits, actual argument is " + index);
133+
}
134+
int pos = index - 1;
135+
long mask = BASE_LONG << (pos);
136+
int result = 0;
137+
while (pos >= 0) {
138+
if ((mask & value) != 0) {
139+
result++;
140+
}
141+
mask = mask >> 1;
142+
pos--;
143+
}
144+
return result;
145+
}
146+
147+
public List<Boolean> toList() {
148+
return toStream().toList();
149+
}
150+
151+
public <A> A foldRight(final F2<Boolean, A, A> f, A acc) {
152+
return toStream().foldRight(b -> p -> f.f(b, p._1()), acc);
153+
}
154+
155+
public <A> A foldLeft(final F2<A, Boolean, A> f, A acc) {
156+
return toStream().foldLeft(f, acc);
157+
}
158+
159+
public BitSet xor(final BitSet bs) {
160+
return longBitSet(value ^ bs.longValue());
161+
}
162+
163+
public BitSet not() {
164+
return longBitSet(~value);
165+
}
166+
167+
public BitSet takeLower(final int n) {
168+
return streamBitSet(toStream().reverse().take(n).reverse());
169+
}
170+
171+
public BitSet takeUpper(final int n) {
172+
String zero = Integer.toString(FALSE_BIT);
173+
String current = asString();
174+
String pad = Monoid.stringMonoid.sumLeft(List.replicate(MAX_BIT_SIZE - current.length(), zero));
175+
return stringBitSet(pad + current.substring(0, Math.max(n - pad.length(), 0)));
176+
}
177+
178+
/**
179+
* Returns the bit set from indices in the range from low (inclusive)
180+
* to high(exclusive) from the least significant bit (on the right),
181+
* e.g. "101101".range(1, 4) == "0110"
182+
*/
183+
public BitSet range(final int highIndex, final int lowIndex) {
184+
int max = Math.max(lowIndex, highIndex);
185+
int min = Math.min(lowIndex, highIndex);
186+
return new BitSet(max == min ? 0L : (value << (64 - max)) >>> (64 - max + min));
187+
}
188+
189+
public static boolean toBoolean(final char c) {
190+
return c != '0';
191+
}
192+
193+
public static boolean toBoolean(final int i) {
194+
return i != FALSE_BIT;
195+
}
196+
197+
public static int toInt(final boolean b) {
198+
return b ? TRUE_BIT : FALSE_BIT;
199+
}
200+
201+
public String asString() {
202+
return Long.toBinaryString(value);
203+
}
204+
}

0 commit comments

Comments
 (0)