1 /* 2 ------------------------------------------------------------------- 3 4 Copyright (C) 2014, Edwin van Leeuwen 5 6 This file is part of todod todo list manager. 7 8 Todod is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3 of the License, or 11 (at your option) any later version. 12 13 Todod is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with Todod. If not, see <http://www.gnu.org/licenses/>. 20 21 ------------------------------------------------------------------- 22 */ 23 24 module todod.set; 25 import std.algorithm; 26 import std.array; 27 import std.container; 28 import std.json; 29 30 /// Set implemented on top of ranges. Unique and ordered (at time of adding) 31 struct Set(T) { 32 /// Add an element to the set 33 void add( E : T )( E element ) { 34 auto elements = _array.find( element ); 35 if ( elements.empty ) { 36 _array ~= element; 37 sort( _array ); 38 } else { 39 if (!element.id.empty) // Will automatically cause sync to HabitRPG id 40 elements[0].id = element.id; 41 } 42 } 43 44 /// Add a range of elements 45 void add(RANGE)(RANGE elements ) { 46 // TODO optimize this since both ranges are sorted 47 foreach (element; elements) 48 add( element ); 49 } 50 51 /// Remove an element from the set 52 void remove(E : T)( E element ) { 53 auto i = countUntil( _array, element ); 54 if (i != -1) 55 _array = _array[0..i] ~ _array[i+1..$]; 56 } 57 58 /// Remove a range of elements 59 void remove(RANGE)( RANGE elements ) { 60 // TODO optimize this since both ranges are sorted 61 foreach (element; elements) 62 remove( element ); 63 } 64 65 /// Returns the front/first element of the set 66 T front() { 67 return _array.front; 68 } 69 70 /// Removes the front element from the set 71 void popFront() { 72 _array.popFront; 73 } 74 75 /// Returns true when the set is empty 76 bool empty() const { 77 if (_array.length > 0) 78 return false; 79 return true; 80 } 81 82 /// Return an array version of the set 83 T[] array() { 84 return _array; 85 } 86 87 /// Number of elements in the set 88 size_t length() const { 89 return _array.length; 90 } 91 92 /// Access by id. 93 T opIndex(size_t id) { 94 return _array[id]; 95 } 96 97 private: 98 T[] _array; 99 } 100 101 unittest { 102 import std.uuid; 103 class Test { 104 UUID id; 105 this() { 106 id = randomUUID; 107 } 108 109 override int opCmp( Object t ) const { 110 return this.id < (cast(Test)(t)).id; 111 } 112 } 113 114 Set!Test set; 115 set.add( new Test ); 116 assert( set.length == 1 ); 117 set.add( [ new Test, new Test ] ); 118 assert( set.length == 3 ); 119 } 120 121 122 /// Convert set to json array. The element needs to implement a toJSON function 123 JSONValue[] toJSON(T)( Set!T set ) { 124 JSONValue[] json; 125 foreach (t; set) 126 json ~= t.toJSON; 127 return json; 128 } 129 130 /// Load set from JSON, needs delegate to convert json into the element type 131 Set!T jsonToSet(T)( in JSONValue json, T delegate( in JSONValue ) convert ) { 132 Set!T set; 133 assert( json.type == JSON_TYPE.ARRAY ); 134 foreach ( js; json.array ) 135 set.add( convert( js ) ); 136 return set; 137 } 138 139 /// Convert Set to JSON given a function to convert the element type to JSON 140 JSONValue setToJSON( T )( Set!T set, JSONValue delegate( in T ) convert ) { 141 JSONValue[] json; 142 foreach ( el; set ) { 143 json ~= convert( el ); 144 } 145 return JSONValue(json); 146 }