order

README

order

Package order enables easier ordering and comparison tasks.

This package provides functionality to easily define and apply order on values. It works out of the box for most primitive types and their pointer versions, and enable order of any object using three-way comparison with a given func(T, T) int function, or by implementing the generic interface: func (T) Compare(T) int.

Supported Tasks:

• Sort / SortStable - sort a slice.

• Search - binary search for a value in a slice.

• MinMax - get indices of minimal and maximal values of a slice.

• Is - get a comparable object for more readable code.

• Select - get the K'th greatest value of a slice.

• IsSorted / IsStrictSorted - check if a slice is sorted.

Types and Values

Order between values can be more forgiving than strict comparison. This library allows sensible type conversions. A type U can be used in order function of type T in the following cases:

• U is a pointer (or pointers chain) to a T.

• T is a pointer (or pointers chain) to a U.

• T and U are of the same kind.

• T and U are of the same number kind group (int?, uint?, float?, complex?) and U's bits number is less or equal to T's bits number.

• U and T are assignable structs.

Usage

Using this library might be less type safe - because of the usage of interfaces API, and less efficient - because of the use of reflection. On the other hand, this library reduce chances for errors by providing a well tested code and more readable code. See below how some order tasks can be translated to be used by this library.

 type person struct {
 	name string
 	age  int
 }

 var persons []person

 // Sort persons (by name and then by age)
-lessPersons := func(i, j int) bool {
-	nameCmp := strings.Compare(persons[i].name, "joe")
-	if nameCmp == 0 {
-		return persons[i].age < persons[i].age
-	}
-	return nameCmp < 0
-}
-sort.Slice(persons, lessPersons)
+orderPersons := order.By(
+	func(a, b person) int { return strings.Compare(a.name, b.name) },
+	func(a, b person) int { return a.age - b.age },
+)
+orderPersons.Sort(persons)

 // Search persons for "joe" at age 42:
