swift - Reduce instances of an object in an array by rule -

i have simple array of custom objects.

i reduce array 1 instance of each color selected largest size.

the solutions have come seem long unwieldy, best approach, i've tried looking @ reduce , filter couldn't work out how apply here.

class foo {      var color: string     var size: int     var shape: string      init(color:string, size:int, shape:string){         self.color = color         self.size = size         self.shape = shape     }  }  var array = [foo]()  array.append(foo(color: "blue", size: 2, shape: "round")) array.append(foo(color: "red", size: 3, shape: "square")) array.append(foo(color: "blue", size: 5, shape: "round")) array.append(foo(color: "yellow", size: 1, shape: "triangle")) array.append(foo(color: "blue", size: 1, shape: "hexagon")) 

you can avoid brute-force o(n^2) nested looping (and enumeration) solution first sorting array, , thereafter filtering out duplicate colour objects using e.g. hash value lookup (method 1 below) or clever exclusion regard sorted array (method 2 below).

note class type naming convention (camelcase): foo rather foo.

disclaimer: don't stare blind on asymptotic complexity notations below, premature optimization is, depending on context , intended usage area of program, of sin. i've included them below have measure compare different methods by. choose 1 think makes sense you.

---

method 1

worst case...

• time complexity: o(n log n)

• space complexity: o(n)

where space complexity refers space used in excess of array final result assigned.

• let foo conform hashable (let hashvalue relate .color property).
• sort array of foo instances w.r.t. decreasing size (.size property).
• filter sorted array w.r.t. first occurrence of each color, using conformance hashable swiftly use o(1) hash value lookup existing color in foo:bool dictionary. adapted comments airspeed velocity in the following answer.

---

method 2 (as proposed nikolai ruhe):

worst case...

• time complexity: o(n log n)

• space complexity: o(1)

• sort array on color (primary) , size (secondary).
• filter sorted array elements has different color predecessors.

---

for third (probably best 1 application) method, see nikolai ruhe:s answer below, presenting method o(n)/o(n) time/space worst case complexity, respectively.

---

implementations

[this step needed method 1] conform foo hashable , equatable:

/* let foo conform hashable */ class foo : hashable {      var color: string     var size: int     var shape: string      init(color:string, size:int, shape:string){         self.color = color         self.size = size         self.shape = shape     }      var hashvalue: int {         return color.hashvalue     }  }  /* , equatable */ func ==(lhs: foo, rhs: foo) -> bool {     return lhs.color == rhs.color } 

set , example filter method(s) follows shortly:

/* foo array example */ var array = [foo]()  array.append(foo(color: "blue", size: 2, shape: "round")) array.append(foo(color: "red", size: 3, shape: "square")) array.append(foo(color: "blue", size: 5, shape: "round")) array.append(foo(color: "yellow", size: 1, shape: "triangle")) array.append(foo(color: "blue", size: 1, shape: "hexagon")) 

filter per specifications:

/* method 1 (assumes foo conforms hashable (& equatable))   */ var addeddict = [foo:bool]() var arrfiltered = array.sort{ $0.0.size > $0.1.size }     .filter {addeddict.updatevalue(true, forkey: $0) == nil }  /* method 2 (as proposed nikolai ruhe)                      */ var previouscolor: string? let arrfiltered = array.sort{ $0.color == $1.color ? $0.size > $1.size : $0.color < $1.color }     .filter{ if $0.color != previouscolor { previouscolor = $0.color; return true }; return false }     /* condensed .filter solution @nikolai ruhe, thanks! */ 

result:

for bar in arrfiltered {     print(bar.color, bar.size) }  /* blue 5    red 3    yellow 1 */ 

the sorting step dominant step in solution (for both methods). swift/stdlib/public/core/sort.swift.gyb, seems if swift uses introsort (specifically, hybrid of introsort combined insertion sort), running in, worst case, o(n log n).