diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | python-pysegmenttree.spec | 413 | ||||
| -rw-r--r-- | sources | 1 |
3 files changed, 415 insertions, 0 deletions
@@ -0,0 +1 @@ +/pysegmenttree-0.2.0.tar.gz diff --git a/python-pysegmenttree.spec b/python-pysegmenttree.spec new file mode 100644 index 0000000..38fe790 --- /dev/null +++ b/python-pysegmenttree.spec @@ -0,0 +1,413 @@ +%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 +[](https://github.com/greshilov/pysegmenttree/blob/master/LICENSE) +[](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml) +[](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 +[](https://github.com/greshilov/pysegmenttree/blob/master/LICENSE) +[](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml) +[](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 +[](https://github.com/greshilov/pysegmenttree/blob/master/LICENSE) +[](https://github.com/greshilov/pysegmenttree/actions/workflows/ci.yaml) +[](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 +* Wed Apr 12 2023 Python_Bot <Python_Bot@openeuler.org> - 0.2.0-1 +- Package Spec generated @@ -0,0 +1 @@ +ce25d241e14592b27b97a95a6db4f876 pysegmenttree-0.2.0.tar.gz |