%global _empty_manifest_terminate_build 0
Name:		python-pysegmenttree
Version:	0.2.0
Release:	1
Summary:	Segment Tree for python 3+
License:	MIT
URL:		https://github.com/greshilov/pysegmenttree.git
Source0:	https://mirrors.nju.edu.cn/pypi/web/packages/c3/f9/7008b984237abd4810948c2586e6540d8c907575a6c7e408e2b6844030c3/pysegmenttree-0.2.0.tar.gz


%description
# pysegmenttree
[![GitHub license](https://img.shields.io/github/license/greshilov/pysegmenttree)](https://github.com/greshilov/pysegmenttree/blob/master/LICENSE)
[![CI](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml/badge.svg)](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml)
[![codecov](https://codecov.io/gh/greshilov/pysegmenttree/branch/master/graph/badge.svg?token=BXXCG2JBPK)](https://codecov.io/gh/greshilov/pysegmenttree)

Segment tree is a data structure to perform efficient range queries over an array.

Properties of the segment tree with the size N.

| Operation | Time complexity |
| --------------- | --------------- |
| build | O(N) |
| query | O(Log[N]) |
| update | O(Log[N]) |

# Key features
* Implements classical data structure to deal with interval queries.
* Includes two classes **IntSegmentTree** and **FloatSegmentTree** implemented in pure C. They can boost performance up to 20x and are used by default for simple data types if possible.

# Installation
```
$ pip install pysegmenttree
```

# Basic usage
```
>> from pysegmenttree import stree

# Build the tree
# 'sum' function is used by default
>> tree = stree([5, 1, 9, 4, 5, 11])

# Find sum on the interval [1, 4)
>> tree.query(1, 4)
14

# Set element with index 3 to 6
>> tree.update(3, 6)
>> tree.query(1, 4)
16
```

# Advanced usage
There are three predefined query functions available that can be used with `int` or `float` trees. Use them as follows:
```
>> from pysegmenttree import stree, QueryFunction
>> tree = stree([5, 1, 9, 4, 5, 11], func=QueryFunction.MIN)

# Find min on the interval [1, 4)
>> tree.query(1, 4)
1
```

Plain python functions are also suitable, but in this case c-extensions will **not** be used.
```
>> tree = stree([5, 1, 9, 4, 5, 11], func=min)
>> tree.query(1, 4)
1
```

Example with user-defined class.
```
>> from pysegmenttree import stree
>> from pysegmenttree.test_utils import Vec2D
# List of 2D vectors
>> tree = stree([Vec2D(0, 1), Vec2D(5, -2), Vec2D(-2, 3)], func=max)
# Find the vector of maximum length on the interval [0, 2)
>> tree.query(0, 2)

Vec2D(x=5, y=-2)
```

# Docs
Docs are available [here](https://pysegmenttree.readthedocs.io/en/latest/).

# Perfomance

Three basic segment tree operations were benchmarked for three different types `int`, `float` and `Vec2D`.
I included results for 3 other python segment trees libraries for comparison.
All code related to benchmarking can be found in `benchmarks` subdirectory.

* [segment-tree](https://github.com/evgeth/segment_tree)
* [segmenttree](https://github.com/1e0ng/segmenttree)
* [c-segment-tree](https://github.com/gilaniasher/segtree-c-python)

## init
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |


[<img src="benchmarks/with_other_libs/data/init.png"/>](benchmarks/with_other_libs/data/init.png "init")

## query
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |
| Queries performed | 10 000 |

[<img src="benchmarks/with_other_libs/data/query.png"/>](benchmarks/with_other_libs/data/query.png "query")

## update
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |
| Updates performed | 10 000 |

[<img src="benchmarks/with_other_libs/data/update.png"/>](benchmarks/with_other_libs/data/update.png "update")


# Development
Read more [here](DEVELOPMENT.md).



%package -n python3-pysegmenttree
Summary:	Segment Tree for python 3+
Provides:	python-pysegmenttree
BuildRequires:	python3-devel
BuildRequires:	python3-setuptools
BuildRequires:	python3-pip
BuildRequires:	python3-cffi
BuildRequires:	gcc
BuildRequires:	gdb
%description -n python3-pysegmenttree
# pysegmenttree
[![GitHub license](https://img.shields.io/github/license/greshilov/pysegmenttree)](https://github.com/greshilov/pysegmenttree/blob/master/LICENSE)
[![CI](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml/badge.svg)](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml)
[![codecov](https://codecov.io/gh/greshilov/pysegmenttree/branch/master/graph/badge.svg?token=BXXCG2JBPK)](https://codecov.io/gh/greshilov/pysegmenttree)

Segment tree is a data structure to perform efficient range queries over an array.

Properties of the segment tree with the size N.

| Operation | Time complexity |
| --------------- | --------------- |
| build | O(N) |
| query | O(Log[N]) |
| update | O(Log[N]) |

# Key features
* Implements classical data structure to deal with interval queries.
* Includes two classes **IntSegmentTree** and **FloatSegmentTree** implemented in pure C. They can boost performance up to 20x and are used by default for simple data types if possible.

# Installation
```
$ pip install pysegmenttree
```

# Basic usage
```
>> from pysegmenttree import stree

# Build the tree
# 'sum' function is used by default
>> tree = stree([5, 1, 9, 4, 5, 11])

# Find sum on the interval [1, 4)
>> tree.query(1, 4)
14

# Set element with index 3 to 6
>> tree.update(3, 6)
>> tree.query(1, 4)
16
```

# Advanced usage
There are three predefined query functions available that can be used with `int` or `float` trees. Use them as follows:
```
>> from pysegmenttree import stree, QueryFunction
>> tree = stree([5, 1, 9, 4, 5, 11], func=QueryFunction.MIN)

# Find min on the interval [1, 4)
>> tree.query(1, 4)
1
```

Plain python functions are also suitable, but in this case c-extensions will **not** be used.
```
>> tree = stree([5, 1, 9, 4, 5, 11], func=min)
>> tree.query(1, 4)
1
```

Example with user-defined class.
```
>> from pysegmenttree import stree
>> from pysegmenttree.test_utils import Vec2D
# List of 2D vectors
>> tree = stree([Vec2D(0, 1), Vec2D(5, -2), Vec2D(-2, 3)], func=max)
# Find the vector of maximum length on the interval [0, 2)
>> tree.query(0, 2)

Vec2D(x=5, y=-2)
```

# Docs
Docs are available [here](https://pysegmenttree.readthedocs.io/en/latest/).

# Perfomance

Three basic segment tree operations were benchmarked for three different types `int`, `float` and `Vec2D`.
I included results for 3 other python segment trees libraries for comparison.
All code related to benchmarking can be found in `benchmarks` subdirectory.

* [segment-tree](https://github.com/evgeth/segment_tree)
* [segmenttree](https://github.com/1e0ng/segmenttree)
* [c-segment-tree](https://github.com/gilaniasher/segtree-c-python)

## init
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |


[<img src="benchmarks/with_other_libs/data/init.png"/>](benchmarks/with_other_libs/data/init.png "init")

## query
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |
| Queries performed | 10 000 |

[<img src="benchmarks/with_other_libs/data/query.png"/>](benchmarks/with_other_libs/data/query.png "query")

## update
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |
| Updates performed | 10 000 |

[<img src="benchmarks/with_other_libs/data/update.png"/>](benchmarks/with_other_libs/data/update.png "update")


# Development
Read more [here](DEVELOPMENT.md).



%package help
Summary:	Development documents and examples for pysegmenttree
Provides:	python3-pysegmenttree-doc
%description help
# pysegmenttree
[![GitHub license](https://img.shields.io/github/license/greshilov/pysegmenttree)](https://github.com/greshilov/pysegmenttree/blob/master/LICENSE)
[![CI](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml/badge.svg)](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml)
[![codecov](https://codecov.io/gh/greshilov/pysegmenttree/branch/master/graph/badge.svg?token=BXXCG2JBPK)](https://codecov.io/gh/greshilov/pysegmenttree)

Segment tree is a data structure to perform efficient range queries over an array.

Properties of the segment tree with the size N.

| Operation | Time complexity |
| --------------- | --------------- |
| build | O(N) |
| query | O(Log[N]) |
| update | O(Log[N]) |

# Key features
* Implements classical data structure to deal with interval queries.
* Includes two classes **IntSegmentTree** and **FloatSegmentTree** implemented in pure C. They can boost performance up to 20x and are used by default for simple data types if possible.

# Installation
```
$ pip install pysegmenttree
```

# Basic usage
```
>> from pysegmenttree import stree

# Build the tree
# 'sum' function is used by default
>> tree = stree([5, 1, 9, 4, 5, 11])

# Find sum on the interval [1, 4)
>> tree.query(1, 4)
14

# Set element with index 3 to 6
>> tree.update(3, 6)
>> tree.query(1, 4)
16
```

# Advanced usage
There are three predefined query functions available that can be used with `int` or `float` trees. Use them as follows:
```
>> from pysegmenttree import stree, QueryFunction
>> tree = stree([5, 1, 9, 4, 5, 11], func=QueryFunction.MIN)

# Find min on the interval [1, 4)
>> tree.query(1, 4)
1
```

Plain python functions are also suitable, but in this case c-extensions will **not** be used.
```
>> tree = stree([5, 1, 9, 4, 5, 11], func=min)
>> tree.query(1, 4)
1
```

Example with user-defined class.
```
>> from pysegmenttree import stree
>> from pysegmenttree.test_utils import Vec2D
# List of 2D vectors
>> tree = stree([Vec2D(0, 1), Vec2D(5, -2), Vec2D(-2, 3)], func=max)
# Find the vector of maximum length on the interval [0, 2)
>> tree.query(0, 2)

Vec2D(x=5, y=-2)
```

# Docs
Docs are available [here](https://pysegmenttree.readthedocs.io/en/latest/).

# Perfomance

Three basic segment tree operations were benchmarked for three different types `int`, `float` and `Vec2D`.
I included results for 3 other python segment trees libraries for comparison.
All code related to benchmarking can be found in `benchmarks` subdirectory.

* [segment-tree](https://github.com/evgeth/segment_tree)
* [segmenttree](https://github.com/1e0ng/segmenttree)
* [c-segment-tree](https://github.com/gilaniasher/segtree-c-python)

## init
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |


[<img src="benchmarks/with_other_libs/data/init.png"/>](benchmarks/with_other_libs/data/init.png "init")

## query
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |
| Queries performed | 10 000 |

[<img src="benchmarks/with_other_libs/data/query.png"/>](benchmarks/with_other_libs/data/query.png "query")

## update
| Param | Value |
| --------- | ------- |
| Tree size | 100 000 |
| Updates performed | 10 000 |

[<img src="benchmarks/with_other_libs/data/update.png"/>](benchmarks/with_other_libs/data/update.png "update")


# Development
Read more [here](DEVELOPMENT.md).



%prep
%autosetup -n pysegmenttree-0.2.0

%build
%py3_build

%install
%py3_install
install -d -m755 %{buildroot}/%{_pkgdocdir}
if [ -d doc ]; then cp -arf doc %{buildroot}/%{_pkgdocdir}; fi
if [ -d docs ]; then cp -arf docs %{buildroot}/%{_pkgdocdir}; fi
if [ -d example ]; then cp -arf example %{buildroot}/%{_pkgdocdir}; fi
if [ -d examples ]; then cp -arf examples %{buildroot}/%{_pkgdocdir}; fi
pushd %{buildroot}
if [ -d usr/lib ]; then
	find usr/lib -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/lib64 ]; then
	find usr/lib64 -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/bin ]; then
	find usr/bin -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/sbin ]; then
	find usr/sbin -type f -printf "/%h/%f\n" >> filelist.lst
fi
touch doclist.lst
if [ -d usr/share/man ]; then
	find usr/share/man -type f -printf "/%h/%f.gz\n" >> doclist.lst
fi
popd
mv %{buildroot}/filelist.lst .
mv %{buildroot}/doclist.lst .

%files -n python3-pysegmenttree -f filelist.lst
%dir %{python3_sitearch}/*

%files help -f doclist.lst
%{_docdir}/*

%changelog
* Tue Apr 25 2023 Python_Bot <Python_Bot@openeuler.org> - 0.2.0-1
- Package Spec generated