balanced_ternary/lib.rs
1//! A [balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary) data structure.
2//!
3//! A `Ternary` object in this module represents a number in the balanced ternary numeral system.
4//! Balanced ternary is a non-standard positional numeral system that uses three digits: {-1, 0, +1}
5//! represented here as `Neg` for -1, `Zero` for 0, and `Pos` for +1. It is useful in some domains
6//! of computer science and mathematics due to its arithmetic properties and representation
7//! symmetry.
8//!
9//! # Data Structures
10//!
11//! - **`Digit` Enum**:
12//! Represents a single digit for balanced ternary values, with possible values:
13//! - `Neg` for -1
14//! - `Zero` for 0
15//! - `Pos` for +1
16//!
17//! - **`Ternary` Struct**:
18//! Represents a balanced ternary number as a collection of `Digit`s.
19//! Provides utility functions for conversion, parsing, and manipulation.
20//!
21//! # Examples
22//!
23//! ## Converting between representations:
24//! ```rust
25//! use balanced_ternary::*;
26//!
27//! let ternary = Ternary::from_dec(5);
28//! assert_eq!(ternary.to_string(), "+--");
29//! assert_eq!(ternary.to_dec(), 5);
30//!
31//! let parsed = Ternary::parse("+--");
32//! assert_eq!(parsed.to_string(), "+--");
33//! assert_eq!(parsed.to_dec(), 5);
34//! ```
35//!
36//! ## Negative numbers:
37//! ```rust
38//! use balanced_ternary::*;
39//!
40//! let neg_five = Ternary::from_dec(-5);
41//! assert_eq!(neg_five.to_string(), "-++");
42//! assert_eq!(neg_five.to_dec(), -5);
43//!
44//! let negated = -&neg_five;
45//! assert_eq!(negated.to_string(), "+--");
46//! assert_eq!(negated.to_dec(), 5);
47//! ```
48//!
49//! ## Larger numbers:
50//! ```rust
51//! use balanced_ternary::*;
52//!
53//! let big = Ternary::from_dec(121);
54//! assert_eq!(big.to_string(), "+++++");
55//! assert_eq!(big.to_dec(), 121);
56//!
57//! let neg_big = Ternary::from_dec(-121);
58//! assert_eq!(neg_big.to_string(), "-----");
59//! assert_eq!(neg_big.to_dec(), -121);
60//! ```
61//!
62//! ## Operations
63//! ```
64//! use balanced_ternary::Ternary;
65//!
66//! let repr9 = Ternary::parse("+00");
67//! let repr4 = Ternary::parse("++");
68//! let repr13 = &repr9 + &repr4;
69//! let repr17 = &repr13 + &repr4;
70//! let repr34 = &repr17 + &repr17;
71//!
72//! assert_eq!(repr13.to_string(), "+++");
73//! assert_eq!(repr17.to_string(), "+-0-");
74//! assert_eq!(repr34.to_string(), "++-+");
75//!
76//! let repr30 = &repr34 - &repr4;
77//! assert_eq!(repr30.to_dec(), 30);
78//! assert_eq!(repr30.to_string(), "+0+0");
79//! ```
80//!
81#![no_std]
82extern crate alloc;
83
84use alloc::string::{String, ToString};
85use alloc::vec;
86use alloc::vec::Vec;
87use core::fmt::{Display, Formatter};
88use core::str::FromStr;
89
90/// Provides helper functions for formatting integers in a given radix.
91///
92/// Used internally to convert decimal numbers into their ternary representation.
93/// - `x`: The number to be formatted.
94/// - `radix`: The base of the numeral system.
95///
96/// Returns a string representation of the number in the specified base.
97fn format_radix(mut x: u32, radix: u32) -> String {
98 let mut result = vec![];
99
100 loop {
101 let m = x % radix;
102 x /= radix;
103 result.push(core::char::from_digit(m, radix).unwrap());
104 if x == 0 {
105 break;
106 }
107 }
108 result.into_iter().rev().collect()
109}
110
111pub mod digit;
112
113pub use crate::digit::Digit;
114
115/// Represents a balanced ternary number using a sequence of `Digit`s.
116///
117/// Provides functions for creating, parsing, converting, and manipulating balanced ternary numbers.
118#[derive(Debug, Clone, PartialEq, Eq, Hash)]
119pub struct Ternary {
120 digits: Vec<Digit>,
121}
122
123impl Ternary {
124 /// Creates a new balanced ternary number from a vector of `Digit`s.
125 pub fn new(digits: Vec<Digit>) -> Ternary {
126 Ternary { digits }
127 }
128
129 /// Returns the number of digits (length) of the balanced ternary number.
130 pub fn log(&self) -> usize {
131 self.digits.len()
132 }
133
134 /// Returns a reference to the [Digit] indexed by `index` if it exists.
135 ///
136 /// Digits are indexed **from the right**:
137 /// ```
138 /// use balanced_ternary::Ternary;
139 ///
140 /// // Indexes :
141 /// // 32
142 /// // 4||1
143 /// // 5||||0
144 /// // ||||||
145 /// // vvvvvv
146 /// let ternary = Ternary::parse("+++--+");
147 /// assert_eq!(ternary.get_digit(1).unwrap().to_char(), '-')
148 /// ```
149 pub fn get_digit(&self, index: usize) -> Option<&Digit> {
150 self.digits.iter().rev().nth(index)
151 }
152
153 /// Parses a string representation of a balanced ternary number into a `Ternary` object.
154 ///
155 /// Each character in the string must be one of `+`, `0`, or `-`.
156 pub fn parse(str: &str) -> Self {
157 let mut repr = Ternary::new(vec![]);
158 for c in str.chars() {
159 repr.digits.push(Digit::from_char(c));
160 }
161 repr
162 }
163
164 /// Converts the `Ternary` object to its integer (decimal) representation.
165 ///
166 /// Calculates the sum of each digit's value multiplied by the appropriate power of 3.
167 pub fn to_dec(&self) -> i64 {
168 let mut dec = 0;
169 for (rank, digit) in self.digits.iter().rev().enumerate() {
170 dec += digit.to_i8() as i64 * 3_i64.pow(rank as u32);
171 }
172 dec
173 }
174
175 /// Creates a balanced ternary number from a decimal integer.
176 ///
177 /// The input number is converted into its balanced ternary representation,
178 /// with digits represented as `Digit`s.
179 pub fn from_dec(dec: i64) -> Self {
180 let sign = dec.signum();
181 let str = format_radix(dec.abs() as u32, 3);
182 let mut next = 0u8;
183 let mut repr = Ternary::new(vec![]);
184 for digit in str.chars().rev() {
185 let digit = u8::from_str(&digit.to_string()).unwrap() + next;
186 if digit < 2 {
187 repr.digits.push(Digit::from_i8(digit as i8));
188 next = 0;
189 } else if digit == 2 {
190 repr.digits.push(Digit::from_i8(-1));
191 next = 1;
192 } else if digit == 3 {
193 repr.digits.push(Digit::from_i8(0));
194 next = 1;
195 }
196 }
197 if next == 1 {
198 repr.digits.push(Digit::from_i8(1));
199 }
200 repr.digits.reverse();
201 if sign == -1 {
202 -&repr
203 } else {
204 repr
205 }
206 }
207}
208
209impl Display for Ternary {
210 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
211 let mut str = String::new();
212 for digit in self.digits.iter() {
213 str.push(digit.to_char());
214 }
215 write!(f, "{}", str)
216 }
217}
218
219pub mod operations;
220
221#[cfg(feature = "tryte")]
222pub mod tryte;
223
224#[cfg(feature = "tryte")]
225pub use crate::tryte::Tryte;
226
227#[cfg(test)]
228#[test]
229fn test_ternary() {
230 use crate::*;
231
232 let repr5 = Ternary::new(vec![Digit::Pos, Digit::Neg, Digit::Neg]);
233 assert_eq!(repr5.to_dec(), 5);
234 let repr5 = Ternary::from_dec(5);
235 assert_eq!(repr5.to_dec(), 5);
236
237 let repr13 = Ternary::new(vec![Digit::Pos, Digit::Pos, Digit::Pos]);
238 assert_eq!(repr13.to_dec(), 13);
239
240 let repr14 = Ternary::parse("+---");
241 let repr15 = Ternary::parse("+--0");
242 assert_eq!(repr14.to_dec(), 14);
243 assert_eq!(repr15.to_dec(), 15);
244 assert_eq!(repr14.to_string(), "+---");
245 assert_eq!(repr15.to_string(), "+--0");
246
247 let repr120 = Ternary::from_dec(120);
248 assert_eq!(repr120.to_dec(), 120);
249 assert_eq!(repr120.to_string(), "++++0");
250 let repr121 = Ternary::from_dec(121);
251 assert_eq!(repr121.to_dec(), 121);
252 assert_eq!(repr121.to_string(), "+++++");
253
254 let repr_neg_5 = Ternary::parse("-++");
255 assert_eq!(repr_neg_5.to_dec(), -5);
256 assert_eq!(repr_neg_5.to_string(), "-++");
257
258 let repr_neg_5 = Ternary::from_dec(-5);
259 assert_eq!(repr_neg_5.to_dec(), -5);
260 assert_eq!(repr_neg_5.to_string(), "-++");
261
262 let repr_neg_121 = Ternary::from_dec(-121);
263 assert_eq!(repr_neg_121.to_dec(), -121);
264 assert_eq!(repr_neg_121.to_string(), "-----");
265
266 let test = Ternary::from_dec(18887455);
267 assert_eq!(test.to_dec(), 18887455);
268 assert_eq!(test.to_string(), "++00--0--+-0++0+");
269}