Skip to content

Instantly share code, notes, and snippets.

@kotet
Last active May 30, 2019
Embed
What would you like to do?
半永続(partially persistent)2分探索木 https://www.youtube.com/watch?v=T0yzrZL1py0
/*
$ rdmd tree.d
insert/print [i,p]: i
value: 2
2 inserted. current version: 1
insert/print [i,p]: i
value: 6
6 inserted. current version: 2
insert/print [i,p]: i
value: 3
3 inserted. current version: 3
insert/print [i,p]: i
value: 4
4 inserted. current version: 4
insert/print [i,p]: i
value: 1
1 inserted. current version: 5
insert/print [i,p]: p
version [1-5]: 4
digraph g {
"n7F0577033060" [label="2"];
nullL7F0577033060 [shape=point];
"n7F0577033060" -> nullL7F0577033060
"n7F05770330F0" [label="6"];
"n7F0577033090" [label="3"];
nullL7F0577033090 [shape=point];
"n7F0577033090" -> nullL7F0577033090
"n7F0577033120" [label="4"];
nullL7F0577033120 [shape=point];
"n7F0577033120" -> nullL7F0577033120
nullR7F0577033120 [shape=point];
"n7F0577033120" -> nullR7F0577033120
"n7F0577033090" -> "n7F0577033120"
"n7F05770330F0" -> "n7F0577033090"
nullR7F05770330F0 [shape=point];
"n7F05770330F0" -> nullR7F05770330F0
"n7F0577033060" -> "n7F05770330F0"
}
insert/print [i,p]: p
version [1-5]: 3
digraph g {
"n7F0577033060" [label="2"];
nullL7F0577033060 [shape=point];
"n7F0577033060" -> nullL7F0577033060
"n7F0577033030" [label="6"];
"n7F0577033090" [label="3"];
nullL7F0577033090 [shape=point];
"n7F0577033090" -> nullL7F0577033090
nullR7F0577033090 [shape=point];
"n7F0577033090" -> nullR7F0577033090
"n7F0577033030" -> "n7F0577033090"
nullR7F0577033030 [shape=point];
"n7F0577033030" -> nullR7F0577033030
"n7F0577033060" -> "n7F0577033030"
}
*/
import std.stdio : readln, writefln, writeln, write;
import std.conv : to;
import std.typecons : Tuple;
import std.exception : collectException;
import std.string : chomp;
struct PersistentBinaryTree(T)
{
size_t v;
enum Field
{
lhs,
rhs
}
struct Node
{
T key;
Node* lhs;
Node* rhs;
Node* now;
Field field;
size_t ver;
this(T _key, Node* _lhs, Node* _rhs)
{
key = _key;
lhs = _lhs;
rhs = _rhs;
}
Node* insert(T x, ref size_t v)
{
if (this.key == x)
return null;
Node* n = &this;
Node* ret = null;
if (this.now) switch (this.field)
{
case Field.lhs:
ret = n = new Node(this.key, this.now, this.rhs);
break;
case Field.rhs:
ret = n = new Node(this.key, this.lhs, this.now);
break;
default:
assert(0);
}
n.field = (x < n.key) ? Field.lhs : Field.rhs;
if (x < n.key && n.lhs)
n.now = n.lhs.insert(x, v);
else if (n.key < x && n.rhs)
n.now = n.rhs.insert(x, v);
else
{
n.now = new Node(x, null, null);
v++;
}
n.ver = v;
return ret;
}
// for debug
string printAll()
{
string result = `"n` ~ (&this).to!string ~ `" [label="<key>` ~ this.key.to!string
~ ` | <lhs> lhs | <rhs> rhs | <now> now | <field> ` ~ (now
? ((this.field == Field.lhs) ? "L" : "R") : "") ~ ` | <ver>` ~ (now
? "v" ~ this.ver.to!string : "") ~ `" shape="record" ]` ~ '\n';
if (this.lhs)
{
result ~= this.lhs.printAll();
result ~= `"n` ~ (&this).to!string ~ `":lhs -> "n` ~ this.lhs.to!string ~ `"` ~ '\n';
}
if (this.rhs)
{
result ~= this.rhs.printAll();
result ~= `"n` ~ (&this).to!string ~ `":rhs -> "n` ~ this.rhs.to!string ~ `"` ~ '\n';
}
if (this.now)
{
result ~= this.now.printAll();
result ~= `"n` ~ (&this).to!string ~ `":now -> "n` ~ this.now.to!string ~ `"` ~ '\n';
}
return result;
}
string print(size_t v)
{
string result = `"n` ~ (&this)
.to!string ~ `" [label="` ~ this.key.to!string ~ '"' ~ "];\n";
if ((this.lhs && (!(this.now) || this.field == Field.rhs || v < this.ver))
|| (this.now && this.field == Field.lhs && this.ver <= v))
{
Node* n = (this.now && this.field == Field.lhs && this.ver <= v) ? this.now
: this.lhs;
assert(n);
result ~= n.print(v);
result ~= `"n` ~ (&this).to!string ~ `" -> "n` ~ n.to!string ~ `"` ~ '\n';
}
else
{
result ~= "nullL" ~ (&this).to!string ~ " [shape=point];\n";
result ~= `"n` ~ (&this).to!string ~ `" -> ` ~ "nullL" ~ (&this).to!string ~ '\n';
}
if ((this.rhs && (!(this.now) || this.field == Field.lhs || v < this.ver))
|| (this.now && this.field == Field.rhs && this.ver <= v))
{
Node* n = (this.now && this.field == Field.rhs && this.ver <= v) ? this.now
: this.rhs;
assert(n);
result ~= n.print(v);
result ~= `"n` ~ (&this).to!string ~ `" -> "n` ~ n.to!string ~ `"` ~ '\n';
}
else
{
result ~= "nullR" ~ (&this).to!string ~ " [shape=point];\n";
result ~= `"n` ~ (&this).to!string ~ `" -> ` ~ "nullR" ~ (&this).to!string ~ '\n';
}
return result;
}
}
Tuple!(size_t, Node*)[] root;
void insert(T x)
{
if (root.length == 0)
{
root ~= Tuple!(size_t, Node*)(++v, new Node(x, null, null));
return;
}
Node* r = root[$ - 1][1].insert(x, v);
if (r)
{
root ~= Tuple!(size_t, Node*)(v, r);
}
}
string printAll()
{
string result = "digraph g {\n";
result ~= `"root" [ label="`;
foreach (i, t; root)
{
if (i)
result ~= " | ";
result ~= "<v" ~ i.to!string ~ "> v" ~ t[0].to!string;
}
result ~= `" shape="record"];` ~ '\n';
foreach (i, t; root)
{
result ~= t[1].printAll();
result ~= `"root":v` ~ i.to!string ~ ` -> "n` ~ t[1].to!string ~ `"` ~ "\n";
}
result ~= "}";
return result;
}
string print(size_t v)
{
if (root.length == 0)
return "";
size_t i;
while (i < root.length && root[i][0] <= v)
i++;
string result = "digraph g {\n";
result ~= root[i - 1][1].print(v);
result ~= "}";
return result;
}
}
void main()
{
PersistentBinaryTree!long t;
while (true)
{
write("insert/print [i,p]: ");
string op = readln();
if (op[0] == 'i')
{
while (true)
{
write("value: ");
long x;
if (!collectException(readln().chomp().to!long, x))
{
t.insert(x);
writeln(x, " inserted. current version: ", t.v);
break;
}
}
}
if (op[0] == 'p')
{
while (true)
{
write("version [", 1, "-", t.v, "]: ");
size_t x;
if (!collectException(readln().chomp().to!size_t, x) && x <= t.v)
{
writeln();
t.print(x).writeln();
writeln();
break;
}
else
{
writeln("debug print");
writeln();
t.printAll().writeln();
writeln();
break;
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment