sets/
setimpls.rs

1use crate::{SType,Set,MutSetOps,trivindex};
2use indxvec::{MinMax,Indices,Vecops};
3
4/// Associated functions for conversions and self operations returning Set<T> = Self
5impl<T> Set<T> where T: Copy+PartialOrd+Default {
6
7    /// Associated constant EMPTYSET, unique for each concrete end-type T
8    pub const EMPTYSET:Set<T> = Set{ stype:SType::Empty, ascending:true, data:Vec::new(), index:Vec::new() };
9
10    /// all in one Initialiser creates a new Set
11    /// of self_type, from slice d, in asc order 
12    pub fn new(set_type: SType, d: &[T], asc:bool) -> Self {  
13        if d.is_empty() { return Set::EMPTYSET }; // no data
14        match set_type {
15            SType::Empty => Set::EMPTYSET, // empty self specified
16            SType::Unordered => Set{ stype:SType::Unordered, ascending:true, data:d.to_vec(), index:Vec::new() }, 
17            SType::Ordered => Set{ stype:SType::Ordered, ascending:asc, data:d.sortm(asc), index:Vec::new() },
18            SType::Indexed =>  Set{ stype:SType::Indexed, ascending:asc, data:d.to_vec(), 
19                index: if asc { d.mergesort_indexed() } else { d.mergesort_indexed().revs() } },
20            SType::Ranked => Set{ stype:SType::Ranked, ascending:asc, data:d.to_vec(), 
21                index: if asc { d.mergesort_indexed().invindex() } else { d.mergesort_indexed().revs().invindex() } } }
22    }
23
24    /// Creates a new empty Set
25    pub fn new_empty() -> Self { Self::EMPTYSET }
26
27    /// Initialiser - creates a new SType::Unordered Set from data
28    pub fn new_unordered(d: &[T]) -> Self {  
29        if !d.is_empty() { // have some data
30            Set{ stype:SType::Unordered, ascending:true, data:d.to_vec(), index:Vec::new() } } 
31        else { Set::EMPTYSET } 
32    }
33
34    /// Initialiser - creates a new SType::Ordered Set in asc order from data 
35    pub fn new_ordered(d: &[T], asc:bool) -> Self {  
36        if !d.is_empty() { // have some data
37            Set{ stype:SType::Ordered, ascending:asc, data:d.sortm(asc), index:Vec::new() } }
38        else { Set::EMPTYSET } 
39    }
40
41    /// Initialiser - creates a new SType::Indexed Set in asc order from data 
42    pub fn new_indexed(d: &[T], asc:bool) -> Self {  
43        if !d.is_empty() { // have some data
44            Set{ stype:SType::Indexed, ascending:asc, data:d.to_vec(), 
45                index: if asc { d.mergesort_indexed() } else { d.mergesort_indexed().revs() } } }
46        else { Set::EMPTYSET } 
47    }
48
49    /// Initialiser - creates a new SType::Ranked Set in asc order from data 
50    pub fn new_ranked(d: &[T], asc:bool) -> Self {  
51        if !d.is_empty() { // have some data
52            Set{ stype:SType::Ranked, ascending:asc, data:d.to_vec(), 
53                index: if asc { d.mergesort_indexed().invindex() } else { d.mergesort_indexed().revs().invindex() } } }
54        else { Set::EMPTYSET } 
55    }
56
57    /// Converter - to SType::Unordered Set
58    /// Caution: this just throws away the valuable index!
59    pub fn to_unordered(&self) -> Self { 
60        match self.stype {
61            SType::Empty => Set::EMPTYSET, // no op 
62            // ascending field has no meaning for unordered, so just inherit it
63            _ => Self{ stype:SType::Unordered, ascending:self.ascending, data:self.data.clone(), index:Vec::new() }
64        }
65    }
66
67    /// Converts any Set type to ordered
68    pub fn to_ordered(&self, asc:bool) -> Self {
69        match self.stype {
70            SType::Empty => Set::EMPTYSET, 
71            SType::Unordered => Self{ stype:SType::Ordered, ascending:asc, data:self.data.sortm(asc), index:Vec::new()},
72            SType::Ordered => if self.ascending == asc { self.clone() } // just a copy
73                else { Self{ stype:SType::Ordered, ascending:asc, data:self.data.revs(), index:Vec::new() } },
74            SType::Indexed => Self{ stype:SType::Ordered, ascending:asc, 
75                data:self.index.unindex(&self.data, self.ascending == asc), index:Vec::new() },
76            SType::Ranked => Self{ stype:SType::Ordered, ascending:asc, 
77                data:self.index.invindex().unindex(&self.data, self.ascending == asc), index:Vec::new() },
78        }    
79    }
80
81    /// Converts any Set type to indexed
82    pub fn to_indexed(&self,asc:bool) -> Self {
83        match self.stype {
84            SType::Empty => Set::EMPTYSET,
85            SType::Unordered => Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(), 
86                index: if asc {self.data.mergesort_indexed()} else {self.data.mergesort_indexed().revs()} },
87            SType::Ordered => Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(), 
88                index: trivindex(self.ascending == asc,self.data.len()) },
89            SType::Indexed =>  if self.ascending == asc { self.clone() } // no op
90                else { Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(),
91                    index: self.index.revs() } },
92            SType::Ranked => Self{ stype:SType::Indexed, ascending:asc, data:self.data.clone(),             
93                index: if self.ascending == asc {self.index.invindex()} else {self.index.invindex().revs()}}
94        }    
95    }
96
97    /// Converts any Set type to ranked
98    pub fn to_ranked(&self,asc:bool) -> Self {
99        match self.stype {
100            SType::Empty => Set::EMPTYSET,
101            SType::Unordered => Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(), 
102                index: if asc {self.data.mergesort_indexed().invindex()} 
103                    else {self.data.mergesort_indexed().revs().invindex()} },
104            SType::Ordered => Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(), 
105                index: trivindex(self.ascending == asc,self.data.len()) },
106            SType::Indexed => Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(),             
107                index: if self.ascending == asc {self.index.invindex()} 
108                    else {self.index.revs().invindex()}}, 
109            SType::Ranked => if self.ascending == asc { self.clone() } // no op
110                else { Self{ stype:SType::Ranked, ascending:asc, data:self.data.clone(),
111                    index: {self.index.complindex()} } }
112        }    
113    }
114
115    /// General converter: s -> Set of the same type and order as self
116    /// self only serves as a template for the type and order and is not involved in the conversion
117    pub fn to_same(&self, s:&Self) -> Self { 
118        match self.stype { 
119            SType::Empty => Set::EMPTYSET, //  was Default::default()
120            SType::Unordered => s.to_unordered(), 
121            SType::Ordered => s.to_ordered(self.ascending),
122            SType::Indexed => s.to_indexed(self.ascending),
123            SType::Ranked => s.to_ranked(self.ascending)
124        }
125    }       
126
127    /// Inserts an item of the same end-type to self
128    pub fn insert(&self, item:T) -> Self {
129        let mut scopy = self.clone();
130        scopy.minsert(item);
131        scopy 
132    }
133
134    /// Deletes an item of the same end-type from self
135    pub fn delete(&self, item:T) -> Self {
136        let mut scopy = self.clone();
137        if scopy.mdelete(item) { scopy } else { self.clone() }
138    }    
139
140    /// Reverses a vec by iterating over only half of its length
141    /// and swapping the items
142    pub fn reverse(&self) -> Self { 
143        let mut scopy = self.clone();
144        scopy.mreverse();
145        scopy
146    }
147 
148    /// Deletes any repetitions
149    pub fn nonrepeat(&self) -> Self { 
150        let mut scopy =  self.clone();
151        scopy.mnonrepeat();
152        scopy
153    }
154
155    /// Union of two selfs  
156    pub fn union(&self, s: &Self) -> Self {
157        let mut scopy =  self.clone();
158        scopy.munion(s);
159        scopy
160    }
161    
162    /// Intersection of two selfs
163    pub fn intersection(&self, s: &Self) -> Self {
164        let mut scopy = self.clone();
165        scopy.mintersection(s);
166        scopy
167    }
168    
169    /// Complement of s in self (i.e. self -= s)
170    pub fn difference(&self, s: &Self) -> Self {
171        let mut scopy = self.clone();
172        scopy.mdifference(s);
173        scopy
174    }
175
176    /// Finds minimum, minimum's first index, maximum, maximum's first index  
177    pub fn infsup(&self) -> MinMax<T> where T: Default {
178        match self.stype {
179            SType::Empty => Default::default(),
180            SType::Unordered => self.data.minmax(),  
181            SType::Ordered => {
182                let last = self.data.len()-1;
183                if self.ascending { MinMax{min:self.data[0],minindex:0,max:self.data[last],maxindex:last} }
184                else { MinMax{min:self.data[last],minindex:last,max:self.data[0],maxindex:0} } 
185            },
186            SType::Indexed => {
187                let last = self.data.len()-1;
188                let firstval = self.data[self.index[0]];
189                let lastval = self.data[self.index[last]];
190                if self.ascending { MinMax{min:firstval,minindex:self.index[0],max:lastval,maxindex:self.index[last]} }
191                else { MinMax{min:lastval,minindex:self.index[last],max:firstval,maxindex:self.index[0]} }
192            }, 
193            SType::Ranked => {
194                let last = self.data.len()-1;
195                let si = self.index.invindex(); // ranks -> sort index
196                let firstval = self.data[si[0]];
197                let lastval = self.data[si[last]];
198                    if self.ascending { MinMax{min:firstval,minindex:si[0],max:lastval,maxindex:si[last]} }
199                    else { MinMax{min:lastval,minindex:si[last],max:firstval,maxindex:si[0]} }
200            }
201        }      
202    }
203    
204    /// Search a Set self for m.
205    /// Returns the subscript of the first m or None   
206    pub fn search(&self, m: T) -> Option<usize> { 
207        match self.stype {
208            SType::Empty => None,
209            SType::Unordered => self.data.member(m,true), // from indxvec ,
210            SType::Ordered => { let r = self.data.binsearch(&m);
211                if r.start == r.end { None } else { Some(r.start) } },    
212            SType::Indexed => { let r = self.data.binsearch_indexed(&self.index,&m);
213                if r.start == r.end { None } else { Some(self.index[r.start]) } },    
214            SType::Ranked =>  { let r = self.data.binsearch_indexed(&self.index.invindex(),&m);
215                if r.start == r.end { None } else { Some(self.index[r.start]) }} 
216            }       
217    }       
218    
219    /// True if m is a member of the self
220    /// Throws away the subscript found by `search`
221    pub fn member(&self, m: T) -> bool {
222        self.search(m).is_some() 
223    }   
224
225}
sets/setimpls.rs

sets/
setimpls.rs
