sets 1.2.1

Generic vectors as sets. Efficiently sorting, merging, ranking, searching, reversing, intersecting, etc.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

use crate::{SType,Set,MutSetOps,trivindex};
use indxvec::{MinMax,Indices,Vecops};

/// Associated functions for conversions and self operations returning Set<T> = Self
impl<T> Set<T> where T: Copy+PartialOrd+Default {

    /// Associated constant EMPTYSET, unique for each concrete end-type T
    pub const EMPTYSET:Set<T> = Set{ stype:SType::Empty, ascending:true, data:Vec::new(), index:Vec::new() };

    /// all in one Initialiser creates a new Set
    /// of self_type, from slice d, in asc order 
    pub fn new(set_type: SType, d: &[T], asc:bool) -> Self {  
        if d.is_empty() { return Set::EMPTYSET }; // no data
        match set_type {
            SType::Empty => Set::EMPTYSET, // empty self specified
            SType::Unordered => Set{ stype:SType::Unordered, ascending:true, data:d.to_vec(), index:Vec::new() }, 
            SType::Ordered => Set{ stype:SType::Ordered, ascending:asc, data:d.sortm(asc), index:Vec::new() },
            SType::Indexed =>  Set{ stype:SType::Indexed, ascending:asc, data:d.to_vec(), 
                index: if asc { d.mergesort_indexed() } else { d.mergesort_indexed().revs() } },
            SType::Ranked => Set{ stype:SType::Ranked, ascending:asc, data:d.to_vec(), 
                index: if asc { d.mergesort_indexed().invindex() } else { d.mergesort_indexed().revs().invindex() } } }
    }

    /// Creates a new empty Set
    pub fn new_empty() -> Self { Self::EMPTYSET }

    /// Initialiser - creates a new SType::Unordered Set from data
    pub fn new_unordered(d: &[T]) -> Self {  
        if !d.is_empty() { // have some data
            Set{ stype:SType::Unordered, ascending:true, data:d.to_vec(), index:Vec::new() } } 
        else { Set::EMPTYSET } 
    }

    /// Initialiser - creates a new SType::Ordered Set in asc order from data 
    pub fn new_ordered(d: &[T], asc:bool) -> Self {  
        if !d.is_empty() { // have some data
            Set{ stype:SType::Ordered, ascending:asc, data:d.sortm(asc), index:Vec::new() } }
        else { Set::EMPTYSET } 
    }

    /// Initialiser - creates a new SType::Indexed Set in asc order from data 
    pub fn new_indexed(d: &[T], asc:bool) -> Self {  
        if !d.is_empty() { // have some data
            Set{ stype:SType::Indexed, ascending:asc, data:d.to_vec(), 
                index: if asc { d.mergesort_indexed() } else { d.mergesort_indexed().revs() } } }
        else { Set::EMPTYSET } 
    }

    /// Initialiser - creates a new SType::Ranked Set in asc order from data 
    pub fn new_ranked(d: &[T], asc:bool) -> Self {  
        if !d.is_empty() { // have some data
            Set{ stype:SType::Ranked, ascending:asc, data:d.to_vec(), 
                index: if asc { d.mergesort_indexed().invindex() } else { d.mergesort_indexed().revs().invindex() } } }
        else { Set::EMPTYSET } 
    }

    /// Converter - to SType::Unordered Set
    /// Caution: this just throws away the valuable index!
    pub fn to_unordered(&self) -> Self { 
        match self.stype {
            SType::Empty => Set::EMPTYSET, // no op 
            // ascending field has no meaning for unordered, so just inherit it
            _ => Self{ stype:SType::Unordered, ascending:self.ascending, data:self.data.clone(), index:Vec::new() }
        }
    }

    /// Converts any Set type to ordered
    pub fn to_ordered(&self, asc:bool) -> Self {
        match self.stype {
            SType::Empty => Set::EMPTYSET, 
            SType::Unordered => Self{ stype:SType::Ordered, ascending:asc, data:self.data.sortm(asc), index:Vec::new()},
            SType::Ordered => if self.ascending == asc { self.clone() } // just a copy
                else { Self{ stype:SType::Ordered, ascending:asc, data:self.data.revs(), index:Vec::new() } },
            SType::Indexed => Self{ stype:SType::Ordered, ascending:asc, 
                data:self.index.unindex(&self.data, self.ascending == asc), index:Vec::new() },
            SType::Ranked => Self{ stype:SType::Ordered, ascending:asc, 
                data:self.index.invindex().unindex(&self.data, self.ascending == asc), index:Vec::new() },
        }    
    }

