#method parameter and trait

51 messages · Page 1 of 1 (latest)

wheat falcon
#

Hello,

I'm trying to design an TrieSet, that is, an ordered set backed by a trie. I wrote a simple trait for the ordered set abstract data type (but the last two methods are commented out for now):

pub trait OrderedSet<E> {
    /// Returns a new instance of `OrderedSet`.
    fn new() -> Self;
    /// Returns the number elements in the `OrderedSet`.
    fn count(&self) -> usize;
    /// Returns whether the ordered set contains no elements.
    fn is_empty(&self) -> bool;
    /// Returns whether the ordered set contains `element`.
    fn contains(&self, element: &E) -> bool;
    /// Inserts `element` to the ordered set.
    /// Returns whether `element` was newly inserted.
    fn add(&mut self, element: E) -> bool;
    /// Removes `element` from the ordered set.
    /// Returns whether `element` was
    fn remove(&mut self, element: &E) -> bool;
    /// Returns the first element in the ordered set.
    fn first(&self) -> Option<&E>;
    /// Returns the last element in the ordered set.
    fn last(&self) -> Option<&E>;
    // /// Returns a iterator pointing to the element right after `element`.
    // fn lower_bound(&self, element: E) -> ;
    // /// Returns an iterator pointing to the element right before `element`.
    // fn upper_bound(&self, element: E) ->;
}

I also think I'm going to have to enforce Ord on E, but that's an issue for later.

The issue I'm facing is that since Tries are optimized for string keys (in this case, I called them elements), I decided to "plug" str inside the angle brackets for my impl block.

# 
impl OrderedSet<str> for TrieSet {
    /// Returns a new instance of `TrieSet`.
    fn new() -> Self {
        Self {
            root: TrieNode {
                children: HashMap::new(),
                is_sentinel: false,
            },
            count: 0,
        }
    }

    /// Returns the number elements in the `TrieSet`.
    fn count(&self) -> usize {
        self.count
    }

    /// Returns the number elements in the `TrieSet`.
    fn is_empty(&self) -> bool {
        self.count == 0
    }

    /// Returns whether the ordered set contains `element`.
    fn contains(&self, element: &str) -> bool {
        todo!()
    }

    /// Inserts `element` to the ordered set.
    /// Returns whether `element` was newly inserted.
    fn add(&mut self, element: String) -> bool {
        todo!()
    }

    /// Removes `element` from the ordered set.
    /// Returns whether `element` was
    fn remove(&mut self, element: &str) -> bool {
        todo!()
    }

    /// Returns the first element in the ordered set.
    fn first(&self) -> Option<&str> {
        todo!()
    }

    /// Returns the element element in the ordered set.
    fn last(&self) -> Option<&str> {
        todo!()
    }
}

However, from the rust docs, I've noticed from some BTreeSet examples, a String is inserted, which is why I wrote element: String in the add() method, but of course, it doesn't align with the str defined within the angle brackets!

So I'm wondering, what should I do? I've considered the simplest solution as just not enforcing str, and leaving it impl OrderedSet<E> for TrieSet or just remove the impl OrderedSet completely, but ideally, I'd like to enforce that the elements are strings only.

tawdry moss
#

you seeem to be a bit confused by having done too much OOP

wheat falcon
wheat falcon
tawdry moss
#

yes

#

if you make many such types

#

afterwards

#

maybe you'll want a trait

#

std doesn't have any such traits for example

wheat falcon
#

Which will all have those methods in common

#

But thanks, I'll remove it then.

wheat falcon
#

My reasoning behind this was so I could do impl OrderedSet for AVLTree, impl OrderedSet for RedBlackTree, and impl OrderedSet for Trie

#

Appreciate the quick response, by the way.

tawdry moss
#

your case might be a little bit on the edge of wether it's a decent idea or not.

#

traits are generally made so that any type that wishes to may implement them

#

independently of the type

#

you don't make a trait to groupd the shared behavior of a few types

#

you make a trait to define the interface you need to implement your algorithms

#

like "i want a type i can iterate over, so i make the Iterator trait"

#

it could be argued an OrderedSet trait might be useful

#

but i would make the types first

#

and worry about that later

wheat falcon
#

What about if I wanted some function that accepts an OrderedSet, then runs something like foo.add(2) since it doesn't care about the underlying container?

#

Would that be a good use case for a trait?

wheat falcon
tawdry moss
#

back to the original question

#

you want to make a TrieSet

#

what does it contain, only strings ?

#

or is it a generic TrieSet

wheat falcon
tawdry moss
#

ok

wheat falcon
#

But my other containers like AVL Tree and Red Black Tree and B-Tree can contain anything (that can be ordered, of course), which is why I had no issue writing impl OrderedSet<E> for AVLTreeSet<E>.

#

But ya, I assume there's no clean solution here, other than forgoing impl OrderedSet<str> for TrieSet and just writingimpl TrieSet. I think impl OrderedSet<String> for TrieSet could work, but accepting a &String for say the contains() method isn't as idiomatic as taking in a &str from what I've read from The Book

tawdry moss
#

that last part is correct

#

your OrderedSets are all based on Ord, right ?

#

you could prob use Borrow then

wheat falcon
wheat falcon
tawdry moss
#

reading this will prob be clearer than i can be

wheat falcon
#

Thanks. I was reading that a few minutes ago. This seems to be the takeaway from what I understand?

#

"As a data collection, HashMap<K, V> owns both keys and values. If the key’s actual data is wrapped in a managing type of some kind, it should, however, still be possible to search for a value using a reference to the key’s data. "

#

So essentially, with Borrow, TrieSet can store owned values, in this case String but the methods can accept &str too?

tawdry moss
#

yes

wheat falcon
#

Awesome. Thanks for mentioning that.

#

And thanks for your help today.