fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <cstdint>
  5. #include <tuple>
  6. #include <random>
  7. #include <algorithm>
  8.  
  9. typedef std::vector<std::uint8_t> DType;
  10. typedef std::vector<DType> Table;
  11. typedef std::map<DType, bool> TableM;
  12. typedef std::vector<std::size_t> CData;
  13. typedef std::tuple<Table, CData> RType;
  14.  
  15. //LZW One of implimentation.
  16. //working on VC12
  17. //why not running??
  18.  
  19. DType MakeProblem(std::size_t N){
  20. 	std::mt19937 mt;
  21. 	std::uniform_int_distribution<> uid(0, 255);
  22.  
  23. 	DType D(N);
  24.  
  25. 	for (auto& o : D) o = uid(mt);
  26.  
  27. 	//std::sort(D.begin(), D.end());
  28.  
  29. 	return D;
  30. }
  31.  
  32. RType EncodeLZW(DType& D){
  33. 	Table Ta;
  34. 	TableM M;
  35. 	CData CD;
  36. 	DType Sug;
  37. 	bool F = false;
  38. 	std::size_t C = 0;
  39.  
  40. 	for (auto& o : D){
  41. 		Sug.push_back(o);
  42. 		M[Sug] = true;
  43. 		Sug.clear();
  44. 	}
  45.  
  46. 	Sug.clear();
  47.  
  48. 	for (std::size_t i = 0; i < D.size(); i++){
  49. 		Sug.push_back(D[i]);
  50. 		if (M[Sug] == true){
  51. 			continue;
  52. 		}
  53. 		M[Sug] = true;
  54. 		i--;
  55. 		Sug.clear();
  56. 	}
  57. 	M[Sug] = true;
  58. 	Sug.clear();
  59.  
  60. 	for (std::size_t i = 0; i < D.size(); i++){
  61. 		Sug.push_back(D[i]);
  62. 		if (M.find(Sug) != M.end()) continue;
  63. 		Sug.pop_back();
  64. 		auto it = find(Ta.begin(), Ta.end(), Sug);
  65. 		if (it == Ta.end()){
  66. 			CD.push_back(Ta.size());
  67. 			Ta.push_back(Sug);
  68. 		}
  69. 		else{
  70. 			CD.push_back(std::distance(Ta.begin(), it));
  71. 		}
  72. 		i--;
  73. 		Sug.clear();
  74. 	}
  75. 	auto it = find(Ta.begin(), Ta.end(), Sug);
  76. 	if (it == Ta.end()){
  77. 		CD.push_back(Ta.size());
  78. 		Ta.push_back(Sug);
  79. 	}
  80. 	else{
  81. 		CD.push_back(std::distance(Ta.begin(), it));
  82. 	}
  83. 	Sug.clear();
  84. 	CD.push_back(Ta.size());
  85.  
  86. 	return std::make_tuple(Ta, CD);
  87. }
  88.  
  89. DType DecodeLZW(RType& R){//手抜き
  90. 	Table& T = std::get<0>(R);
  91. 	CData& C = std::get<1>(R);
  92. 	DType D;
  93.  
  94. 	for (auto& A : C){
  95. 		for (auto& o : T[A]){
  96. 			D.push_back(o);
  97. 		}
  98. 	}
  99.  
  100. 	return D;
  101. }
  102.  
  103. int main(){
  104.  
  105. 	auto D = MakeProblem(10240);
  106. 	auto En = EncodeLZW(D);
  107. 	auto De = DecodeLZW(En);
  108.  
  109. 	auto& T = std::get<0>(En);
  110. 	auto& C = std::get<1>(En);
  111.  
  112.  
  113. 	if (D == De){
  114. 		std::cout << "Match!" << std::endl;
  115. 	}
  116. 	else{
  117. 		std::cout << "Miss Match!" << std::endl;
  118. 	}
  119. 	std::cout << "From " << D.size() << "Byte!" << std::endl;
  120. 	std::cout << "Table = " << T.size() << "Count!" << std::endl;
  121. 	std::cout << "Data = " << C.size() << "Count!" << std::endl;
  122.  
  123. 	return 0;
  124. }
Runtime error #stdin #stdout 0.2s 4088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cF0kDA
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!