-searchPersons := func(int i) bool {
-	nameCmp := strings.Compare(persons[i].name, "joe")
-	if nameCmp == 0 {
-		return persons[i].age >= 42
-	}
-	return nameCmp > 0 {
-}
-i := sort.Search(persons, searchPersons)
-// Standard library search does not guarantee equality, we should check:
-if i >= len(persons) || persons[i].name != "joe" || persons[i].age != 42 {
-	i := -1
-}
+i := orderPersons.Search(persons, person{name: "joe", age: 42})

 // Another way is that person will implement a `Compare(T) int` method, and the order object
 // will know how to handle it:
+func (p person) Compare(other person) int { ... }
+order.Search(persons, person{name: "joe", age: 42})

 // Conditions can also be defined on comparable types:
 var t, start, end time.Time
-if (t.After(start) || t.Equal(start)) && t.Before(end) { ... }
+if isT := order.Is(t); isT.GreaterEqual(start) && isT.Less(end) { ... }

Examples

A simple example that shows how to use the order library with different basic types.

// The order function can be used to check values equality:
fmt.Println("now > one-second-ago ?",
    Is(time.Now()).Greater(time.Now().Add(-time.Second)))
fmt.Println("foo == bar ?",
    Is("foo").Equal("bar"))

// Checking if a value is within a range:
if is := Is(3); is.GreaterEqual(3) && is.Less(4) {
    fmt.Println("3 is in [3,4)")
}

Output:

now > one-second-ago ? true
foo == bar ? false
3 is in [3,4)

Comparable

A type may implement a func (t T) Compare(other T) int function. In this case it could be just used with the order package functions.

oranges := []orange{5, 2, 24}
Sort(oranges)
fmt.Println(oranges)

Output:

[2 5 24]

Complex

An example of ordering struct with multiple fields with different priorities.

// Define a struct with fields of different types.
type person struct {
    name string
    age  int
}
// Order persons: first by name and then by age - reversed.
orderPersons := By(
    func(a, b person) int { return strings.Compare(a.name, b.name) },
    func(a, b person) int { return a.age - b.age },
).Reversed()

// Sort a list of persons in reversed order.
list := []person{
    {"Bar", 10},
    {"Foo", 10},
    {"Bar", 11},
}
orderPersons.Sort(list)
fmt.Println("Reversed:", list)

// Search for a specific person in the sorted list.
fmt.Println("Index of {Foo 10}:", orderPersons.Search(list, person{"Foo", 10}))

Output:

Reversed: [{Foo 10} {Bar 11} {Bar 10}]
Index of {Foo 10}: 0

SliceOperations

// The order function can be used to sort lists:
list := []int{2, 1, 3}
Sort(list)
fmt.Println("Sorted:", list)

// Values can be looked up in sorted lists using a binary search:
fmt.Println("Index of 2:", Search(list, 2))

// Get the minimal and maximal values:
minI, maxI := MinMax(list)
fmt.Printf("Min: %d, max: %d\n", list[minI], list[maxI])

// Get the k'th greatest value:
Select(list, len(list)/2)
fmt.Printf("Median: %d\n", list[1])

Output:

Sorted: [1 2 3]
Index of 2: 1
Min: 1, max: 3
Median: 2

---

Created by goreadme

Documentation

Overview

Package order enables easier ordering and comparison tasks.

This package provides functionality to easily define and apply order on values. It works out of the box for most primitive types and their pointer versions, and enable order of any object using (three-way comparison) https://en.wikipedia.org/wiki/Three-way_comparison with a given `func(T, T) int` function, or by implementing the generic interface: `func (T) Compare(T) int`.

Supported Tasks:

* [x] `Sort` / `SortStable` - sort a slice.

* [x] `Search` - binary search for a value in a slice.

* [x] `MinMax` - get indices of minimal and maximal values of a slice.

* [X] `Is` - get a comparable object for more readable code.

+ [x] `Select` - get the K'th greatest value of a slice.

* [x] `IsSorted` / `IsStrictSorted` - check if a slice is sorted.

Types and Values

Order between values can be more forgiving than strict comparison. This library allows sensible type conversions. A type `U` can be used in order function of type `T` in the following cases:

* `U` is a pointer (or pointers chain) to a `T`.

* `T` is a pointer (or pointers chain) to a `U`.

* `T` and `U` are of the same kind.

* `T` and `U` are of the same number kind group (int?, uint?, float?, complex?) and `U`'s bits number is less or equal to `T`'s bits number.

* `U` and `T` are assignable structs.

Usage

Using this library might be less type safe - because of the usage of interfaces API, and less efficient - because of the use of reflection. On the other hand, this library reduce chances for errors by providing a well tested code and more readable code. See below how some order tasks can be translated to be used by this library.

 type person struct {
 	name string
 	age  int
 }

 var persons []person

 // Sort persons (by name and then by age)
-lessPersons := func(i, j int) bool {
-	nameCmp := strings.Compare(persons[i].name, "joe")
-	if nameCmp == 0 {
-		return persons[i].age < persons[i].age
-	}
-	return nameCmp < 0
-}
-sort.Slice(persons, lessPersons)
+orderPersons := order.By(
+	func(a, b person) int { return strings.Compare(a.name, b.name) },
+	func(a, b person) int { return a.age - b.age },
+)
+orderPersons.Sort(persons)

 // Search persons for "joe" at age 42:
-searchPersons := func(int i) bool {
-	nameCmp := strings.Compare(persons[i].name, "joe")
-	if nameCmp == 0 {
-		return persons[i].age >= 42
-	}
-	return nameCmp > 0 {
-}
-i := sort.Search(persons, searchPersons)
-// Standard library search does not guarantee equality, we should check:
-if i >= len(persons) || persons[i].name != "joe" || persons[i].age != 42 {
-	i := -1
-}
+i := orderPersons.Search(persons, person{name: "joe", age: 42})

 // Another way is that person will implement a `Compare(T) int` method, and the order object
 // will know how to handle it:
+func (p person) Compare(other person) int { ... }
+order.Search(persons, person{name: "joe", age: 42})

 // Conditions can also be defined on comparable types:
 var t, start, end time.Time
-if (t.After(start) || t.Equal(start)) && t.Before(end) { ... }
+if isT := order.Is(t); isT.GreaterEqual(start) && isT.Less(end) { ... }

Example

A simple example that shows how to use the order library with different basic types.

// The order function can be used to check values equality:
fmt.Println("now > one-second-ago ?",
	Is(time.Now()).Greater(time.Now().Add(-time.Second)))
fmt.Println("foo == bar ?",
	Is("foo").Equal("bar"))

// Checking if a value is within a range:
if is := Is(3); is.GreaterEqual(3) && is.Less(4) {
	fmt.Println("3 is in [3,4)")
}

Output:

now > one-second-ago ? true
foo == bar ? false
3 is in [3,4)

Example (Comparable)

A type may implement a `func (t T) Compare(other T) int` function. In this case it could be just used with the order package functions.

oranges := []orange{5, 2, 24}
Sort(oranges)
fmt.Println(oranges)

Output:

[2 5 24]

Example (Complex)

An example of ordering struct with multiple fields with different priorities.

// Define a struct with fields of different types.
type person struct {
	name string
	age  int
}
// Order persons: first by name and then by age - reversed.
orderPersons := By(
	func(a, b person) int { return strings.Compare(a.name, b.name) },
	func(a, b person) int { return a.age - b.age },
).Reversed()

// Sort a list of persons in reversed order.
list := []person{
	{"Bar", 10},
	{"Foo", 10},
	{"Bar", 11},
}
orderPersons.Sort(list)
fmt.Println("Reversed:", list)

// Search for a specific person in the sorted list.
fmt.Println("Index of {Foo 10}:", orderPersons.Search(list, person{"Foo", 10}))

Output:

Reversed: [{Foo 10} {Bar 11} {Bar 10}]
Index of {Foo 10}: 0

Example (SliceOperations)

// The order function can be used to sort lists:
list := []int{2, 1, 3}
Sort(list)
fmt.Println("Sorted:", list)

// Values can be looked up in sorted lists using a binary search:
fmt.Println("Index of 2:", Search(list, 2))

// Get the minimal and maximal values:
minI, maxI := MinMax(list)
fmt.Printf("Min: %d, max: %d\n", list[minI], list[maxI])

// Get the k'th greatest value:
Select(list, len(list)/2)
fmt.Printf("Median: %d\n", list[1])

Output:

Sorted: [1 2 3]
Index of 2: 1
Min: 1, max: 3
Median: 2

Index

• func IsSorted(slice interface{}) bool
• func IsStrictSorted(slice interface{}) bool
• func MinMax(slice interface{}) (min, max int)
• func Search(slice, value interface{}) int
• func Select(slice interface{}, k int)
• func Sort(slice interface{})
• func SortStable(slice interface{})
• type Condition
  • func Is(value interface{}) Condition
  • func (c Condition) Equal(rhs interface{}) bool
  • func (c Condition) Greater(rhs interface{}) bool
  • func (c Condition) GreaterEqual(rhs interface{}) bool
  • func (c Condition) Less(rhs interface{}) bool
  • func (c Condition) LessEqual(rhs interface{}) bool
  • func (c Condition) NotEqual(rhs interface{}) bool
• type Fn
  • func (fn Fn) T() reflect.Type
• type Fns
  • func By(fns ...interface{}) Fns
  • func (fns Fns) Is(lhs interface{}) Condition
  • func (fns Fns) IsSorted(slice interface{}) bool
  • func (fns Fns) IsStrictSorted(slice interface{}) bool
  • func (fns Fns) MinMax(slice interface{}) (min, max int)
  • func (fns Fns) Reversed() Fns
  • func (fns Fns) Search(slice, value interface{}) int
  • func (fns Fns) Select(slice interface{}, k int)
  • func (fns Fns) Sort(slice interface{})
  • func (fns Fns) SortStable(slice interface{})
  • func (fns Fns) T() reflect.Type

Examples

• Package
• Package (Comparable)
• Package (Complex)
• Package (SliceOperations)

Functions

func IsSorted

func IsSorted(slice interface{}) bool

IsSorted returns whether a Slice<T> if T implements a `func (T) Compare(T) int` is sorted. See Fn.IsSorted. It panics if slice does not implement the compare function.

func IsStrictSorted

func IsStrictSorted(slice interface{}) bool

IsStrictSorted returns whether a Slice<T> if T implements a `func (T) Compare(T) int` is strictly sorted. See Fn.IsStrictSorted. It panics if slice does not implement the compare function.

func MinMax

func MinMax(slice interface{}) (min, max int)

MinMax returns the indices of the minimal and maximal values in a Slice<T> if T implements a `func (T) Compare(T) int` for a value. See Fn.MinMax. It panics if slice does not implement the compare function.

func Search

func Search(slice, value interface{}) int

Search a Slice<T> if T implements a `func (T) Compare(T) int` for a value. See Fn.Search.

func Select

func Select(slice interface{}, k int)

Select applies select-k algorithm on a Slice<T> if T implements a `func (T) Compare(T) int`. See Fn.Select. It panics if slice does not implement the compare function.

func Sort

func Sort(slice interface{})

Sort a Slice<T> if T implements a `func (T) Compare(T) int`. See Fn.Sort. It panics if slice does not implement the compare function.

func SortStable

func SortStable(slice interface{})

SortStable a Slice<T> if T implements a `func (T) Compare(T) int`. See Fn.SortStable. It panics if slice does not implement the compare function.

Types

type Condition

type Condition struct {
	Fns
	// contains filtered or unexported fields
}

Condition allows comparing a given lhs value.

func Is

func Is(value interface{}) Condition

Is returns a Condition<T> for type T the implements a `func (T) Compare(T) int`. It panics if value does not implement the compare function.

func (Condition) Equal

func (c Condition) Equal(rhs interface{}) bool

Equal tests if the compared lhs object is equal to the given rhs object.

func (Condition) Greater

func (c Condition) Greater(rhs interface{}) bool

Greater tests if the lhs object is greater than the given rhs object.

func (Condition) GreaterEqual

func (c Condition) GreaterEqual(rhs interface{}) bool

GreaterEqual tests if the lhs object is greater than or equal to the given rhs object.

func (Condition) Less

func (c Condition) Less(rhs interface{}) bool

Less tests if the lhs object is less than the given rhs object.

func (Condition) LessEqual

func (c Condition) LessEqual(rhs interface{}) bool

LessEqual tests if the lhs object is less than or equal to the given rhs object.

func (Condition) NotEqual

func (c Condition) NotEqual(rhs interface{}) bool

NotEqual tests if the compared lhs object is not equal to the given rhs object.

type Fn

type Fn struct {
	// contains filtered or unexported fields
}

Fn represent an order function.

func (Fn) T

func (fn Fn) T() reflect.Type

T returns the type of the function T.

type Fns

type Fns []Fn

Fns is a list of order functions, used to check the order between two T types.

func By

func By(fns ...interface{}) Fns

By enables ordering values of type T by a given list of three-way comparison functions of the form `func(T, T) int`. Each function compares two values (`lhs`, `rhs`) of type T, and returns a value `c` of type int as follows:

If lhs > rhs then c > 0. If lhs == rhs then c = 0. If lhs < rhs then c < 0.

The list of functions is used in order to define multiple orderings. When two values are compared, the first function is evaluated, if the comparison value is not zero, the value is returned. Otherwise, the following function is evaluated until a non-zero value is returned. If all the comparison functions returned zero, the returned value is also zero.

func (Fns) Is

func (fns Fns) Is(lhs interface{}) Condition

Is returns a comparable object.

func (Fns) IsSorted

func (fns Fns) IsSorted(slice interface{}) bool

IsSorted returns whether the slice is in an increasing order, according to the comparsion function.

To check if a slice is in a decreasing order, it is possible to `fn.Reversed().IsSorted(slice)`.

func (Fns) IsStrictSorted

func (fns Fns) IsStrictSorted(slice interface{}) bool

IsStrictSorted returns whether the slice is in a strictly increasing order, according to the comparsion function.

To check if a slice is in a strictly decreasing order, it is possible to `fn.Reversed().IsStrictSorted(slice)`.

func (Fns) MinMax

func (fns Fns) MinMax(slice interface{}) (min, max int)

MinMax returns the indices of the minimal and maximal values in the given slice. It returns values (-1, -1) if the slice is empty. If there are several minimal/maximal values, this function will return the index of the first of them.

func (Fns) Reversed

func (fns Fns) Reversed() Fns

Reversed returns a reversed comparison of the original function.

func (Fns) Search

func (fns Fns) Search(slice, value interface{}) int

Search searches the given slice for a value. The given slice should be sorted relative to the comparsion function. It returns an index of an element that is equal to the given value. It returns -1 if no element was found that is equal to the given value.

func (Fns) Select

func (fns Fns) Select(slice interface{}, k int)

Select applies select-k algorithm on the given slice and k index. After invoking this method, the k'th greatest element according to the comparison function will be available in the k'th index. As a side effect, the slice will be partitioned according to the k'th index:

{slice[i] <= slice[k] | i < k}
{slice[i] >= slice[k] | i > k}

This function will panic if k is out of the bounds of slice.

func (Fns) Sort

func (fns Fns) Sort(slice interface{})

Sort sorts a given slice according to the comparison function.

func (Fns) SortStable

func (fns Fns) SortStable(slice interface{})

SortStable sorts a given slice according to the comparison function, while keeping the original order of equal elements.

func (Fns) T

func (fns Fns) T() reflect.Type

T returns the type of the functions list T.