    /// Converts any Set type to indexed
    pub fn to_indexed(&self,asc:bool) -> Self {
        match self.stype {
            SType::Empty => Set::EMPTYSET,
            SType::Unordered => Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(), 
                index: if asc {self.data.mergesort_indexed()} else {self.data.mergesort_indexed().revs()} },
            SType::Ordered => Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(), 
                index: trivindex(self.ascending == asc,self.data.len()) },
            SType::Indexed =>  if self.ascending == asc { self.clone() } // no op
                else { Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(),
                    index: self.index.revs() } },
            SType::Ranked => Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(),             
                index: if self.ascending == asc {self.index.invindex()} else {self.index.invindex().revs()}}
        }    
    }

    /// Converts any Set type to ranked
    pub fn to_ranked(&self,asc:bool) -> Self {
        match self.stype {
            SType::Empty => Set::EMPTYSET,
            SType::Unordered => Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(), 
                index: if asc {self.data.mergesort_indexed().invindex()} 
                    else {self.data.mergesort_indexed().revs().invindex()} },
            SType::Ordered => Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(), 
                index: trivindex(self.ascending == asc,self.data.len()) },
            SType::Indexed => Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(),             
                index: if self.ascending == asc {self.index.invindex()} 
                    else {self.index.revs().invindex()}}, 
            SType::Ranked => if self.ascending == asc { self.clone() } // no op
                else { Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(),
                    index: {self.index.complindex()} } }
        }    
    }

    /// General converter: s -> Set of the same type and order as self
    /// self only serves as a template for the type and order and is not involved in the conversion
    pub fn to_same(&self, s:&Self) -> Self { 
        match self.stype { 
            SType::Empty => Set::EMPTYSET, //  was Default::default()
            SType::Unordered => s.to_unordered(), 
            SType::Ordered => s.to_ordered(self.ascending),
            SType::Indexed => s.to_indexed(self.ascending),
            SType::Ranked => s.to_ranked(self.ascending)
        }
    }       

    /// Inserts an item of the same end-type to self
    pub fn insert(&self, item:T) -> Self {
        let mut scopy = self.clone();
        scopy.minsert(item);
        scopy 
    }

    /// Deletes an item of the same end-type from self
    pub fn delete(&self, item:T) -> Self {
        let mut scopy = self.clone();
        if scopy.mdelete(item) { scopy } else { self.clone() }
    }    

    /// Reverses a vec by iterating over only half of its length
    /// and swapping the items
    pub fn reverse(&self) -> Self { 
        let mut scopy = self.clone();
        scopy.mreverse();
        scopy
    }
 
    /// Deletes any repetitions
    pub fn nonrepeat(&self) -> Self { 
        let mut scopy =  self.clone();
        scopy.mnonrepeat();
        scopy
    }

    /// Union of two selfs  
    pub fn union(&self, s: &Self) -> Self {
        let mut scopy =  self.clone();
        scopy.munion(s);
        scopy
    }
    
    /// Intersection of two selfs
    pub fn intersection(&self, s: &Self) -> Self {
        let mut scopy = self.clone();
        scopy.mintersection(s);
        scopy
    }
    
    /// Complement of s in self (i.e. self -= s)
    pub fn difference(&self, s: &Self) -> Self {
        let mut scopy = self.clone();
        scopy.mdifference(s);
        scopy
    }

    /// Finds minimum, minimum's first index, maximum, maximum's first index  
    pub fn infsup(&self) -> MinMax<T> where T: Default {
        match self.stype {
            SType::Empty => Default::default(),
            SType::Unordered => self.data.minmax(),  
            SType::Ordered => {
                let last = self.data.len()-1;
                if self.ascending { MinMax{min:self.data[0],minindex:0,max:self.data[last],maxindex:last} }
                else { MinMax{min:self.data[last],minindex:last,max:self.data[0],maxindex:0} } 
            },
            SType::Indexed => {
                let last = self.data.len()-1;
                let firstval = self.data[self.index[0]];
                let lastval = self.data[self.index[last]];
                if self.ascending { MinMax{min:firstval,minindex:self.index[0],max:lastval,maxindex:self.index[last]} }
                else { MinMax{min:lastval,minindex:self.index[last],max:firstval,maxindex:self.index[0]} }
            }, 
            SType::Ranked => {
                let last = self.data.len()-1;
                let si = self.index.invindex(); // ranks -> sort index
                let firstval = self.data[si[0]];
                let lastval = self.data[si[last]];
                    if self.ascending { MinMax{min:firstval,minindex:si[0],max:lastval,maxindex:si[last]} }
                    else { MinMax{min:lastval,minindex:si[last],max:firstval,maxindex:si[0]} }
            }
        }      
    }
    
    /// Search a Set self for m.
    /// Returns the subscript of the first m or None   
    pub fn search(&self, m: T) -> Option<usize> { 
        match self.stype {
            SType::Empty => None,
            SType::Unordered => self.data.member(m,true), // from indxvec ,
            SType::Ordered => { let r = self.data.binsearch(&m);
                if r.start == r.end { None } else { Some(r.start) } },    
            SType::Indexed => { let r = self.data.binsearch_indexed(&self.index,&m);
                if r.start == r.end { None } else { Some(self.index[r.start]) } },    
            SType::Ranked =>  { let r = self.data.binsearch_indexed(&self.index.invindex(),&m);
                if r.start == r.end { None } else { Some(self.index[r.start]) }} 
            }       
    }       
    
    /// True if m is a member of the self
    /// Throws away the subscript found by `search`
    pub fn member(&self, m: T) -> bool {
        self.search(m).is_some() 
    }   

}