jaypha.container.set source code

1 //Written in the D programming language
2 /*
3  * Simple set implementation
4  *
5  * Copyright 2009-2014 Jaypha
6  *
7  * Distributed under the Boost Software License, Version 1.0.
8  * (See http://www.boost.org/LICENSE_1_0.txt)
9  *
10  * Authors: Jason den Dulk
11  */
12 
13 module jaypha.container.set;
14 
15 //----------------------------------------------------------------------------
16 // Simple collection where each element is unique.
17 //----------------------------------------------------------------------------
18 struct Set(E)
19 //----------------------------------------------------------------------------
20 {
21   void put(E e)
22   {
23     foreach (i; theSet)
24       if (e == i) return;
25     
26     theSet ~= e;
27   }
28 
29   @property size_t size() { return theSet.length; }
30   alias size length;
31 
32   @property auto range()
33   {
34     return theSet;
35   }
36 
37   private:
38     E[] theSet;
39 }
40 
41 //----------------------------------------------------------------------------
42 // Like Set, but the elements are ordered, and the set is indexable.
43 //----------------------------------------------------------------------------
44 struct IndexableSet(E)
45 //----------------------------------------------------------------------------
46 {
47   size_t put(E e)
48   {
49     foreach (i,j; theSet)
50       if (e == j) return i;
51 
52     theSet ~= e;
53     return theSet.length-1;
54   }
55 
56   @property size_t size() { return theSet.length; }
57   alias size length;
58 
59   E opIndex(size_t i) { return theSet[i]; }
60 
61   @property auto range()
62   {
63     return theSet;
64   }
65 
66   private:
67     E[] theSet;
68 }
69 
70 alias IndexableSet OrderedSet;
71 
72 //----------------------------------------------------------------------------
73 
74 unittest
75 {
76   Set!long set;
77 
78   assert(set.size == 0);
79 
80   set.put(5);
81   assert(set.size == 1);
82   set.put(7);
83   assert(set.size == 2);
84   set.put(5);
85   assert(set.size == 2);
86 
87   assert(set.range == [5,7]);
88 
89   IndexableSet!long oSet;
90 
91   assert(oSet.size == 0);
92 
93   oSet.put(5);
94   assert(oSet.size == 1);
95   oSet.put(7);
96   assert(oSet.size == 2);
97   oSet.put(5);
98   assert(oSet.size == 2);
99 
100   assert(oSet.range == [5,7]);
101   assert(oSet[0] == 5);
102   assert(oSet[1] == 7);
103 }