dict 0.1.2

Crate implementing real associative arrays, also known as dictionaries
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

//!
//! Crate implementing real associative arrays, also known as dictionaries.
//!
//! Associative arrays behave just like indexed arrays, but use unique strings as indexes instead
//! of integers.
//!
//! In contrast to Hashmaps, associative arrays don't have the restriction of one to one mapping
//! between keys and values. Also, the value doesn't need to be a string, but can be any generic
//! type T.
//!
//! This associative array implementation is built as a Trait implementation over std::vec::Vec, so
//! all [Vec methods](https://doc.rust-lang.org/std/vec/struct.Vec.html) are also available 
//! for a Dict object.
//!
//! Insert time is O(n²), and retrieval time is O(log n). This means that it is far more efficient
//! to query values than to insert them. If we need frequent inserts in big sets, it can be more
//! efficient to implement a solution based on linked lists or binary heaps.
//!
//! # Examples
//!
//! ```
//! use dict::{ Dict, DictIface };
//!
//! //create a dictionary of strings
//! let mut dict = Dict::<String>::new();
//! assert_eq!( dict.is_empty(), true );
//! assert_eq!( dict.len(), 0 );
//!
//! // add an element "val" indexed by the key "key"
//! assert_eq!( dict.add( "key".to_string(), "val".to_string() ), true );
//! assert_eq!( dict.is_empty(), false );
//! assert_eq!( dict.len(), 1 );
//!
//! // keys must be unique
//! assert_eq!( dict.add( "key".to_string()      , "other_val".to_string() ), false );
//! assert_eq!( dict.len(), 1 );
//! assert_eq!( dict.add( "other_key".to_string(), "other_val".to_string() ), true );
//! assert_eq!( dict.len(), 2 );
//!
//! // we can access the value by its key string with get()
//! assert_eq!( dict.get( "key" ).unwrap(), "val" );
//! assert_eq!( dict.contains_key( "key" ), true );
//! assert_eq!( dict.remove_key( "key" ).unwrap(), "val" );
//! assert_eq!( dict.contains_key( "key" ), false );
//! ```
//!
//! # More information
//!
//! Copyleft 2018 by Ignacio Nunez Hernanz - nacho _at_ ownyourbits _dot_ com
//!
//! GPL licensed
//!
//! More at [OwnYouBits](https://ownyourbits.com)
//! [github](https://github.com/nachoparker/rust-dict)
//!

pub struct DictEntry<T> { pub key : String, pub val : T }

pub type Dict<T> = Vec<DictEntry<T>>;

pub trait DictIface<T> {
    fn add( &mut self, key : String, val : T ) -> bool;
    fn get( &self, key : &str ) -> Option<&T>;
    fn contains_key( &self, key : &str ) -> bool;
    fn remove_key( &mut self, key : &str ) -> Option<T>;
}

impl<T> DictIface<T> for Dict<T> {
    /// Add an element _val_ of type T, indexed by the string _key_.
    fn add( &mut self, key : String, val : T ) -> bool {
        match self.binary_search_by( |o| o.key.cmp( &key.to_string() ) ) {
            Ok (  _  ) => return false,   // key exists
            Err( pos ) => self.insert( pos, DictEntry{ key, val } ),
        }
        true
    }
    /// Remove the element identified by the key _key_ and return it, if exists.
    fn remove_key( &mut self, key : &str ) -> Option<T> {
        if let Ok( pos ) = self.binary_search_by( |o| o.key.cmp( &key.to_string() ) ) {
            let entry = self.remove( pos );
            Some( entry.val )
        } else { None }
    }
    /// Return a reference to the value identified by the key _key_, if exists.
    fn get( &self, key : &str ) -> Option<&T> {
        if let Ok( pos ) = self.binary_search_by( |o| o.key.cmp( &key.to_string() ) ) {
            Some( &self[pos].val )
        } else { None }
    }
    /// Return true if an element identified by the key _key_ exists.
    fn contains_key( &self, key : &str ) -> bool {
        self.get( key ).is_some()
    }
}

// License
//
// This script is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This script is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this script; if not, write to the
// Free Software Foundation, Inc., 59 Temple Place, Suite 330,