Error `T` might need a bound for `std::cmp::PartialEq` in singly linked list

help
1

While doing the Rust track in Exercism, I came accross the singly linked list exercise. Once my compilation passed the tests, I continued to work on the code to add some more functionality and train myself.
The error I get while compiling is error[E0369]: binary operation == cannot be applied to type T

The code is something like this:

#[derive(Default)]
struct Node<T>{
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T: PartialEq> PartialEq for Node<T> {
    fn eq(&self, other: &Self) -> bool {
        self.data == other.data
    }
}

#[derive(Default)]
pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
    length: usize,
}

Some implementation and then the problem

pub fn find(&self, value: T) -> bool {
        let mut head = self.head.borrow();

        while let Some(node) = head {
            match node.next {
                None => return false,
                Some(a) => {if a.data == value { return true }},
            }
            head = &node.next;
        }
        false
    }

The error happens when comparing a.data with value.
I thought that the PartialEq implementation for Node should take care of that.
If possible, I would like some assistance in that matter.

Thanks

2

Could you share the full code which reproduces an error? I wasn't able to get it in your current variant - playground.

3 
use std::iter::FromIterator;

#[derive(Default)]
struct Node<T>{
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T: PartialEq> PartialEq for Node<T> {
    fn eq(&self, other: &Self) -> bool {
        self.data == other.data
    }
}

#[derive(Default)]
pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
    length: usize,
}

impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self {
        SimpleLinkedList {
            head: None,
            length: 0
        }
    }

    pub fn len(&self) -> usize {
        self.length
    }

    pub fn push(&mut self, _element: T) {
        let node = Box::new(Node {
            data: _element,
            next: self.head.take(),
        });
        self.head = Some(node);
        self.length += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        match self.head.take() {
            None => None,
            Some(node) => {
                self.head = node.next;
                self.length -= 1;
                Some(node.data)
            }
        }
    }

    pub fn peek(&self) -> Option<&T> {
        match &self.head {
            None => None,
            Some(node) => Some(&node.data),
        }
    }

    pub fn find(&self, value: T) -> bool {
        self.head.iter().find(| node | node.data == value).is_some()
    }

    pub fn rev(mut self) -> SimpleLinkedList<T> {
        let mut current_node = self.head.take();
        let mut previous = None;

        while let Some(mut node) = current_node {
            let next = node.next;
            node.next = previous;
            previous = Some(node);
            current_node = next;
        }
        self.head = previous;
        self
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<T> FromIterator<T> for SimpleLinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(_iter: I) -> Self {
        let mut c = SimpleLinkedList::new();
        for i in _iter {
            c.push(i);
        }
        c
    }
}

// In general, it would be preferable to implement IntoIterator for SimpleLinkedList<T>
// instead of implementing an explicit conversion to a vector. This is because, together,
// FromIterator and IntoIterator enable conversion between arbitrary collections.
// Given that implementation, converting to a vector is trivial:
//
// let vec: Vec<_> = simple_linked_list.into_iter().collect();
//
// The reason this exercise's API includes an explicit conversion to Vec<T> instead
// of IntoIterator is that implementing that interface is fairly complicated, and
// demands more of the student than we expect at this point in the track.

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
    fn into(mut self) -> Vec<T> {
        let mut vec = vec![];

        while let Some(element) = self.pop() {
            vec.push(element);
        }
        vec.reverse();
        vec
    }
}
4

Sorry, wrong version. This is the version that uses the iterator

Just use the find method from the code I sent before. The rest is identical

5 
error[E0599]: no method named `borrow` found for enum `std::option::Option<std::boxed::Box<Node<T>>>` in the current scope
  --> src/lib.rs:30:34
   |
30 |         let mut head = self.head.borrow();
   |                                  ^^^^^^ method not found in `std::option::Option<std::boxed::Box<Node<T>>>`
   |
   = help: items from traits can only be used if the trait is in scope
help: the following trait is implemented but not in scope; perhaps add a `use` for it:
   |
1  | use std::borrow::Borrow;
   |

Are you sure that the structure is correct?

6

Your compiler errors go away by adding

use std::borrow::Borrow;

at the top of your module, and changing

match node.next {

with

match &node.next {

Since you can't move out of node since it's under a reference.

7

Thanks, but those are only there due to the change in the find function from the two versions I sent. That's my fault.
But still, the error I mentioned in the post about comparing T values is still there.
Playground

8

Oh, add a bound to T on the find method:

pub fn find(&self, value: T) -> bool 
    where T: PartialEq<T> { /* */ }

Or, make another impl block:

impl<T: PartialEq<T>> SimpleLinkedList<T> {
    pub fn find(&self, value: T) -> bool {
        /* */
    }
}
2 Likes
9

Here you didn't specify that you're only implementing these methods if T: PartialEq, so you can't rely on that in the body of find().

10

Thank you very much.

11

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.