Java で C++ のパトリシア トライを書き直そうとしています。C++コードはこちらから
私は少し立ち往生しています。
だからここに私の理解があります：
#define ZEROTAB_SIZE 256
head->key = (char*)calloc(ZEROTAB_SIZE, 1);
キー用に 256 ビットの配列を作成するため、最大長 32 文字の文字列を作成し、すべての文字を 8 ビットで表すことができます。これをJavaのchar配列で実装できますか?
template <class T>
int PatriciaTrie<T>::bit_get(PatriciaTrieKey bit_stream, int n) {
if (n < 0) return 2; // "pseudo-bit" with a value of 2.
int k = (n & 0x7);
return ( (*(bit_stream + (n >> 3))) >> k) & 0x1;
}
k は n の最後の 7 ビットを取得し、文字列の n/8 文字に移動します (右にシフトすると 8 未満のものはすべて削除されてゼロになるため、正確には n/8 ではありません)、bit_stream[n> の値をシフトします。 >3] k によって、最後のビットを取得します。Javaで配列を使用する場合、これを次のように書き換えることができますか
return (bit_stream[n>>3] >> k) & 0x1;
?
template <class T>
int PatriciaTrie<T>::bit_first_different(PatriciaTrieKey k1, PatriciaTrieKey k2) {
if (!k1 || !k2)
return 0; // First bit is different!
int n = 0;
int d = 0;
while ( (k1[n] == k2[n]) &&
(k1[n] != 0) &&
(k2[n] != 0) )
n++;
while (bit_get(&k1[n], d) == bit_get(&k2[n], d))
d++;
return ((n << 3) + d);
}
ここがややこしいところです。最初の部分から 2 番目の while ループまでは十分に明確に見えます。ループして、ゼロ以外のビットがいくつあるかを確認しますが、2 番目のループが何をしているのかわかりません。アドレスを取得します。 2つのキーの最初のビットが等しいかどうかをチェックし、等しい場合は、等しくないビットが見つかるまでもう一度チェックしますか?
主に、キーのアドレスがここでどのように使用されているかわかりませんが、bit_get クラスでのビット シフトについても混乱する可能性があります。
JavaクラスのC ++とJavaのトライを比較したいのですが、実装をできるだけ類似させたいと思っています。