sets/
mutimpls.rs

1#![warn(missing_docs)]
2use crate::{trivindex,SType,Set,MutSetOps};
3use indxvec::{Indices,Vecops,Mutops};
4
5impl<T> MutSetOps<T> for Set<T> where T:Copy+PartialOrd+Default {
6
7    /// Makes a Set unordered
8    /// Caution: this just throws away the valuable index!
9    fn munordered(&mut self) { 
10        match self.stype {
11            SType::Empty | SType::Unordered => return, // no op
12            SType::Ordered => (), // leave data as is, just change SType below
13            SType::Indexed | SType::Ranked  => self.index = Vec::new() // remove the index
14        }
15        self.stype = SType::Unordered;
16        // ascending field has no meaning for unordered, so leaving it as it is 
17    }
18
19    /// Makes a Set ordered
20    fn mordered(&mut self, quantify: impl Copy + Fn(&T) -> f64, asc:bool) {
21        match self.stype {
22            SType::Empty => return, // no op
23            SType::Unordered => { self.data.muthashsort(quantify); if !asc { self.data.mutrevs() } },
24            SType::Ordered => if self.ascending != asc { self.data.mutrevs() }, 
25            SType::Indexed => { 
26                self.data = self.index.unindex(&self.data, self.ascending == asc);
27                self.index = Vec::new(); },
28            SType::Ranked => {
29                self.data = self.index.invindex().unindex(&self.data, self.ascending == asc);
30                self.index = Vec::new(); }
31        } 
32        self.stype = SType::Ordered; // new SType 
33        self.ascending = asc;  // new ordering    
34    }
35
36    /// Makes any Set indexed
37    fn mindexed(&mut self, quantify: impl Copy + Fn(&T) -> f64, asc:bool) { 
38        match self.stype { 
39            SType::Empty => return, // empty set, no op 
40            SType::Unordered => {                 
41                self.index = self.data.hashsort_indexed(quantify);
42                if !asc { self.index.mutrevs(); }; },
43            SType::Ordered => self.index = trivindex(self.ascending == asc,self.data.len()),
44            SType::Indexed => if self.ascending != asc { self.index.mutrevs() },
45            SType::Ranked => {
46                if self.ascending != asc { self.index = self.index.complindex() }; 
47                self.index = self.index.invindex(); }, 
48        }
49        self.stype = SType::Indexed; // new SType 
50        self.ascending = asc;  // new ordering 
51    }
52
53    /// Converts any Set type to ranked
54    fn mranked(&mut self,asc:bool) {
55        match self.stype {
56            SType::Empty => return, // empty set, no op 
57            SType::Unordered =>  {                 
58                self.index = self.data.mergesort_indexed().invindex();
59                if !asc { self.index.complindex(); }; },
60            SType::Ordered => self.index = trivindex(self.ascending == asc,self.data.len()),
61            SType::Indexed => {
62                if self.ascending != asc { self.index.mutrevs() }; 
63                self.index = self.index.invindex(); }, 
64            SType::Ranked => if self.ascending != asc { self.index = self.index.complindex() }
65        } 
66        self.stype = SType::Ranked; // new SType 
67        self.ascending = asc;  // new ordering    
68    }
69
70    /// General converter: s -> Set of the same type and order as self
71    /// self only serves as a template for the type and order and is not involved in the conversion
72    fn msame(&mut self, s:&mut Self, quantify: impl Copy + Fn(&T) -> f64) { 
73        match self.stype { 
74            SType::Empty => *s = Set::EMPTYSET, //  was Default::default()
75            SType::Unordered => s.munordered(), 
76            SType::Ordered => s.mordered(quantify, self.ascending),
77            SType::Indexed => s.mindexed(quantify,self.ascending),
78            SType::Ranked => s.mranked(self.ascending)
79        }
80    }  
81    
82    /// Deletes an item from self
83    /// Returns false if item not found 
84    fn mdelete(&mut self, item:T) -> bool where Self:Sized {
85        match self.stype {
86            SType::Empty => false, // empty set
87            SType::Unordered => {
88                if let Some(i) = self.data.member(item,true) {
89                    // don't care about order, swap_remove swaps in the last item, fast
90                    self.data.swap_remove(i); true }
91                else { false }
92            }, 
93            SType::Ordered => {
94                let r = self.data.binsearch(&item);
95                if r.is_empty() { return false; };
96                self.data.remove(r.start); // remove + shift, preserves ordering
97                true
98            },
99
100            SType::Indexed => {
101                let r = self.data.binsearch_indexed(&self.index,&item);
102                if r.is_empty() { return false; };
103                let datasub = self.index[r.start];
104                self.data.remove(datasub); // remove + shift data , preserves ordering
105                self.index.remove(r.start); // remove + shift data , preserves ordering               
106                for idxitem in  &mut self.index { // repair the whole sort index
107                    if *idxitem > datasub { *idxitem -= 1 };
108                }
109                true },
110
111            SType::Ranked => {
112                let mut sortindex = self.index.invindex();
113                let r = self.data.binsearch_indexed(&sortindex,&item);
114                if r.is_empty() { return false; };
115                let datasub = sortindex[r.start];
116                self.data.remove(datasub); // remove + shift data , preserves ordering
117                sortindex.remove(r.start); // remove + shift data , preserves ordering               
118                for idxitem in &mut sortindex { // repair the whole sort index
119                    if *idxitem > datasub { *idxitem -= 1 };
120                }
121                self.index = sortindex.invindex(); // reconstruct rank index
122                true },
123        }
124    }  
125
126    /// Deletes all occurrences of a matching item from self
127    /// Returns number found and deleted 
128    fn mdeleteall(&mut self, item:T) -> usize where Self:Sized {
129        let mut count = 0_usize;
130        match self.stype {
131            SType::Empty => 0, // empty set
132            SType::Unordered => {
133                while let Some(i) = self.data.member(item,true) {
134                    count += 1;
135                    // don't care about order, swap_remove swaps in the last item, fast
136                    self.data.swap_remove(i);
137                };
138                count
139            }, 
140            SType::Ordered => {
141                let r = self.data.binsearch(&item);
142                if r.is_empty() { return 0; };
143                let count = r.len();
144                self.data.drain(r); 
145                count
146            },
147
148            SType::Indexed => {
149                let mut ord_data = self.index.unindex(&self.data,self.ascending);
150                let r = ord_data.binsearch(&item);
151                if r.is_empty() { return 0; }; 
152                let count = r.len();
153                ord_data.drain(r);
154                self.data = ord_data;
155                self.index = trivindex(self.ascending,self.data.len());
156                count },
157
158            SType::Ranked => {
159                let mut ord_data = self.index.invindex().unindex(&self.data,self.ascending);
160                let r = ord_data.binsearch(&item);
161                if r.is_empty() { return 0; }; 
162                let count = r.len();
163                ord_data.drain(r);
164                self.data = ord_data;
165                self.index = trivindex(self.ascending,self.data.len());
166                count } 
167        }
168    }  
169
170    /// Inserts an item v of the same end-type to self
171    fn minsert(&mut self, item:T) {
172        match self.stype {
173            SType::Empty => {  // initially empty set
174                self.stype = crate::SType::Ordered;
175                self.data.push(item);
176            },
177            SType::Unordered => self.data.push(item), 
178            SType::Ordered => {
179                // binsearch finds the right sort position
180                let range = self.data.binsearch(&item);
181                self.data.insert(range.start,item); // shifts the rest  
182            },
183            SType::Indexed => {
184                let irange = self.data.binsearch_indexed(&self.index,&item); 
185                // simply push the item to the end of unordered data self.data
186                self.data.push(item);
187                // and insert its subscipt into the right place in the sort index    
188                self.index.insert(irange.start,self.data.len()-1);                
189
190            }
191            SType::Ranked => {
192               // invert the rank index to get the sort index position
193                let irange = self.data.binsearch_indexed(&self.index.invindex(),&item);
194                // simply push the new item to the end of unordered data self.data
195                self.data.push(item);
196                // and insert its index position (rank) into the same place in the rank index    
197                self.index.push(irange.start);
198            }
199        };
200    }
201
202    /// Reverses a vec by iterating over only half of its length
203    /// and swapping the items
204    fn mreverse(&mut self) { 
205        match self.stype {
206            SType::Empty => Default::default(), // empty set
207            SType::Unordered => self.data.mutrevs(), 
208            SType::Ordered => {        
209                self.ascending = !self.ascending;
210                self.data.mutrevs(); 
211            },
212            SType::Indexed => {
213                self.ascending = !self.ascending;
214                self.index.mutrevs(); 
215            },
216            SType::Ranked => {
217                self.ascending = !self.ascending;
218                self.index = self.index.complindex();                
219            }
220        }
221    }
222
223    /// Deletes all repetitions
224    fn mnonrepeat(&mut self) {
225        if self.data.len() < 2 { return }; // nothing to be done here
226        match self.stype {
227            SType::Empty => (), // empty set, do nothing
228            SType::Unordered => { // sort data 
229                self.data = self.data.sortm(true);
230                self.data.dedup(); 
231            }, 
232            SType::Ordered =>  self.data.dedup(),
233            SType::Indexed => { // spoofed by sorted data and trivial index
234                let mut orddata = self.index.unindex(&self.data,self.ascending);
235                orddata.dedup();
236                self.data = orddata; // resets data to ordered
237                self.index = trivindex(self.ascending, self.data.len());
238            },
239            SType::Ranked => { // spoofed by sorted data and trivial index
240                let mut orddata = self.index.invindex().unindex(&self.data,self.ascending);
241                orddata.dedup();
242                self.data = orddata; // resets data to ordered
243                self.index = trivindex(self.ascending, self.data.len());       
244            }
245        }
246    }
247
248    /// sets union
249    fn munion(&mut self, s: &Self) {
250        let mut selford = self.to_ordered(true);
251        let sord = s.to_ordered(true);
252        selford.data = selford.data.merge(&sord.data);
253        *self = self.to_same(&selford); // back to original type and order 
254    }
255
256    /// Intersection of two unordered sets, assigned to self
257    fn mintersection(&mut self, s: &Self) {
258        let mut selford = self.to_ordered(true);
259        let sord = s.to_ordered(true);
260        selford.data = selford.data.intersect(&sord.data);
261        *self = self.to_same(&selford); // back to original type and order 
262    }
263
264    /// Complement of s in self (i.e. self -= s)
265    fn mdifference(&mut self, s: &Self) {
266        let mut selford = self.to_ordered(true);
267        let sord = s.to_ordered(true);
268        selford.data = selford.data.diff(&sord.data);
269        *self = self.to_same(&selford); // back to original type and order
270    }    
271}
sets/mutimpls.rs

sets/
mutimpls.rs
