| 660 | |
| 661 | template <class T, bool minimize> |
| 662 | void TCompactTrieTest::TestRandom(const size_t n, const size_t maxKeySize) { |
| 663 | const TStringBuf EMPTY_KEY = TStringBuf("", 1); |
| 664 | TCompactTrieBuilder<char, typename T::TData, T> builder; |
| 665 | typedef TMap<TString, typename T::TData> TKeys; |
| 666 | TKeys keys; |
| 667 | |
| 668 | typename T::TData dummy; |
| 669 | for (size_t i = 0; i < n; ++i) { |
| 670 | const TString key = RandStr(maxKeySize); |
| 671 | if (key != EMPTY_KEY && keys.find(key) == keys.end()) { |
| 672 | const typename T::TData val = T::Data(key); |
| 673 | keys[key] = val; |
| 674 | UNIT_ASSERT_C(!builder.Find(key.data(), key.size(), &dummy), "key = " << HexEncode(TString(key))); |
| 675 | builder.Add(key.data(), key.size(), val); |
| 676 | UNIT_ASSERT_C(builder.Find(key.data(), key.size(), &dummy), "key = " << HexEncode(TString(key))); |
| 677 | UNIT_ASSERT(dummy == val); |
| 678 | } |
| 679 | } |
| 680 | |
| 681 | TBufferStream stream; |
| 682 | size_t len = builder.Save(stream); |
| 683 | TCompactTrie<char, typename T::TData, T> trie(stream.Buffer().Data(), len); |
| 684 | |
| 685 | TBufferStream buftmp; |
| 686 | if (minimize) { |
| 687 | CompactTrieMinimize<T>(buftmp, stream.Buffer().Data(), len, false); |
| 688 | } |
| 689 | TCompactTrie<char, typename T::TData, T> trieMin(buftmp.Buffer().Data(), buftmp.Buffer().Size()); |
| 690 | |
| 691 | TCompactTrieBuilder<char, typename T::TData, T> prefixGroupedBuilder(CTBF_PREFIX_GROUPED); |
| 692 | |
| 693 | for (typename TKeys::const_iterator i = keys.begin(), mi = keys.end(); i != mi; ++i) { |
| 694 | UNIT_ASSERT(!prefixGroupedBuilder.Find(i->first.c_str(), i->first.size(), &dummy)); |
| 695 | UNIT_ASSERT(trie.Find(i->first.c_str(), i->first.size(), &dummy)); |
| 696 | UNIT_ASSERT(dummy == i->second); |
| 697 | if (minimize) { |
| 698 | UNIT_ASSERT(trieMin.Find(i->first.c_str(), i->first.size(), &dummy)); |
| 699 | UNIT_ASSERT(dummy == i->second); |
| 700 | } |
| 701 | |
| 702 | prefixGroupedBuilder.Add(i->first.c_str(), i->first.size(), dummy); |
| 703 | UNIT_ASSERT(prefixGroupedBuilder.Find(i->first.c_str(), i->first.size(), &dummy)); |
| 704 | |
| 705 | for (typename TKeys::const_iterator j = keys.begin(), end = keys.end(); j != end; ++j) { |
| 706 | typename T::TData valFound; |
| 707 | if (j->first <= i->first) { |
| 708 | UNIT_ASSERT(prefixGroupedBuilder.Find(j->first.c_str(), j->first.size(), &valFound)); |
| 709 | UNIT_ASSERT_VALUES_EQUAL(j->second, valFound); |
| 710 | } else { |
| 711 | UNIT_ASSERT(!prefixGroupedBuilder.Find(j->first.c_str(), j->first.size(), &valFound)); |
| 712 | } |
| 713 | } |
| 714 | } |
| 715 | |
| 716 | TBufferStream prefixGroupedBuffer; |
| 717 | prefixGroupedBuilder.Save(prefixGroupedBuffer); |
| 718 | |
| 719 | UNIT_ASSERT_VALUES_EQUAL(stream.Buffer().Size(), prefixGroupedBuffer.Buffer().Size()); |