Implement `Clone` and `Debug` for `FenwickTree`

[NotLeonian]

Implement the Clone and Debug traits for FenwickTree.

For the Clone trait, it should be enough to add a Clone trait bound to T and write an explicit impl.

For the Debug trait, I think that discussion is needed regarding the output format. Unlike Segtree and LazySegtree, FenwickTree does not have self.log. Additionally, in a Fenwick Tree, the structure does not explicitly store all segments like a Segment Tree or Lazy Segment Tree. This difference causes gaps in the tree representation, making it problematic to use the same output format.

Therefore, I propose an output format that includes self.n, self.e, and the return values of the accum function for 1..=self.n. For example, if self.n = 10, self.e = 0, and the array is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], the output could be one of the following:

FenwickTree { n: 10, e: 0, accum: [0, 1, 3, 6, 10, 15, 21, 28, 36, 45] }

n: 10
e: 0
accum: 0        1       3       6       10      15      21      28      36      45

With this implementation, the required trait bounds for T are limited to Clone + Debug + std::ops::AddAssign<T>.

[TonalidadeHidrica]

We may also accept the "alternate" flag (#) to adopt both.

[NotLeonian]

Thank you! That certainly sounds like a better approach. By "both," do you mean both the output format similar to Segtree and LazySegtree and the format I proposed? Or do you mean both of the two formats I proposed?

[TonalidadeHidrica]

That's what I obfuscated indeed 😜 There are two rooms and we need to discuss which to print for each of them. Personally I think the following two would be a good choice:

• Printing it in a single line with the ordinary struct-like formatting, as shown in your first example.
• Printing it as an ASCII art like this, including as much information as possible. Showing the internal structure may help debugging when the user's Add implementation (or e) is wrong.

Tree:
|                                    28 |
|                6  |                   |
|      1  |         |      9  |         |      17 |
| 0  |    | 2  |    | 4  |    | 6  |    | 8  |    |
Accum:
| 0  | 1  | 3  | 6  | 10 | 15 | 21 | 28 | 36 | 45 |
Elem:
| 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  |
Index:
| 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  |

Alternatively, one may delegate the latter format to Display and keep Debug simple. In that case, only showing the internal array would be that without # and those including accum and elem would be #.

[NotLeonian]

I see, that makes a lot of sense. The ASCII art-like representation seems really useful, though I do have some concerns about potential formatting issues. Also, I agree that using the Display trait certainly makes it clearer and easier to understand, especially for users who aren’t familiar with the alternate flag.

If we go with the ASCII art-like format, it would be nice to update Segtree and LazySegtree as well to keep things consistent.

[koba-e964]

I disagree with implementing Display as Display is not implemented for standard containers such as Vec, HashMap and HashSet.

it is often preferable to only implement Display when there is a single most "obvious" way that values can be formatted as text.

https://doc.rust-lang.org/std/fmt/trait.Display.html

[TonalidadeHidrica]

Considering that this is not a library for public use but rather competitive-programming oriented, sometimes it may be good idea not follow the convention in standard Rust language. A notable example is that we allow arithmetic operations of modint against arbitrary integer types, which doesn't follow usual Rust philosophy. Of course, whether to provide the visualization feature via Display requires a thorough discussions, but in my opinion giving a chance of easy debugging in a short-handed way is not necessarily a bad idea.

[NotLeonian]

I'd like to share my current thoughts on the output format for the Debug implementation. Please note that my opinion has changed from when I originally opened this issue, as I wasn't very familiar with the behavior of std::fmt at the time.

Unlike graph-related data structures, I believe users of FenwickTree are more interested in the sequence of values represented by the structure, rather than its internal state. That said, the fields such as n and e should be displayed as they are. In contrast to SegTree or LazySegtree, a FenwickTree does not store values directly at each index. In this sense, it is similar to a cumulative sum array, and in fact, some users use a FenwickTree as a more efficient alternative to such arrays.

When debugging a cumulative sum implemented using a Vec, we don’t typically show the value at each index explicitly, but this is generally sufficient as a Debug representation. For these reasons, I think it would be reasonable to display the cumulative sums in the form of an accum: [...] field.

Also, since the alternate flag for Debug ({:#?}) already has a defined behavior in Rust, I don't think it's a good idea to change the displayed content based on it. I’d prefer to implement fmt using helpers like debug_struct so that it supports the standard alternate flag correctly. If we wanted to introduce a way to switch between display formats, using the - flag—which is documented as "currently not used"—would be technically possible, but I don't think that would be a clean design either.

To help clarify what I have in mind, I’m also considering opening a draft PR with a sample implementation.

[mizar]

Since there seems to be no objection to implementing the Clone trait, I propose that the Clone trait be implemented in a separate PR.

[NotLeonian]

I agree with the suggestion to implement the Clone trait separately. I'm planning to create a new branch with only the Clone implementation committed and open a separate PR for it.

In the draft PR I previously created, I had committed both the Clone and Debug implementations together. I would appreciate any suggestions on how to handle that draft PR going forward—for example, whether I should revise its content or simply close it.

[mizar]

One idea would be to create a commit and PR that implements only the Clone trait, and merge or rebase the draft tree based on that commit.

[NotLeonian]

Thank you. I've opened PRs that implement only the Clone trait for FenwickTree and the other structs. Once the Clone-related changes are merged, I plan to rebase the existing draft PR to clean it up accordingly.

[NotLeonian]

I unintentionally closed the previous draft PR by renaming its branch.

Although the rebase was successful, the commit message still refers to the original implementation (including Clone), and the branch also contains a formatting commit added for rustfmt. Because of that, I personally feel that continuing with this branch would not be clean.

I plan to keep the rebased branch in my repository for reference, but I propose creating a new branch from scratch to open a fresh draft PR.

Thank you for your understanding...