1  #![doc = include_str!("../README.md")]
  2  // uncomment for discovering new lints:
  3  // #![deny(clippy::all, clippy::pedantic, clippy::nursery, clippy::cargo)]
  4  #![warn(clippy::cargo_common_metadata)]
  5  #![warn(clippy::doc_markdown)]
  6  #![warn(clippy::missing_panics_doc)]
  7  #![warn(clippy::must_use_candidate)]
  8  #![warn(clippy::semicolon_if_nothing_returned)]
  9  #![warn(missing_docs)]
 10  #![warn(rustdoc::missing_crate_level_docs)]
 11  
 12  use cowstr::{SubStr, EMPTY_SUBSTR};
 13  
 14  use constptr::ConstPtr;
 15  
 16  /// A `StrStr` is a dynamic string made from a tree of immutable `SubStr's`. Inserting and
 17  /// removing data only needs to adjust the tree instead shifting characters around.
 18  pub struct StrStr {
 19      subs: Node,
 20  }
 21  
 22  /// The nodes linking a `StrStr` tree together.
 23  /// This tree must be kept normalized, that means empty Leaves are removed, except when at the root.
 24  /// Operations may try to optimize it ins several ways.
 25  enum Node {
 26      // Leafs containing `SubStr's`. There is no parent pointer here to minimize the size of
 27      // this enum. When traversing its enough to cache the last branch.
 28      Str(SubStr),
 29      // A branch, pointing to sub branches or leafs. Storing the parent here comes for free
 30      // since the Box is much smaller than a Str(SubStr).
 31      Concat { concat: Box<(Node, Node)>, parent: Option<ConstPtr<Node>> },
 32  }
 33  
 34  // ctors
 35  impl StrStr {
 36      /// Creates a empty `StrStr`
 37      fn new() -> Self {
 38          Self {
 39              subs: Node::Str(EMPTY_SUBSTR.clone()),
 40          }
 41      }
 42  }
 43  
 44  // mutation methods
 45  impl StrStr {
 46      pub fn append(&mut self) -> &mut Self { todo!()}
 47  
 48      pub fn prepend(&mut self) -> &mut Self { todo!()}
 49      
 50      pub fn insert(&mut self) -> &mut Self { todo!()}
 51  
 52      pub fn remove(&mut self) -> &mut Self { todo!()}
 53  }
 54  
 55  /*
 56  TODO: methods
 57      insert / Index
 58      remove ranges
 59  
 60      normalize/flatten
 61      optimize
 62      range -> &str
 63      -> iter<char>
 64      -> iter<u8>
 65      Extend
 66      regex/pattern api search/replace
 67      https://crates.io/crates/regex-automata
 68      undoable?
 69  
 70  TODO: impl traits:
 71  Add
 72  AddAssign
 73  Index
 74  Ord
 75  Eq
 76  Hash
 77   */
 78  
 79  // query methods
 80  impl StrStr {
 81      pub fn is_empty(&self) -> bool {
 82          match &self.subs {
 83              Node::Str(s) if s.len() == 0 => true,
 84              _ => false,
 85          }
 86      }
 87  }
 88  
 89  #[test]
 90  fn smoke() {
 91      let empty = StrStr::new();
 92      assert!(empty.is_empty());
 93  }
 94  
 95  #[test]
 96  fn expected_size() {
 97      // A Node should use a niche and be the same size as a SubStr.
 98      assert_eq!(std::mem::size_of::<SubStr>(), std::mem::size_of::<Node>());
 99  }
100  
101