indexedRelation source code

1 module indexedRelation;
2 
3 import std.functional: unaryFun;
4 import std.typecons: Nullable, Tuple, nullable;
5 
6 version (unittest) {
7     import std.exception: assertThrown;
8 }
9 
10 /// A bag of records with efficient lookup on multiple independent keys.
11 public class IndexedRelation(Record, Indices...) {
12     private Record[] records;
13     private Tuple!Indices indices;
14 
15     public this() {
16         static foreach (i; 0 .. Indices.length) {
17             indices[i] = new Indices[i];
18         }
19     }
20 
21     public void insert(Record record) {
22         records ~= [record];
23         static foreach (i; 0 .. Indices.length) {
24             indices[i].insert(record);
25         }
26     }
27 
28     public auto lookup(int i)(Indices[i].Key key) {
29         return indices[i].lookup(key);
30     }
31 }
32 
33 /// An index based on a hash table. Allows multiple records with the same key.
34 public class HashTableIndex(Record, string KeyString) {
35     private alias KeyFunction = unaryFun!KeyString;
36     public alias Key = typeof(KeyFunction(Record.init));
37 
38     private Record[][Key] records;
39 
40     public void insert(Record record) {
41         records[KeyFunction(record)] ~= [record];
42     }
43 
44     public Record[] lookup(Key key) {
45         if (key !in records) return [];
46         return records[key];
47     }
48 }
49 
50 /// An index based on a hash table. Prohibits multiple records with the same
51 /// key.
52 public class UniqueHashTableIndex(Record, string KeyString) {
53     private alias KeyFunction = unaryFun!KeyString;
54     public alias Key = typeof(KeyFunction(Record.init));
55 
56     private Record[Key] records;
57 
58     public void insert(Record record) {
59         auto key = KeyFunction(record);
60         if (key in records) {
61             throw new Exception("Key already present in unique index");
62         }
63         records[key] = record;
64     }
65 
66     public Nullable!Record lookup(Key key) {
67         if (key !in records) return Nullable!Record.init;
68         return records[key].nullable;
69     }
70 }
71 
72 unittest {
73     struct Employee {
74         public ulong id;
75         public string firstName;
76         public string lastName;
77         public ulong salary;
78     }
79 
80     auto employee1 = Employee(1, "John", "Backus", 1000);
81     auto employee2 = Employee(2, "Rob", "Pike", 1100);
82     auto employee3 = Employee(3, "Walter", "Bright", 1200);
83 
84     auto employees = new IndexedRelation!(
85         Employee,
86         UniqueHashTableIndex!(Employee, "a.id"),
87         HashTableIndex!(Employee, "a.firstName"),
88         HashTableIndex!(Employee, "a.firstName.toUpper")
89     );
90 
91     employees.insert(employee1);
92     employees.insert(employee2);
93     employees.insert(employee3);
94     assertThrown(employees.insert(employee1));
95 
96     assert(employees.lookup!0(1) == employee1.nullable);
97     assert(employees.lookup!1("Rob") == [employee2]);
98     assert(employees.lookup!2("WALTER") == [employee3]);
99 
100     assert(employees.lookup!0(4) == Nullable!Employee.init);
101     assert(employees.lookup!1("Guido") == []);
102     assert(employees.lookup!2("BJARNE") == []);
103 }